Gossip Along the Way: Order-Optimal Consensus through Randomized Path Averaging
Florence Benezit, Georgios Alexandros Dimakis, Patrick Thiran and Martin Vetterli
National Science Foundation CCF-0635114
Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust algorithms for distributed information processing over networks. However, for many topologies that are realistic for wireless ad hoc and sensor networks (like grids and random geometric graphs), the standard nearest-neighbor gossip converges very slowly. A recently proposed algorithm called geographic gossip improves gossip efficiency by a sqrt(n) factor for random geometric graphs, by exploiting geographic information of node locations. In this paper we prove that a variation of geographic gossip averages along routed paths, improves efficiency by an additional sqrt(n) factor, and is order optimal for grids and random geometric graphs. Our analysis provides some general techniques and can be used to provide bounds on the performance of randomized message passing algorithms operating over various graph topologies.
- A. G. Dimakis, A. Sarwate, and M. Wainwright, "Geographic Gossip: Efficient Aggregation for Sensor Networks," IPSN, 2006.
- F. Benezit, A. G. Dimakis, P. Thiran, and M. Vetterli, "Gossip Along the Way: Order-Optimal Consensus through Randomized Path Averaging," Allerton Conference, 2007.