Performance metrics in the consensus problem: a Survey *

Linear consensus is a distributed algorithm which ensures that, under certain assumptions, a set of agents reach asymptotically the same opinion over a certain variable. Moreover this occurs with only a local exchange of information, namely the information exchange takes place only between agents which are neighbors in a graph representing the system communication architecture. Several performance metrics have been proposed for the evaluation of this algorithm. Particularly interesting and challenging is to relate performance to the communication topology. Different performance metrics may yield to different answers in comparing alternative communication topologies. In this paper, we present a number of possible performance metrics. Moreover, we show how these metrics are related to the communication topology. In particular, when available, we present bounds by which it is possible to relate performance and topology for general graphs, for graphs with symmetries, called Cayley graphs, and for geometric graphs.