Quadratic indices for the analysis of consensus algorithms

Average-consensus algorithms allow to compute the average of some agents' data in a distributed way, and they are used as a basic building block in algorithms for distributed estimation, load balancing, formation and distributed control. Traditional analysis of linear average-consensus algorithms studies, for a given communication graph, the convergence rate, given by the essential spectral radius of the transition matrix (i.e. the second largest eigenvalues' modulus). For many graph families, such analysis predicts a performance which degrades when the number of agents grows, basically because spreading information across a larger graph requires a longer time. However, if you consider other well-known quadratic performance indices (involving all the eigenvalues of the transition matrix), the scaling law with respect to the number of agents can be different. This is consistent with the fact that, in many applications, for example in estimation problems, it is natural to expect that a larger number of cooperating agents has a positive, not a negative effect on performance. In this paper, we consider two different quadratic indices, which arise naturally from some estimation and control problems in which the consensus algorithm is used. We provide analytical results on their asymptotic behavior when the communication network belongs to some families of Cayley graphs. This framework includes grids on toruses in arbitrary dimensions, which are conjectured to be a good approximation of random geometric graphs; indeed, we show simulation results supporting this conjecture.