Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols

Michele Flammini 1 Stéphane Pérennes
1 SLOOP - Simulation, Object Oriented Languages and Parallelism
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this paper we extend the technique provided in [6] to allow the determination of lower bounds on the broadcasting and gossiping time required by the so-called «restricted» protocols. Informally, a protocol is (i,o)-restricted at a given processor if every outgoing activation of an arc depends on at most i previous incoming activations and any incoming activation influences at most o successive outgoing activations. Examples of restricted protocols are those running on bounded degree networks or systolic. We thus derive improved lower bounds on the broadcasting time in several well-known networks, such as Butterfly, de Bruijn and Kautz graphs. Moreover, we derive the first general lower bound on the gossiping time of $d$-bounded degree networks in the directed and half-duplex cases. Improved lower bounds on gossiping are also obtained for Butterfly, de Bruijn and Kautz graphs. Finally, as a corollary we obtain the same lower bounds on s-systolic protocols obtained in [6]. All the results are also extended to other communication models, such as c-port and/or postal and optical.
Type de document :
RR-3612, INRIA. 1999
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:44:01
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:33:09



  • HAL Id : inria-00073066, version 1



Michele Flammini, Stéphane Pérennes. Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols. RR-3612, INRIA. 1999. 〈inria-00073066〉



Consultations de la notice


Téléchargements de fichiers