Consensus and Averaging

A number of agents exchange their values asynchronously and form weighted averages with (possibly outdated) values possessed by their neighbors. Under rather weak conditions, the agents are guaranteed to converge to a common value.

This scheme is described and analyzed in:

The main convergence result is stated as Lemma 2.1 of: A simplified version is presented in Section 7.3 of: and is then used in Section 7.6 for combining the updates of different agents interested in solving a common optimization problem.

For an overview of convergence results and some extensions, see:

Convergence rate and computation-theoretic analysis

A convergence time that increases with the square of the number of nodes can be attained even by deterministic and leaderless averaging algorithms with limited memory:

On the other hand, order of n-squared appears to be a barrier for the convergence time of iterative averaging methods. This can be made precise for a specific class of algorithms: Iterative consensus and averaging algorithms can be made to converge in polynomial time. They can run in order of n-squared time, even for the case of time-varying interconnection graphs, if the memory at each node is allowed to increase with the total number of nodes.