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

ABSTRACT

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.

REFERENCES

• 1: W. Aiello , F. Chung, Random Evolution in Massive Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.510, October 14-17, 2001
• 2: A. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286, 1999.
• 3: B. Bollobás. Random Graphs. Academic Press, 1985.
• 4: H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23:493--507, 1952.
• 5: F.R.K. Chung and L. Lu. Connected components in random graphs with given expected degre sequences. Annals of Combinatorics, 6:125--145, 2002.
• 6: F.R.K. Chung and L. Lu. The average distances in random graphs with given expected degrees. Internet Mathematics, 1:91--114, 2003.
• 7: F.R.K. Chung and L. Lu. Coupling on-line and off-line analyses for random power law graphs,. Internet Mathematics, 1:409--461, 2004.
• 8: F.R.K. Chung, L. Lu, and V. Vu. Eigenvalues of random power law graphs. Annals of Combinatorics, 7:21--33, 2003.
• 9: F.R.K. Chung, L. Lu, and V. Vu. The spectra of random graphs with given expected degrees. Proceedings of National Academy of Sciences, 100:6313--6318, 2003.
• 10: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 11: R. Elsässer. On randomized broadcasting in power law graphs. Manuscript, 2006.
• 12: Robert Els , Burkhard Monien, Load balancing of unit size tokens and expansion properties of graphs, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777461]
• 13: R. Elsässer, B. Monien, and S. Schamberger. Load balancing of indivisible unit size tokens in dynamic and heterogeneous networks. In Proc. of ESA, pages 640--651, 2004.
• 14: P. Erdős and A. Rényi. On random graphs I. Publ. Math. Debrecen, 6:290--297, 1959.
• 15: P. Erdős and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17--61, 1960.
• 16: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.251-262, Oct. 1999
• 17: U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. Random Structures and Algorithms, 1(4):447--460, 1990.
• 18: Leszek Gąsieniec , Andrzej Pelc, Adaptive broadcasting with faulty nodes, Parallel Computing, v.22 n.6, p.903-912, Sept. 1996 [doi>10.1016/0167-8191(96)00023-3]
• 19: E.N. Gilbert. Random graphs. The Annals of Mathematical Statistics, 30:1141--1144, 1959.
• 20: Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
• 21: R. Karp , C. Schindelhauer , S. Shenker , B. Vocking, Randomized rumor spreading, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.565, November 12-14, 2000
• 22: David Kempe , Jon Kleinberg , Alan Demers, Spatial gossip and resource location protocols, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.163-172, July 2001, Hersonissos, Greece [doi>10.1145/380752.380796]
• 23: T. Leighton, B. Maggs, and R. Sitamaran. On the fault tolerance of some popular bounded-degree networks. In Proc. of FOCS'92, pages 542--552, 1992.
• 24: Michael David Mitzenmacher , Alistair Sinclair, The power of two choices in randomized load balancing, 1996
• 25: M. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.
• 26: Boris Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, v.47 n.1, p.213-223, Feb. 1987 [doi>10.1137/0147013]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
broadcasting, random graphs