Order-Optimal Consensus through Randomized Path Averaging

Simple item page
dc.creatorBenezit, F.
dc.creatorDimakis, A. G.
dc.creatorThiran, P.
dc.creatorVetterli, M.
dc.date2008-02-19
dc.date.accessioned2026-07-07T09:21:41Z
dc.date.available2026-07-07T09:21:41Z
dc.descriptionGossip 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.
dc.description26 pages
dc.identifierhttps://arxiv.org/abs/0802.2587
dc.identifierhttp://arxiv.org/abs/0802.2587
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/155114
dc.subjectInformation Theory
dc.subjectNetworking and Internet Architecture
dc.subjectProbability
dc.titleOrder-Optimal Consensus through Randomized Path Averaging
dc.typetext

Files

Collections

arXiv