Fast radio broadcasting with advice
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | ILCINKAS, David | |
| hal.structure.identifier | Department of Computer Science [Liverpool] | |
| dc.contributor.author | KOWALSKI, Dariusz R. | |
| hal.structure.identifier | Département d'Informatique et d'Ingénierie [DII] | |
| dc.contributor.author | PELC, Andrzej | |
| dc.date.accessioned | 2024-04-15T09:49:33Z | |
| dc.date.available | 2024-04-15T09:49:33Z | |
| dc.date.issued | 2010-03 | |
| dc.identifier.issn | 1879-2294 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198266 | |
| dc.description.abstractEn | We 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.sponsorship | Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322 | |
| dc.language.iso | en | |
| dc.publisher | Elsevier | |
| dc.subject.en | radio network | |
| dc.subject.en | distributed algorithm | |
| dc.subject.en | deterministic broadcasting | |
| dc.subject.en | advice | |
| dc.title.en | Fast radio broadcasting with advice | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1016/j.tcs.2010.01.004 | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| bordeaux.journal | Theoretical Computer Science | |
| bordeaux.page | 1544-1557 | |
| bordeaux.volume | 411 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.issue | 14-15 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00464580 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00464580v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Theoretical%20Computer%20Science&rft.date=2010-03&rft.volume=411&rft.issue=14-15&rft.spage=1544-1557&rft.epage=1544-1557&rft.eissn=1879-2294&rft.issn=1879-2294&rft.au=ILCINKAS,%20David&KOWALSKI,%20Dariusz%20R.&PELC,%20Andrzej&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||