The power of memory in randomized broadcasting

ABSTRACT

In this paper we analyze the runtime and number of message transmissions generated by simple randomized broadcasting algorithms in random-like networks, and show that an apparently minor change in the ability of the nodes implies an exponential decrease in the average communication overhead produced by these algorithms at an arbitrary node.

A natural randomized broadcasting protocol, called random phone call model, has been introduced by Karp et al. [20]. In this model it is assumed that in each time step, every node of G calls a neighbor, chosen uniformly at random, and establishes a communication channel with this neighbor. Any node u is then allowed to send/receive messages to/from all nodes which have established communication channels with u in the current time step. Karp et al. showed that some piece of information r, placed initially on one of the nodes of a complete graph of size n, can be spread with probability 1 - n^-Ω(1) to all nodes of this graph within O(log n) time steps, by using O(n log log n) transmissions related to r. Furthermore, they proved that this result is asymptotically optimal among all address-oblivious broadcasting algorithms. In a recent paper [9], we analyzed the random phone call model in traditional random graphs G_n,p with p > log² n/n, and showed that any address-oblivious broadcasting algorithm requires with high probability Ω(log n) time steps and Ω(n (log log n + log n/log(pn))) message transmissions to inform all nodes of such a graph. In this paper we consider two simple modifications of the random phone call model, and show that in both cases the number of total message transmissions can be reduced significantly (up to almost a logarithmic factor). In the first case, we allow each node of a random graph G_n,p with p > log^δ n/n, where λ is a properly chosen constant, to call in every time step four different neighbors, chosen uniformly at random, and we prove that the number of message transmissions decreases to O(n log log n). This can be viewed as a "power of multiple choices" type theorem for randomized broadcasting. Then we show that if in the random phone call model the nodes are provided with a little memory, i.e., they are able to remember the addresses of the nodes chosen in the most recent three time steps, then the communication overhead decreases substantially, too. Finally, we prove the optimality of our results.

The algorithms presented in this paper can cope with restricted communication failures, only require rough estimates of the number of nodes, and are robust against slight topological changes. In addition, our results can be extended to the generalized random graph model of [6].

REFERENCES

• 1: N. Alon and J. Spencer. The Probabilistic Method. John Wiley, 1991.
• 2: B. Bollobás. Random Graphs. Academic Press, 1985.
• 3: 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
• 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. Chung and L. Lu. Concentration inequalities and martingale inequalities --- a survey. Internet Mathematics (to appear).
• 6: F. Chung and L. Lu. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6:125--145, 2002.
• 7: 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
• 8: 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]
• 9: 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]
• 10: P. Erdös and A. Rényi. On random graphs I. Publ. Math. Debrecen, 6:290--297, 1959.
• 11: P. Erdös and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17--61, 1960.
• 12: 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]
• 13: U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. Random Structures and Algorithms, 1(4):447--460, 1990.
• 14: A. M. Frieze and G. R. Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics, 10:57--77, 1985.
• 15: 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]
• 16: E. N. Gilbert. Random graphs. The Annals of Mathematical Statistics, 30:1141--1144, 1959.
• 17: Gnutella. The gnutella protocol specification v.0.4.
• 18: 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]
• 19: S. Jagannathan, G. Pandurangan, and S. Srinivasan. Query protocols for highly resilient peer-to-peer networks. In Proc. of ISCA PDCS'06, pages 247--252, 2006.
• 20: 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
• 21: C. Law and K.-Y. Siu. Distributed construction of random expander networks. In Proc. of INFOCOM'03, pages 2133--2143, 2003.
• 22: 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.
• 23: 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]
• 24: B. D. McKay and N. C. Wormald. Asymptotic enumeration by degree sequence of graphs with degrees o(sqrt(n)). Combinatorica, 11:369--382, 1991.
• 25: M. Mitzenmacher. The Power of Two Choices in Randomized Load Balancing. PhD thesis, University of California at Berkeley, 1996.
• 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: N. C. Wormald. Models of random regular graphs. Surveys in Combinatorics, 276:293--298, 1999.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
      G.2.3 Applications

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory