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]