Robust average consensus using Total Variation Gossip Algorithm

Consider a connected network of N agents observing N arbitrary samples. We investigate distributed algorithms, also known as gossip algorithms, whose aim is to compute the sample average by means of local computations and nearby information sharing between agents. First, we analyze the convergence of some widespread gossip algorithms in the presence of misbehaving (stubborn) agents which permanently introduce some false value inside the distributed averaging process. We show that the network is driven to a state which exclusively depends on the stubborn agents. Second, we introduce a novel gossip algorithm called Total Variation Gossip Algorithm. We show that, provided that the sample vector satisfies some regularity condition, the final estimate of the network remains close to the sought consensus, and is unsensitive to large perturbations of stubborn agents. Numerical experiments complete our theoretical results.