2009/11/17 by Atish Das Sarma, Danupon Nanongkai, Sarma, Atish Das +5
Computer Science · Mathematics · #Distributed systems and fault tolerance #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.0911.3195
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 ℓ in O(√(ℓ 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 O(ℓ2/3D1/3) rounds (Das Sarma et al., PODC 2009). We further extend our algorithms to efficiently perform k independent random walks in O(√(kℓ D) + k) rounds. We then show that there is a fundamental difficulty in improving the dependence on ℓ any further by proving a lower bound of Ω(√((ℓ)/(log ℓ)) + 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 O(√(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.