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.