Distributed Average Consensus with Time-Varying Metropolis Weights

Unpublished manuscript, June 2006.

(Much of the material can be found in the conference papers A Space-Time Diffusion Scheme for Peer-to-Peer Least-Squares Estimation and A Scheme for Robust Distributed Sensor Fusion Based on Average Consensus.)

• avg_metropolis.pdf

Given a network of processes where each node has an initial scalar value, we consider the problem of computing their average asymptotically using a distributed, linear iterative algorithm. At each iteration, each node replaces its own value with a weighted average of its previous value and the values of its neighbors. We introduce the Metropolis weights, a simple choice for the averaging weights used in each step. We show that with these weights, the values at every node converge to the average, provided the infinitely occurring communication graphs are jointly connected.