HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 11:44:01 AM
Last modification on : Friday, February 4, 2022 - 3:12:36 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:33:09 PM


  • 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⟩



Record views


Files downloads