Efficient Distributed Random Walks with Applications

Author: Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali

Download: arXiv of the journal versionarXiv of the conference version

Conference: PODC 2010

Journal: Journal of the ACM 2013


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 \tilde{O}(\sqrt{\ell D})  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 \tilde{O}(\ell^{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   \tilde{O}(\sqrt{k\ell D} + 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(\sqrt{\frac{\ell}{\log \ell}} + 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 \tilde{O}(\sqrt{m}D) 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.

Update History

Mar 03, 2009 (New version posted on ArXiv)
Nov 06, 2009 (Link to arXiv posted)
Feb 18, 2010 (New version posted)
Feb 18, 2013 (Journal version posted)


1 Comment »

  1. danupon said

    The earlier version of this paper was titled “Near-Optimal Sublinear Time Bounds for Distributed Random Walks” and can be found at http://arxiv.org/abs/0911.3195. We changed the name since we include more applications to the paper.

RSS feed for comments on this post · TrackBack URI

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: