Efficient Communication in Unknown Networks

Luisa Gargano 1 Andrzej Pelc Stéphane Pérennes Ugo Vaccaro
1 SLOOP - Simulation, Object Oriented Languages and Parallelism
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We consider the problem of disseminating messages in networks whose topology and size are not known to nodes. Three communication tasks of increasing difficulty are studied. In blind broadcasting (BB) the goal is to communicate the source message to all nodes. In acknowledged blind broadcasting (ABB) the goal is to achieve BB and inform the source about it. Finally, in full synchronization (FS) all nodes must simultaneously enter the state terminated after receiving the source message. We show that BB is achieved in time at most $2n$ in any $n$-node network and show networks in which time $2n-o(n)$ is needed. For ABB we show algorithms working in time $(2+\epsi- lon)n$, for any fixed positive constant $\epsilon$ and sufficiently large $n$. Using large messages, the source can additionally learn the entire topology of the network and time can be reduced to $2n$. Finally, we show a simple algorithm for FS working in time $3n$, and indicate how this time can be slightly reduced using large messages. The optimal time of full synchronization remains an open problem. This is the first paper devoted to the study of deterministic communication under network ignorance scenario.
Type de document :
Rapport
RR-3609, INRIA. 1999
Liste complète des métadonnées

https://hal.inria.fr/inria-00073069
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:44:16
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:33:15

Fichiers

Identifiants

  • HAL Id : inria-00073069, version 1

Collections

Citation

Luisa Gargano, Andrzej Pelc, Stéphane Pérennes, Ugo Vaccaro. Efficient Communication in Unknown Networks. RR-3609, INRIA. 1999. 〈inria-00073069〉

Partager

Métriques

Consultations de la notice

204

Téléchargements de fichiers

614