CS 789 THEORY SEMINAR [home]

Speaker:  David Kempe
Affiliation: Computer Science, Cornell University
Date: Monday, October 7, 2002
Title: "Protocols and Impossibility Results for Gossip-Based Communication
          Mechanisms" 

Abstract:

In recent years, gossip-based algorithms have gained prominence as a methodology for designing robust and scalable communication schemes in large distributed systems. The premise underlying distributed gossip is very simple: in each time step, each node v in the system selects some other node w as a communication partner --- generally by a simple randomized rule --- and exchanges information with w; over a period of time, information spreads through the system in an "epidemic fashion". 

A fundamental issue which is not well understood is the following: how does the underlying low-level gossip mechanism --- the means by which communication partners are chosen --- affect one's ability to design efficient high-level gossip-based protocols? We establish one of the first concrete results addressing this question, by showing a fundamental limitation on the power of the commonly used uniform gossip mechanism for solving nearest-resource location problems. In contrast, very efficient protocols for this problem can be designed using a non-uniform spatial gossip mechanism, as established in earlier work with Alan Demers.

We go on to consider the design of protocols for more complex problems, providing an efficient distributed gossip-based protocol for a set of nodes in Euclidean space to construct an approximate minimum spanning tree. Here too, we establish a contrasting limitation on the power of uniform gossip for solving this problem. Finally, we investigate gossip-based packet routing as a primitive that underpins the communication patterns in many protocols, and as a way to understand the capabilities of different gossip mechanisms at a general level.

Joint work with Jon Kleinberg