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 ather 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 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.