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>