Speaker: Keren Censor-Hillel, MIT Computer Science and
Artificial Intelligence Laboratory (CSAIL), Theory of Distributed Systems Group

Title: Fast Information Spreading in Graphs with Large
Weak Conductance

Abstract:

Gathering data from nodes in a network is at the heart of
many distributed applications, most notably, while performing a global task. We
consider information spreading among n nodes of a network, where each node v
has a message m(v) which must be received by all other nodes. The time required
for information spreading has been previously upper-bounded with an inverse
relationship to the conductance of the underlying communication graph. This
implies high running times for graphs with small conductance.

In this talk I will describe an information spreading
algorithm which overcomes communication bottlenecks and thus achieves fast
information spreading for a wide class of graphs, despite their small
conductance. As a key tool in our study we use the recently defined concept of
weak conductance, a generalization of classic graph conductance which measures
how well-connected the components of a graph are. Our hybrid algorithm, which
alternates between random and deterministic communication phases, exploits the connectivity
within components by first applying partial information spreading, after which
messages are sent across bottlenecks, thus spreading further throughout the
network. This yields substantial improvements over the best known running times
of algorithms for information spreading on any graph that has a large weak
conductance, from polynomial to polylogarithmic number of rounds.

[Joint work with Hadas Shachnai, to appear in SODA 2011]