[Colloq] Talk - Tuesday, Dec. 15 - Gopal Pandurangan, Nanyang Technological University and Brown University

[Rachel Kalweit]

The College of Computer and Information Science Colloquium presents:

Speaker: Gopal Pandurangan, Nanyang Technological University and Brown University
Date: Wednesday, December 15, 2009
Time: 11:00am
Location: 366 West Village H

Title: Walking Faster  in a Distributed Network

Abstract:
Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this talk, 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 L as a subroutine always do so naively, i.e., in O(L) rounds. We present a fast distributed algorithm for performing random walks. We show that  a random walk sample of length L can be computed in O(L^{1/2}D^{1/2}) rounds on an undirected unweighted network, where D is the diameter of the network. For small diameter graphs, this is a significant improvement over the naive O(L) bound.  We show that our algorithm is near-optimal by giving a almost matching lower bound. We also show that our algorithm  can be applied to speedup the more general Metropolis-Hastings sampling.

We extend our algorithms to  show how k independent walks can be performed in O((kLD)^1/2) + K) rounds.  Our techniques can be useful in speeding up distributed algorithms for a variety of applications that use random walks as a subroutine. We mention one such application involving the decentralized computation of spectral gap and mixing time, subroutines that can be useful in the design of self-regulating and self-aware networks.

Joint work with Atish Das Sarma, Danupon Nanongkai, and Prasad Tetali (Georgia Tech.).

Host: Rajmohan Rajaraman