How Fast Can You Walk in a Distributed Network?

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. Most algorithms that compute a random walk sample of length ` always do so naively, i.e., in O(`) rounds. Recently, a significantly faster distributed algorithm was presented that ran in time Õ(`2/3D1/3) [Das Sarma, Nanongkai and Pandurangan, PODC 2009]. This work conjectured that: (1) it might be possible to obtain a running time of Õ( `D); and (2) this is essentially the best that one can achieve. This paper makes significant progress towards answering these conjectures. The first main contribution of this paper is an improved distributed algorithm for performing random walks. We show that a random walk of length ` can be performed in Õ min