General resilient consensus algorithms
Guilherme Ramos, Daniel Silvestre, Carlos Silvestre
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 O(C), then the proposed correction algorithms have polynomial-time complexity O(Cnf) (and O(Cn) 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.