Efficient distributed random walks with applications

DOI10.1145/1835698.1835745MaRDI QIDQ5176199zbMATH OpenOpenAlexFDO

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

Publication date 2 March 2015

Published in Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

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

zbMATH Keywords

decentralized computationdistributed algorithmsmixing timerandom samplingrandom spanning treerandom walks

Mathematics Subject Classification ID

Random walks on graphs (05C81) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Randomized algorithms (68W20)

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 $ell$ in $ildeO(sqrtellD)$ 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 $ildeO(el{l}^{2/3}{D}^{1/3})$ rounds (Das Sarma et al., PODC 2009). We further extend our algorithms to efficiently perform $k$ independent random walks in $ildeO(sqrtkellD+k)$ rounds. We then show that there is a fundamental difficulty in improving the dependence on $ell$ any further by proving a lower bound of $Omega(sqrtfracelllogell+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 $ildeO(sqrtmD)$ 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.

Recommendations

• Fast distributed random walks
• Distributed random walks
• Fast distributed computation in dynamic networks via random walks
• Distributed computation in dynamic networks via random walks
• How to compute times of random walks based distributed algorithms
• A tight unconditional lower bound on distributed randomwalk computation
• Random walks, heat equation and distributed algorithms
• Distributed algorithms with dynamical random transitions
• Distributed randomized algorithms for probabilistic performance analysis

Cites work

• Elastic Transactions
• Software transactional memory
• Toward a theory of transactional contention managers

Cited in

(14)

• Random walks, heat equation and distributed algorithms
• Sampling-based algorithm for link prediction in temporal networks
• Distributed computation in dynamic networks via random walks
• A tight unconditional lower bound on distributed randomwalk computation
• How Well Do Random Walks Parallelize?
• scientific article; zbMATH DE number 1305416 (Why is no real title available?)
• Fast distributed computation in dynamic networks via random walks
• Fast distributed random walks
• Distributed MST and routing in almost mixing time
• Distributed random walks
• How to compute times of random walks based distributed algorithms
• Distributed routing of ads and bids through random walks in the IDOS system
• Termination of amnesiac flooding
• Distributed PageRank computation with improved round complexities

Describes a project that uses

Uses Software

• CCSTM

This page was built for publication: Efficient distributed random walks with applications

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