Fast Information Spreading in Graphs with Large Weak Conductance
Speaker: Keren Censor-Hillel , MIT
Date: November 9 2010
Time: 4:15PM to 5:15PM
Location: 32-G144
Host: Scott Aaronson, CSAIL, MIT
Contact: Be Blackburn , 3-6098, imbe@mit.edu
Relevant URL: 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.
See other events that are part of Theory Colloquium 2010/2011
See other events happening in November 2010
