Computer Science – Information Theory
Scientific paper
2008-02-19
Computer Science
Information Theory
26 pages
Scientific paper
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.
Benezit F.
Dimakis Alexandros G.
Thiran Patrick
Vetterli Martin
No associations
LandOfFree
Order-Optimal Consensus through Randomized Path Averaging does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Order-Optimal Consensus through Randomized Path Averaging, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Order-Optimal Consensus through Randomized Path Averaging will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-338205