2010/07/16 by Fabio Pasqualetti, Pasqualetti, Fabio, Antonio Bicchi +3 · 2 citations
Computer Science · Engineering · #Advanced Memory and Neural Computing #Distributed Control Multi-Agent Systems #Distributed systems and fault tolerance #FOS: Electrical engineering #FOS: Mathematics #Logic, Reasoning, and Knowledge #Optimization and Control (math.OC) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1007.2738
openalex publication_date 2010/07/16 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
This work addresses the problem of ensuring trustworthy computation in a\nlinear consensus network. A solution to this problem is relevant for several\ntasks in multi-agent systems including motion coordination, clock\nsynchronization, and cooperative estimation. In a linear consensus network, we\nallow for the presence of misbehaving agents, whose behavior deviate from the\nnominal consensus evolution. We model misbehaviors as unknown and unmeasurable\ninputs affecting the network, and we cast the misbehavior detection and\nidentification problem into an unknown-input system theoretic framework. We\nconsider two extreme cases of misbehaving agents, namely faulty (non-colluding)\nand malicious (Byzantine) agents. First, we characterize the set of inputs that\nallow misbehaving agents to affect the consensus network while remaining\nundetected and/or unidentified from certain observing agents. Second, we\nprovide worst-case bounds for the number of concurrent faulty or malicious\nagents that can be detected and identified. Precisely, the consensus network\nneeds to be 2k+1 (resp. k+1) connected for k malicious (resp. faulty) agents to\nbe generically detectable and identifiable by every well behaving agent. Third,\nwe quantify the effect of undetectable inputs on the final consensus value.\nFourth, we design three algorithms to detect and identify misbehaving agents.\nThe first and the second algorithm apply fault detection techniques, and\naffords complete detection and identification if global knowledge of the\nnetwork is available to each agent, at a high computational cost. The third\nalgorithm is designed to exploit the presence in the network of weakly\ninterconnected subparts, and provides local detection and identification of\nmisbehaving agents whose behavior deviates more than a threshold, which is\nquantified in terms of the interconnection structure.\n