Title:	Randomized Gossip Algorithms for Distributed Computation

Speaker: Devavrat Shah

Place: 	32-G531, Stata Center
Time: 	1-2:30 pm
Date: 	Friday, October 6, 2006

Abstract:

Recently emerging networks such as peer-to-peer, sensor and
adhoc networks require the algorithms operating within
them to be totally distributed and robust against changes
in the topology. Motivated by these concerns, in this talk
I will speak about randomized gossip algorithms where nodes
make distributed decisions based on local random operations.

In the first half of the talk, I will present a simple gossip
algorithm for counting number of nodes in a network in a
totally distributed manner. This algorithm is built upon
an extremal property of exponential random variables. We will
discuss the dependence of the running time of algorithm on
the network topology. In the later half of the talk, I will
present two applications of this algorithm: (1) network scheduling
and (2) (a class of) distributed optimization.

The first half of the talk is based on a joint work with Damon
Mosk-Aoyama (appeared in PODC 2006). The talk will be informal
and I will appreciate audience participation.