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:
V. D. Blondel, J. M. Hendrickx, A. Olshevsky, and J. N. Tsitsiklis,
"Convergence in Multiagent Coordination, Consensus, and Flocking," in Proceedings of the
Joint 44th IEEE Conference on Decision
and Control and European Control Conference (CDC-ECC'05), Seville, Spain, December 2005. [corrected version]
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.
A. Olshevsky and J. N. Tsitsiklis,
"Convergence Speed in Distributed Consensus and Averaging",
SIAM Journal on Control and Optimization,
Vol. 48, No. 1, 2009, pp. 33-55.
A slightly augmented version was reprinted in:
A. Olshevsky and J. N. Tsitsiklis, "Convergence Speed in Distributed Consensus and Averaging,'' SIAM Review,
Vol. 53, No. 4, 2011, pp. 747-772.