# Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 66 references that are in the map.
- First posted on arXiv 24 Apr 2022.

## Builds on (most cited first, 29 of 29)

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Inverting Gradients -- How easy is it to break privacy in federated learning?](https://mlsanity.com/paper/2003.14053/) (2020)
- [Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learning](https://mlsanity.com/paper/1812.00535/) (2018)
- [Byzantine-Resilient Secure Federated Learning](https://mlsanity.com/paper/2007.11115/) (2020)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [LightSecAgg: a Lightweight and Versatile Design for Secure Aggregation in Federated Learning](https://mlsanity.com/paper/2109.14236/) (2021)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [On the Optimal Recovery Threshold of Coded Matrix Multiplication](https://mlsanity.com/paper/1801.10292/) (2018)
- [ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding](https://mlsanity.com/paper/1901.09671/) (2019)
- [A Scalable Approach for Privacy-Preserving Collaborative Machine Learning](https://mlsanity.com/paper/2011.01963/) (2020)
- [CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning](https://mlsanity.com/paper/1902.00641/) (2019)
- [Gradient Coding from Cyclic MDS Codes and Expander Graphs](https://mlsanity.com/paper/1707.03858/) (2017)
- [SwiftAgg+: Achieving Asymptotically Optimal Communication Loads in Secure Aggregation for Federated Learning](https://mlsanity.com/paper/2203.13060/) (2022)
- [Straggler-aware Distributed Learning: Communication Computation Latency Trade-off](https://mlsanity.com/paper/2004.04948/) (2020)
- [Analog Lagrange Coded Computing](https://mlsanity.com/paper/2008.08565/) (2020)
- [A Fundamental Tradeoff between Computation and Communication in Distributed Computing](https://mlsanity.com/paper/1604.07086/) (2016)
- [Near-Optimal Straggler Mitigation for Distributed Gradient Methods](https://mlsanity.com/paper/1710.09990/) (2017)
- [A Unified Coding Framework for Distributed Computing with Straggling Servers](https://mlsanity.com/paper/1609.01690/) (2016)
- [Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier](https://mlsanity.com/paper/2001.05101/) (2020)
- [Rateless Codes for Near-Perfect Load Balancing in Distributed Matrix-Vector Multiplication](https://mlsanity.com/paper/1804.10331/) (2018)
- [Coded Distributed Computing with Partial Recovery](https://mlsanity.com/paper/2007.02191/) (2020)
- [On the Capacity of Secure Distributed Matrix Multiplication](https://mlsanity.com/paper/1806.00469/) (2018)
- [Coded sparse matrix computation schemes that leverage partial stragglers](https://mlsanity.com/paper/2012.06065/) (2020)
- [A Scalable Framework for Wireless Distributed Computing](https://mlsanity.com/paper/1608.05743/) (2016)
- [List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier](https://mlsanity.com/paper/2101.11653/) (2021)
- [Adaptive Verifiable Coded Computing: Towards Fast, Secure and Private Distributed Machine Learning](https://mlsanity.com/paper/2107.12958/) (2021)
- [Hierarchical Coded Matrix Multiplication](https://mlsanity.com/paper/1907.08818/) (2019)

## Abstract (arXiv)

We consider the problem of evaluating arbitrary multivariate polynomials over a massive dataset containing multiple inputs, on a distributed computing system with a master node and multiple worker nodes. Generalized Lagrange Coded Computing (GLCC) codes are proposed to simultaneously provide resiliency against stragglers who do not return computation results in time, security against adversarial workers who deliberately modify results for their benefit, and information-theoretic privacy of the dataset amidst possible collusion of workers. GLCC codes are constructed by first partitioning the dataset into multiple groups, then encoding the dataset using carefully designed interpolating polynomials, and sharing multiple encoded data points to each worker, such that interference computation results across groups can be eliminated at the master. Particularly, GLCC codes include the state-of-the-art Lagrange Coded Computing (LCC) codes as a special case, and exhibit a more flexible tradeoff between communication and computation overheads in optimizing system efficiency. Furthermore, we apply GLCC to distributed training of machine learning models, and demonstrate that GLCC codes achieve a speedup of up to 2.5--3.9× over LCC codes in training time, across experiments for training image classifiers on different datasets, model architectures, and straggler patterns.