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\times$, and also achieves a $2.36\times$-$12.65\times$ speedup over the state-of-the-art straggler mitigation strategies.

References in corpus (8)

• Speeding Up Distributed Machine Learning Using Codes
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Communication-Computation Efficient Gradient Coding
• Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
• CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning
• Fundamental Limits of Coded Linear Transform
• Robust Gradient Descent via Moment Encoding with LDPC Codes
• Near-Optimal Straggler Mitigation for Distributed Gradient Methods

Cited by in corpus (23)

• Computation Scheduling for Distributed Machine Learning with Straggling Workers
• Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
• Adaptive Verifiable Coded Computing: Towards Fast, Secure and Private Distributed Machine Learning
• Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier
• Cross Subspace Alignment Codes for Coded Distributed Batch Computation
• A Survey of Coded Distributed Computing
• Double Blind $T$-Private Information Retrieval
• Coded Computation across Shared Heterogeneous Workers with Communication Delay
• Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers
• DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation
• On the Feasibility of Sybil Attacks in Shard-Based Permissionless Blockchains
• A Systematic Approach towards Efficient Private Matrix Multiplication
• Secure Coded Multi-Party Computation for Massive Matrix Operations
• A locality-based approach for coded computation
• Private Secure Coded Computation
• Coded Federated Computing in Wireless Networks with Straggling Devices and Imperfect CSI
• On the Generic Capacity of $K$-User Symmetric Linear Computation Broadcast
• Transition Waste Optimization for Coded Elastic Computing
• Heterogeneity-aware Gradient Coding for Straggler Tolerance
• ByzShield: An Efficient and Robust System for Distributed Training
• On the Capacity of Computation Broadcast
• Coded Elastic Computing
• Folded Polynomial Codes for Coded Distributed $A{A}^{\top }$-Type Matrix Multiplication