PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Qian Yu, Songze Li, Netanel Raviv, Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, Salman Avestimehr

arXiv:1806.00939v4cs.ITcs.DCcs.LG

TL;DR

Distributed computation over massive datasets must handle stragglers, malicious workers, and privacy against collusion. LCC uses Lagrange-polynomial coding for arbitrary multivariate polynomial computations, achieves the optimal supported tradeoff, and improves least-squares regression performance in Amazon EC2 experiments.

  • Problem

    Distributed computation must address stragglers, Byzantine workers, and dataset privacy when data is processed across many workers.

  • Method

    LCC encodes dataset inputs with a Lagrange polynomial so workers compute coded inputs while supporting polynomial functions.

  • Results

    LCC achieves the optimal resiliency-security-privacy tradeoff, with (K+T−1) deg f+S+2A+1 ≤ N characterizing achievable parameters under the stated conditions.

  • Takeaways & Limitations

    LCC extends secure and private coded computing beyond linear functions to arbitrary multivariate polynomials covered by the framework.

Abstract

from arXiv · show

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.

I. INTRODUCTION

LCC addresses distributed-computing delays, malicious workers, and colluding-worker privacy through Lagrange-polynomial coding. It achieves an optimal resiliency-security-privacy tradeoff and improves least-squares regression performance in Amazon EC2 experiments.

  • Motivation: 5 to 8 times slower stragglers can create significant delays in distributed computations.Distributing data across servers also creates substantial bandwidth bottlenecks.
  • Lagrange Coded Computing: LCC simultaneously provides straggler resiliency, Byzantine-worker security, and information-theoretic dataset privacy.It applies to arbitrary multivariate polynomial computations, including machine-learning gradients, loss functions, and tensor algebra.
  • Lagrange Coded Computing: N coded inputs let workers compute polynomial functions while enabling the master to decode results despite stragglers, adversaries, and colluding workers.The coding strategy creates computational redundancy across workers.
  • Optimality: (K+T−1) deg f+S+2A+1 ≤ N is sufficient for LCC to achieve (S, A, T).Adding one worker can increase straggler resiliency by 1 or malicious-server robustness by 1/2 while preserving privacy.
  • Optimality: LCC achieves the optimal tradeoff among resiliency, security, and privacy under the paper’s stated complexity constraints.The result extends coding-theoretic scaling to private distributed computing, where an additional worker enables privacy against 1/degf additional colluding workers.
  • Evaluation: 13.43× is the reported maximum speedup over uncoded distributed least-squares regression in Amazon EC2 experiments.The paper also compares LCC with state-of-the-art straggler mitigation strategies.

II. PROBLEM FORMULATION AND EXAMPLES

The paper formalizes distributed evaluation of polynomial functions with linear-coded worker inputs and defines resiliency, security, and privacy requirements. It presents linear, bilinear, tensor, and gradient computations as examples covered by this framework.

  • Problem formulation: The framework evaluates a nonconstant multivariate polynomial f over dataset items X1,...,XK in a master-worker system.The polynomial maps an input vector space V to an output vector space U over field F.
  • Problem formulation: Each worker stores a possibly random linear encoding of the dataset, computes f on that coded input, and returns the result to the master.Linear encoding is used to keep encoding complexity low and implementation simple.
  • System requirements: Resiliency requires correct outputs despite up to S workers failing to respond, while security requires correctness despite up to A workers returning arbitrary errors.The master waits for a subset of the fastest workers before decoding.
  • System requirements: Privacy requires zero mutual information between the dataset and encoded data observed by any set of up to T colluding workers.The dataset is treated as uniformly random, and privacy is information-theoretic.
  • Problem formulation: The goal is to characterize achievable (S,A,T) regions for given N, K, and f over sufficiently large fields.Decoding functions must return all required outputs correctly while satisfying the system requirements.
  • Examples: The framework covers linear matrix-vector products, bilinear products, higher-degree tensor algebra, and distributed gradient computations.Examples include linear regression iterations, matrix multiplication building blocks, tensor coordinate transformations, and empirical-risk gradients.

III. MAIN RESULTS AND PRIOR WORKS

LCC characterizes and achieves the feasible tradeoff among straggler resiliency, Byzantine security, and dataset privacy, with optimality under stated scheme constraints.

  • Main results: LCC achieves (S, A, T) when (K + T −1) deg f + S + 2A + 1 ≤ N.A variation achieves an alternative region K(S + 2A + deg f · T + 1) ≤ N.
  • Main results: LCC uses Lagrange-polynomial encoding so workers evaluate the desired function over coded data while supporting resiliency, security, and privacy.The encoding functions are evaluations of a degree K −1 Lagrange polynomial, and worker computations evaluate its composition with f.
  • Main results: Adding one worker increases straggler resiliency by 1 or malicious-server robustness by 1/2 while preserving the privacy constraint.The left-hand side of the main inequality is independent of N; uncoded replication requires K additional machines to increase resiliency by 1.
  • Optimality: LCC achieves the optimal resiliency-security-privacy tradeoff for multilinear functions under linear encoding across all problem scenarios.Without security constraints, it is also optimal for arbitrary polynomials under linear decoding and sufficiently large or zero field characteristic.
  • Optimality: The paper proves LCC’s optimality by showing that any scheme outperforming it would violate decodability under two computation instances with identical intermediate results but different outputs.The appendix additionally establishes optimal randomness for schemes universally achieving the same tradeoff for all linear functions.

