10/26/2012
CSE Colloquium
11:00 AM
Lopata 101
Rajmohan Rajaraman
Professor
Northeastern University
On the Complexity of Information Spreading
in Dynamic Networks
We study how to spread k distinct tokens of information to every node on an n-node dynamic network, the edges of which are changing at each round. This basic gossip problem can be completed in a linear number of rounds in any connected static network. The central question of our study is: Can this gossip problem be solved in a linear number of rounds on any connected dynamic network? Our focus is on token forwarding algorithms, which do not manipulate tokens in any way other than storing, copying and forwarding them.We present a nearly quadratic lower bound on the gossip time in a strongly adaptive adversary model, in which the adversary sets the edges of a connected network in each round with knowledge of the algorithm's moves. This establishes a near-linear factor gap between network coding and token forwarding approaches for such dynamic network models. Surprisingly, this lower bound also holds for well-mixed initial distributions, where each node starts with a uniform random sample of a constant fraction of the k tokens. Our lower bound motivates us to study weaker notions of adversary. We present a simple randomized protocol that completes gossip starting from any well-mixed distribution in near-linear rounds against a weak adaptive adversary. This algorithm includes a new communication protocol for uniform sampling that may be of independent interest. We also obtain a near-linear round centralized algorithm that solves the gossip problem for every initial distribution in an offline setting where the evolution of the dynamic network is known to the algorithm in advance. (Joint work with Chinmoy Dutta, Gopal Pandurangan, Zhifeng Sun, and Emanuele Viola. To appear in SODA 2013.)
Biography
Rajmohan Rajaraman is a Professor of Computer Science at Northeastern University, Boston, currently on sabbatical at Google Research, Mountain View. His primary research interest is in theoretical computer science, with a focus on approximation algorithms and distributed computing. He obtained a Bachelor's degree in CS from IIT Kanpur, India in 1991 and MS and PhD in CS from the University of Texas at Austin in 1993 and 1997, respectively. He was a postdoctoral fellow at DIMACS for a year before joining the faculty at Northeastern in 1998. He is the recipient of an NSF Career award and has co-authored best papers in ICDCS 2006 and WiSec 2011.
Computer Science & Engineering
Computer Science and Engineering (314) 935-6160
Back to Calendar