# Byzantine Fault-Tolerance in Federated Local SGD under 2f-Redundancy

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 53 references that are in the map.
- First posted on arXiv 26 Aug 2021.

## Builds on (most cited first, 30 of 31)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Local Model Poisoning Attacks to Byzantine-Robust Federated Learning](https://mlsanity.com/paper/1911.11815/) (2019)
- [FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping](https://mlsanity.com/paper/2012.13995/) (2020)
- [The Hidden Vulnerability of Distributed Learning in Byzantium](https://mlsanity.com/paper/1802.07927/) (2018)
- [Federated Optimization:Distributed Optimization Beyond the Datacenter](https://mlsanity.com/paper/1511.03575/) (2015)
- [RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets](https://mlsanity.com/paper/1811.03761/) (2018)
- [Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation](https://mlsanity.com/paper/1903.03936/) (2019)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Generalized Byzantine-tolerant SGD](https://mlsanity.com/paper/1802.10116/) (2018)
- [Byzantine-Resilient Secure Federated Learning](https://mlsanity.com/paper/2007.11115/) (2020)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Byzantine Stochastic Gradient Descent](https://mlsanity.com/paper/1803.08917/) (2018)
- [Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks](https://mlsanity.com/paper/1912.12716/) (2019)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Byzantine-Robust Federated Machine Learning through Adaptive Model Averaging](https://mlsanity.com/paper/1909.05125/) (2019)
- [Opportunities of Federated Learning in Connected, Cooperative and Automated Industrial Systems](https://mlsanity.com/paper/2101.03367/) (2021)
- [Geometric Median in Nearly Linear Time](https://mlsanity.com/paper/1606.05225/) (2016)
- [ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning](https://mlsanity.com/paper/1708.08155/) (2017)
- [Approximate Byzantine Fault-Tolerance in Distributed Optimization](https://mlsanity.com/paper/2101.09337/) (2021)
- [Distributed Optimization Under Adversarial Nodes](https://mlsanity.com/paper/1606.08939/) (2016)
- [Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks](https://mlsanity.com/paper/1910.06093/) (2019)
- [Phocas: dimensional Byzantine-resilient stochastic gradient descent](https://mlsanity.com/paper/1805.09682/) (2018)
- [Making a Case for Federated Learning in the Internet of Vehicles and Intelligent Transportation Systems](https://mlsanity.com/paper/2102.10142/) (2021)
- [Byzantine-Resilient Distributed Optimization of Multi-Dimensional Functions](https://mlsanity.com/paper/2003.09038/) (2020)
- [Finite-time Guarantees for Byzantine-Resilient Distributed State Estimation with Noisy Measurements](https://mlsanity.com/paper/1810.10086/) (2018)
- [Secure State Estimation against Sensor Attacks in the Presence of Noise](https://mlsanity.com/paper/1510.02462/) (2015)
- [Byzantine Fault Tolerant Distributed Linear Regression](https://mlsanity.com/paper/1903.08752/) (2019)

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

- [Byzantine-Robust Decentralized Learning via ClippedGossip](https://mlsanity.com/paper/2202.01545/) (2022)
- [Byzantine-Robust Federated Learning: Impact of Client Subsampling and Local Updates](https://mlsanity.com/paper/2402.12780/) (2024)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [FedCut: A Spectral Analysis Framework for Reliable Detection of Byzantine Colluders](https://mlsanity.com/paper/2211.13389/) (2022)
- [Federated Cubic Regularized Newton Learning with Sparsification-amplified Differential Privacy](https://mlsanity.com/paper/2408.04315/) (2024)
- [Utilizing Redundancy in Cost Functions for Resilience in Distributed Optimization and Learning](https://mlsanity.com/paper/2110.10858/) (2021)
- [Trade-off in Estimating the Number of Byzantine Clients in Federated Learning](https://mlsanity.com/paper/2510.04432/) (2025)

## Abstract (arXiv)

We consider the problem of Byzantine fault-tolerance in federated machine learning. In this problem, the system comprises multiple agents each with local data, and a trusted centralized coordinator. In fault-free setting, the agents collaborate with the coordinator to find a minimizer of the aggregate of their local cost functions defined over their local data. We consider a scenario where some agents (f out of N) are Byzantine faulty. Such agents need not follow a prescribed algorithm correctly, and may communicate arbitrary incorrect information to the coordinator. In the presence of Byzantine agents, a more reasonable goal for the non-faulty agents is to find a minimizer of the aggregate cost function of only the non-faulty agents. This particular goal is commonly referred as exact fault-tolerance. Recent work has shown that exact fault-tolerance is achievable if only if the non-faulty agents satisfy the property of 2f-redundancy. Now, under this property, techniques are known to impart exact fault-tolerance to the distributed implementation of the classical stochastic gradient-descent (SGD) algorithm. However, we do not know of any such techniques for the federated local SGD algorithm - a more commonly used method for federated machine learning. To address this issue, we propose a novel technique named comparative elimination (CE). We show that, under 2f-redundancy, the federated local SGD algorithm with CE can indeed obtain exact fault-tolerance in the deterministic setting when the non-faulty agents can accurately compute gradients of their local cost functions. In the general stochastic case, when agents can only compute unbiased noisy estimates of their local gradients, our algorithm achieves approximate fault-tolerance with approximation error proportional to the variance of stochastic gradients and the fraction of Byzantine agents.