The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science
 
                    Foundations of Computer Science Seminar
 
                  Room 141 (faculty lounge), Ziskind Building
                          on Tuesday, January 3, 2012
                                    at 11:00
 
                         Note the unusual day and time
 
                              Keren Censor-Hillel
                                   CSAIL, MIT
 
                                 will speak on
 
                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.
 
---------------------------------------------------------
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Yaeli Malka   <yaeli.malka@weizmann.ac.il>