000153198 001__ 153198
000153198 005__ 20190316234908.0
000153198 0247_ $$2doi$$a10.1109/TIT.2010.2060050
000153198 022__ $$a0018-9448
000153198 02470 $$2ISI$$a000283260900025
000153198 037__ $$aARTICLE
000153198 245__ $$aOrder-Optimal Consensus Through Randomized Path Averaging
000153198 269__ $$a2010
000153198 260__ $$bInstitute of Electrical and Electronics Engineers$$c2010
000153198 336__ $$aJournal Articles
000153198 520__ $$aGossip 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.
000153198 6531_ $$aAverage Consensus
000153198 6531_ $$aDistributed Algorithms
000153198 6531_ $$aGossip Algorithms
000153198 6531_ $$aSensor Networks
000153198 700__ $$0240372$$g166121$$aBénézit, Florence
000153198 700__ $$aDimakis, Alexandros G.
000153198 700__ $$0240373$$g103925$$aThiran, Patrick
000153198 700__ $$aVetterli, Martin$$g107537$$0240184
000153198 773__ $$j56$$tIEEE Transactions on Information Theory$$k10$$q5150-5167
000153198 8564_ $$uhttps://infoscience.epfl.ch/record/153198/files/BDTV%2C%2015.2010.pdf$$zn/a$$s1761274$$yn/a
000153198 909C0 $$xUS00024$$0252614$$pLCA
000153198 909C0 $$pLCAV$$xU10434$$0252056
000153198 909C0 $$xU10431$$0252454$$pLCA3
000153198 909CO $$qGLOBAL_SET$$pIC$$particle$$ooai:infoscience.tind.io:153198
000153198 917Z8 $$x184677
000153198 917Z8 $$x184677
000153198 917Z8 $$x184677
000153198 917Z8 $$x218003
000153198 937__ $$aEPFL-ARTICLE-153198
000153198 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000153198 980__ $$aARTICLE