Reaching consensus about gossip: convergence times and costs
P. Thiran (EPFL), F. Bénézit (EPFL), P. Denantes (EPFL), A. G. Dimakis (UC Berkeley), M. Vetterli (EPFL)
Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust methods for distributed information processing over networks.
However, for many topologies that are realistic for wireless adhoc and sensor networks (such as grids and random geometric graphs), the standard nearest-neighbour gossip converges slowly. In this talk, we will introduce and discuss metrics for convergence time and cost that allow us to clearly characterize the steady state regime of the convergence, not only for i.i.d. but for all stationary and ergodic time-varying networks. We will next describe a variation of geographic gossip that averages along routed paths, and which is proven to be order optimal, contrary to standard nearest-neighbour gossip.