TV regularization for robust consensus in distributed systems.

Summary Consider a network of agents whose objective is to find a consensus on the minimizer of some unknown function. An important special case is obtained when this minimizer is the average of values locally observed by the agents. We are interested in distributed algorithms allowing to estimate the solution through exchanges between the agents, supposedly connected by a graph. The literature is rich in distributed algorithms solving such a problem. However, these algorithms are very sensitive to possible deficient behaviors of some agents (malicious agents or "stubborn" agents refusing to update their estimate). Our goal is to propose robust algorithms. We introduce a relaxation of the initial problem based on total variation. We show that the solutions of the initial problem and the relaxed problem coincide, under certain verifiable regularity conditions. We provide two distributed algorithms leading to the solution. Finally, we test the robustness of our algorithms in the presence of a stubborn agent continuously injecting an inconsistent estimate into the network: we show that, independently of the magnitude of the inconsistent estimate, the estimates are kept in a neighborhood of the desired consensus. Numerical results confirm the robustness of our algorithms in this paper.