000134051 001__ 134051
000134051 005__ 20190316234514.0
000134051 037__ $$aCONF
000134051 245__ $$aGossip along the way: order-optimal consensus through randomized path averaging
000134051 260__ $$c2007
000134051 269__ $$a2007
000134051 336__ $$aConference Papers
000134051 520__ $$aGossip 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 / \log n}$ factor for random geometric graphs, by exploiting geographic information of node locations. In this paper we prove that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional $\sqrt{n / \log 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.
000134051 700__ $$0240372$$aBenezit, Florence$$g166121
000134051 700__ $$aDimakis, Alexandros
000134051 700__ $$0240373$$aThiran, Patrick$$g103925
000134051 700__ $$0240184$$aVetterli, Martin$$g107537
000134051 7112_ $$aForty-Fifth Annual Allerton Conference on Communication, Control, and Computing$$cUniversity of Illinois at Urbana-Champaign$$dSeptember 26-28, 2007
000134051 773__ $$tAllerton
000134051 8564_ $$zURL
000134051 8564_ $$s346014$$uhttps://infoscience.epfl.ch/record/134051/files/Allerton_final_gossip-4.pdf$$zn/a
000134051 909C0 $$0252056$$pLCAV$$xU10434
000134051 909C0 $$0252614$$pLCA$$xUS00024
000134051 909C0 $$0252454$$pLCA3$$xU10431
000134051 909CO $$ooai:infoscience.tind.io:134051$$pconf$$pIC$$qGLOBAL_SET
000134051 937__ $$aLCAV-CONF-2009-004
000134051 973__ $$aEPFL$$rNON-REVIEWED$$sPUBLISHED
000134051 980__ $$aCONF