Technion
 
         Computer Science Colloquium
 
Time+Place : Sunday 08/01/2012 14:30 room 337-8 Taub  Bld.
Speaker    : Keren Censor-Hillel
Affiliation: CSAIL, M I T
Host       : Hagit Attiya
Title      : Fast Distributed Computing Despite Poor Connectivity
 
Abstract   :
 
Distributed computing is becoming the predominant form of computation and
communication world round, from cell phones to multi-core machines. As these
systems grow in size, they become distributed, attempting to maintain global
computation and coordination despite ever weaker local guarantees. This talk
will address distributed computing in the Gossip model, where each node in a
network is restricted to contacting only a single neighbor in each round of
communication. I will show that any algorithm that requires T rounds in the
Local model (where each node contacts all neighbors in each round) can be
simulated in O(T+polylog(n)) rounds in the GOSSIP model, implying that these
two models of distributed computation are essentially equivalent.
 
The main result that leads to this simulation is an algorithm for the Gossip
model in which each node exchanges information (perhaps indirectly) with
each of its neighbors within a polylogarithmic number of rounds. This holds
for every graph, despite the possibility of large degrees. A key ingredient
in this algorithm is a recursive decomposition of graphs into clusters of
sufficiently large conductance, allowing fast exchange of information
between nodes inside clusters and between clusters. To convert the
multiplicative polylogarithmic overhead for each simulated round into the
additive overhead in the final simulation result, I show connections between
sparse graph spanners and algorithms in the Gossip model. This allows to
simulate known constructions of nearly-additive sparse spanners, which can
be used for even more efficient communication.
 
Short Bio:
 
Keren Censor-Hillel is currently the Simons Postdoctoral Fellow at the
Theory of Computation Group of the Computer Science and Artificial
Intelligence Laboratory (CSAIL) at MIT. She received her PhD from the
Department of Computer Science at the Technion in 2010, under the
supervision of Prof. Hagit Attiya. Her research interests are in theory of
computation, and focus on distributed computing. Keren is also a Rothschild
Fellow, and received an Adams Fellowship from the Israel Academy of Sciences
and Humanities, a Google Anita Borg Memorial Scholarship, the Best Student
Paper Award and Best Student Presentation Award in PODC 2009, as well as
several teaching awards.
 
----------------------------------------------------------
Visit our home page-   <http://www.cs.technion.ac.il/~colloq>
 
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Hadas Heier   <heier@cs.technion.ac.il>