More Web Proxy on the site http://driver.im/

research-article

Efficient distributed random walks with applications

Authors:

Atish Das Sarma,

Danupon Nanongkai,

Gopal Pandurangan,

Prasad TetaliAuthors Info & Claims

PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

Pages 201 - 210

https://doi.org/10.1145/1835698.1835745

Published: 25 July 2010 Publication History

Abstract

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. We first present a fast sublinear time distributed algorithm for performing random walks whose time complexity is sublinear in the length of the walk. Our algorithm performs a random walk of length l in Õ(√l D) rounds (with high probability) on an undirected network, where D is the diameter of the network. This improves over the previous best algorithm that ran in Õ(l^2/3D^1/3) rounds (Das Sarma et al., PODC 2009). We further extend our algorithms to efficiently perform k independent random walks in Õ(√kl D + k) rounds. We then show that there is a fundamental difficulty in improving the dependence on l any further by proving a lower bound of Ω(√l/log l + D) under a general model of distributed random walk algorithms. Our random walk algorithms are useful in speeding up distributed algorithms for a variety of applications that use random walks as a subroutine. We present two main applications. First, we give a fast distributed algorithm for computing a random spanning tree (RST) in an arbitrary (undirected) network which runs in Õ(√mD) rounds (with high probability; here m is the number of edges). Our second application is a fast decentralized algorithm for estimating mixing time and related parameters of the underlying network. Our algorithm is fully decentralized and can serve as a building block in the design of topologically-aware networks.

References

[1]

D. Aldous. The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discrete Math., 3(4):450--465, 1990.

Digital Library

[2]

R. Aleliunas, R. Karp, R. Lipton, L. Lovasz, and C. Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In FOCS, 1979.

Digital Library

