Order-Optimal Consensus through Randomized Path Averaging
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust message-passing schemes 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 as slowly as flooding ($O(n^2)$ messages).
A recently proposed algorithm called geographic gossip improves gossip efficiency by a $\sqrt{n}$ factor, by exploiting geographic information to enable multi-hop long distance communications. In this paper we prove that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional $\sqrt{n}$ factor and is order optimal ($O(n)$ messages) for grids and random geometric graphs.
We develop a general technique (travel agency method) based on Markov chain mixing time inequalities, which can give bounds on the performance of randomized message-passing algorithms operating over various graph topologies.
26 pages
26 pages