On the optimality of general lower bounds for broadcasting and gossiping

In this paper we show that many general lower bounds on the broadcasting an d gossiping time are optimal. In particular, let b(G) be the broadcasting t ime of a network G under the basic one-port model. The only lower bound on b(G) holding for every n vertices graph G is max(log(2) n, Diam (G)), but t he log(2) n factor cannot be achieved in bounded degree networks. In fact, let the parameter d be defined in undirected graphs as the maximum degree m inus one and for directed graphs as the maximum out-degree. Then, in [SIAM J. Discrete Math., 1 (1998), pp. 531-540; SIAM J. Discrete Math., 5 (1992), pp. 10-24] it has been proved that, for any graph G of parameter d, b(G) g reater than or equal to log(2) n/log(2) xi, where is the largest real numbe r such that xi (d) - xi (d-1) -xi (d-2)- ... -xi - 1 = 0. Since then many p apers have proposed constructions of bounded degree networks having a small broadcast time [Proceedings of the 2nd International Euro-Par Conference ( EUROPAR), Lecture Notes in Comput. Sci. 1123, Springer-Verlag, New York, 19 96, pp. 313-324; IEEE Trans. Comput., 33 (1984), pp. 190-194], but so far t he optimality of [SIAM J. Discrete Math., 1 ( 1998), pp. 531-540; SIAM J. D iscrete Math., 5 (1992), pp. 10-24] was still an open question. In this paper we prove that the above lower bound is tight, improving all t he existing upper bounds by means of probabilistic methods. Namely, we show that for n arbitrarily large there exist families of n vertices graphs in which a uniformly drawn graph has broadcasting time as predicted by [SIAM J . Discrete Math., 1 (1998), pp. 531-540; SIAM J. Discrete Math., 5 (1992), pp. 10-24] with probability converging to 1. Moreover, we show that [SIAM J . Discrete Math., 1 (1998), pp. 531-540; SIAM J. Discrete Math., 5 (1992), pp. 10-24] is attained even in the case of gossiping and systolic gossiping in the full-duplex mode. Finally, new upper bounds on bounded-degree and systolic gossiping are also determined in the directed and half-duplex modes. While the systolic const ruction is tight and matches the lower bound of [Inform and Comput., to app ear], we strongly conjecture that the bounded-degree result is optimal and that a corresponding matching lower bound is still to be proven.