How to Gossip

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.