Publication

Order-Optimal Consensus Through Randomized Path Averaging

Abstract

Gossip 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.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.