Optimal strategies in the average consensus problem

Let a set of communicating agents compute the average of their initial positions, where every agent is restricted to communicate to a given small number of other agents (average consensus problem). We prove that the optimal topology of communication is given by a de Bruijn graph. Consensus is then reached in finitely many steps. This solution is valid when the number of agents is an exact power of the out-degree of the communication graph. We introduce an algebraic tool, the shifted Kronecker product, and a more general family of strategies, also based on a de Bruijn communication graph. Those strategies are compared to Cayley strategies in terms of the speed of convergence. We also show that quantized communication between the agents still allows finite convergence, to a consensus, which is not in general the average of the initial positions. (C) 2009 Elsevier B.V. All rights reserved.