Randomized consensus algorithms over large scale networks

Suppose we have a directed graph G with set of nodes V = {1,...,N} and a measure x_i for every node i euro V. The average consensus problem consists in computing the average x_A= N^-1Sigma_i x_i in an iterative way, exchanging information among nodes exclusively along the available edges in G. This problem appears in a number of different contexts since the 80´s (decentralized computation, load balancing, clock syncronization) and, recently, has attracted much attention for possible applications to sensor networks (data fusion problems) and to coordinated control for mobile autonomous agents. Several algorithms for average consensus can be found in the literature: they differentiate on the basis of the amount of communication and computation they use, on their scalability with respect to the number of nodes, on their adaptability to time-varying graphs, and, finally, they can be deterministic or random. In this presentation we will focus on random algorithms: we will review some algorithms present in the literature and we will propose some new ones. We will present some performance results which will allow to make some comparison. Finally, we will establish some probabilistic concentration results which will give a stronger significance to previous results.