PaperlayerView exact revision on arXiv

Source-linked AI summary

Consensus Computation in Unreliable Networks: A System Theoretic Approach

Fabio Pasqualetti, Antonio Bicchi, Francesco Bullo

arXiv:1007.2738v4math.OCeess.SY

TL;DR

The paper asks how linear consensus networks can compute trustworthy values despite misbehaving agents. It models misbehavior as unknown inputs and applies system-theoretic detection and identification analysis, obtaining connectivity bounds and detection procedures. The main scope boundary is that local identification is sensitive to perturbations and network clustering requires further study.

  • Problem

    Trustworthy computation in linear consensus is threatened by misbehaving agents, motivating detection and identification for applications including motion coordination, clock synchronization, and cooperative estimation.

  • Method

    The paper models misbehavior as unknown inputs, distinguishes faulty and Byzantine agents, and applies unknown-input observers and system-theoretic analysis to characterize attacks and design detection algorithms.

  • Results

    2k + 1 connectivity is required for k Byzantine agents and k + 1 connectivity for k faulty agents to be generically detectable and identifiable by every well-behaving agent.

  • Takeaways & Limitations

    The results characterize graph-connectivity requirements for resilience and provide exact, approximate, and local procedures for detecting and identifying misbehaving agents.

  • Takeaways & Limitations

    Local identification is affected by any positive perturbation over time, and effective clustering of large networks requires additional research.

Abstract

from arXiv · show

This work 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.

I. INTRODUCTION

The paper frames trustworthy linear consensus as a distributed-computation problem complicated by misbehaving agents, and recasts detection and identification in system-theoretic terms. It distinguishes faulty and Byzantine behavior while deriving connectivity bounds and algorithmic procedures.

  • Linear consensus lets agents agree on quantities such as workload, clock speed, velocity, rendezvous points, or formation patterns.
  • Misbehaving agents arise from random non-colluding faults or coordinated Byzantine behavior intended to disrupt network functions.Faulty agents ignore network structure and other faults; Byzantine agents may know the network and collude.
  • The paper recasts unreliable linear consensus as a system-theoretic problem and characterizes policies that make misbehaving agents undetectable or unidentifiable.
  • The paper combines exact identification with approximate, lower-complexity procedures and analyzes detection complexity and consensus-network resilience.The paper also organizes numerical studies and a conclusion around these analyses.
  • 2k + 1 connectivity permits identification of k Byzantine agents, whereas identification is impossible at 2k connectivity or less.
  • k + 1 connectivity permits identification of k faulty agents, whereas identification is impossible at k connectivity or less.

II. NOTATION AND PRELIMINARY CONCEPTS

This section introduces the linear-system notation and connects fault detection and isolation to unknown inputs, residual generators, and invariant-subspace solvability conditions.

  • The system notation uses matrices A ∈ R^n×n, B ∈ R^n×m, and C ∈ R^p×n for a linear discrete-time system.
  • Controlled and conditioned invariant subspaces describe state trajectories invisible at the output and support system-theoretic fault analysis.
  • Fault detection models each failure as an unknown, unmeasurable input added to the nominal system.
  • A residual generator processes observables to produce residuals that identify whether a particular failure input becomes nonzero.
  • Under the stated solvability condition, the filter can be designed as a dead-beat device with finite convergence time.

III. LINEAR CONSENSUS IN THE PRESENCE OF MISBEHAVING AGENTS

The paper models misbehavior as exogenous inputs to linear consensus dynamics and uses matrix structure to analyze consensus disruption and steady-state effects. A single misbehaving agent can steer the final consensus value under the presented construction.

  • A linear iteration updates each agent using a matrix whose nonzero entries follow the directed communication graph.
  • For a primitive row-stochastic matrix, the consensus system asymptotically makes all agent states coincide.
  • Misbehaving agents are modeled by adding exogenous inputs, yielding x(t + 1) = Ax(t) + u(t).
  • An agent is misbehaving when its associated input is nonzero at some time.
  • The misbehaving-agent set K is represented by input columns BK selected from canonical basis vectors.
  • A single misbehaving agent can prevent the network from reaching consensus by choosing ui(t) = −Aix(t) + c.
  • The well-behaving subsystem uses Q for internal interactions and R for connections with the misbehaving node; proper submatrices of a consensus matrix are Schur stable.
  • A single misbehaving agent can steer the network to any consensus value by choosing the constant c.

IV. DETECTION AND IDENTIFICATION OF MISBEHAVING AGENTS

