# Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks

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

## Key facts

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

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

- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning](https://mlsanity.com/paper/2302.07173/) (2023)
- [Byzantine-Robust Decentralized Learning via ClippedGossip](https://mlsanity.com/paper/2202.01545/) (2022)
- [Byzantine-robust Federated Learning through Collaborative Malicious Gradient Filtering](https://mlsanity.com/paper/2109.05872/) (2021)
- [Maximizing Communication Efficiency for Large-scale Training via 0/1 Adam](https://mlsanity.com/paper/2202.06009/) (2022)
- [Byzantine Fault-Tolerance in Federated Local SGD under 2f-Redundancy](https://mlsanity.com/paper/2108.11769/) (2021)
- [Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attacks](https://mlsanity.com/paper/2107.10302/) (2021)
- [ApproxIFER: A Model-Agnostic Approach to Resilient and Robust Prediction Serving Systems](https://mlsanity.com/paper/2109.09868/) (2021)
- [MixTailor: Mixed Gradient Aggregation for Robust Learning Against Tailored Attacks](https://mlsanity.com/paper/2207.07941/) (2022)
- [FedREP: A Byzantine-Robust, Communication-Efficient and Privacy-Preserving Framework for Federated Learning](https://mlsanity.com/paper/2303.05206/) (2023)
- [Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz](https://mlsanity.com/paper/2310.14616/) (2023)
- [Tolerating Adversarial Attacks and Byzantine Faults in Distributed Machine Learning](https://mlsanity.com/paper/2109.02018/) (2021)
- [FedQV: Leveraging Quadratic Voting in Federated Learning](https://mlsanity.com/paper/2401.01168/) (2024)
- [The poison of dimensionality](https://mlsanity.com/paper/2409.17328/) (2024)
- [SignSGD: Fault-Tolerance to Blind and Byzantine Adversaries](https://mlsanity.com/paper/2202.02085/) (2022)
- [FedCut: A Spectral Analysis Framework for Reliable Detection of Byzantine Colluders](https://mlsanity.com/paper/2211.13389/) (2022)
- [SignSGD with Federated Defense: Harnessing Adversarial Attacks through Gradient Sign Decoding](https://mlsanity.com/paper/2402.01340/) (2024)
- [Fluid Democracy in Federated Data Aggregation](https://mlsanity.com/paper/2507.02710/) (2025)
- [On the Optimal Batch Size for Byzantine-Robust Distributed Learning](https://mlsanity.com/paper/2305.13856/) (2023)
- [FedSECA: Sign Election and Coordinate-wise Aggregation of Gradients for Byzantine Tolerant Federated Learning](https://mlsanity.com/paper/2411.03861/) (2024)

## Abstract (arXiv)

Recent advances in large-scale distributed learning algorithms have enabled communication-efficient training via SignSGD. Unfortunately, a major issue continues to plague distributed learning: namely, Byzantine failures may incur serious degradation in learning accuracy. This paper proposes Election Coding, a coding-theoretic framework to guarantee Byzantine-robustness for SignSGD with Majority Vote, which uses minimum worker-master communication in both directions. The suggested framework explores new information-theoretic limits of finding the majority opinion when some workers could be malicious, and paves the road to implement robust and efficient distributed learning algorithms. Under this framework, we construct two types of explicit codes, random Bernoulli codes and deterministic algebraic codes, that can tolerate Byzantine attacks with a controlled amount of computational redundancy. For the Bernoulli codes, we provide upper bounds on the error probability in estimating the majority opinion, which give useful insights into code design for tolerating Byzantine attacks. As for deterministic codes, we construct an explicit code which perfectly tolerates Byzantines, and provide tight upper/lower bounds on the minimum required computational redundancy. Finally, the Byzantine-tolerance of the suggested coding schemes is confirmed by deep learning experiments on Amazon EC2 using Python with MPI4py package.