Fast distributed random walks

ABSTRACT

Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this paper, we focus on the problem of performing random walks efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain a random walk sample.

All previous algorithms that compute a random walk sample of length ℓ as a subroutine always do so naively, i.e., in O(ℓ) rounds. The main contribution of this paper is a fast distributed algorithm for performing random walks. We show that a random walk sample of length ℓ can be computed in Õ(ℓ^2/3 D^1/3) rounds on an undirected unweighted network, where D is the diameter of the network.¹ When ℓ = Ω(D log n), this is an improvement over the naive O(ℓ) bound. (We show that Ω(min{D, ℓ}) is a lower bound and hence in general we cannot have a running time faster than the diameter of the graph.) We also show that our algorithm can be applied to speedup the more general Metropolis-Hastings sampling.

We extend our algorithms to perform a large number, k, of random walks efficiently. We show how k destinations can be sampled in Õ((kℓ)^2/3 D^1/3) rounds if k ≤ ℓ² and Õ((kℓ)^1/2) rounds otherwise. We also present faster algorithms for performing random walks of length larger than (or equal to) the mixing time of the underlying graph. Our techniques can be useful in speeding up distributed algorithms for a variety of applications that use random walks as a subroutine.

REFERENCES

• 1: L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman. Search in power-law networks. Physical Review, 64, 2001.
• 2: Romas Aleliunas , Richard M. Karp , Richard J. Lipton , Laszlo Lovasz , Charles Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, Proceedings of the 20th Annual Symposium on Foundations of Computer Science, p.218-223, October 29-31, 1979
• 3: Noga Alon , Chen Avin , Michal Koucky , Gady Kozma , Zvi Lotker , Mark R. Tuttle, Many random walks are faster than one, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378557]
• 4: Baruch Awerbuch , Alan Baratz , David Peleg, Cost-sensitive analysis of communication protocols, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.177-187, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93417]
• 5: H. Baala , O. Flauzac , J. Gaber , M. Bui , T. El-Ghazawi, A self-stabilizing distributed algorithm for spanning tree construction in wireless ad hoc networks, Journal of Parallel and Distributed Computing, v.63 n.1, p.97-104, January 2003 [doi>10.1016/S0743-7315(02)00028-X]
• 6: Judit Bar-Ilan , Dror Zernik, Random Leaders and Random Spanning Trees, Proceedings of the 3rd International Workshop on Distributed Algorithms, p.1-12, September 26-28, 1989
• 7: T. Bernard, A. Bui, and O. Flauzac. Random distributed self-stabilizing structures maintenance. In ISSADS, pages 231--240, 2004.
• 8: Ashwin R. Bharambe , Mukesh Agrawal , Srinivasan Seshan, Mercury: supporting scalable multi-attribute range queries, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 9: A. Broder, Generating random spanning trees, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.442-447, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63516]
• 10: M. Bui, T. Bernard, D. Sohier, and A. Bui. Random walks in distributed computing: A survey. In IICS, pages 1--14, 2004.
• 11: F. Chung. Spectral Graph Theory. American Mathematical Society, Providence, RI, USA, 1997.
• 12: B. F. Cooper. Quickly routing searches without having to move content. In IPTPS, pages 163--172, 2005.
• 13: Don Coppersmith , Prasad Tetali , Peter Winkler, Collisions among random walks on a graph, SIAM Journal on Discrete Mathematics, v.6 n.3, p.363-374, Aug. 1993 [doi>10.1137/0406029]
• 14: Atish Das Sarma , Sreenivas Gollapudi , Rina Panigrahy, Estimating PageRank on graph streams, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376928]
• 15: Shlomi Dolev , Elad Schiller , Jennifer L. Welch, Random Walk for Self-Stabilizing Group Communication in Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.5 n.7, p.893-905, July 2006 [doi>10.1109/TMC.2006.104]
• 16: S. Dolev and N. Tzachar. Spanders: Distributed spanning expanders. Dept. of Computer Science, Ben-Gurion University, TR-08-02, 2007.
• 17: Ayalvadi J. Ganesh , Anne-Marie Kermarrec , Laurent Massoulié, Peer-to-Peer Membership Management for Gossip-Based Protocols, IEEE Transactions on Computers, v.52 n.2, p.139-149, February 2003 [doi>10.1109/TC.2003.1176982]
• 18: C. Gkantsidis, M. Mihail, and A. Saberi. Hybrid search schemes for unstructured peer-to-peer networks. In INFOCOM, pages 1526--1537, 2005.
• 19: Navin Goyal , Luis Rademacher , Santosh Vempala, Expanders via random spanning trees, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.576-585, January 04-06, 2009, New York, New York
• 20: W. K. Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(1):97--109, April 1970.
• 21: Amos Israeli , Marc Jalfon, Token management schemes and random walks yield self-stabilizing mutual exclusion, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.119-131, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93409]
• 22: David R. Karger , Matthias Ruhl, Simple efficient load balancing algorithms for peer-to-peer systems, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007919]
• 23: 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]
• 24: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 25: C. Law and K.-Y. Siu. Distributed construction of random expander networks. In INFOCOM, 2003.
• 26: Dmitri Loguinov , Anuj Kumar , Vivek Rai , Sai Ganesh, Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863999]
• 27: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 28: N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6):1087--1092, 1953.
• 29: Michael Mitzenmacher , Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, New York, NY, 2005
• 30: Ramses Morales , Indranil Gupta, AVMON: Optimal and Scalable Discovery of Consistent Availability Monitoring Overlays for Distributed Systems, Proceedings of the 27th International Conference on Distributed Computing Systems, p.55, June 25-27, 2007 [doi>10.1109/ICDCS.2007.87]
• 31: G. Pandurangan and M. Khan. Theory of communication networks. In Algorithms and Theory of Computation Handbook, Second Edition. CRC Press, 2009.
• 32: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 33: R. Sami and A. Twigg. Lower bounds for distributed markov chain problems. CoRR, abs/0810.5263, 2008.
• 34: David Bruce Wilson, Generating random spanning trees more quickly than the cover time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.296-303, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237880]
• 35: Ming Zhong , Kai Shen, Random walk based node sampling in self-organizing networks, ACM SIGOPS Operating Systems Review, v.40 n.3, July 2006 [doi>10.1145/1151374.1151386]
• 36: M. Zhong, K. Shen, and J. I. Seiferas. Non-uniform random membership management in peer-to-peer networks. In INFOCOM, pages 1151--1161, 2005.

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:
distributed algorithm, metropolis-hastings sampling, random sampling, random walks