Spring 2007 Seminar Series

DATE: Thursday, March 1, 2007
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the Philip M. Morse Reading Room, E40-106

SPEAKER:
Christos Papadimitriou

TITLE
Linked Decompositions of Networks and Polya Urns with Choice

ABSTRACT
We propose a novel graph decomposition that enables a scalable form of internet routing with roughly sqrt(n) memory and logarithmic delay. Subnetworks are required to be small and with small diameter, no three of them to overlap, but any two of them to do so. Our main result is that several popular models of "internet-like graphs", most importantly the preferential attachment one proposed by Albert and Barabasi, have such decompositions almost surely; experiments show that so does the real internet. Part of our analysis involves a variant of the polya urn model in which we have a choice between two or more urns; in contrast to the traditional polya urn model, this twist results in very balanced loads.

 

Joint work with Henry Lin, Christos Amanatidis, Martha Sideri, and Dick Karp.