[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.

Digital Library

[4]

H. Baala, O. Flauzac, J. Gaber, M. Bui, and T. A. 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.

Digital Library

[5]

J. Bar-Ilan and D. Zernik. Random leaders and random spanning trees. In 3rd International Workshop on Distributed Algorithms (later called DISC), 1989.

Digital Library

[6]

T. Batu, L. Fortnow, E. Fischer, R. Kumar, R. Rubinfeld, and P. White. Testing random variables for independence and identity. In FOCS, pages 442--451, 2001.

Digital Library

[7]

A. Broder. Generating random spanning trees. In FOCS, 1989.

Digital Library

[8]

M. Bui, T. Bernard, D. Sohier, and A. Bui. Random walks in distributed computing: A survey. In IICS, pages 1--14, 2004.

Digital Library

[9]

C. Cooper, A. Frieze, and T. Radzik. Multiple random walks in random regular graphs. In Preprint, 2009.

[10]

A. Das Sarma, S. Gollapudi, and R. Panigrahy. Estimating pagerank on graph streams. In PODS, pages 69--78, 2008.

Digital Library

[11]

A. Das Sarma, D. Nanongkai, and G. Pandurangan. Fast distributed random walks. In PODC, pages 161--170, 2009.

Digital Library

[12]

A. Das Sarma, D. Nanongkai, G. Pandurangan, and P. Tetali. Efficient distributed random walks with applications. CoRR, abs/0911.3195, 2010. URL: http://arxiv.org/abs/0911.3195.

[13]

D. Dubhashi, F. Grandioni, and A. Panconesi. Distributed algorithms via lp duality and randomization. In Handbook of Approximation Algorithms and Metaheuristics. 2007.

[14]

M. Elkin. An overview of distributed approximation. ACM SIGACT News Distributed Computing Column, 35(4):40--57, December 2004.

Digital Library

[15]

M. Elkin. An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput., 36(2):433--456, 2006. Also appeared in STOC'04.

Digital Library

[16]

R. Elsässer and T. Sauerwald. Tight bounds for the cover time of multiple random walks. In ICALP (1), pages 415--426, 2009.

Digital Library

[17]

J. Garay, S. Kutten, and D. Peleg. A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput., 27:302--316, 1998.

Digital Library

[18]

C. Gkantsidis, G. Goel, M. Mihail, and A. Saberi. Towards topology aware networks. In IEEE INFOCOM, 2007.

Digital Library

[19]

N. Goyal, L. Rademacher, and S. Vempala. Expanders via random spanning trees. In SODA, 2009.

Digital Library

[20]

M. Jerrum and A. Sinclair. Approximating the permanent. SIAM Journal of Computing, 18(6):1149--1178, 1989.

Digital Library

[21]

J. Kelner and A. Madry. Faster generation of random spanning trees. In IEEE FOCS, 2009.

Digital Library

[22]

D. Kempe and F. McSherry. A decentralized algorithm for spectral analysis. Journal of Computer and System Sciences, 74(1):70--83, 2008.

Digital Library

[23]

M. Khan, F. Kuhn, D. Malkhi, G. Pandurangan, and K. Talwar. Efficient distributed approximation algorithms via probabilistic tree embeddings. In PODC, pages 263--272, 2008.

Digital Library

[24]

M. Khan and G. Pandurangan. A fast distributed approximation algorithm for minimum spanning trees. Distributed Computing, 20:391--402, 2008.

[25]

S. Kutten and D. Peleg. Fast distributed construction of k-dominating sets and applications. J. Algorithms, 28:40--66, 1998.

Digital Library

[26]

N. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, San Mateo, CA, 1996.

Digital Library

[27]

S. Muthukrishnan and G. Pandurangan. The bin-covering technique for thresholding random geometric graph properties. In ACM SODA, 2005. To appear in Journal of Computer and System Sciences.

Digital Library

[28]

G. Pandurangan and M. Khan. Theory of communication networks. In Algorithms and Theory of Computation Handbook, Second Edition. CRC Press, 2009.

[29]

D. Peleg. Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.

Digital Library

[30]

D. Peleg and V. Rubinovich. A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput., 30(5):1427--1442, 2000. Also in FOCS'99.

Digital Library

[31]

R. Sami and A. Twigg. Lower bounds for distributed markov chain problems. CoRR, abs/0810.5263, 2008.

[32]

J. S. Vitter. Random sampling with a reservoir. ACM Trans. Math. Softw., 11(1):37--57, 1985. Also in FOCS'83.

Digital Library

[33]

M. Zhong and K. Shen. Random walk based node sampling in self-organizing networks. Operating Systems Review, 40(3):49--55, 2006

Digital Library

Cited By

Hussak WTrehan A(2023)Termination of amnesiac floodingDistributed Computing10.1007/s00446-023-00448-y36:2(193-207)Online publication date: 1-May-2023
https://doi.org/10.1007/s00446-023-00448-y
Luo SWu XKao B(2022)Distributed PageRank computation with improved round complexitiesInformation Sciences: an International Journal10.1016/j.ins.2022.05.108607:C(109-125)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.ins.2022.05.108
Ghaffari MKuhn FSu HSchiller ESchwarzmann A(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
https://dl.acm.org/doi/10.1145/3087801.3087827
Show More Cited By

Index Terms

Efficient distributed random walks with applications
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

Fast distributed random walks
PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

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 ...
Distributed Random Walks

Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this article, we focus on the problem of sampling random walks efficiently in a distributed ...
Efficient random walk sampling in distributed networks

Performing random walks in networks is a fundamental primitive that has found numerous applications in communication networks such as token management, load balancing, network topology discovery and construction, search, and peer-to-peer membership ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

July 2010

494 pages

ISBN:9781605588889

DOI:10.1145/1835698

General Chairs:
Andrea Richa
Arizona State University, USA
,
Rachid Guerraoui
EPFL, Switzerland

Copyright © 2010 ACM.

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: 25 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '10

Sponsor:

PODC '10: ACM Symposium on Principles of Distributed Computing

July 25 - 28, 2010

Zurich, Switzerland

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
443
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)3

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hussak WTrehan A(2023)Termination of amnesiac floodingDistributed Computing10.1007/s00446-023-00448-y36:2(193-207)Online publication date: 1-May-2023
https://doi.org/10.1007/s00446-023-00448-y
Luo SWu XKao B(2022)Distributed PageRank computation with improved round complexitiesInformation Sciences: an International Journal10.1016/j.ins.2022.05.108607:C(109-125)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.ins.2022.05.108
Ghaffari MKuhn FSu HSchiller ESchwarzmann A(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
https://dl.acm.org/doi/10.1145/3087801.3087827
Ahmed NChen LWang YLi BLi YLiu W(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
https://dl.acm.org/doi/10.1016/j.ins.2016.09.029
Millán VCholvi VFernández Anta ALópez L(2016)Resource location based on precomputed partial random walks in dynamic networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2016.04.008103:C(165-180)Online publication date: 5-Jul-2016
https://dl.acm.org/doi/10.1016/j.comnet.2016.04.008
Dutta CPandurangan GRajaraman RRoche S(2015)Coalescing-Branching Random Walks on GraphsACM Transactions on Parallel Computing10.1145/28178302:3(1-29)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.1145/2817830
Das Sarma AMolla APandurangan G(2015)Efficient random walk sampling in distributed networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.01.00277:C(84-94)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1016/j.jpdc.2015.01.002
Censor-Hillel KGhaffari MKuhn FHalldórsson MDolev S(2014)Distributed connectivity decompositionProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611491(156-165)Online publication date: 15-Jul-2014
https://dl.acm.org/doi/10.1145/2611462.2611491
Ghaffari M(2014)Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating SetAutomata, Languages, and Programming10.1007/978-3-662-43951-7_41(483-494)Online publication date: 2014
https://doi.org/10.1007/978-3-662-43951-7_41
Dutta CPandurangan GRajaraman RRoche SBlelloch GVöcking B(2013)Coalescing-branching random walks on graphsProceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures10.1145/2486159.2486197(176-185)Online publication date: 23-Jul-2013
https://dl.acm.org/doi/10.1145/2486159.2486197
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents