Agreement, consensus, rendez-vous: a review of some open problem


Il Prof. Fabio Fagnani, del Politecnico di Torino, terra' mercoledì 20 maggio alle ore 16:15 in aula 1AD/50 un seminario dal titolo "Agreement, consensus, rendez-vous: a review of some open problem".

The simplest instance of the consensus problem can be formulated as follows. Suppose we have a directed graph G with set of nodes V = {1, ... , N } and a measure x_i for every node i ∈ V. The (average) consensus problem consists in computing the arithmetic mean of the x_i's 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 (distributed estimation 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 spite of the enormous amount of literature on the subject there are still quite basic open questions not yet answered. One big issue on which this talk will focus is on measuring the performance of such an algorithm. As we will see, this is related to the type of application we have in mind and it becomes a particularly subtle question for randomized algorithms.

Rif. int. P. Dai Pra