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

# Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols

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.
Keywords :
Document type :
Reports
Domain :

https://hal.inria.fr/inria-00073066
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

### Identifiers

• HAL Id : inria-00073066, version 1

### Citation

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