A. LCC vs. Prior Works

LCC generalizes coded computing to arbitrary multivariate polynomial computations and improves secure/private distributed computation relative to prior designs, especially BGW-based approaches.

  • LCC vs. Prior Works: LCC recovers distributed-storage and matrix multiplication results as special cases of its general theorem.The identity function yields a distributed-storage setting, while matrix-vector and matrix-matrix multiplication instantiate polynomial computation.
  • Comparison: Table I compares BGW-based designs and LCC using computation normalized by evaluating f and randomness normalized by the length of Xi.The caption defines the table’s computational-complexity and randomness normalizations.
  • LCC vs. Prior Works: LCC extends coded computing beyond prior linear and bilinear focuses to arbitrary multivariate polynomial computations arising in machine learning.Matrix-vector multiplication, matrix-matrix multiplication, and polynomial-loss gradient computation are included as special cases.
  • Secure and private computing: Compared with BGW-based designs, LCC reduces randomness, storage overhead, and computation complexity by a factor of K, while requiring more workers for the same privacy level.BGW uses KT random entries, whereas LCC uses T; each LCC worker stores one encoded datum and computes f once.
  • Secure and private computing: LCC’s one-shot approach avoids BGW’s communication round for every bilinear operation, which otherwise increases communication overhead.Conventional multi-round BGW requires Ω(log deg(f)) computation and communication rounds.

IV. LAGRANGE CODED COMPUTING

This section introduces LCC through an example illustrating its core encoding, worker computation, and recovery components.

  • IV. LAGRANGE CODED COMPUTING: The section begins by presenting an example to illustrate the key components of LCC.The formal construction proves Theorem 1 and characterizes the achievable (S, A, T) region.

A. Illustrating Example

The example partitions data into two batches and uses eight workers to demonstrate simultaneous straggler resilience, Byzantine security, and privacy.

  • Illustrating Example: With K = 2 batches and N = 8 workers, the example achieves (S, A, T) = (1, 1, 1).The inputs are two square matrix batches.
  • Encoding: LCC encodes X1, X2, and one uniformly random matrix Z using a Lagrange interpolation polynomial.Workers store evaluations u(α1), ..., u(α8) of the encoding polynomial.
  • Privacy: Each worker sees a masked linear combination of X1 and X2, providing perfect privacy against one colluding worker.The masking term is a nonzero multiple of uniformly random Z.
  • Recovery: Workers compute f(u(αj)), evaluations of the composition polynomial f(u(z)) whose degree is at most 4.The master decodes this polynomial and evaluates it at z = 1 and z = 2 to recover f(X1) and f(X2).
  • Recovery: One adversary and one straggler require three additional evaluations beyond the five needed to interpolate a degree-4 polynomial.The Reed-Solomon decoder uses two additional evaluations per adversary and one per straggler.

B. General Description

LCC encodes dataset inputs with a Lagrange interpolation polynomial, evaluates coded inputs at worker-specific points, and decodes polynomial evaluations to recover the desired outputs while preserving privacy.

  • LCC interpolates a degree-at-most K+T−1 polynomial that maps the original inputs and T random values to prescribed points.
  • Each worker receives a coded input obtained by evaluating the interpolation polynomial at a distinct worker-specific point.
  • Workers apply f to their coded inputs, giving the master evaluations of f(u(z)) that can be Reed-Solomon decoded when enough responses arrive.
  • The master evaluates the recovered polynomial at the input points to obtain f(Xi) for every dataset item.
  • LCC privacy relies on the bottom T × N encoding submatrix being MDS, so random padding masks data observed by any T colluding workers.

V. OPTIMALITY OF LCC

The paper proves that LCC attains the optimal tradeoff among straggler resiliency, adversary security, and dataset privacy under stated encoding and decoding constraints.

  • The optimality proof seeks worker lower bounds for schemes achieving specified resiliency, security, and privacy parameters.
  • The recovery threshold is the minimum number of workers required for guaranteed decodability, and privacy increases its lower bound by T · deg f.
  • LCC matches the recovery-threshold bound, thereby achieving optimum straggler resiliency for the considered multilinear computations.
  • The converse extends the recovery-threshold argument to adversaries through an extended Hamming-distance concept and to general polynomials through multilinearization.

VI. APPLICATION TO LINEAR REGRESSION AND EXPERIMENTS ON AWS EC2

The paper applies LCC to quadratic gradient computation in distributed linear regression and evaluates it against uncoded, gradient-coding, and matrix-vector-multiplication approaches on AWS EC2.

  • LCC fits linear regression because its gradient computation is a quadratic function of the input dataset.
  • The distributed implementation partitions X, stores coded sub-matrices at workers, and reconstructs X⊤Xw from the fastest responses.
  • LCC reduces the regression recovery threshold to RLCC = 2(K −1) + 1.
  • LCC codes directly on data and has a smaller recovery threshold than gradient coding and matrix-vector multiplication under the stated storage comparisons.
  • AWS EC2 experiments used Nesterov accelerated gradient descent on 40 workers across natural and artificially delayed-straggler scenarios.
  • 6.79×-13.43×: LCC speeds up the uncoded scheme; 2.36-4.29×: GC; and 1.01-12.65×: MVM.
  • When data points greatly exceed features, LCC is up to 12.65× faster than MVM because MVM communicates vectors proportional to m.

SUPPLEMENTARY MATERIAL

The supplementary material describes LCC’s encoding, worker computation, decoding, complexity, matrix structure, and an uncoded repetition variant.

  • LCC encoding generates T uniform random variables and uses fast polynomial interpolation to produce coded inputs for workers.
  • Each worker computes f on its coded input without changing the computation procedure.
  • The master waits for the fastest N−S workers and uses interpolation or Reed-Solomon decoding to recover all outputs.
  • Encoding and decoding can achieve almost linear computational complexity through fast polynomial operations and error-correction techniques.
  • The MDS property of the relevant matrix supports recovery from worker subsets and underlies the coding construction.
  • An uncoded LCC variation recovers repetition, while Shamir-based storage provides privacy but does not improve LCC.

E. Proof of Lemma 1

The proof establishes lower bounds on recovery thresholds and shows how linear encoding and multilinearity support the converse and achievability arguments for LCC.

  • Converse bound: R∗(N, K, f) is bounded below by (K −1)d + 1 when N ≥Kd −1, and by N −⌊N/K⌋+1 when N < Kd −1.The converse is proved by induction over the degree of multilinear functions.
  • Inductive reduction: The converse reduces a degree-d0+1 multilinear function to a degree-d0 function f′ that returns a linear map on its remaining input.This construction transfers a computation strategy for f into one for f′.
  • Encoding structure: Because encoding is linear, the encoding matrix has rank K, allowing a basis subset of workers to support the constructed reduced computation.The proof uses the trivial left null space of the encoding matrix to select K basis columns.
  • Decoding construction: Multilinearity lets selected workers return constant zero under specially chosen inputs, so decoding can rely on results from the remaining workers.The argument first cancels one input entry and then extends decodability to general values using orthogonal vectors.
  • Resiliency and security: An S-resilient and A-secure scheme has Hamming distance at least S + 2A + 1, connecting straggler tolerance and adversary tolerance.This distance relation supplies the converse needed for the joint resiliency-security tradeoff.
  • Non-zero reduction: The proof that f′ is non-zero uses the highest-degree terms of f and requires the field characteristic to exceed d.When all inputs are identical, equation (16) yields the highest-degree contribution multiplied by (−1)^d d! .

I. Optimality in randomness

The paper proves optimality for LCC’s randomness usage and analyzes recovery-threshold optimality for linear regression. These results establish lower bounds that LCC meets exactly or within a factor of two, under the stated settings.

  • Optimal randomness: Any linear scheme universally achieving a Theorem 1 tradeoff point for all linear functions uses at least as much randomness as LCC.The tradeoff point satisfies K + T + S + 2A = N.
  • Privacy lower bound: Information-theoretic privacy against T colluding workers requires at least T random entries in the encoding.This follows by mapping the encoding problem to a secure RAID scheme with N = n and T = z.
  • Linear-regression lower bound: For linear regression, every coded computation scheme requires at least ⌈n/r⌉ workers to decode the final result.The lower bound is derived from the rank needed to represent the input matrix through workers’ encoded sub-matrices.
  • Scope of the converse: The linear-regression converse does not rely on workers computing matrix-matrix products, because workers may compute arbitrary functions on locally stored coded sub-matrices.Accordingly, the earlier Theorem 2 converse does not apply in this more general model.
  • Linear-regression optimality: LCC achieves a recovery threshold below twice the lower bound, with RLCC = 2⌈n/r⌉ − 1 < 2R∗.The converse applies to the most general computation model, while additional requirements can yield exact optimality.

K. Complete Experimental Results

The experiments evaluate LCC, gradient coding, matrix-vector multiplication coding, and uncoded computation for distributed linear regression on Amazon EC2 clusters across three scenarios.

  • Compared schemes: Four implementations are compared: LCC, cyclic-repetition gradient coding, matrix-vector multiplication coding, and an uncoded scheme.The comparison measures linear-regression runtime on Amazon EC2 clusters.
  • Experimental scenarios: Scenarios 1 and 2 use 8000 input data points and 7000 features, while Scenario 3 uses 160000 input data points and 500 features.These settings vary the relative numbers of data points and features.
  • Straggler model: Scenarios 2 and 3 impose a 0.5-second delay on each worker with probability 5% per iteration to simulate stragglers.The experiments report detailed runtime breakdowns in Tables II, III, and IV.
  • Runtime measurement: Computation time sums the maximum local processing time among non-straggling workers over 100 iterations, while communication time is total runtime minus computation time.This decomposition separates processing and communication contributions to runtime.
Loading 1806.00939v4…