Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes

Abstract

We consider the setting of a Master server, M, who possesses confidential data (e.g., personal, genomic or medical data) and wants to run intensive computations on it, as part of a machine learning algorithm for example. The Master wants to distribute these computations to untrusted workers who have volunteered or are incentivized to help with this task. However, the data must be kept private and not revealed to the individual workers. Some of the workers may be stragglers, e.g., slow or busy, and will take a random time to finish the task assigned to them. We are interested in reducing the delays experienced by the Master. We focus on linear computations as an essential operation in many iterative algorithms such as principal component analysis, support vector machines and other gradient-descent based algorithms. A classical solution is to use a linear secret sharing scheme, such as Shamir's scheme, to divide the data into secret shares on which the workers can perform linear computations. However, classical codes can provide straggler mitigation assuming a worst-case scenario of a fixed number of stragglers. We propose a solution based on new secure codes, called Staircase codes, introduced previously by two of the authors. Staircase codes allow flexibility in the number of stragglers up to a given maximum, and universally achieve the information theoretic limit on the download cost by the Master, leading to latency reduction. Under the shifted exponential model, we find upper and lower bounds on the Master's mean waiting time. We derive the distribution of the Master's waiting time, and its mean, for systems with up to two stragglers. For systems with any number of stragglers, we derive an expression that can give the exact distribution, and the mean, of the waiting time of the Master. We show that Staircase codes always outperform classical secret sharing codes.

Submitted to IEEE Transactions of Information Theory for possible publication

References in corpus (15)

• Revisiting Distributed Synchronous SGD
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding
• Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
• Factoring nonnegative matrices with linear programs
• Minimizing Latency for Secure Distributed Computing
• Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
• CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning
• PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent
• Rate-Efficiency and Straggler-Robustness through Partition in Distributed Two-Sided Secure Matrix Computation
• Cross Subspace Alignment Codes for Coded Distributed Batch Computation
• On the Upload versus Download Cost for Secure and Private Matrix Multiplication
• Private Learning on Networks: Part II
• Private Learning on Networks
• Gradient Coding

Cited by in corpus (7)

• Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
• Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
• A Survey of Coded Distributed Computing
• Latency optimal storage and scheduling of replicated fragments for memory-constrained servers
• Diversity/Parallelism Trade-off in Distributed Systems with Redundancy
• Load balancing policies without feedback using timed replicas
• Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication