The DOI matches its OpenAlex record; 7 of the 7 references it cites were found in a registry or an index.
Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
Open accessAbstract
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\times$, and also achieves a $2.36\times$-$12.65\times$ speedup over the state-of-the-art straggler mitigation strategies.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Shamir, A. (1979) · Communications of the ACM · doi:10.1145/359168.359176 · Cited by 13,756
Understanding Machine Learning: From Theory to Algorithms
Shalev-Shwartz, S., & Ben-David, S. (2014) · doi:10.1017/cbo9781107298019 · Cited by 3,115
SecureML: A System for Scalable Privacy-Preserving Machine Learning
Mohassel, P., & Zhang, Y. (2017) · 2017 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2017.12 · Cited by 1,936
Dean, J., & Barroso, L. A. (2013) · Communications of the ACM · doi:10.1145/2408776.2408794 · Cited by 1,852
Roth, R. (2006) · doi:10.1017/cbo9780511808968 · Cited by 912
Speeding Up Distributed Machine Learning Using Codes
Lee, K., Lam, M., Pedarsani, R., Papailiopoulos, D., & Ramchandran, K. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2736066 · Cited by 829
Secure Multiparty Computation and Secret Sharing
Cramer, R., Damgård, I. B., & Nielsen, J. B. (2015) · doi:10.1017/cbo9781107337756 · Cited by 595
Cited by
Edge artificial intelligence for 6g: vision, enabling technologies, and applications
Letaief, K. B., Shi, Y., Lu, J., & Lu, J. (2022) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2021.3126076 · Cited by 829
“This calls for rigorous privacy-preserving mechanisms and secure aggregation rules [43].”
BackgroundTurbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning
So, J., Guler, B., & Avestimehr, A. S. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3054610 · Cited by 318
VFL: A Verifiable Federated Learning With Privacy-Preserving for Big Data in Industrial IoT
Fu, A., Zhang, X., Xiong, N., Gao, Y., Wang, H., & Zhang, J. (2022) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2020.3036166 · Cited by 288
Modern computing: Vision and challenges
Gill, S. S., Wu, H., Patros, P., Ottaviani, C., Arora, P., Pujol, V. C., Haunschild, D., Parlikad, A. K., Cetinkaya, O., Lutfiyya, H., et al. (2024) · Telematics and Informatics Reports · doi:10.1016/j.teler.2024.100116 · Cited by 197
DETOX: A redundancy-based framework for faster and more robust gradient aggregation
Rajput, S., Wang, H., Charles, Z., & Papailiopoulos, D. (2019) · arXiv · doi:10.48550/arxiv.1907.12205 · Cited by 72
Metadata
- Authors
- Yu, Q., Li, S., Raviv, N., Kalan, S. M. M., Soltanolkotabi, M., & Avestimehr, S.
- Venue
- arXiv (Cornell University)
- Publisher
- arXiv
- Published
- 2018
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1806.00939
- OpenAlex
- W2806273311
- Cited by
- 200
- References
- 7
- Type
- posted content
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy. https://app.cochat.ai/papers/10.48550/arxiv.1806.00939
- The paper
- Yu, Q., Li, S., Raviv, N., Kalan, S. M. M., Soltanolkotabi, M., & Avestimehr, S. (2018). Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1806.00939
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.