General resilient consensus algorithms

Abstract

We address the problem of reaching resilient consensus among a set of agents in the presence of faulty nodes (attacked or noisy). We propose general algorithms, i.e., receiving as inputs a consensus algorithm, the network topology, the initial states, and the number of maximum allowed faulty nodes. These algorithms let the agents identify the set of attacked nodes and correct the consensus value by ignoring the faulty nodes. We prove that if the number of faulty nodes is below the maximum allowed, then each non-faulty agent detects them without false positives. If the inputted discrete-time consensus algorithm has polynomial-time complexity $\mathcal{O}\left(C\right)$, then the proposed correction algorithms have polynomial-time complexity $\mathcal{O}\left(C{n}^f\right)$ (and $\mathcal{O}\left(Cn\right)$ for the detection of faulty nodes), for n nodes, and f maximum allowed faulty nodes. Finally, we show the effectiveness of the algorithms through simulation, pointing out attacking scenarios dealt with our methods, where the state-of-the-art underperformed.

Keywords:

• Consensus
• resilient consensus
• multi-agent systems
• cyber-security

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was partially supported by project MYRG2018-00198-FST of the University of Macau (Universidade de Macau), and by the Portuguese Fundação para a Ciência e a Tecnologia (FCT) through Institute for Systems and Robotics (ISR), under Laboratory for Robotics and Engineering Systems (LARSyS) project UIDB/EEA/50009/2020. G. Ramos acknowledges the support of Institute for Systems and Robotics, Instituto Superior Técnico (Portugal), through scholarship BL229/2018_IST-ID, and he further acknowledges Instituto de Telecomunicaçães (Portugal), through scholarship UID/EEA/50008/2017. Also, this work was supported in part by FCT project POCI-01-0145-FEDER-031411-HARMONY.