Fast Distributed Random Walks (PODC’09)

RandomWalkAuthors: 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 Computin[wiki]


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 \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 show that  a random walk sample of length \ell can be computed in \tilde{O}(\ell^{2/3}D^{1/3}) rounds on an undirected unweighted network, where D is the diameter of the network. (\tilde{O} hides \frac{log{n}}{\delta} factors where n is the number of nodes in the network and \delta is the minimum degree.) For small diameter graphs, this is a significant improvement over the naive O(\ell) 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, k, of random walks efficiently. We show how k destinations can be sampled in \tilde{O}((k\ell)^{2/3}D^{1/3}) rounds if k\leq \ell^2 and \tilde{O}((k\ell)^{1/2}) 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)


1 Comment »

  1. danupon said

    Random walks in networks are a fundamental tool in many network applications. This paper presents the first non-trivial distributed algorithms for performing random walks that are significantly faster than existing approaches.

RSS feed for comments on this post · TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: