Consensus Computation in Unreliable Networks: A System Theoretic Approach

By Fabio Pasqualetti, Antonio Bicchi, Francesco Bullo. IEEE Transactions on Automatic Control, 2010

526 citations recorded by the source corpus.

This paper addresses the problem of ensuring trustworthy computation in a linear consensus network. A solution to this problem is relevant for several tasks in multi-agent systems including motion coordination, clock synchronization, and cooperative estimation. In a linear consensus network, we allow for the presence of misbehaving agents, whose behavior deviate from the nominal consensus evolution. We model misbehaviors as unknown and unmeasurable inputs affecting the network, and we cast the misbehavior detection and identification problem into an unknown-input system theoretic framework. We consider two extreme cases of misbehaving agents, namely faulty (non-colluding) and malicious (Byzantine) agents. First, we characterize the set of inputs that allow misbehaving agents to affect the consensus network while remaining undetected and/or unidentified from certain observing agents. Second, we provide worst-case bounds for the number of concurrent faulty or malicious agents that can be detected and identified. Precisely, the consensus network needs to be 2k+1 (resp. k+1) connected for k malicious (resp. faulty) agents to be generically detectable and identifiable by every well behaving agent. Third, we quantify the effect of undetectable inputs on the final consensus value. Fourth, we design three algorithms to detect and identify misbehaving agents. The first and the second algorithm apply fault detection techniques, and affords complete detection and identification if global knowledge of the network is available to each agent, at a high computational cost. The third algorithm is designed to exploit the presence in the network of weakly interconnected subparts, and provides local detection and identification of misbehaving agents whose behavior deviates more than a threshold, which is quantified in terms of the interconnection structure.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/26f9b854f646d126010ec76594783fcf56cc7745

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

On the Performance Analysis of Resilient Networked Control Systems Under Replay Attacks (2013, background): “In the context of multi-agent systems, the papers of [25], [28] determine conditions under which consensus multi-agent systems can detect misbehaving agents.”
Resilient Distributed Parameter Estimation With Heterogeneous Data (2018, methodology): “must additionally filter and process the information they receive from neighbors [10], [11], [18], [19], [21], [22].”
A survey of distributed optimization (2019, background): “Although distributed resilient consensus has been well studied (see, e.g., LeBlanc, Zhang, Kout-soukos, & Sundaram, 2013; Pasqualetti, Bicchi, & Bullo, 2012; Sundaram & Hadjicostis, 2011 ), distributed resilient optimization with adversarial agents is less studied and there are only a limited…”
On the Performance Degradation of Cyber-Physical Systems Under Stealthy Integrity Attacks (2016, background): “This is in sharp contrast with the deterministic case discussed in [6]–[9]where the probability of alarm is either 0 or 1.”
Adaptive Fault-Tolerant Tracking Control for Linear and Lipschitz Nonlinear Multi-Agent Systems (2015, background): “In [23], the problem of distributed reliable computation in networks with misbehaving nodes is discussed, and the relationship with the fault detection and isolation for linear systems is established.”
Resilient Asymptotic Consensus in Robust Networks (2013, background): “The following definitions generalize this notion of redundancy to the entire network.”
Recent Advances in Consensus of Multi-Agent Systems: A Brief Survey (2017, background): “During the past decades, numerous results on FDI and FTC have been achieved [58], [126].”
Privacy preserving average consensus (2014, background): “This may turn out to be desirable for some applications, such as malicious intrusion detection and identification [8] and finite-step consensus [9], [10].”
Attack Detection and Identification in Cyber-Physical Systems (2013, background): “Finally, with respect to [20] and our earlier work [21], we consider continuous-time descriptor systems, and we include parameters constraints.”
Control-Theoretic Methods for Cyberphysical Security: Geometric Principles for Optimal Cross-Layer Resilient Control Systems (2015, methodology): “Because there exists a linking of size two from any two attack nodes to the output vertices, every set of two attackers is detectable, and every set of one attacker is identifiable (see the section “Fundamental Attack Detection and Identification Limitations” and [34], [29], [28]).”
Secure State Estimation and Control of Cyber-Physical Systems: A Survey (2021, background): “For example, it is disclosed in [70] that κ Byzantine agents can be detected and identiﬁed by each agent in normal behavior when the linear consensus network is (2 κ + 1)-connected.”
A systems and control perspective of CPS security (2019, background): “The same ideas have been used in multi-agent systems in the presence of misbehaving nodes [143], [173], [174].”
Physical Authentication of Control Systems: Designing Watermarked Control Inputs to Detect Counterfeit Sensor Outputs (2015, background): “In scenarios [6, 7, 8, 9, 10], the attacker can either arbitrarily perturb the system along certain directions without being detected by any filter or cannot induce any perturbation, without incurring detection.”