Bénézit, FlorenceDimakis, Alexandros G.Thiran, PatrickVetterli, Martin2010-10-142010-10-142010-10-14201010.1109/TIT.2010.2060050https://infoscience.epfl.ch/handle/20.500.14299/55504WOS:000283260900025Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust mes- sage-passing schemes for distributed information processing over networks. However, for many topologies that are realistic for wire- less 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 n^1/2 factor, by exploiting geographic information to enable multihop long-distance communications. This paper proves that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional n^1/2 factor, and is order optimal (O(n) messages) for grids and random geometric graphs with high prob- ability. 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 algo- rithms operating over various graph topologies.Average ConsensusDistributed AlgorithmsGossip AlgorithmsSensor Networkstext::journal::journal article::research article