Afficher la notice abrégée

Fast Radio Broadcasting with Advice

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorILCINKAS, David
hal.structure.identifierDepartment of Computer Science [Liverpool]
dc.contributor.authorKOWALSKI, Dariusz R.
hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorPELC, Andrzej
dc.contributor.editorAlexander A. Shvartsman, Pascal Felber
dc.date.accessioned2024-04-15T09:53:46Z
dc.date.available2024-04-15T09:53:46Z
dc.date.issued2008-06
dc.date.conference2008-06
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198626
dc.description.abstractEnWe study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with {\em advice}. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under complete knowledge of the network we give a tight answer to the above question: $O(n)$ bits of advice are sufficient but $o(n)$ bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of advice.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherSpringer Berlin / Heidelberg
dc.source.titleProceedings of the 15th International Colloquium on Structural Information and Communication Complexity
dc.subject.enradio network
dc.subject.endistributed algorithm
dc.subject.endeterministic broadcasting
dc.subject.enadvice
dc.title.enFast Radio Broadcasting with Advice
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-540-69355-0_24
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.page291-305
bordeaux.volume5058
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleSIROCCO 2008
bordeaux.countryCH
bordeaux.title.proceedingProceedings of the 15th International Colloquium on Structural Information and Communication Complexity
bordeaux.conference.cityVillars-sur-Ollon
bordeaux.peerReviewedoui
hal.identifierhal-00341449
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00341449v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Proceedings%20of%20the%2015th%20International%20Colloquium%20on%20Structural%20Information%20and%20Communication%20Complexity&rft.date=2008-06&rft.volume=5058&rft.spage=291-305&rft.epage=291-305&rft.au=ILCINKAS,%20David&KOWALSKI,%20Dariusz%20R.&PELC,%20Andrzej&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