The average consensus problem asks a collection of graph vertices on a connected graph that is undirected
to reach agreement using only local communication. If graph
vertex 
starts with a scalar value 
, the required common value is the arithmetic
mean
 |
(1)
|
A standard linear formulation collects the values in a vector 
and uses a matrix 
whose off-diagonal entries are zero between nonadjacent graph vertices, giving the iteration
 |
(2)
|
The iteration reaches average consensus for every initial vector iff
 |  |  |
(3)
|
 |  |  |
(4)
|
 |  |  |
(5)
|
where 
is the all-ones vector and 
is the spectral radius.
The first two conditions preserve the sum and fix constant
vectors, while the last condition contracts all other
components. The spectral radius in the final condition
is the asymptotic convergence factor (Xiao and Boyd 2004). If 
has nonnegative entries, the first two conditions state that
it is a doubly stochastic matrix.
Choosing the weights to minimize the convergence factor gives the fastest distributed linear averaging problem. With symmetric weights, this optimization can be expressed as a semidefinite programming problem (Xiao and Boyd 2004). A gossip algorithm instead performs randomized local pairwise updates to solve the average consensus problem (Boyd et al. 2006).
