# Adaptive Verifiable Coded Computing: Towards Fast, Secure and Private Distributed Machine Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 42 references that are in the map.
- First posted on arXiv 27 Jul 2021.

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

- [Deep Learning with Limited Numerical Precision](https://mlsanity.com/paper/1502.02551/) (2015)
- [Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware](https://mlsanity.com/paper/1806.03287/) (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)
- [DRACO: Byzantine-resilient Distributed Training via Redundant Gradients](https://mlsanity.com/paper/1803.09877/) (2018)
- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud](https://mlsanity.com/paper/1706.10268/) (2017)
- [DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation](https://mlsanity.com/paper/1907.12205/) (2019)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [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)
- [Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing](https://mlsanity.com/paper/2009.08327/) (2020)
- [On Polynomial Approximations for Privacy-Preserving and Verifiable ReLU Networks](https://mlsanity.com/paper/2011.05530/) (2020)
- [Byzantine-Robust and Privacy-Preserving Framework for FedML](https://mlsanity.com/paper/2105.02295/) (2021)
- [When Do Redundant Requests Reduce Latency ?](https://mlsanity.com/paper/1311.2851/) (2013)
- [List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier](https://mlsanity.com/paper/2101.11653/) (2021)
- [Collaborative Decoding of Polynomial Codes for Distributed Computation](https://mlsanity.com/paper/1905.13685/) (2019)
- [INTERPOL: Information Theoretically Verifiable Polynomial Evaluation](https://mlsanity.com/paper/1901.03379/) (2019)

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

- [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)
- [Edge Private Graph Neural Networks with Singular Value Perturbation](https://mlsanity.com/paper/2403.10995/) (2024)
- [Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation](https://mlsanity.com/paper/2204.11168/) (2022)

## Abstract (arXiv)

Stragglers, Byzantine workers, and data privacy are the main bottlenecks in distributed cloud computing. Some prior works proposed coded computing strategies to jointly address all three challenges. They require either a large number of workers, a significant communication cost or a significant computational complexity to tolerate Byzantine workers. Much of the overhead in prior schemes comes from the fact that they tightly couple coding for all three problems into a single framework. In this paper, we propose Adaptive Verifiable Coded Computing (AVCC) framework that decouples the Byzantine node detection challenge from the straggler tolerance. AVCC leverages coded computing just for handling stragglers and privacy, and then uses an orthogonal approach that leverages verifiable computing to mitigate Byzantine workers. Furthermore, AVCC dynamically adapts its coding scheme to trade-off straggler tolerance with Byzantine protection. We evaluate AVCC on a compute-intensive distributed logistic regression application. Our experiments show that AVCC achieves up to 4.2× speedup and up to 5.1% accuracy improvement over the state-of-the-art Lagrange coded computing approach (LCC). AVCC also speeds up the conventional uncoded implementation of distributed logistic regression by up to 7.6×, and improves the test accuracy by up to 12.1%.