Multi-agent systems. Accuracy guarantees for a class of randomized averaging algorithms

Julien M. Hendrickx

ICTEAM Institute, Université catholique de Louvain, Belgium

Wednesday 10th May 2017

14:15:00

Multi-agent systems. Accuracy guarantees for a class of randomized averaging algorithms

We consider a class of algorithms meant for averaging data in a decentralized way, but where the value computed might differ from the real average due to asymmetric or asynchronous communications and lost messages. We provide a new general upper bound on the mean difference between the value computed and the initial average. We particularize our results to various algorithms in the literature (and their generalization), obtaining bounds that match or outperform the previously available ones, and establishing the accuracy of several methods for which the question was open. We also compare the robustness of these algorithms with that of the push-sum method, which is specifically tailored for directed asynchronous communications. Our results are based on a novel approach apparently unrelated to the convergence properties of the systems, and lead to bounds depending on local parameters easily controlled by the designer. Contatto: domenico.brunetto@polimi.it