Topology Free Resilient Distributed Estimation

Yuan Chen, Soummya Kar, José M. F. Moura

Abstract

This paper studies resilient distributed estimation under measurement attacks. A set of agents each makes successive local, linear, noisy measurements of an unknown vector field collected in a vector parameter. The local measurement models are heterogeneous across agents and may be locally unobservable for the unknown parameter. An adversary compromises some of the measurement streams and changes their values arbitrarily. The agents' goal is to cooperate over a peer-to-peer communication network to process their (possibly compromised) local measurements and estimate the value of the unknown vector parameter. We present SAGE, the Saturating Adaptive Gain Estimator, a distributed, recursive, consensus+innovations estimator that is resilient to measurement attacks. We demonstrate that, as long as the number of compromised measurement streams is below a particular bound, then, SAGE guarantees that all of the agents' local estimates converge almost surely to the value of the parameter. The resilience of the estimator -- i.e., the number of compromised measurement streams it can tolerate -- does not depend on the topology of the inter-agent communication network. Finally, we illustrate the performance of SAGE through numerical examples.

Introduction

In the era of the Internet of Things (IoT) and autonomous vehicle swarms, distributed systems must cooperate to estimate global states—such as environmental conditions, traffic patterns, or spatial fields—using local, noisy measurements. While distributed estimation offers scalability and robustness to single-point failures, it introduces significant vulnerabilities to cyber-attacks. If an adversary compromises even a small subset of sensors and injects "pathological" data, this misinformation can propagate through the peer-to-peer network, potentially causing the entire global estimate to collapse.

Existing resilient estimation frameworks often struggle with three practical realities: heterogeneity (sensors measuring different aspects of a state), local unobservability (no single sensor can see the whole picture), and high-intensity background noise. This paper introduces SAGE (Saturating Adaptive Gain Estimator), a distributed algorithm designed to maintain accuracy despite arbitrary measurement corruption, without requiring the network to explicitly identify which sensors are compromised.

The SAGE Algorithm

SAGE is built upon the Consensus + Innovations framework. In this recursive setup, each agent in the network maintains a local estimate of the unknown parameter $\theta^*$ and updates it at each time step using two primary mechanisms:

  1. Consensus: The agent averages its current estimate with those of its immediate neighbors to ensure network-wide agreement.
  2. Innovation: The agent incorporates its own local measurements to pull the estimate toward the physical truth.

The Saturating Adaptive Gain

The defining feature of SAGE is its non-linear approach to innovation. Traditional estimators treat all data linearly, which allows an adversary to pull the estimate arbitrarily far by providing extreme values. SAGE addresses this by applying a Saturating Adaptive Gain. If a local measurement deviates significantly from the current estimate—suggesting either a malicious attack or a massive noise spike—the gain "saturates," effectively clipping the influence of that measurement.

To refine this process over time, SAGE employs a time-varying threshold ($\gamma_t$). In the early stages of estimation, the threshold is relatively wide, allowing agents to learn and move toward the general vicinity of the parameter. As the estimates begin to converge, the threshold tightens. This adaptive narrowing allows the network to filter out increasingly subtle adversarial manipulations that might otherwise hide within the statistical noise.

Theoretical Insights: Topology Independence

Perhaps the most significant theoretical contribution of this work is the discovery of topology independence. In many existing resilient distributed systems, the number of attackers the system can tolerate is limited by the "connectedness" (vertex connectivity) of the communication graph.

In contrast, the resilience of SAGE depends solely on the redundancy of the measurements (specifically, s-sparse observability). As long as the remaining "good" sensors collectively provide enough information to observe the entire parameter, SAGE guarantees that all agents' local estimates will converge almost surely to the true value. This holds true regardless of how the agents are wired together, provided the communication network remains connected. This "implicit resilience" allows SAGE to ignore malicious data naturally without the computational burden of explicit outlier detection.

Numerical Validation

The authors validated SAGE through two rigorous numerical simulations:

1. Large-Scale Random Networks

In a setup involving 500 agents in a random geometric network, the agents attempted to estimate a 2D vector. 100 of these agents were fully compromised with a fixed adversarial offset. SAGE demonstrated remarkable robustness to noise, maintaining convergence even at a Signal-to-Noise Ratio (SNR) as low as -25 dB. This confirms that the adaptive thresholding effectively distinguishes between zero-mean statistical noise and biased adversarial attacks.

2. High-Dimensional Image Recovery

To test SAGE in a heterogeneous, high-dimensional environment, 100 robots were tasked with reconstructing a 10,000-pixel image. Each robot could only "see" a small 45x45 patch of the image, meaning no single robot had enough data to reconstruct the whole. An adversary compromised 10 robots, affecting over 16,000 measurement streams. While standard Consensus + Innovations estimators failed, producing a corrupted and blurry result, SAGE successfully reconstructed the image with high fidelity.

Conclusion and Future Directions

SAGE provides a robust, computationally efficient solution for distributed estimation in adversarial environments. By decoupling resilience from network topology and utilizing adaptive saturation gains, it ensures convergence even under heavy measurement corruption and noise.

Future research will focus on extending SAGE to dynamic parameters, where the target state is time-varying (e.g., tracking a moving target). Additionally, the authors aim to investigate roaming attacks, where the set of compromised sensors changes over time, and further refine the methods for optimal hyperparameter tuning in real-world deployments.

Summary updated

Abstract

This paper studies resilient distributed estimation under measurement attacks. A set of agents each makes successive local, linear, noisy measurements of an unknown vector field collected in a vector parameter. The local measurement models are heterogeneous across agents and may be locally unobservable for the unknown parameter. An adversary compromises some of the measurement streams and changes their values arbitrarily. The agents' goal is to cooperate over a peer-to-peer communication network to process their (possibly compromised) local measurements and estimate the value of the unknown vector parameter. We present SAGE, the Saturating Adaptive Gain Estimator, a distributed, recursive, consensus+innovations estimator that is resilient to measurement attacks. We demonstrate that, as long as the number of compromised measurement streams is below a particular bound, then, SAGE guarantees that all of the agents' local estimates converge almost surely to the value of the parameter. The resilience of the estimator -- i.e., the number of compromised measurement streams it can tolerate -- does not depend on the topology of the inter-agent communication network. Finally, we illustrate the performance of SAGE through numerical examples.
BibTeX
@article{chen2019topology,
  author = {Yuan Chen and Soummya Kar and José M. F. Moura},
  title = {{Topology Free Resilient Distributed Estimation}},
  journal = {IEEE TSP},
  year = {2019},
  doi = {10.1109/tsp.2019.2931171},
}
Figure