**Authors:** Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan

**Download:** PDF of the journal version,** **PDF of the conference version, Slides

**Journal: **Journal of the ACM 2013

**Conference: **PODC 2009: 28th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing [wiki]

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

All previous algorithms that compute a random walk sample of length as a subroutine always do so naively, i.e., in rounds. The main contribution of this paper is a fast distributed

algorithm for performing random walks. We show that a random walk sample of length can be computed in rounds on an undirected unweighted network, where is the diameter of the network. ( hides factors where is the number of nodes in the network and is the minimum degree.) For small diameter graphs, this is a significant improvement over the naive bound. We also show that our algorithm can be applied to speedup the more general Metropolis-Hastings sampling.

We extend our algorithms to perform a large number, , of random walks efficiently. We show how destinations can be sampled in rounds if and rounds otherwise. We also present faster algorithms for performing random walks of length larger than (or equal to) the mixing time of the underlying graph. Our techniques can be useful in speeding up distributed algorithms for a variety of applications that use random walks as a subroutine.

**Keywords: **Random walks, Random sampling, Distributed algorithm, Metropolis-Hastings sampling.

**Update History**

**[v1]** May 31, 2009 (Conference version)

**[v2]** Feb 18, 2013 (Journal version posted)