The paper frames detection and identification of misbehaving agents as unknown-input system problems, characterizing when attacks remain hidden and deriving connectivity-based resilience bounds. It distinguishes undetectability from unidentifiability and treats malicious and faulty behaviors separately.

  • Problem formulation: Detection asks whether misbehavior is present, whereas identification asks which agent or subset caused the observed behavior.An input is unidentifiable when its output can be matched by a different misbehaving set; undetectability is the special case where the alternative input is zero.
  • Problem formulation: Undetectable inputs are also unidentifiable, but unidentifiable inputs need not be undetectable.The distinction separates attacks indistinguishable from normal operation from attacks confusable with another misbehaving set.
  • Malicious behaviors: A k-connected network can contain undetectable inputs from a specific set of k misbehaving agents.The construction uses a vertex cut and nontrivial zero dynamics visible from a particular observing node.
  • Malicious behaviors: Every input is identifiable from node j exactly when the system augmented with every alternative misbehaving set has no zero dynamics.If up to k agents may misbehave, correct identification requires this condition for every set of 2k inputs.
  • Malicious behaviors: In a k-connected network, at most k−1 misbehaving agents can be detected and at most ⌊(k−1)/2⌋ can be identified by every agent.These are worst-case bounds for malicious behaviors and provide an alternative proof of established resilience bounds.
  • Faulty behaviors: For faulty agents, every input can be detectable, but a specific set of k faulty agents has no identifiable input.Faulty agents inject identifiable inputs by definition, yet a vertex cut can make their behavior indistinguishable from another set regardless of the input function.

V. EFFECTS OF UNIDENTIFIED MISBEHAVING AGENTS

The section characterizes when misbehaving agents can remain unidentified and how their inputs affect consensus, emphasizing left-invertibility and zero-dynamics stability. It also gives conditions under which attacks are detectable or can alter the final consensus value.

  • State observation: For row-stochastic irreducible networks, every node can detect the network state asymptotically, and each single-node input channel is stabilizable.These properties support local observer or controller construction using information from out-neighbors.
  • Undetectable attacks: Changing misbehaving agents’ initial values is undetectable when the modified state remains valid, producing a final consensus-state effect of 1πB_Kc.The effect is a constant shift determined by the altered initial state and the limiting consensus projection.
  • Undetectable attacks: Exponentially decaying inputs can alter the final consensus value without detection exactly when they follow input-zero directions under exponentially stable zero dynamics.If an admissible state region is known, the effect can be tightly bounded and states outside the region can be detected.
  • Zero dynamics: A consensus system’s zero dynamics need not be stable or left-invertible; examples include unstable zeros and invisible nonzero inputs.One example has invariant zeros {0, +2, −2}; another is not left-invertible because inputs satisfying u1 = −u2 are invisible to the observer.
  • Left-invertibility: A single intruder is left-invertible from any observing node, so distinct inputs produce distinct outputs when the initial state is known.This follows from irreducibility and the existence of a nonzero path between intruder and observer.
  • Zero-dynamics stability: Zero dynamics are exponentially stable when the misbehaving set and observer neighborhood satisfy specified separation conditions, or when all misbehaving agents lie in the observer neighborhood.The conditions are expressed through separation between K, Nj, and the remaining nodes, together with left-invertibility where required.
  • Undetectable attacks: When zero dynamics have unstable zeros, intruders may inject non-vanishing unidentified inputs, while admissible-state-region detection can still detect inputs along unstable zero directions.The section explicitly limits this observation to a detection procedure based on an admissible region.

VI. GENERIC DETECTION AND IDENTIFICATION OF MISBEHAVING AGENTS

This section uses structured-system genericity to relate network connectivity to the absence of zero dynamics. It then derives generic detection and identification guarantees for malicious and faulty agents.

  • Structured systems: Structured systems represent uncertain numerical entries as fixed zeros or indeterminate parameters, with realizations obtained by assigning values to those parameters.Connectivity is defined from the graph of nonzero parameters, and generic rank is the maximum rank over realizations.
  • Generic zero dynamics: If a k-connected structured system has generic input rank below k, almost every consensus realization has no zero dynamics.The result transfers from generic realizations in the full parameter space to the feasible set of consensus matrices.
  • Generic zero dynamics: A constructive transformation using a positive Perron-Frobenius eigenvector produces consensus realizations that preserve the absence of zero dynamics.Diagonal scaling and normalization convert a nonnegative irreducible system into a consensus matrix while retaining the relevant system property.
  • Detection and identification guarantees: Generically, up to ⌊(k−1)/2⌋ malicious agents and k−1 faulty agents are identifiable by every well-behaving agent, while up to k−1 misbehaving agents are detectable.The section next introduces three algorithms for detecting and identifying misbehaving agents.

