Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols
Michele Flammini, Stéphane Pérennès · SIAM Journal on Discrete Mathematics · 2004
In this paper we extend the technique provided in [M. Flammini and S. Pérennès, Inform. and Comput., to appear] to allow the determination of lower bounds on the broadcasting and gossiping time required by the so-called restricted protocols. Informally, a protocol is {\small $({\cal I}, {\cal O})$}-restricted if at every processor each outgoing activation of an arc depends on at most ${\cal I}$ previous incoming activations and any incoming activation influences at most ${\cal O}$ successive outgoing activations. Examples of restricted protocols are systolic ones and those running on bounded degree networks. Thus, under the basic whispering model, we provide the first general lower bound on the gossiping time of d-bounded degree networks in the directed and half-duplex cases. Moreover, significantly improved broadcasting and gossiping lower bounds are obtained for well-known networks such as butterfly, de Bruijn, and Kautz graphs. All the results are also extended to other communication models such as the c-port and/or postal one.