University of Padova
We give an overview on both classical and recent results on two performance metrics used to evaluate a linear consensus algorithm, namely the rate of convergence of the network to its final value and the l2 norm of the discrepancy between the state and the final value. The main goal is to analyze such metrics for families of increasing graphs, showing the dependence on the number of agents in the network. We illustrate results for graphs with symmetries (Cayley graphs) as well as novel results on a class of geometric graphs. We also underline the range of theoretical tools used in the proofs, which vary from geometric characterization of the spectrum of a graph to state aggregation techniques and electrical analogy between Markov Chains and resistive networks.