VII. INTRUSION DETECTION ALGORITHMS

The paper presents three decentralized algorithms for detecting and identifying misbehaving agents, ranging from globally informed complete identification to locally informed identification in weakly coupled networks.

  • Three decentralized algorithms address misbehavior detection and identification; the first two require complete network knowledge, whereas the third uses partial local knowledge.The first two use local measurements but require global consensus-network knowledge; the third requires only a neighborhood of the consensus graph.
  • Detection filter: The detection filter asymptotically estimates the network state independently of misbehaving-agent behavior when all misbehaving agents are among the observer’s modeled neighbors.Its residual remains nonzero only when the misbehaving input is nonzero in the limit.
  • Complete detection and identification: Complete Identification generically detects and identifies every misbehaving agent in finite time when connectivity is k+1 for faulty agents or 2k+1 for malicious agents.The observer must know A and an upper bound k on the number of misbehaving agents.
  • Complete detection and identification: Complete identification designs residual generators for every candidate set of k+1 misbehaving agents and identifies agents by testing whether corresponding residuals vanish or remain nonzero.Dead-beat filters make detection and identification finite-time and independent of the misbehaving input.
  • Complete detection and identification: The complete procedure can become computationally inapplicable as network size grows because each agent repeatedly updates many residual filters.Its strong assumptions include full graph-topology knowledge and a filter count proportional to the network size.
  • Local detection and identification: Local identification decomposes the consensus matrix into weakly coupled blocks and designs residual generators using only the observer’s block topology.For block h, faulty agents are identifiable when their inputs lie within a range bounded below by εαu_max and above by u_max.
  • Local detection and identification: Local identification depends critically on coupling magnitude: any positive ε eventually makes perturbation effects relevant and can prevent correct identification.Thus, the method’s local guarantees apply over a finite-time regime controlled by ε and input magnitude.

A. Complete detection and identification

The complete procedure uses residual generators to test candidate misbehaving sets from a globally known network model. In the example, faulty nodes are isolated, while malicious behavior reduces the tolerable number of agents.

  • A 3-connected example allows every well-behaving node to detect and identify up to 2 faulty agents.For any three-agent candidate set, the relevant system is left-invertible; for any two-agent set, it has no invariant zeros.
  • Residuals associated with faulty agents 3 and 7 remain nonzero, while the residual for candidate agent 4 is zero, so agent 1 identifies 3 and 7.The residual for agent 4 is zero independently of the network’s initial condition.
  • If misbehaving nodes are malicious, the example tolerates no more than 1 misbehaving node.Two alternative misbehaving sets can produce exactly the same output dynamics for agent 1 and are therefore indistinguishable.

B. Local detection and identification

The local procedure exploits weak interconnections and clustered topology to identify nearby misbehaving agents using local information, but its success depends on sufficiently small coupling and sufficiently large deviations.

  • The local procedure can identify a misbehaving agent after 2 time steps in the illustrated residual-generator example.The example considers inputs from misbehaving agents 2 and 7 and observes residuals at agent 3.
  • For sufficiently small ε, local detection and identification is possible in clustered networks with small inter-area edge weights.The method can promptly identify misbehaving agents within the same group and help restore network functionality.
  • The approximation procedure becomes more convenient for larger consensus networks with weakly interconnected clusters.Such clustering may permit simpler and more efficient protocols within each cluster.
  • In a network partitioned into 3 areas, each agent uses only its subnetwork topology to identify neighboring misbehaving agents.The figure compares the smallest misbehaving-agent residual with the largest well-behaving-agent residual as ε varies.

IX. CONCLUSION

The paper frames reliable computation with misbehaving nodes as a system-theoretic fault-detection problem and characterizes resilience through graph connectivity. It also identifies open issues involving attack gains, protocol dependence, and clustering.

  • Linear consensus networks are resilient to k concurrent faults when connectivity is k+1 for faulty agents and 2k+1 for Byzantine failures.The conclusion states these bounds as generic detection-and-identification conditions.
  • For faulty agents, good performance can remain possible without complete network-topology knowledge and under memory or computation constraints.This contrasts with the stronger requirements of the complete identification procedure.
  • Further work should characterize gains from misbehaving inputs to observations, study specific consensus protocols, and address clustering large networks into smaller parts.The paper notes that some undetectable behaviors may be infeasible depending on the gain magnitude.
Loading 1007.2738v4…