Which Distributed Averaging Algorithm Should I Choose for my Sensor Network?

Average consensus and gossip algorithms have recently received significant attention, mainly because they constitute simple and robust algorithms for distributed information processing over networks. Inspired by heat diffusion, they compute the average of sensor networks measurements by iterating local averages until a desired level of convergence. Confronted with the diversity of these algorithms, the engineer may be puzzled in his choice for one of them. As an answer to his/her need, we develop precise mathematical metrics, easy to use in practice, to characterize the convergence speed and the cost (time, message passing, energy...) of each of the algorithms. In contrast to other works focusing on time-invariant scenarios, we evaluate these metrics for ergodic time- varying networks. Our study is based on Oseledec’s theorem, which gives an almost-sure description of the convergence speed of the algorithms of interest. We further provide upper bounds on the convergence speed. Finally, we use these tools to make some experimental observations illustrating the behavior of the convergence speed with respect to network topology and reliability in both average consensus and gossip algorithms.

Published in:
IEEE Infocom
Presented at:
IEEE INFOCOM 2008, Phoenix, AZ, 13-18 April 2008
Institute of Electrical and Electronics Engineers
Other identifiers:

 Record created 2008-04-07, last modified 2018-03-18

Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
(Not yet reviewed)