TDS Seminar: How Fast is Robust Gossip?
Speaker: Dan Alistarh , EPFL
Date: September 29 2010
Time: 1:00PM to 2:00PM
Location: 32-G531
Host: Nancy Lynch, MIT
Contact: Alex Cornejo, 6172531922, acornejo@csail.mit.edu
Relevant URL: http://groups.csail.mit.edu/tds/tds-seminars.html
Title: How Fast is Robust Gossip?
Abstract:
Gossip, also known as epidemic dissemination, is a popular technique for spreading information in distributed systems. This talk describes some of the trade-offs between the message complexity of gossip protocols, and their ability to tolerate node failures.
We start by presenting a new gossip protocol, TrickleGossip, which is the first to achieve sub-quadratic message complexity while tolerating adaptive failures. Second, we show a direct relation between resilience and message complexity, demonstrating that gossip protocols which tolerate a large number of adaptive failures need to use a super-linear number of messages with high probability. Finally, we will talk about some of the applications of our results to other distributed problems, and discuss some open questions.
See other events that are part of Theory of Distributed Systems 2010/2011
See other events happening in September 2010
