Byzantine-Resilient Decentralized Stochastic Optimization with Robust Aggregation Rules

Zhaoxian Wu, Tianyi Chen, Qing Ling

Abstract: This paper focuses on decentralized stochastic optimization in the presence of Byzantine attacks. During the optimization process, an unknown number of malfunctioning or malicious workers, termed as Byzantine workers, disobey the algorithmic protocol and send arbitrarily wrong messages to their neighbors. Even though various Byzantine-resilient algorithms have been developed for distributed stochastic optimization with a central server, we show that there are two major issues in the existing robust aggregation rules when being applied to the decentralized scenario: disagreement and non-doubly stochastic virtual mixing matrix. This paper provides comprehensive analysis that discloses the negative effects of these two issues, and gives guidelines of designing favorable Byzantine-resilient decentralized stochastic optimization algorithms. Under these guidelines, we propose iterative outlier scissor (IOS), an iterative filtering-based robust aggregation rule with provable performance guarantees. Numerical experiments demonstrate the effectiveness of IOS.

Introduction

In decentralized stochastic optimization, there is no central server. Instead, nodes (workers) update their local models and share them with immediate neighbors. While this peer-to-peer approach enhances privacy and scalability, it is highly vulnerable to Byzantine attacks, where malicious nodes send poisoned data to disrupt training.

Existing robust aggregation rules designed for central-server systems, such as the coordinate-wise median or Krum, fail in decentralized networks due to two primary issues:

  1. Disagreement: Nodes may fail to reach consensus because robust rules can prevent them from averaging out differences.
  2. Bias (Non-doubly stochasticity): If the influence nodes exert on each other is unbalanced (non-doubly stochastic mixing matrix), the network optimizes a distorted objective function rather than the true average.

Methodology: Iterative Outlier Scissor (IOS)

To address these failures, the authors establish theoretical guidelines for decentralized robust rules, defining two key properties: Robust Contractive Aggregation (RCA) and Robust Doubly Stochastic Aggregation (RDSA).

Algorithm 1: The general framework for Byzantine-resilient Decentralized SGD.

The proposed Iterative Outlier Scissor (IOS) algorithm implements these properties through iterative filtering. At each communication step, an honest node evaluates models from its neighbors, calculates a weighted average, and "scissors" out the neighbor's model furthest from that average. This process repeats until the node has discarded a number of neighbors equal to the estimated number of Byzantine attackers ($q_n$). Crucially, IOS maintains the "doubly stochastic" property, ensuring that the influence of every honest node remains balanced throughout training.

Experimental Results

The researchers evaluated IOS using the MNIST dataset across various network topologies, including "Two-castle" and "Octopus" graphs, under both i.i.d. and non-i.i.d. data distributions.

Comparison of Accuracy and Disagreement Measure across different aggregation rules.

Key findings include:

  • Resilience to Attacks: IOS maintained an accuracy of approximately 91.7% on MNIST, matching the performance of a network with no attackers, even against brutal "sign-flipping" and "ALIE" attacks.
  • Superiority over Existing Rules: In non-i.i.d. scenarios where standard rules like Krum or Coordinate-wise Median dropped to 10-30% accuracy, IOS remained stable.
  • Consensus Stability: As shown in the Disagreement Measure plots, IOS allows nodes to reach a precise consensus, whereas other robust rules often lead to significant disagreement between honest nodes.

Conclusion

IOS demonstrates that by carefully designing aggregation rules to satisfy RCA and RDSA properties, decentralized networks can achieve high tolerance to Byzantine attacks—even when nearly one-third of a node's neighbors are malicious. Future work may involve combining IOS with variance reduction techniques to further minimize asymptotic learning errors caused by stochastic noise.

Summary updated

Abstract

This paper focuses on decentralized stochastic optimization in the presence of Byzantine attacks. During the optimization process, an unknown number of malfunctioning or malicious workers, termed as Byzantine workers, disobey the algorithmic protocol and send arbitrarily wrong messages to their neighbors. Even though various Byzantine-resilient algorithms have been developed for distributed stochastic optimization with a central server, we show that there are two major issues in the existing robust aggregation rules when being applied to the decentralized scenario: disagreement and non-doubly stochastic virtual mixing matrix. This paper provides comprehensive analysis that discloses the negative effects of these two issues, and gives guidelines of designing favorable Byzantine-resilient decentralized stochastic optimization algorithms. Under these guidelines, we propose iterative outlier scissor (IOS), an iterative filtering-based robust aggregation rule with provable performance guarantees. Numerical experiments demonstrate the effectiveness of IOS. The code of simulation implementation is available at github.com/Zhaoxian-Wu/IOS.
BibTeX
@article{wu2023byzantine,
  author = {Zhaoxian Wu and Tianyi Chen and Qing Ling},
  title = {{Byzantine-Resilient Decentralized Stochastic Optimization with Robust Aggregation Rules}},
  journal = {IEEE Trans. Signal Process.},
  year = {2023},
  url = {https://openreview.net/forum?id=LbURtGEOw9},
}
Figure