How to Gossip


January 4, 2013


Bernard Haeupler




Gossip algorithms have recently gained attention as a powerful approach for achieving robust and message efficient multicast communication. This talk presents several ideas to improve the efficiency and applicability of these algorithms.

In particular, we provide the first gossip protocol whose efficiency does not rely on expansion properties of the network but which instead performs well on any topology. We also give a novel analysis that shows that a wide variety of natural gossip processes very robustly achieve the same (or even better efficiency) without using any randomization. The existence of such protocols is somewhat surprising because conventional wisdom suggested that both robustness and the efficient information dispersion of gossip protocols stem from their use of randomness.

We also show how combining gossip protocols with network coding can drastically improve the throughput in settings where the amount of data to be multicast is much larger than what can be transmitted in one round. While the idea of using network coded gossip is not new analyzing its performance turned out to be very challenging even in the simplest setting. We introduce projection analysis, as a very simple and powerful technique for providing sharp convergence times in all settings considered in the literature. Beyond this we demonstrate how the projection analysis directly extends to highly dynamic networks.


Bernard Haeupler

Bernhard Haeupler is a Ph.D. candidate in the Department of Computer Science at MIT. Before starting at MIT as an Akamai Presidential Fellow and receiving a M.S. degree in Computer Science in 2010 he studied at the Technical University Munich where he received M.S. degrees in Mathematics and Applied Mathematics. He also spend a year at Princeton University as a visiting graduate student.

His research interests include theoretical computer science, the design and analysis of randomized and combinatorial algorithms, network communications, information theory and distributed computing. His works received the best student paper awards at STOC’11 and SODA’13.