On the communication complexity of randomized broadcasting in random-like graphs

Broadcasting algorithms have a various range of applications in different fields of computer science. In this paper we analyze the number of message transmissions generated by efficient randomized broadcasting algorithms in random-like networks. We mainly consider the classical random graph model, i.e., a graph G_p with n nodes in which any two arbitrary nodes are connected with probability p, independently. For these graphs, we present an efficient broadcasting algorithm based on the random phone call model introduced by Karp et al. [21], and show that the total number of message transmissions generated by this algorithm is bounded by an asymptotically optimal value in almost all connected random graphs. More precisely, we show that if p ≥ log^δ n/n for some constant δ > 2, then we are able to broadcast any information r in a random graph G_p of size n in O(log n) steps by using at most O(n max{log log n, log n/ log d}) transmissions related to r, where d = pn denotes the expected average degree in G_p. We also show that for these kind of graphs there is a a matching lower bound on the number of transmissions generated by any efficient broadcasting algorithm which works within the limits of the random phone call model. Please note that the main result holds with probability 1-1/n^Ω(1), even if n and d are unknown to the nodes of the graph.The algorithm we present in this paper is based on a simple communication model [21], is scalable, and robust. It can efficiently handle restricted communication failures and certain changes in the size of the network, and can also be extended to certain types of truncated power law graphs based on the models of [1, 2, 5]. In addition, our methods and results might be useful for further research on this field.