Afficher la notice abrégée

Broadcasting on Large Scale Heterogeneous Platforms under the Bounded Multi-Port Model

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorBEAUMONT, Olivier
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorEYRAUD-DUBOIS, Lionel
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorKUMAR, Shailesh
dc.date.accessioned2024-04-15T09:49:56Z
dc.date.available2024-04-15T09:49:56Z
dc.date.created2010
dc.date.issued2010-04
dc.date.conference2010-04
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198291
dc.description.abstractEnWe consider the problem of broadcasting a large message in a large scale distributed platform. The message must be sent from a source node, with the help of the receiving peers which may forward the message to other peers. In this context, we are interested in maximizing the throughput (i.e. the maximum streaming rate, once steady state has been reached). The platform model does not assume that the topology of the platform is known in advance: we consider an Internet-like network, with complete potential connectivity. Furthermore, the model associates to each node local properties (incoming and outgoing bandwidth), and the goal is to build an overlay which will be used to perform the broadcast operation. We model contentions using the bounded multi-port model: a processor can be involved simultaneously in several communications, provided that its incoming and outgoing bandwidths are not exceeded. For the sake of realism, it is also necessary to bound the number of simultaneous connections that can be opened at a given node (ie its outdegree). We prove that unfortunately, this additional constraint makes the problem of maximizing the overall throughput NP Complete. On the other hand, we also propose a polynomial time algorithm to solve this problem, based on a slight resource augmentation on the outdegree of the nodes.
dc.description.sponsorshipSimulation extrêmement extensible avec SimGrid - ANR-08-SEGI-0022
dc.language.isoen
dc.subject.enBroadcast Scheduling Resource Augmentation NP Completeness Approximation Algorithms Communication modeling
dc.title.enBroadcasting on Large Scale Heterogeneous Platforms under the Bounded Multi-Port Model
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.title24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010)
bordeaux.countryUS
bordeaux.conference.cityAtlanta
bordeaux.peerReviewedoui
hal.identifierinria-00444586
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00444586v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2010-04&rft.au=BEAUMONT,%20Olivier&EYRAUD-DUBOIS,%20Lionel&KUMAR,%20Shailesh&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée