# Distributed Random Walks

arXiv: https://arxiv.org/abs/1302.4544 · HTML: https://mlsanity.com/paper/1302.4544/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2013.

## Built on by (most cited first, 2 of 2)

- [Efficient and Local Parallel Random Walks](https://mlsanity.com/paper/2112.00655/) (2021)
- [Collaborative Learning in General Graphs with Limited Memorization: Complexity, Learnability, and Reliability](https://mlsanity.com/paper/2201.12482/) (2022)

## Abstract (arXiv)

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 ℓ 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 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 ℓ in tildeO(√ℓ D) rounds (tildeO 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(ℓ) 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 tildeO(√kℓ D + 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.