Distributed random walks

DOI10.1145/2432622.2432624MaRDI QIDQ5395702zbMATH OpenOpenAlexWikidataFDO

Authors Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali

Publication date 17 February 2014

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.4544

zbMATH Keywords

decentralized computationdistributed algorithmsmixing timerandom samplingrandom spanning treerandom walks

Mathematics Subject Classification ID

Random walks on graphs (05C81) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

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 sampling random walks efficiently in a distributed network and its applications. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain random walk samples. All previous algorithms that compute a random walk sample of length $ell$ as a subroutine always do so naively, i.e., in $O(ell)$ rounds. The main contribution of this paper is a fast distributed algorithm for performing random walks. We present a 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 $ell$ in $ildeO(sqrtellD)$ rounds ($ildeO$ hides $polylogn$ factors where $n$ is the number of nodes in the network) with high probability on an undirected network, where $D$ is the diameter of the network. For small diameter graphs, this is a significant improvement over the naive $O(ell)$ bound. Furthermore, our algorithm is optimal within a poly-logarithmic factor as there exists a matching lower bound [Nanongkai et al. PODC 2011]. We further extend our algorithms to efficiently perform $k$ independent random walks in $ildeO(sqrtkellD+k)$ rounds. We also show that our algorithm can be applied to speedup the more general Metropolis-Hastings sampling. Our random walk algorithms can be used to speed up distributed algorithms in applications that use random walks as a subroutine, such as computing a random spanning tree and estimating mixing time and related parameters. Our algorithm is fully decentralized and can serve as a building block in the design of topologically-aware networks.

Recommendations

• Efficient distributed random walks with applications
• Fast distributed random walks
• Distributed computation in dynamic networks via random walks
• Fast distributed computation in dynamic networks via random walks
• A tight unconditional lower bound on distributed randomwalk computation

Cited in

(22)

• Random walks, heat equation and distributed algorithms
• What can be sampled locally?
• Sampling-based algorithm for link prediction in temporal networks
• Estimating graph parameters with random walks
• Distributed computation in dynamic networks via random walks
• A tight unconditional lower bound on distributed randomwalk computation
• Improving random walk estimation accuracy with uniform restarts
• Aggregation is the key to succeed in random walks
• How Well Do Random Walks Parallelize?
• scientific article; zbMATH DE number 1305416 (Why is no real title available?)
• Fast distributed PageRank computation
• Fast distributed computation in dynamic networks via random walks
• Improving resource location with locally precomputed partial random walks
• A two-sided error distributed property tester for conductance
• Fast distributed random walks
• Efficient distributed random walks with applications
• How to compute times of random walks based distributed algorithms
• Multiple random walks on graphs: mixing few to cover many
• A parallel pagerank algorithm for undirected graph
• Time- and communication-efficient overlay network construction via gossip
• Multiple random walks on graphs: mixing few to cover many
• Towards communication-efficient Peer-to-Peer networks

This page was built for publication: Distributed random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5395702)