# Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy

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

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2018.

## Built on by (most cited first, 30 of 66)

- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications](https://mlsanity.com/paper/2111.12444/) (2021)
- [LightSecAgg: a Lightweight and Versatile Design for Secure Aggregation in Federated Learning](https://mlsanity.com/paper/2109.14236/) (2021)
- [CodedPaddedFL and CodedSecAgg: Straggler Mitigation and Secure Aggregation in Federated Learning](https://mlsanity.com/paper/2112.08909/) (2021)
- [SwiftAgg+: Achieving Asymptotically Optimal Communication Loads in Secure Aggregation for Federated Learning](https://mlsanity.com/paper/2203.13060/) (2022)
- [DReS-FL: Dropout-Resilient Secure Federated Learning for Non-IID Clients via Secret Data Sharing](https://mlsanity.com/paper/2210.02680/) (2022)
- [FedVS: Straggler-Resilient and Privacy-Preserving Vertical Federated Learning for Split Models](https://mlsanity.com/paper/2304.13407/) (2023)
- [DarKnight: An Accelerated Framework for Privacy and Integrity Preserving Deep Learning Using Trusted Hardware](https://mlsanity.com/paper/2207.00083/) (2022)
- [The Federation Strikes Back: A Survey of Federated Learning Privacy Attacks, Defenses, Applications, and Policy Landscape](https://mlsanity.com/paper/2405.03636/) (2024)
- [Stochastic Coded Federated Learning with Convergence and Privacy Guarantees](https://mlsanity.com/paper/2201.10092/) (2022)
- [Secure Federated Clustering](https://mlsanity.com/paper/2205.15564/) (2022)
- [A Survey of Privacy Threats and Defense in Vertical Federated Learning: From Model Life Cycle Perspective](https://mlsanity.com/paper/2402.03688/) (2024)
- [Byzantine-Resilient Secure Aggregation for Federated Learning Without Privacy Compromises](https://mlsanity.com/paper/2405.08698/) (2024)
- [ApproxIFER: A Model-Agnostic Approach to Resilient and Robust Prediction Serving Systems](https://mlsanity.com/paper/2109.09868/) (2021)
- [Private Aggregation in Hierarchical Wireless Federated Learning with Partial and Full Collusion](https://mlsanity.com/paper/2306.14088/) (2023)
- [Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework](https://mlsanity.com/paper/2406.00300/) (2024)
- [Game of Coding: Sybil Resistant Decentralized Machine Learning with Minimal Trust Assumption](https://mlsanity.com/paper/2410.05540/) (2024)
- [List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier](https://mlsanity.com/paper/2101.11653/) (2021)
- [LEGATO: A LayerwisE Gradient AggregaTiOn Algorithm for Mitigating Byzantine Attacks in Federated Learning](https://mlsanity.com/paper/2107.12490/) (2021)
- [Adaptive Verifiable Coded Computing: Towards Fast, Secure and Private Distributed Machine Learning](https://mlsanity.com/paper/2107.12958/) (2021)
- [MPC-Pipe: an Efficient Pipeline Scheme for Secure Multi-party Machine Learning Inference](https://mlsanity.com/paper/2209.13643/) (2022)
- [ByzSecAgg: A Byzantine-Resistant Secure Aggregation Scheme for Federated Learning Based on Coded Computing and Vector Commitment](https://mlsanity.com/paper/2302.09913/) (2023)
- [HiFGL: A Hierarchical Framework for Cross-silo Cross-device Federated Graph Learning](https://mlsanity.com/paper/2406.10616/) (2024)
- [General Coded Computing: Adversarial Settings](https://mlsanity.com/paper/2502.08058/) (2025)
- [LoByITFL: Low Communication Secure and Private Federated Learning](https://mlsanity.com/paper/2405.19217/) (2024)
- [Game of Coding With an Unknown Adversary](https://mlsanity.com/paper/2502.07109/) (2025)
- [Coding for Distributed Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2101.02308/) (2021)
- [Optimal Communication-Computation Trade-Off in Heterogeneous Gradient Coding](https://mlsanity.com/paper/2103.01589/) (2021)
- [Coded-InvNet for Resilient Prediction Serving Systems](https://mlsanity.com/paper/2106.06445/) (2021)
- [Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2208.03134/) (2022)

## Abstract (arXiv)

We consider a scenario involving computations over a massive dataset stored distributedly across multiple workers, which is at the core of distributed learning algorithms. We propose Lagrange Coded Computing (LCC), a new framework to simultaneously provide (1) resiliency against stragglers that may prolong computations; (2) security against Byzantine (or malicious) workers that deliberately modify the computation for their benefit; and (3) (information-theoretic) privacy of the dataset amidst possible collusion of workers. LCC, which leverages the well-known Lagrange polynomial to create computation redundancy in a novel coded form across workers, can be applied to any computation scenario in which the function of interest is an arbitrary multivariate polynomial of the input dataset, hence covering many computations of interest in machine learning. LCC significantly generalizes prior works to go beyond linear computations. It also enables secure and private computing in distributed settings, improving the computation and communication efficiency of the state-of-the-art. Furthermore, we prove the optimality of LCC by showing that it achieves the optimal tradeoff between resiliency, security, and privacy, i.e., in terms of tolerating the maximum number of stragglers and adversaries, and providing data privacy against the maximum number of colluding workers. Finally, we show via experiments on Amazon EC2 that LCC speeds up the conventional uncoded implementation of distributed least-squares linear regression by up to 13.43×, and also achieves a 2.36×-12.65× speedup over the state-of-the-art straggler mitigation strategies.