Distributed Random Walks

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.