TDS Seminar: Fast Information Spreading in Graphs with a Large Weak Conductance
Speaker: Keren Censor , MIT
Date: September 24 2010
Time: 1:00PM to 2:00PM
Location: 32-G575* note change
Host: Nancy Lynch, MIT
Contact: Alex Cornejo, acornejo@csail.mit.edu
Relevant URL: Title: Fast Information Spreading in Graphs with a 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]
See other events that are part of Theory of Distributed Systems 2010/2011
See other events happening in September 2010
