On the Impacts of Redundancy, Diversity, and Trust in Resilient Distributed State Estimation

Aritra Mitra, Faiq Ghawash, Shreyas Sundaram, Waseem Abbas

Abstract: We address the problem of distributed state estimation of a linear dynamical process in an attack-prone environment. Recent attempts to solve this problem impose stringent redundancy requirements on the measurement and communication resources of the network. In this paper, we take a step towards alleviating such strict requirements by exploring two complementary directions: (i) making a small subset of the nodes immune to attacks, or "trusted", and (ii) incorporating diversity into the network. We define graph-theoretic constructs that formally capture the notions of redundancy, diversity, and trust. Based on these constructs, we develop a resilient estimation algorithm and demonstrate that even relatively sparse networks that either exhibit node-diversity, or contain a small subset of trusted nodes, can be just as resilient to adversarial attacks as more dense networks. Finally, given a finite budget for network design, we focus on characterizing the complexity of (i) selecting a set of trusted nodes, and (ii) allocating diversity, so as to achieve a desired level of robustness. We establish that, unfortunately, each of these problems is NP-complete.

Introduction

In distributed state estimation, a network of sensors collaborates to track the state of a dynamic system, such as a power grid or a fleet of autonomous vehicles. While distributed architectures offer scalability and robustness to random failures, they are highly vulnerable to Byzantine adversaries. These malicious actors can compromise specific nodes and inject coordinated, false data to steer the entire network toward an incorrect estimate.

Traditional mathematical guarantees for resilient estimation typically rely on high redundancy. For a network to effectively ignore $f$ malicious neighbors, it often requires a connectivity degree of at least $2f+1$. In many practical deployments, such as sparse Internet of Things (IoT) networks, achieving this level of density is economically or physically impossible. This research explores whether raw connectivity can be traded for other architectural features: device hardening (Trust) and component variety (Diversity).

Core Concepts of Resilient Estimation

The authors introduce a formal graph-theoretic framework that treats Redundancy, Diversity, and Trust as interchangeable facets of network robustness. They define a new property called $(r, \Delta(\cdot), T)$-reachability, which determines if a node can reliably "reach" the truth based on its neighborhood composition.

Figure 1: Visualizing the three pillars of network resilience: (a) Redundancy, (b) Diversity (node colors), and (c) Trust.
  • Redundancy: Relying on a large number of neighbors to outvote malicious actors.
  • Diversity: Utilizing varied hardware or software (represented as "colors"). If an attacker exploits a vulnerability specific to one sensor model, they only compromise one color. If the network has enough different types, it can triangulate the truth even if one entire type is compromised.
  • Trust: Hardening a small subset of nodes against any attack through physical security or cryptographic measures. A single trusted node can provide as much mathematical resilience as many untrusted redundant connections.

The LFRE Algorithm

To operationalize these concepts, the authors developed the Local-Filtering based Resilient Estimation (LFRE) algorithm. Unlike standard filters that simply average incoming data, LFRE employs a hierarchical filtering logic to maintain accuracy under attack.

Figure 2: The data filtering hierarchy in the LFRE algorithm, showing (a) prioritization of trusted nodes and (c) the fallback to trimmed mean estimation.

As illustrated in the figure above, the algorithm follows a specific priority sequence:

  1. Trust Priority: If a node has a trusted neighbor, it prioritizes that data as a reliable anchor.
  2. Diversity Consensus: If diverse neighbors are available, the algorithm uses a sorting mechanism to reject outliers that do not match the consensus of different sensor types.
  3. Trimmed Mean Fallback: If neither trust nor diversity is sufficient, the algorithm falls back to a "trimmed mean" approach, discarding the $f$-largest and $f$-smallest values to eliminate potential Byzantine influence.

Complexity and Network Design

A key finding of the paper is the "Design Paradox." While the LFRE algorithm is computationally efficient to run, designing the optimal network—deciding exactly which nodes to harden or which sensor types to assign to minimize costs—is NP-complete.

The authors established this by reducing the "Set Cover" problem to two new problems: Trusted Strong-Robustness Augmentation (TSRA) and q-Colored Strong-Robustness Augmentation (q-CSRA). This theoretical result implies that there is no quick algorithmic fix for optimal network hardening; instead, engineers must rely on sophisticated heuristics and approximation algorithms.

Conclusion

This research demonstrates that distributed networks do not need to be dense to be secure. By strategically incorporating a small amount of diversity or a few trusted nodes, sparse networks can achieve the same level of Byzantine resilience as fully connected graphs.

Future work will focus on extending these proofs to non-linear dynamical systems and dynamic network topologies where links may be intermittent. Additionally, the development of efficient approximation algorithms for the NP-complete design problems remains a critical step toward automating the creation of secure, cost-effective distributed sensor networks.

Summary updated

Abstract

We address the problem of distributed state estimation of a linear dynamical process in an attack-prone environment. Recent attempts to solve this problem impose stringent redundancy requirements on the measurement and communication resources of the network. In this paper, we take a step towards alleviating such strict requirements by exploring two complementary directions: (i) making a small subset of the nodes immune to attacks, or "trusted", and (ii) incorporating diversity into the network. We define graph-theoretic constructs that formally capture the notions of redundancy, diversity, and trust. Based on these constructs, we develop a resilient estimation algorithm and demonstrate that even relatively sparse networks that either exhibit node-diversity, or contain a small subset of trusted nodes, can be just as resilient to adversarial attacks as more dense networks. Finally, given a finite budget for network design, we focus on characterizing the complexity of (i) selecting a set of trusted nodes, and (ii) allocating diversity, so as to achieve a desired level of robustness. We establish that, unfortunately, each of these problems is NP-complete.
BibTeX
@article{mitra2021impacts,
  author = {Aritra Mitra and Faiq Ghawash and Shreyas Sundaram and Waseem Abbas},
  title = {{On the Impacts of Redundancy, Diversity, and Trust in Resilient Distributed State Estimation}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2021},
  url = {https://openreview.net/forum?id=7FMt8CtHtP},
}
Figure