Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems

ABSTRACT

We consider broadcasting in random d-regular graphs by using a simple modification of the so-called random phone call model introduced by Karp et al. [19]. In the phone call model every time step each node calls on a randomly chosen neighbour to establish a communication channel with this node. The communication channels can then be used to transmit messages in both directions. We show that, if we allow every node to choose four distinct neighbours instead of one, then the average number of message transmissions per node decreases exponentially. Formally, we present a broadcasting algorithm that has time complexity O(log n) and uses O(n log log n) transmissions per message. In contrast, we show for the standard model that every distributed and address-oblivious algorithm that broadcasts a message in time O(log n) needs Ω(n log n/ log d) message transmissions. Our algorithm can efficiently handle limited communication failures, only requires rough estimates of the number of nodes, and is robust against limited changes in the size of the network. Our results have applications in peer-to-peer networks and replicated databases.

REFERENCES

• 1: B. Bollobás. Random Graphs. Academic Press, 1985.
• 2: Sherif Botros , Steve Waterhouse, Search in JXTA and Other Distributed Networks, Proceedings of the First International Conference on Peer-to-Peer Computing (P2P'01), p.30, August 27-29, 2001
• 3: Stephen Boyd , Arpita Ghosh , Balaji Prabhakar , Devavrat Shah, Randomized gossip algorithms, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2508-2530, June 2006 [doi>10.1109/TIT.2006.874516]
• 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: Colin Cooper , Martin Dyer , Catherine Greenhill, Sampling regular graphs and a peer-to-peer network, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 6: 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]
• 7: Benjamin Doerr , Tobias Friedrich , Thomas Sauerwald, Quasirandom rumor spreading, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.773-781, January 20-22, 2008, San Francisco, California
• 8: Robert Elsässer, On the communication complexity of randomized broadcasting in random-like graphs, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148135]
• 9: R. Els\"asser and T. Sauerwald. Broadcasting vs. mixing and information dissemination on Cayley graphs. In Proc. of STACS'07, pp. 163--174, 2007.
• 10: Robert Elsässer , Thomas Sauerwald, The power of memory in randomized broadcasting, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.218-227, January 20-22, 2008, San Francisco, California
• 11: P. Erd\H os and A. Rényi. On random graphs I. Publ. Math. Debrecen, 6:290--297, 1959.
• 12: P. Erd\H os and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17--61, 1960.
• 13: Tomas Feder , Adam Guetz , Milena Mihail , Amin Saberi, A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.69-76, October 21-24, 2006 [doi>10.1109/FOCS.2006.5]
• 14: U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. Random Structures and Algorithms, 1(4):447--460, 1990.
• 15: A.M. Frieze and G.R. Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics, 10:57--77, 1985.
• 16: Gnutella. The gnutella protocol specification v.0.4.
• 17: 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]
• 18: S. Jagannathan, G. Pandurangan, and S. Srinivasan. Query protocols for highly resilient peer-to-peer networks. In Proc. of ISCA PDCS'06, pp. 247--252, 2006.
• 19: 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
• 20: 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]
• 21: C. Law and K.-Y. Siu. Distributed construction of random expander networks. In Proceedings of the 22nd INFOCOM, pp. 2133--2143, 2003.
• 22: Peter Mahlmann , Christian Schindelhauer, Distributed random digraph transformations for peer-to-peer networks, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148162]
• 23: B. D. McKay , N. C. Wormald, Asymptotic enumeration by degree sequence of graphs of high degree, European Journal of Combinatorics, v.11 n.6, p.565-580, Nov. 1990
• 24: M. Newman. The Structure and Function of Complex Networks. SIAM Review, 45(2):167-- 256, 2003.
• 25: G. Pandurangan, Building Low-Diameter P2P Networks, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.492, October 14-17, 2001
• 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]
• 27: R.W. Robinson and N.C. Wormald. Almost all regular graphs are Hamiltonian. Random Structures and Algorithms, 5:363--374, 1994.
• 28: T. Sauerwald. On Mixing and Edge Expansion Properties in Randomized Broadcasting . In Proc. of ISAAC'07, pp. 196--207, 2007.

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 regular graphs