FRAIGNIAUD, Pierre; ILCINKAS, David; PELC, Andrzej

doi:10.1016/j.jcss.2009.07.002

Metadatos

Licencia de uso del documento

FRAIGNIAUD, Pierre
Laboratoire d'informatique Algorithmique : Fondements et Applications [LIAFA]

ILCINKAS, David
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

PELC, Andrzej
Département d'Informatique et d'Ingénierie [DII]

Idioma

Article de revue

Este ítem está publicado en

Journal of Computer and System Sciences. 2010, vol. 76, n° 3-4, p. 222-232

Elsevier

Resumen en inglés

We study the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. Our approach is {\em quantitative}: we investigate the minimum total number of bits of information (minimum size of advice) that has to be available to nodes, regardless of the type of information provided. We compare the size of advice needed to perform broadcast and wakeup (the latter is a broadcast in which nodes can transmit only after getting the source information), both using a linear number of messages (which is optimal). We show that the minimum size of advice permitting the {\em wakeup} with a linear number of messages in a $n$-node network, is $\Theta (n \log n)$, while the {\em broadcast} with a linear number of messages can be achieved with advice of size $O(n)$. We also show that the latter size of advice is almost optimal: no advice of size $o(n)$ can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.< Leer menos

Palabras clave en inglés

Algorithm

Broadcasting

Wakeup

Size of advice

Message complexity

Network

Graph

URI

https://oskar-bordeaux.fr/handle/20.500.12278/198342

DOI

http://dx.doi.org/10.1016/j.jcss.2009.07.002

Proyecto ANR

Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322

Orígen

Importado de Hal

Centros de investigación

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800