Efficient distributed random walks with applications

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 Õ(l2/3D1/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.

• Publication year

  2009

• Venue

  ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

• Publication date

  2009-11-16

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/1835698.1835745arXiv 0911.3195
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Theory of communication networks

  2010cited by this paper
• Faster Generation of Random Spanning Trees

  2009cited by this paper
• Multiple Random Walks in Random Regular Graphs

  2009cited by this paper
• Fast distributed random walks

  2009influential reference
• Tight bounds for the cover time of multiple random walks

  2009cited by this paper
• Lower bounds for distributed markov chain problems

  2008cited by this paper
• Expanders via random spanning trees

  2008cited by this paper
• Estimating PageRank on graph streams

  2008cited by this paper
• Efficient distributed approximation algorithms via probabilistic tree embeddings

  2008cited by this paper
• Many random walks are faster than one

  2007cited by this paper
• Towards Topology Aware Networks

  2007cited by this paper
• Distributed Approximation Algorithms via LP-Duality and Randomization

  2007cited by this paper
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem

  2006cited by this paper
• A fast distributed approximation algorithm for minimum spanning trees

  2006cited by this paper
• Random walk based node sampling in self-organizing networks

  2006cited by this paper
• The bin-covering technique for thresholding random geometric graph properties

  2005cited by this paper
• Probability and Computing: Randomized Algorithms and Probabilistic Analysis

  2005influential reference
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem

  2004cited by this paper
• Random Walks in Distributed Computing: A Survey

  2004cited by this paper
• A decentralized algorithm for spectral analysis

  2004influential reference
• Distributed approximation: a survey

  2004cited by this paper
• A self-stabilizing distributed algorithm for spanning tree construction in wireless ad hoc networks

  2003cited by this paper
• Asymptotic Enumeration of Spanning Trees

  2002influential reference
• 6.856 — Randomized Algorithms

  2002cited by this paper
• Testing random variables for independence and identity

  2001influential reference
• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction

  2000cited by this paper
• A near-tight lower bound on the time complexity of distributed MST construction

  1999cited by this paper
• Fast Distributed Construction of Small k-Dominating Sets and Applications

  1998cited by this paper
• Fast distributed construction of k-dominating sets and applications

  1995cited by this paper
• A sub-linear time distributed algorithm for minimum-weight spanning trees

  1993cited by this paper
• Distributed Algorithms

  1992cited by this paper
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees

  1990cited by this paper
• Random Leaders and Random Spanning Trees

  1989cited by this paper
• Approximating the Permanent

  1989cited by this paper
• Random Walks on ℤ

  1988cited by this paper
• Distributed Computing: A Locality-Sensitive Approach

  1987influential reference
• Random sampling with a reservoir

  1985cited by this paper
• Random walks, universal traversal sequences, and the complexity of maze problems

  1979cited by this paper

• Termination of amnesiac flooding

  2023cites this paper
• Distributed PageRank computation with improved round complexities

  2022cites this paper
• Terminating cases of flooding

  2020cites this paper
• On the Termination of Flooding

  2020cites this paper
• Distributed PageRank Computation: An Improved Theoretical Study

  2019cites this paper
• Fast Fault-Tolerant Sampling via Random Walk in Dynamic Networks

  2019influential citation
• The Communication Cost of Information Spreading in Dynamic Networks

  2018cites this paper
• Near-Optimal Distributed DFS in Planar Graphs

  2017cites this paper
• Distributively Computing Random Walk Betweenness Centrality in Linear Time

  2017cites this paper
• Distributed MST and Routing in Almost Mixing Time

  2017cites this paper
• Sampling-based algorithm for link prediction in temporal networks

  2016cites this paper
• Coalescing-Branching Random Walks on Graphs

  2015cites this paper
• Efficient random walk sampling in distributed networks

  2015cites this paper
• Resource location based on precomputed partial random walks in dynamic networks

  2015cites this paper
• Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set

  2014cites this paper
• Random walks in distributed networks and their applications

  2014cites this paper
• Distributed connectivity decomposition

  2013cites this paper
• Distributed Random Walks

  2013influential citation
• Improving resource location with locally precomputed partial random walks

  2013cites this paper
• D C ] 1 9 Fe b 20 13 Distributed Random Walks ∗

  2013cites this paper
• Resource Location Mechanisms for Complex Networks Based on Random Walks

  2013influential citation
• Coalescing-branching random walks on graphs

  2013cites this paper
• Near-optimal random walk sampling in distributed networks

  2012influential citation
• Fast Distributed PageRank Computation

  2012cites this paper
• Branching Random Walks on Graphs

  2012cites this paper
• Self-healing Deterministic Expanders

  2012cites this paper
• Resource location based on partial random walks in networks with resource dynamics

  2012cites this paper
• Fast Distributed Computation in Dynamic Networks via Random Walks

  2012cites this paper
• Graph and geometric algorithms on distributed networks and databases

  2011cites this paper
• A tight unconditional lower bound on distributed randomwalk computation

  2011cites this paper
• Reducing Search Lengths with Locally Precomputed Partial Random Walks

  2011influential citation
• Graph and geometric algorithms on distributed networks and databases

  2011cites this paper
• Algorithms for large graphs

  2010cites this paper
• Expansion and the cover time of parallel random walks

  2010cites this paper