Distributed consensus algorithms .

Author

Florence Benezit, Martin Vetterli

Abstract

Distributed schemes are adapted to sensor networks since they have limited connection range. Our goal is to study distributed algorithms that allow spreading global information through the network. A first important set of algorithms is average consensus algorithms. They allow the sensors to know the spatial global average of the nodes measures, so that the nodes can make local decisions according to global knowledge. Average consensus algorithms are random algorithms based on diffusion, which is a slow phenomenon, so optimizing them is crucial. We created a rigorous theoretical framework, which studies random diffusion consensus algorithms in a deterministic way. Our analysis points out the parameters to optimize and allows many accurate simulations, very useful to understand the underlying phenomena. We are currently applying our results on mobile network models. In parallel, we managed to find a distributed scheme that performs optimally in network size. Indeed, its computation cost evolves linearly with the number n of sensors and averaging n values obviously requires at least n operations. This scheme is called path averaging. It consists in generating random routes along which we average the states until convergence. We proved the convergence result on grids and regular geometric graphs. Sensor networks are often modeled as random geometric graphs, which are regular geometric graphs with high probability, when they are well connected. Finally, inspired by quantized average consensus algorithms, we created a distributed voter algorithm. Every node initially votes for A or B, and our algorithm is able to tell the winning vote whenever the sensors have at least 2 memory bits. The figure shows snapshots of the evolution of the algorithm. First figure shows the initial votes: red or blue. Green nodes think there was the same number of red and blue nodes at the beginning. In the last figure, the algorithm has converged.

 

Voter algorithm example.

Collaborations

Martin Vetterli, Patrick Thiran.

Project Period, Funding Sources

November 2005- Ongoing,MICS.

Major Publications

[1]Which Distributed Averaging Algorithm Should I Choose for my Sensor Network?, Patrick Denantes, Florence Benezit, Patrick Thiran, Martin Vetterli, Infocom 2008.
[2]Order-Optimal Consensus through Randomized Path Averaging F. Benezit, A. G. Dimakis, P. Thiran and M. Vetterli. Allerton 2007.