Order-Optimal Consensus through Randomized Path Averaging

@misc{citeulike:2404929, abstract = {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.}, author = {Benezit, F. and Dimakis, A. G. and Thiran, P. and Vetterli, M. }, citeulike-article-id = {2404929}, eprint = {0802.2587}, keywords = {algorithms, graph, topology}, month = {Feb}, posted-at = {2008-02-21 01:29:25}, priority = {2}, title = {Order-Optimal Consensus through Randomized Path Averaging}, url = {http://arxiv.org/abs/0802.2587}, year = {2008} }

TY - ELEC ID - citeulike:2404929 L3 - citeulike-article-id:2404929 TI - Order-Optimal Consensus through Randomized Path Averaging N2 - 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. KW - algorithms KW - graph KW - topology AU - Benezit, F AU - Dimakis, AG AU - Thiran, P AU - Vetterli, M PY - 2008/Feb/19/ UR - http://arxiv.org/abs/0802.2587 ER -