6th International Conference on Performance Evaluation Methodologies and Tools

Research Article

Robust Average Consensus using Total Variation Gossip Algorithm

Download515 downloads
  • @INPROCEEDINGS{10.4108/valuetools.2012.250316,
        author={Walid Ben-Ameur and Pascal Bianchi and J\^{e}r\^{e}mie Jakubowicz},
        title={Robust Average Consensus using Total Variation Gossip Algorithm},
        proceedings={6th International Conference on Performance Evaluation Methodologies and Tools},
        publisher={IEEE},
        proceedings_a={VALUETOOLS},
        year={2012},
        month={11},
        keywords={multiagent systems distributed optimization gossip algorithms stubborn agents},
        doi={10.4108/valuetools.2012.250316}
    }
    
  • Walid Ben-Ameur
    Pascal Bianchi
    Jérémie Jakubowicz
    Year: 2012
    Robust Average Consensus using Total Variation Gossip Algorithm
    VALUETOOLS
    ICST
    DOI: 10.4108/valuetools.2012.250316
Walid Ben-Ameur1, Pascal Bianchi2,*, Jérémie Jakubowicz1
  • 1: Institut TELECOM, TELECOM SudParis, UMR CNRS 5157
  • 2: Institut TELECOM, TELECOM ParisTech, CNRS/LTCI
*Contact email: pascal.bianchi@telecom-paristech.fr

Abstract

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.