# Distributed Optimization Under Adversarial Nodes

arXiv: https://arxiv.org/abs/1606.08939 · HTML: https://mlsanity.com/paper/1606.08939/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2016.

## Built on by (most cited first, 20 of 20)

- [Byzantine-Robust Decentralized Learning via ClippedGossip](https://mlsanity.com/paper/2202.01545/) (2022)
- [Robust Multi-Agent LLMs under Byzantine Faults](https://mlsanity.com/paper/2605.09076/) (2026)
- [On the Tradeoff between Privacy Preservation and Byzantine-Robustness in Decentralized Learning](https://mlsanity.com/paper/2308.14606/) (2023)
- [Byzantine Fault-Tolerance in Federated Local SGD under 2f-Redundancy](https://mlsanity.com/paper/2108.11769/) (2021)
- [Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2206.02834/) (2022)
- [Bristle: Decentralized Federated Learning in Byzantine, Non-i.i.d. Environments](https://mlsanity.com/paper/2110.11006/) (2021)
- [A survey on secure decentralized optimization and learning](https://mlsanity.com/paper/2408.08628/) (2024)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [Distributed Online Optimization with Byzantine Adversarial Agents](https://mlsanity.com/paper/2109.12340/) (2021)
- [Distributed Statistical Min-Max Learning in the Presence of Byzantine Agents](https://mlsanity.com/paper/2204.03187/) (2022)
- [Byzantine-Robust Decentralized Stochastic Optimization with Stochastic Gradient Noise-Independent Learning Error](https://mlsanity.com/paper/2308.05292/) (2023)
- [Resilient Consensus-based Multi-agent Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2111.06776/) (2021)
- [Detection of Insider Attacks in Distributed Projected Subgradient Algorithms](https://mlsanity.com/paper/2101.06917/) (2021)
- [Design and Analysis of Robust Resilient Diffusion over Multi-Task Networks Against Byzantine Attacks](https://mlsanity.com/paper/2206.12749/) (2022)
- [Resilient Output Consensus Control of Heterogeneous Multi-agent Systems against Byzantine Attacks: A Twin Layer Approach](https://mlsanity.com/paper/2303.15299/) (2023)
- [A Unified Framework for Center-based Clustering of Distributed Data](https://mlsanity.com/paper/2402.01302/) (2024)
- [VALID: a Validated Algorithm for Learning in Decentralized Networks with Possible Adversarial Presence](https://mlsanity.com/paper/2405.07316/) (2024)
- [Personalized and Resilient Distributed Learning Through Opinion Dynamics](https://mlsanity.com/paper/2505.14081/) (2025)
- [Fully Byzantine-Resilient Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2609.25701/) (2026)
- [Learning from Unreliable Trajectories: Adversarially-Robust Federated Q-Learning](https://mlsanity.com/paper/2610.06918/) (2026)

## Abstract (arXiv)

We investigate the vulnerabilities of consensus-based distributed optimization protocols to nodes that deviate from the prescribed update rule (e.g., due to failures or adversarial attacks). We first characterize certain fundamental limitations on the performance of any distributed optimization algorithm in the presence of adversaries. We then propose a resilient distributed optimization algorithm that guarantees that the non-adversarial nodes converge to the convex hull of the minimizers of their local functions under certain conditions on the graph topology, regardless of the actions of a certain number of adversarial nodes. In particular, we provide sufficient conditions on the graph topology to tolerate a bounded number of adversaries in the neighborhood of every non-adversarial node, and necessary and sufficient conditions to tolerate a globally bounded number of adversaries. For situations where there are up to F adversaries in the neighborhood of every node, we use the concept of maximal F-local sets of graphs to provide lower bounds on the distance-to-optimality of achievable solutions under any algorithm. We show that finding the size of such sets is NP-hard.