Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols

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.