IBM Israel Research Seminars

Of late, it has been widely observed that "epidemic gossip" is an efficient and robust mechanism for spreading information in a fault-prone distributed network. That is, if each node occasionally sends all its information to a randomly chosen node in the network, then the information is rapidly disseminated. If the network is synchronous, i.e., if bounds on network delays and processor speeds are known, then this simple epidemic strategy is fast and efficient. In this talk, however, I will focus on asynchronous networks.

First, I will attempt to provide some insight as to why gossip is more difficult in an asynchronous network by showing that an adaptive adversary can always prevent the efficient dissemination of gossip; specifically, I will demonstrate that it is impossible for asynchronous gossip to be both time and message efficient. I will then proceed to consider the case of an oblivious adversary, presenting two new gossip protocols; I will show that these new gossip protocols are competitive with the best-known synchronous gossip protocols in terms of time and message complexity.

Finally, I will discuss the connection between asynchronous gossip and the problem of fault-tolerant consensus (via the Canetti-Rabin framework), and I will show how our gossip protocols immediately lead to new randomized consensus protocols that provide an improved trade-off between time and message complexity. Of note, I will show how to construct a consensus protocol that runs in (expected) constant time and has sub-quadratic message complexity; to the best of our knowledge, this is the first asynchronous consensus protocol that achieves these bounds.

Joint work with: Chryssis Georgiou, Rachid Guerraoui, and Darek Kowalski

About the Speaker
Seth Gilbert is currently a postdoc in the Distributed Programming Laboratory (LPD) at EPFL in Switzerland. His research focuses primarily on the challenges associated with highly dynamic distributed systems, particularly wireless ad hoc networks. Prior to EPFL, Seth received his PhD from MIT in the Theory of Distributed Systems (TDS) group under Nancy Lynch. Previously, he worked at Microsoft, developing new tools to simplify the production of large-scale software. He graduated from Yale University with a degree in Electrical Engineering and Math.