Reducing Communication Overhead for Average Consensus

Average consensus is an iterative protocol where nodes in a network, each having an initial scalar value called estimate, perform a distributed algorithm to calculate the average of all estimates presented in the network by using only local communication. With every iteration, nodes receive the estimates from their neighbors, and they update their own estimate by the weighted average of the received ones. While the average consensus protocol converges asymptotically to consensus, implementing a termination algorithm is challenging when nodes are not aware of some global information (e.g. the diameter of the network or the number of nodes presented). In this report, we are interested in decreasing the rate of the messages sent in the network as the estimates are closer to consensus. We propose a totally distributed algorithm for average consensus where nodes send more messages when the nodes have large differences in their estimates, and reduce their rate of sending messages when the consensus is almost reached. The convergence of the system is guaranteed to be within a predefined margin from the true average and the communication overhead is largely reduced.Le consensus de moyenne est un protocole itératif où les nœuds d'un réseau, ayant chacun une estimation initiale, exécutent un algorithme distribué pour calculer la moyenne de ces estimations en utilisant uniquement les communication locales. A chaque itération, les nœuds échangent leurs estimations avec leurs voisins. Ces estimations seront remplacées par la moyenne pondérée de celles reçues. La convergence du consensus de moyenne est asymptotique et la mise en œuvre d'un protocole de terminaison est difficile lorsque les nœuds ne connaissent pas l'estimation global (par exemple, le diamètre du réseau ou le nombre de nœuds). Dans ce rapport, nous intéressons à la réduction du taux de messages envoyés dans le réseau quand les estimations deviennent proche du consensus. Nous présentons un algorithme de consensus de moyenne totalement distribué, où les nœuds envoient plus de messages lorsque la différence entre leurs estimations est grande et moins de messages lorsque le système est à peu prés convergeant. La convergence du système est garantie d'être proche de la vraie moyenne et le coût des communications est fortement réduit