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

By Qian Yu, Netanel Raviv, Jinhyun So, Amir Salman Avestimehr. 2018

461 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, ML Systems & Hardware, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

In ML Systems & Hardware

In Privacy & Security

Citations in the corpus

FedML: A Research Library and Benchmark for Federated Machine Learning (2020, methodology): “We also plan to include an implementation of Lagrange Coded Computing (LCC) [115].”
Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning (2020, methodology): “To do so, we leverage Lagrange coding [14], which has been applied to other problems such as offloading or collaborative machine learning in the privacy-preserving manner [47], [48].”
DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation (2019, positive): “The second approach instead assigns each node redundant gradients, and uses this redundancy to eliminate the effect of Byzantine failures [7, 8, 9].”
Data Encoding for Byzantine-Resilient Distributed Optimization (2019, methodology): “the encoding time of our scheme is much less (by a factor of O(m log(2)(m))) than that of [29], whereas, for corruption cm, where c < 12 , the scheme of [29] takes O( m log2(m) )-factor less time in encoding than ours.”
On the Upload versus Download Cost for Secure and Private Matrix Multiplication (2019, background): “The authors in [5] proposed the idea of Lagrange”
Distributed and Private Coded Matrix Computation with Flexible Communication Load (2019, methodology): “In [13] Lagrange coding is presented which achieves the minimum recovery threshold for multilinear functions by generalizing MatDot codes.”
ON THE CAPACITY OF SECURE DISTRIBUTED FAST FOURIER TRANSFORM (2018, background): “A few works that do take security into account include [14, 15] where both works used secret sharing scheme along with different encoding strategies to make sure that the computations are secure, and [16] proposed a novel coded computing strat-”
CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning (2019, methodology): “See https://www.ieee.org/publications/rights/index.html for more information. coding [8], to guarantee privacy (in an information-theoretic sense) while simultaneously distributing the workload among multiple workers.”
Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications (2021, background): “This calls for rigorous privacy-preserving mechanisms and secure aggregation rules [43].”
Federated Learning with Buffered Asynchronous Aggregation (2021, methodology): “Most previous works analyze synchronous federated learning methods, such as the works in (Lin et al., 2018; Li et al., 2018; Reddi et al., 2020; Li et al., 2020; Stich, 2019; Yu et al., 2019b; Li et al., 2019; Haddadpour and Mahdavi, 2019; Karimireddy et al., 2020).”
Private Secure Coded Computation (2019, unknown): “Data security in coded computation was studied in previous works [5] - [7].”
A Scalable Approach for Privacy-Preserving Collaborative Machine Learning (2020, methodology): “Information-theoretic privacy of Lagrange coding against T colluding clients follows from [40].”
Gradient Coding From Cyclic MDS Codes and Expander Graphs (2017, background): “Furthermore, the exact setting was also discussed subsequent to this work in [26] and [27].”