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>