Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 1999

Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-3612.pdf (327.62 Ko) Télécharger le fichier

Dates et versions

inria-00073066 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00073066 , version 1

Citer

Michele Flammini, Stéphane Pérennes. Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols. RR-3612, INRIA. 1999. ⟨inria-00073066⟩
109 Consultations
239 Téléchargements

Partager

Gmail Facebook X LinkedIn More