[Colloquium] David Kempe, Cornell University, Monday, April 28, 2003

[Margery Ishmael]

--------------------------------------------------------------------------

DEPARTMENT OF COMPUTER SCIENCE - TALK

Monday, April 28, 2003 at 2:30 pm in Ryerson 251

---------------------------------------------------------------------------

Speaker: David Kempe
From: Cornell University
url: http://www.cs.cornell.edu/kempe/

Title: "Gossip and Information Flow in Networks"

Abstract:
Networks are becoming increasingly prominent as a framework for
understanding designed or natural phenomena, ranging from
decentralized computer systems to social interaction patterns. They
serve as a means to facilitate decentralized computation and the
dissemination of information. Designing and analyzing their function
therefore requires a theory of information flow in networks, building
on an understanding of their structure. The goal of such a theory is
to help in developing algorithms for core questions, including: How to
find a piece of information? How to spread information? How to perform
shared computations?

In this talk, we present a decentralized randomized communication
scheme called "Spatial Gossip", a scheme with good local and global
information dissemination guarantees. We show how Spatial Gossip can
be used to design simple protocols for the "Resource Location
Problem", in which the nodes of a network are trying to locate the
closest copy of a resource (product, machine time, memory, ...).
Alternately, we may view gossip not only as a design principle, but as
an observable phenomenon, for instance in social networks.
The communication mechanism is not under the control of a protocol
designer; the task of an algorithm is then to judiciously choose nodes
at which to "seed" the communication. In this talk, we present an
algorithm that can be shown to select approximately optimal seed node
sets.

Along the way, we touch on several other issues, such as how to add
the notion of time to graphs in order to reason about information
flow, and how the choice of a communication mechanism between nodes
affects their ability to perform distributed computations.

*The talk will be followed by refreshments in Ryerson 255*

Host: Eric Vigoda


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margery Ishmael
Secretary to the Chairman, Department of Computer Science
The University of Chicago
1100 E. 58th Street, Chicago, IL. 60637-1581
tel. 773.834.8977 fax. 773.702.8487
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-