Lagrange Coded Computing: Optimal Design for Resiliency, Security, and Privacy
Abstract
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.
Additional Information
© 2019 by the author(s). This material is based upon work supported by Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001117C0053, ARO award W911NF1810400, NSF grants CCF-1703575, ONR Award No. N00014-16-1-2189, and CCF-1763673. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. Qian Yu is supported by the Google PhD Fellowship.Attached Files
Published - yu19b.pdf
Supplemental Material - yu19b-supp.pdf
Files
Name | Size | Download all |
---|---|---|
md5:2086c63f9ab6b00f8f8d69817fadfb7c
|
396.3 kB | Preview Download |
md5:5628553c74094bfb1bc663ff1a645f3e
|
819.2 kB | Preview Download |
Additional details
- Eprint ID
- 101454
- Resolver ID
- CaltechAUTHORS:20200221-101228104
- HR001117C0053
- Defense Advanced Research Projects Agency (DARPA)
- W911NF1810400
- Army Research Office (ARO)
- CCF-1703575
- NSF
- N00014-16-1-2189
- Office of Naval Research (ONR)
- CCF-1763673
- NSF
- Created
-
2020-02-21Created from EPrint's datestamp field
- Updated
-
2020-02-21Created from EPrint's last_modified field