skip to main content
10.1145/1582716.1582745acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
research-article

Fast distributed random walks

Published: 10 August 2009 Publication History

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 D1/3) rounds on an undirected unweighted network, where D is the diameter of the network.1 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 D1/3) rounds if k ≤ ℓ2 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]
R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In FOCS, pages 218--223, 1979.
[3]
N. Alon, C. Avin, M. Koucký, G. Kozma, Z. Lotker, and M. R. Tuttle. Many random walks are faster than one. In SPAA, pages 119--128, 2008.
[4]
B. Awerbuch, A. Baratz, and D. Peleg. Cost-sensitive analysis of communication protocols. In 9th ACM PODC, pages 177--187, 1990.
[5]
H. Baala, O. Flauzac, J. Gaber, M. Bui, and T. El-Ghazawi. A self-stabilizing distributed algorithm for spanning tree construction in wireless ad hoc networks. J. Parallel Distrib. Comput., 63(1):97--104, 2003.
[6]
J. Bar-Ilan and D. Zernik. Random leaders and random spanning trees. In Proceedings of the 3rd International Workshop on Distributed Algorithms, pages 1--12, London, UK, 1989. Springer-Verlag.
[7]
T. Bernard, A. Bui, and O. Flauzac. Random distributed self-stabilizing structures maintenance. In ISSADS, pages 231--240, 2004.
[8]
A. R. Bharambe, M. Agrawal, and S. Seshan. Mercury: supporting scalable multi-attribute range queries. In SIGCOMM, pages 353--366, 2004.
[9]
A. Z. Broder. Generating random spanning trees. In FOCS, pages 442--447, 1989.
[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]
D. Coppersmith, P. Tetali, and P. Winkler. Collisions among random walks on a graph. SIAM J. Discret. Math., 6(3):363--374, 1993.
[14]
A. Das Sarma, S. Gollapudi, and R. Panigrahy. Estimating pagerank on graph streams. In PODS, pages 69--78, 2008.
[15]
S. Dolev, E. Schiller, and J. L. Welch. Random walk for self-stabilizing group communication in ad hoc networks. IEEE Trans. Mob. Comput., 5(7):893--905, 2006. also in PODC'02.
[16]
S. Dolev and N. Tzachar. Spanders: Distributed spanning expanders. Dept. of Computer Science, Ben-Gurion University, TR-08-02, 2007.
[17]
A. J. Ganesh, A.-M. Kermarrec, and L. Massoulié. Peer-to-peer membership management for gossip-based protocols. IEEE Trans. Comput., 52(2):139--149, 2003.
[18]
C. Gkantsidis, M. Mihail, and A. Saberi. Hybrid search schemes for unstructured peer-to-peer networks. In INFOCOM, pages 1526--1537, 2005.
[19]
N. Goyal, L. Rademacher, and S. Vempala. Expanders via random spanning trees. In SODA, pages 576--585, 2009.
[20]
W. K. Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(1):97--109, April 1970.
[21]
A. Israeli and M. Jalfon. Token management schemes and random walks yield self-stabilizing mutual exclusion. In PODC, pages 119--131, 1990.
[22]
D. R. Karger and M. Ruhl. Simple efficient load balancing algorithms for peer-to-peer systems. In SPAA, pages 36--43, 2004.
[23]
D. Kempe, J. M. Kleinberg, and A. J. Demers. Spatial gossip and resource location protocols. In STOC, pages 163--172, 2001.
[24]
J. M. Kleinberg. The small-world phenomenon: an algorithm perspective. In STOC, pages 163--170, 2000.
[25]
C. Law and K.-Y. Siu. Distributed construction of random expander networks. In INFOCOM, 2003.
[26]
D. Loguinov, A. Kumar, V. Rai, and S. Ganesh. Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience. In SIGCOMM, pages 395--406, 2003.
[27]
Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. Search and replication in unstructured peer-to-peer networks. In ICS, pages 84--95, 2002.
[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]
M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York, NY, USA, 2005.
[30]
R. Morales and I. Gupta. Avmon: Optimal and scalable discovery of consistent availability monitoring overlays for distributed systems. In ICDCS, page 55, 2007.
[31]
G. Pandurangan and M. Khan. Theory of communication networks. In Algorithms and Theory of Computation Handbook, Second Edition. CRC Press, 2009.
[32]
D. Peleg. Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.
[33]
R. Sami and A. Twigg. Lower bounds for distributed markov chain problems. CoRR, abs/0810.5263, 2008.
[34]
D. B. Wilson. Generating random spanning trees more quickly than the cover time. In STOC, pages 296--303, 1996.
[35]
M. Zhong and K. Shen. Random walk based node sampling in self-organizing networks. Operating Systems Review, 40(3):49--55, 2006.
[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.

Cited By

View all

Index Terms

  1. Fast distributed random walks

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing
    August 2009
    356 pages
    ISBN:9781605583969
    DOI:10.1145/1582716
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 10 August 2009

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. distributed algorithm
    2. metropolis-hastings sampling
    3. random sampling
    4. random walks

    Qualifiers

    • Research-article

    Conference

    PODC '09

    Acceptance Rates

    PODC '09 Paper Acceptance Rate 27 of 110 submissions, 25%;
    Overall Acceptance Rate 740 of 2,477 submissions, 30%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)9
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Node Embedding Accelerates Randoms Walk on a Graph2024 IEEE 48th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC61105.2024.00079(537-545)Online publication date: 2-Jul-2024
    • (2023)Termination of amnesiac floodingDistributed Computing10.1007/s00446-023-00448-y36:2(193-207)Online publication date: 1-May-2023
    • (2022)Distributed PageRank computation with improved round complexitiesInformation Sciences10.1016/j.ins.2022.05.108607(109-125)Online publication date: Aug-2022
    • (2020)DConstructor: Efficient and Robust Network Construction with Polylogarithmic OverheadProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405716(438-447)Online publication date: 31-Jul-2020
    • (2019)Random walk with jumps in large-scale random geometric graphsComputer Communications10.1016/j.comcom.2010.01.02633:13(1505-1514)Online publication date: 4-Jan-2019
    • (2019)Deterministic Coresets for Stochastic Matrices with Applications to Scalable Sparse PageRankTheory and Applications of Models of Computation10.1007/978-3-030-14812-6_25(410-423)Online publication date: 13-Apr-2019
    • (2017)Distributed MST and Routing in Almost Mixing TimeProceedings of the ACM Symposium on Principles of Distributed Computing10.1145/3087801.3087827(131-140)Online publication date: 25-Jul-2017
    • (2016)Churn- and DoS-resistant Overlay Networks Based on Network ReconfigurationProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/2935764.2935783(417-427)Online publication date: 11-Jul-2016
    • (2016)Sampling-based algorithm for link prediction in temporal networksInformation Sciences: an International Journal10.1016/j.ins.2016.09.029374:C(1-14)Online publication date: 20-Dec-2016
    • (2016)DEXDistributed Computing10.1007/s00446-015-0258-329:3(163-185)Online publication date: 1-Jun-2016
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media