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

I Introduction

The massive size of modern datasets necessitates computational tasks to be performed in a distributed fashion, where the data is dispersed among many servers that operate in parallel . As we “scale out” computations across many servers, however, several fundamental challenges arise. Cheap commodity hardware tends to vary greatly in computation time, and it has been demonstrated that a small fraction of servers, referred to as stragglers, can be $5$ to $8$ times slower than the average, thus creating significant delays in computations. Also, as we distribute computations across many servers, massive amounts data must be moved between them to execute the computational tasks, often over many iterations of a running algorithm, and this creates a substantial bandwidth bottleneck . Distributed computing systems are also much more susceptible to adversarial servers, making security and privacy a major concern .

We consider a general scenario in which the computation is carried out distributively across several workers, and propose Lagrange Coded Computing (LCC), a new framework to simultaneously provide

resiliency against straggler workers that may prolong computations;

security against Byzantine (or malicious, adversarial) workers, with no computational restriction, that deliberately send erroneous data in order to affect the computation for their benefit; and

(information-theoretic) privacy of the dataset amidst possible collusion of workers.

LCC can be applied to any computation scenario in which the function of interest is an arbitrary multivariate polynomial of the input dataset. This covers many computations of interest in machine learning, such as various gradient and loss-function computations in learning algorithms and tensor algebraic operations (e.g., low-rank tensor approximation). The key idea of LCC is to encode the input dataset using the well-known Lagrange polynomial, in order to create computational redundancy in a novel coded form across the workers. This redundancy can then be exploited to provide resiliency to stragglers, security against malicious servers, and privacy of the dataset.

Our main result is that by carefully encoding the dataset the proposed LCC achieves $(S,A,T)$ if $(K+T-1)\deg f+S+2A+1\leq N$. The significance of this result is that by one additional worker (i.e., increasing $N$ by 1) LCC can increase the resiliency to stragglers by 1 or increase the robustness to malicious servers by $1/2$, while maintaining the privacy constraint. Hence, this result essentially extends the well-known optimal scaling of error-correcting codes (i.e., adding one parity can provide robustness against one erasure or $1/2$ error in optimal maximum distance separable codes) to the distributed secure computing paradigm.

We prove the optimality of LCC by showing that it achieves the optimal tradeoff between resiliency, security, and privacy. In other words, any computing scheme (under certain complexity constrains on the encoding and decoding designs) can achieve $(S,A,T)$ if and only if $(K+T-1)\deg f+S+2A+1\leq N$.More accurately, when $N<K\textup{deg}f-1$, we prove that the optimal tradeoff is instead given by $K(S+2A+\textup{deg}\ f\cdot T+1)\leq N$, which can be achieved by a variation of the LCC scheme, as described in Appendix D. This result further extends the scaling law in coding theory to private computing, showing that any additional worker enables data privacy against $1/\textup{deg}f$ additional colluding workers.

Finally, we specialize our general theoretical guarantees for LCC in the context of least-squares linear regression, which is one of the elemental learning tasks, and demonstrate its performance gain by optimally suppressing stragglers. Leveraging the algebraic structure of gradient computations, several strategies have been developed recently to exploit data and gradient coding for straggler mitigation in the training process (see, e.g., ). We implement LCC for regression on Amazon EC2 clusters, and empirically compare its performance with the conventional uncoded approaches, and two state-of-the-art straggler mitigation schemes: gradient coding (GC) and matrix-vector multiplication (MVM) based approaches . Our experiment results demonstrate that compared with the uncoded scheme, LCC improves the run-time by $6.79\times$-$13.43\times$. Compared with the GC scheme, LCC improves the run-time by $2.36\times$-$4.29\times$. Compared with the MVM scheme, LCC improves the run-time by $1.01\times$-$12.65\times$.

Related works. There has recently been a surge of interest on using coding theoretic approaches to alleviate key bottlenecks (e.g., stragglers, bandwidth, and security) in distributed machine learning applications (e.g., ). As we discuss in more detail in Section III-A, the proposed LCC scheme significantly advances prior works in this area by 1) generalizing coded computing to arbitrary multivariate polynomial computations, which are of particular importance in learning applications; 2) extending the application of coded computing to secure and private computing; 3) reducing the computation/communication load in distributed computing (and distributed learning) by factors that scale with the problem size, without compromising security and privacy guarantees; and 4) enabling $2.36\times$-$12.65\times$ speedup over the state-of-the-art in distributed least-squares linear regression in cloud networks.

Secure multiparty computing (MPC) and secure/private Machine Learning (e.g., ) are also extensively studied topics that address a problem setting similar to LCC. As we elaborate in Section III-A, compared with conventional methods in this area (e.g., the celebrated BGW scheme for secure/private MPC ), LCC achieves substantial reduction in the amount of randomness, storage overhead, and computation complexity.

II Problem Formulation and Examples

Resiliency, i.e., robustness against stragglers. Formally, the master must be able to obtain the correct values of $Y_{1},\ldots,Y_{K}$ even if up to $S$ workers fail to respond (or respond after the master executes the decoding algorithm), where $S$ is the resiliency parameter of the system. A scheme that guarantees resiliency against $S$ stragglers is called $S$-resilient.

Security, i.e., robustness against adversaries. That is, the master must be able to obtain correct values of $Y_{1},\ldots,Y_{K}$ even if up to $A$ workers return arbitrarily erroneous results, where $A$ is the security parameter of the system. A scheme that guarantees security against $A$ adversaries is called $A$-secure.

This framework encapsulates many computation tasks of interest, which we highlight as follows.

III Main Results and Prior Works

We now state our main results and discuss their connections with prior works. Our first theorem characterizes the region for $(S,A,T)$ that LCC achieves (i.e., the set of all feasible $S$-resilient, $A$-secure, and $T$-private schemes via LCC as defined in the previos section).

Given a number of workers $N$ and a dataset $X=(X_{1},\ldots,X_{K})$, LCC provides an $S$-resilient, $A$-secure, and $T$-private scheme for computing $\{f(X_{i})\}_{i=1}^{K}$ for any polynomial $f$, as long as

To prove Theorem 1, we formally present LCC in Section IV, which achieves the stated resiliency, security, and privacy. The key idea is to encode the input dataset using the well-known Lagrange polynomial. In particular, encoding functions (i.e., $g_{i}$’s) in LCC amount to evaluations of a Lagrange polynomial of degree $K-1$ at $N$ distinct points. Hence, computations at the workers amount to evaluations of a composition of that polynomial with the desired function $f$. Therefore, inequality (1) may simply be seen as the number of evaluations that are necessary and sufficient in order to interpolate the composed polynomial, which is later evaluated at a certain point to finalize the computation. LCC also has a number of additional properties of interest. First, the proposed encoding is identical for all computations $f$, which allows pre-encoding of the data without knowing the identity of the computing task (i.e., universality). Second, decoding and encoding rely on polynomial interpolation and evaluation, and hence efficient off-the-shelf subroutines can be used.A more detailed discussion on the coding complexities of LCC can be found in Appendix B.

Besides the coding approach presented to achieve Theorem 1, a variation of LCC can be used to achieve any $(S,A,T)$ as long as $K(S+2A+\textup{deg}\ f\cdot T+1)\leq N$. This scheme (presented in Appendix D) achieves an improved region when $N<K\textup{deg}f-1$ and $T=0$, where it recovers the uncoded repetition scheme. For brevity, we refer the better of these two scheme as LCC when presenting optimality results (i.e., Theorem 2).

Note that LHS of inequality (1) is independent of the number of workers $N$, hence the key property of LCC is that adding $1$ worker can increase its resilience to stragglers by 1 or its security to malicious servers by $1/2$, while keeping the privacy constraint $T$ the same. Note that using an uncoded replication based approach, to increase the resiliency to stragglers by 1, one needs to essentially repeat each computation once more (i.e., requiring $K$ more machines as opposed to $1$ machine in LCC). This result essentially extends the well-known optimal scaling of error-correcting codes (i.e., adding one parity can provide robustness against one erasure or $1/2$ error in optimal maximum distance separable codes) to the distributed computing paradigm.

Our next theorem demonstrates the optimality of LCC.

Theorem 2 is proved in Section V. The main proof idea is to show that any computing strategy that outperforms LCC would violate the decodability requirement, by finding two instances of the computation process where the same intermediate computing results correspond to different output values.

In addition to the result we show in Theorem 2, we can also prove that LCC achieves optimality in terms of the amount of randomness used in data encoding. Specifically, we show in Appendix I that LCC requires injecting the minimum amount of randomness, among all computing schemes that universally achieve the same resiliency-security-privacy tradeoff for all linear functions $f$.

We conclude this section by discussing several lines of related work in the literature and contrasting them with LCC.

The study of coding theoretic techniques for accelerating large scale distributed tasks (a.k.a. coded computing) was initiated in . Following works focused largely on matrix-vector and matrix-matrix multiplication (e.g., ), gradient computation in gradient descent algorithms (e.g., ), communication reduction via coding (e.g., ), and secure and private computing (e.g., ).

More importantly, LCC improves and generalizes these works on coded computing in a few aspects: Generality–LCC significantly generalizes prior works to go beyond linear and bilinear computations that have so far been the main focus in this area, and can be applied to arbitrary multivariate polynomial computations that arise in machine learning applications. In fact, many specific computations considered in the past can be seen as special cases of polynomial computation. This includes matrix-vector multiplication, matrix-matrix multiplication, and gradient computation whenever the loss function at hand is a polynomial, or is approximated by one. Universality–once the data has been coded, any polynomial up to a certain degree can be computed distributedly via LCC. In other words, data encoding of LCC can be universally used for any polynomial computation. This is in stark contrast to previous task specific coding techniques in the literature. Furthermore, workers apply the same computation as if no coding took place; a feature that reduces computational costs, and prevents ordinary servers from carrying the burden of outliers. Security and Privacy–other than a handful of works discussed above, straggler mitigation (i.e., resiliency) has been the primary focus of the coded computing literature. This work extends the application of coded computing to secure and private computing for general polynomial computations.

Providing security and privacy for multiparty computing (MPC) and Machine Learning systems is an extensively studied topic which addresses a problem setting similar to LCC. To illustrate the significant role of LCC in secure and private computing, let us consider the celebrated BGW MPC scheme . Conventionally, the BGW scheme operates in a multi-round fashion, requiring significantly more communication overhead than one-shot approaches. For simplicity of comparison, we present a modified one-shot version of BGW.

Given inputs $\{X_{i}\}_{i=1}^{K}$, BGW first uses Shamir’s scheme to encode the dataset in a privacy-preserving manner as $P_{i}(z)=X_{i}+Z_{i,1}z+\ldots+Z_{i,T}z^{T}$ for every $i\in[K]$, where $Z_{i,j}$’s are i.i.d uniformly random variables and $T$ is the number of colluding workers that should be tolerated. The key distinction between the data encoding of BGW scheme and LCC is that we instead use Lagrange polynomials to encode the data. This results in significant reduction in the amount of randomness needed in data encoding (BGW needs $KT$ $z_{i,j}$’s while as we describe in the next section, LCC only needs $T$ amount of randomness).

Hence, in overall comparison with the BGW scheme, LCC results in a factor of $K$ reduction in the amount of randomness, storage overhead, and computation complexity, while requiring more workers to guarantee the same level of privacy. This is summarized in Table I.A BGW scheme was also proposed in for secure MPC, however for a substantially different setting. Similarly, a comparison can be made by adapting it to our setting, leading to similar results, which we omit for brevity.

Recently, has also combined ideas from the BGW scheme and to form polynomial sharing, a private coded computation scheme for arbitrary matrix polynomials. However, polynomial sharing inherits the undesired BGW property of performing a communication round for every bilinear operation in the polynomial; a feature that drastically increases communication overhead, and is circumvented by the one-shot approach of LCC. DRACO is also recently proposed as a secure computation scheme for gradients. Yet, DRACO employs a blackbox approach, i.e., the resulting gradients are encoded rather than the data itself, and the inherent algebraic structure of the gradients is ignored. For this approach, shows that a $2A+1$ multiplicative factor of redundant computations is necessary. In LCC however, the blackbox approach is disregarded in favor of an algebraic one, and consequently, a $2A$ additive factor suffices.

LCC has also been recently applied to several applications in which security and privacy in computations are critical. For example, in , LCC has been applied to enable a scalable and secure approach to sharding in blockchain systems. Also, in , a privacy-preserving approach for machine learning has been developed that leverages LCC to provides substantial speedups over cyrptographic approaches that relay on MPC.

IV Lagrange Coded Computing

In this Section we prove Theorem 1 by presenting LCC and characterizing the region for $(S,A,T)$ that it achieves.For an algorithmic illustration, see Appendix A. We start with an example to illustrate the key components of LCC.

Consider the function $f(X_{i})=X_{i}^{2}$, where input $X_{i}$’s are $\sqrt{M}\times\sqrt{M}$ square matrices for some square integer $M$. We demonstrate LCC in the scenario where the input data $X$ is partitioned into $K=2$ batches $X_{1}$ and $X_{2}$, and the computing system has $N=8$ workers. In addition, the suggested scheme is $1$-resilient, $1$-secure, and $1$-private (i.e., achieves $(S,A,T)=(1,1,1)$).

Normally, a polynomial of degree $4$ can be interpolated from $5$ evaluations at distinct points. However, the presence of $A=1$ adversary and $S=1$ straggler requires the master to employ a Reed-Solomon decoder, and have three additional evaluations at distinct points (in general, two additional evaluations for every adversary and one for every straggler). Finally, after decoding polynomial $f(u(z))$, the master can obtain $f(X_{1})$ and $f(X_{2})$ by evaluating it at $z=1$ and $z=2$.

IV-B General Description

V Optimality of LCC

The proof rely on the following key lemma, which characterizes the recovery threshold of any encoding scheme, defined as the minimum number of workers that the master needs to wait to guarantee decodability.

Given any multilinear $f$, the recovery threshold of any valid linear encoding scheme, denoted by $R$, satisfies

Moreover, if the encoding scheme is $T$ private, we have $R\geq R_{\textup{LCC}}(N,K,f)+T\cdot\deg f$.

The proof of Lemma 1 can be found in Appendix E, by constructing instances of the computation process for any assumed scheme that achieves smaller recovery threshold, and proving that such scheme fails to achieve decodability in these instances. Intuitively, note that the recovery threshold is exactly the difference between $N$ and the number of stragglers that can be tolerated, inequality (1) in fact proves that LCC (described in Section IV and Appendix G) achieves the optimum resiliency, as it exactly achieves the stated recovery threshold. Similarly, one can verify that Lemma 1 essentially states that LCC achieves the optimal tradeoff between resiliency and privacy.

Assuming the correctness of Lemma 1, the two parts of Theorem 2 can be proved as follows. To prove part (a) of the converses, we need to extend Lemma 1 to also take adversaries into account. This is achieved by using an extended concept of Hamming distance, defined in for coded computing. Part (b) requires generalizing Lemma 1 to arbitrary polynomial functions, which is proved by showing that for any $f$ that achieves any $(S,T)$ pair, there exists a multilinear function with the same degree for which a computation scheme can be found to achieves the same requirement. The detailed proofs can be found in Appendices F and G respectively.

VI Application to Linear Regression and Experiments on AWS EC2

In this section we demonstrate a practical application of LCC in accelerating distributed linear regression, whose gradient computation is a quadratic function of the input dataset, hence matching well the LCC framework. We also experimentally demonstrate its performance gain over state of the arts via experiments on AWS EC2 clusters.

To run GD distributedly over a system comprising a master node and $n$ worker nodes, we first partition $\bm{X}=[\bm{X}_{1}\cdots\bm{X}_{n}]^{\top}$ into $n$ sub-matrices. Each worker stores $r$ coded sub-matrices generated from linearly combining $\bm{X}_{j}$s, for some parameter $1\leq r\leq n$. Given the current weight $\bm{w}$, each worker performs computation using its local storage, and sends the result to the master. Master recovers $\bm{X}^{\top}\bm{X}\bm{w}=\sum_{j=1}^{n}\bm{X}_{j}\bm{X}_{j}^{\top}\bm{w}$ using the results from a subset of fastest workers.Since the value of $\bm{X}^{\top}\bm{y}$ does not vary across iterations, it only needs to be computed once. We assume that it is available at the master for weight updates. To measure performance of any linear regression scheme, we consider the metric recovery threshold (denoted by $R$), defined as the minimum number of workers the master needs to wait for, to guarantee decodability (i.e., tolerating the remaining stragglers).

We cast this gradient computation to the computing model in Section II, by grouping the sub-matrices into $K\!\!=\!\!\lceil\frac{n}{r}\rceil$ blocks such that $\bm{X}=[\bar{\bm{X}}_{1}\cdots\bar{\bm{X}}_{K}]^{\top}$. Then computing $\bm{X}\bm{X}^{\top}\bm{w}$ reduces to computing the sum of a degree-$2$ polynomial $f(\bar{\bm{X}}_{k})=\bar{\bm{X}}_{k}\bar{\bm{X}}_{k}^{\top}\bm{w}$, evaluated over $\bar{\bm{X}}_{1},\ldots,\bar{\bm{X}}_{K}$. Now, we can use LCC to decide on the coded storage as in (2), and achieve a recovery threshold of $R_{\textup{LCC}}=2(K-1)+1=2\lceil\tfrac{n}{r}\rceil-1$ (Theorem 1).This recovery threshold is also optimum within a factor of $2$, as we proved in Appendix J.

Comparisons with state of the arts. The conventional uncoded scheme picks $r=1$, and has each worker $j$ compute $\bm{X}_{j}\bm{X}_{j}^{\top}\bm{w}$. Master needs result from each work, yielding a recovery threshold of $R_{\textup{uncoded}}=n$. By redundantly storing/processing $r>1$ uncoded sub-matrices at each worker, the “gradient coding” (GC) methods code across partial gradients computed from uncoded data, and reduce the recovery threshold to $R_{\textup{GC}}=n-r+1$. An alternative “matrix-vector multiplication based” (MVM) approach requires two rounds of computation. In the first round, an intermediate vector $\bm{z}=\bm{X}\bm{w}$ is computed distributedly, which is re-distributed to the workers in the second round for them to collaboratively compute $\bm{X}^{\top}\bm{z}$. Each worker stores coded data generated using MDS codes from $\bm{X}$ and $\bm{X}^{\top}$ respectively. MVM achieves a recovery threshold of $R_{\textup{MVM}}=\lceil\frac{2n}{r}\rceil$ in each round, when the storage is evenly split between rounds.

Compared with GC, LCC codes directly on data, and reduces the recovery threshold by about $r/2$ times. While the amount of computation and communication at each worker is the same for GC and LCC, LCC is expected to finish much faster due to its much smaller recovery threshold. Compared with MVM, LCC achieves a smaller recovery threshold than that in each round of MVM (assuming even storage split). While each MVM worker performs less computation in each iteration, it sends two vectors whose sizes are respectively proportional to $m$ and $d$, whereas each LCC worker only sends one dimension-$d$ vector.

We run linear regression on AWS EC2 using Nesterov’s accelerated gradient descent, where all nodes are implemented on t2.micro instances. We generate synthetic datasets of $m$ data points, by 1) randomly sampling a true weight $\bm{w}^{*}$, 2) randomly sampling each input $\bm{x}_{i}$ of $d$ features and computing its output $y_{i}=\bm{x}_{i}^{\top}\bm{w}^{*}$. For each dataset, we run GD for $100$ iterations over $n=40$ workers. We consider different dimensions of input matrix $\bm{X}$ as listed in the following scenarios.

We let the system run with naturally occurring stragglers in scenario 1. To mimic the effect of slow/failed workers, we artificially introduce stragglers in scenarios 2 and 3, by imposing a $0.5$ seconds delay on each worker with probability $5\%$ in each iteration.

To implement LCC, we set the $\beta_{i}$ parameters to $1,...,\frac{n}{r}$, and the $\alpha_{i}$ parameters to $0,\ldots,n-1$. To avoid numerical instability due to large entries of the decoding matrix, we can embed input data into a large finite field, and apply LCC in it with exact computations. However in all of our experiments the gradients are calculated correctly without carrying out this step.

Results. For GC and LCC, we optimize the total run-time over $r$ subject to local memory size. For MVM, we further optimize the run-time over the storage assigned between two rounds of matrix-vector multiplications. We plot the measured run-times in Figure 2, and list the detailed breakdowns of all scenarios in Appendix K.

We draw the following conclusions from experiments.

LCC achieves the least run-time in all scenarios. In particular, LCC speeds up the uncoded scheme by $6.79\times$-$13.43\times$, the GC scheme by $2.36$-$4.29\times$, and the MVM scheme by $1.01$-$12.65\times$.

In scenarios 1 & 2 where the number of inputs $m$ is close to the number of features $d$, LCC achieves a similar performance as MVM. However, when we have much more data points in scenario 3, LCC finishes substantially faster than MVM by as much as $12.65\times$. The main reason for this subpar performance is that MVM requires large amounts of data transfer from workers to the master in the first round and from master to workers in the second round (both are proportional to $m$). However, the amount of communication from each worker or master is proportional to $d$ for all other schemes, which is much smaller than $m$ in scenario 3.

Acknowledgement

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. M. Soltanolkotabi is supported by the Packard Fellowship in Science and Engineering, a Sloan Research Fellowship in Mathematics, an NSF-CAREER under award #1846369, the Air Force Office of Scientific Research Young Investigator Program (AFOSR-YIP) under award #FA9550-18-1-0078, an NSF-CIF award #1813877, and a Google faculty research award. Qian Yu is supported by the Google PhD Fellowship.

References

Supplementary Material

$\{\alpha_{i}\}_{i\in[N]}\cap\{\beta_{j}\}_{j\in[K]}=\varnothing$ (this requirement is alleviated if $T=0$).

B Coding Complexities of LCC

Finally, note that the adversaries can only affect a fixed subset of $A$ workers’ results for all entries. This decoding time can be further reduced by computing the final outputs entry-wise: for each iteration, ignore computing results from adversaries identified in earlier steps, and proceed decoding with the rest of the results.

The matrix $U^{bottom}$ is an MDS matrix.

To show that $U^{bottom}$ is an MDS matrix, it is shown that $U^{bottom}$ can be obtained from $V$ by multiplying rows and columns by nonzero scalars. Let $[T:K]\triangleq\{T+1,T+2,\ldots,T+K\}$, and notice that for $(s,r)\in[T]\times[N]$, entry $(s,r)$ of $U^{bottom}$ can be written as

where $V$ is a $T\times N$ matrix such that

Since $\{\beta_{t}\}_{t=1}^{K}\cap\{\alpha_{r}\}_{r=1}^{N}=\varnothing$, and since all the $\beta_{i}$’s are distinct, it follows from (C) that $U^{bottom}$ can be obtained from $V$ by multiplying each row and each column by a nonzero element, and hence $U^{bottom}$ is an MDS matrix as well. ∎

D The Uncoded Version of LCC

In Section IV-B, we have described the LCC scheme, which provides an $S$-resilient, $A$-secure, and $T$-private scheme as long as $(K+T-1)\deg f+S+2A+1\leq N$. Instead of explicitly following the same construction, a variation of LCC can be made by instead selecting the values of $\alpha_{i}$’s from the set $\{\beta_{j}\}_{j\in[K]}$ (not necessarily distinctly).

We refer to this approach as the uncoded version of LCC, which essentially recovers the uncoded repetition scheme, which simply replicates each $X_{i}$ onto multiple workers. By replicating every $X_{i}$ between $\lfloor N/K\rfloor$ and $\lceil N/K\rceil$ times, it can tolerate at most $S$ stragglers and $A$ adversaries, whenever

which achieves the optimum resiliency and security when the number of workers is small and no data privacy is required (specifically, $N<K\deg f-1$ and $T=0$, see Section V).

When privacy is taken into account (i.e., $T>0$), an alternative approach in place of repetition is to instead store each input variable using Shamir’s secret sharing scheme over $\lfloor N/K\rfloor$ to $\lceil N/K\rceil$ machines. This approach achieves any $(S,A,T)$ tuple whenever $N\geq K(S+2A+\textup{deg}\ f\cdot T+1)$. However, it does not improve LCC.

E Proof of Lemma 1

Without loss of generality, we assume both the encoding and decoding functions are deterministic in this proof, as the randomness does not help with decodability.Note that this argument requires the assumption that the decoder does not have access to the random keys, as assumed in Section II. Similar to , we define the minimum recovery threshold, denoted by $R^{*}(N,K,f)$, as the minimum number of workers that the master has to wait to guarantee decodability, among all linear encoding schemes. Then we essentially need to prove that $R^{*}(N,K,f)\geq R^{*}_{\textup{LCC}}(N,K,f)$, i.e., $R^{*}(N,K,f)\geq(K-1)d+1$ when $N\geq Kd-1$, and $R^{*}(N,K,f)\geq N-\lfloor N/K\rfloor+1$ when $N<Kd-1$.

Obviously $R^{*}(N,K,f)$ is a non-decreasing function with respect to $N$. Hence, it suffices to prove that $R^{*}(N,K,f)\geq N-\lfloor N/K\rfloor+1$ when $N\leq Kd-1$. We prove this converse bound by induction.

(a) If $d=1$, then $f$ is a linear function, and we aim to prove $R^{*}(N,K,f)\geq N+1$ for $N\leq K-1$. This essentially means that no valid computing schemes can be found when $N<K$. Assuming the opposite, suppose we can find a valid computation design using at most $K-1$ workers, then there is a decoding function that computes all $f(X_{i})$’s given the results from these workers.

(b) Suppose we have a matching converse for any multilinear function with $d=d_{0}$. We now prove the lower bound for any multilinear function $f$ of degree $d_{0}+1$. Similar to part (a), it is easy to prove that $R^{*}(N,K,f)\geq N+1$ for $N\leq K-1$. Hence, we focus on $N\geq K$.

The proof idea is to construct a multilinear function $f^{\prime}$ with degree $d_{0}$ based on function $f$, and to lower bound the minimum recovery threshold of $f$ using that of $f^{\prime}$. More specifically, this is done by showing that given any computation design for function $f$, a computation design can also be developed for the corresponding $f^{\prime}$, which achieves a recovery threshold that is related to that of the scheme for $f$.

In particular, for any non-zero function $f(X_{i,1},X_{i,2},...,X_{i,d_{0}+1})$, we let $f^{\prime}$ be a function which takes inputs $X_{i,1},X_{i,2},...,X_{i,d_{0}}$ and returns a linear map, such that given any $X_{i,1},X_{i,2},...,X_{i,d_{0}+1}$, we have $f^{\prime}(X_{i,1},X_{i,2},...,X_{i,d_{0}})(X_{i,d_{0}+1})=f(X_{i,1},X_{i,2},...,X_{i,d_{0}+1})$. One can verify that $f^{\prime}$ is a multilinear function with degree $d_{0}$, Given parameters $K$ and $N$, we now develop a computation strategy for $f^{\prime}$ for a dataset of $K$ inputs and a cluster of $N^{\prime}\triangleq N-K$ workers, which achieves a recovery threshold of $R^{*}(N,K,f)-(K-1)$. We construct this computation strategy based on an encoding strategy of $f$ that achieves the recovery threshold $R^{*}(N,K,f)$. For brevity, we refer to these two schemes as the $f^{\prime}$-scheme and $f$-scheme respectively.

To summarize, we have essentially proved that $R^{*}(N,K,f)-(K-1)\geq R^{*}(N-K,K,f^{\prime})$. We can verify that the converse bound $R^{*}(N,K,f)\geq N-\lfloor N/K\rfloor+1$ under the condition $N\leq Kd-1$ can be derived given the above result and the induction assumption, for any function $f$ with degree $d_{0}+1$.

Now we proceed to prove the rest of Lemma 1, explicitly, we aim to prove that the recovery threshold of any $T$-private encoding scheme is at least $R_{\textup{LCC}}(N,K,f)+T\cdot\deg f$. Inequality (1) essentially covers the case for $T=0$. Hence, we focus on $T>0$. To simplify the proof, we prove a stronger version of this statement: when $T>0$, any valid $T$-private encoding scheme uses at least $N\geq R_{\textup{LCC}}(N,K,f)+T\cdot\deg f$ workers. Equivalently, we aim to show that $N\geq(K+T-1)\deg f+1$ for any such scheme.

We prove this fact using an inductive approach. To enable an inductive structure, we prove a even stronger converse by considering a more general class of computing tasks and a larger class of encoding schemes, formally stated in the following lemma.

Lemma 3 is proved by induction with respect to the tuple $(d,T,r)$. Specifically, we prove that (a) Lemma 3 holds when $(d,T,r)=(0,0,1)$; (b) If Lemma 3 holds for any $(d,T,r)=(d_{0},0,r_{0})$, then it holds when $(d,T,r)=(d_{0},0,r_{0}+1)$; (c) If Lemma 3 holds for any $(d,T,r)=(d_{0},0,r_{0})$, then it holds when $(d,T,r)=(d_{0},T,r_{0})$ for any $T$; (d) If Lemma 3 holds for any $d=d_{0}$ and arbitrary values of $T$ and $r$, then it holds if $(d,T,r)=(d_{0}+1,0,1)$. Assuming the correctness of these statements, Lemma 3 directly follows by induction’s principle. Now we provide the proof of these statements as follows.

(a). When $(d,T,r)=(0,0,1)$, we need to show that at least $1$ worker is needed. This directly follows from the decodability requirement, because the master aims to recover a variable, and at least one variable is needed to provide the information.

For case (i), similar to the ideas we used to prove inequality (1), it suffices to show that if the given computing scheme uses $N$ workers, we can construct another computation scheme achieving the same $T_{X}$, for a different computing task with parameters $d=d_{0}$ and $r=r_{0}$, using at most $N-1$ workers.

Now for any $k\in[m]$, we can restrict the value of $\Gamma$ to a subspace with dimension $r_{0}$, such that $\Gamma_{j}$ is zero for any $j\in\mathcal{J}_{k}$. After applying this operation, from the computation results of workers in $[N]\backslash\mathcal{I}_{k}$, the master can recover a computing function with $r=r_{0}$, where $K^{\prime}=K-|\mathcal{J}_{k}|$ sub-functions has non-zero $\Gamma_{j}$’s. By applying the induction assumption on this provided computing scheme, we have $N-|\mathcal{I}_{k}|\geq(T_{\textup{X}}+K-|\mathcal{J}_{k}|-1)d_{0}+r_{0}$. By taking the summation of the this inequality over $k\in[m]$, we have

Note that $r_{0}+1>1$, which implies that at least two ${\Gamma}_{j}$’s are not identical up to a constant factor. Hence, $m-1>0$, and (8) is equivalently

Since $T_{\textup{X}}$ and $r_{0}$ are both positive, we have $(T_{\textup{X}}-1)d_{0}+r_{0}>0$. Consequently, $\left((T_{\textup{X}}-1)d_{0}+r_{0}\right)\frac{1}{m-1}>0$, and we have

(c). Assuming that for any $(d,T,r)=(d_{0},0,r_{0})$, any valid computing scheme requires $N\geq(T_{\textup{X}}+K-1)d_{0}+r_{0}$ workers, we need to prove that for $(d,T,r)=(d_{0},T_{0},r_{0})$, $N\geq(T_{\textup{X}}+K-1)d_{0}+T_{0}+r_{0}$. Equivalently, we aim to show that for any $T_{0}>0$, in order to provide $T_{0}$-privacy to the $d_{0}+1$th entry, $T_{0}$ extra worker is needed. Similar to the earlier steps, we consider an arbitrary valid computing scheme for $(d,T,r)=(d_{0},T_{0},r_{0})$ that uses $N$ workers. We aim to construct a new scheme for $(d,T,r)=(d_{0},0,r_{0})$, for the same computation task and the same $T_{\textup{X}}$, which uses at most $N-T_{0}$ workers.

(d). Assuming that for any $d=d_{0}$ and arbitrary values of $T$ and $r$, any valid computing scheme requires $N\geq(T_{\textup{X}}+K-1)d_{0}+T+r$ workers, we need to prove that for $(d,T,r)=(d_{0}+1,0,1)$, $N\geq(T_{\textup{X}}+K-1)(d_{0}+1)+1$. Observing that for any computing task with $r=1$, by fixing an non-zero $\Gamma$, it essentially computes $K$ functions where each multiplies $d_{0}$ variables. Moreover, for each function, by viewing the first $(d_{0}-1)$ entries as a vector $X^{\prime}_{i}$ and by viewing the last entry as a scalar $\Gamma^{\prime}_{i}$, it essentially recovers the case where the parameter $d$ is reduced by $1$, $K$ remain unchanged, and $r$ equals $K$. By adapting any computing scheme in the same way, we have $T_{\textup{X}}$ remain unchanged, and $T$ becomes $T_{\textup{X}}$. Then by induction assumption, any computing scheme for $(d,T,r)=(d_{0}+1,0,1)$ requires at least $(T_{\textup{X}}+K-1)d_{0}+T_{\textup{X}}+K=(T_{\textup{X}}+K-1)(d_{0}+1)+1$ workers. ∎

Using exactly the same arguments, Lemma 3 can be extended to the case where the entries of $X$ are encoded under different privacy requirements. Specifically, if the $i$th entry is $T_{i}$-privately encoded, then at least $\sum_{i=1}^{d}T_{i}+(K-1)d+T+r$ worker is needed. Lemma 3 and this extended version are both tight, in the sense for any parameter values of $d$, $K$ and $r$, there are computing tasks where a computing scheme that uses the matching number of workers can be found, using constructions similar to the Lagrange coded computing.

Now using Lemma 3, we complete the proof of Lemma 1 for $T>0$. Similar to the proof ideas for inequality (1) part (a), we consider any multilinear function $f$ with degree $d$, and we find constant vectors $V_{1},...,V_{d}$, such that $f(V_{1},...,V_{d})$ is non-zero. Then by restricting the input variables to be constant multiples of $V_{1},...,V_{d}$, this computing task reduces to multiplying $d$ scalars, given $K$ inputs. As stated in Lemma 3 and discussed in part (d) of its induction proof, such computation requires $(T+K-1)d+1$ workers. This completes the proof of Lemma 1.

F Optimality on the Resiliency-Security-Privacy Tradeoff for Multilinear Functions

In this appendix, we prove the first part of Theorem 2 using Lemma 1. Specifically, we aim to prove that LCC achieves the optimal trade-off between resiliency, security, and privacy for any multilinear function $f$. By comparing Lemma 1 and the achievability result presented in Theorem 1 and Appendix D, we essentially need to show that for any linear encoding scheme that can tolerates $A$ adversaries and $S$ stragglers, it can also tolerate $S+2A$ stragglers.

This converse can be proved by connecting the straggler mitigation problem and the adversary tolerance problem using the extended concept of Hamming distance for coded computing, which is defined in . Specifically, given any (possibly random) encoding scheme, its hamming distance is defined as the minimum integer, denoted by $d$, such that for any two instances of input $X$ whose outputs $Y$ are different, and for any two possible realizations of the $N$ encoding functions, the computing results given the encoded version of these two inputs, using the two lists of encoding functions respectively, differs for at least $d$ workers.

It was shown in that this hamming distance behaves similar to its classical counter part: an encoding scheme is $S$-resilient and $A$-secure whenever $S+2A\leq d-1$. Hence, for any encoding scheme that is $A$-secure and $S$-reselient, it has a hamming distance of at least $S+2A+1$. Consequently it can tolerate $S+2A$ stragglers. Combining the above and Lemma 1, we have completed the proof.

G Optimality on the Resiliency-Privacy Tradeoff for General Multivariate Polynomials

In this appendix, we prove the second part of Theorem 2 using Lemma 1. Specifically, we aim to prove that LCC achieves the optimal trade-off between resiliency and privacy, for general multivariate polynomial $f$. The proof is carried out by showing that for any function $f$ that allows $S$-resilient $T$-private designs, there exists a multilinear function with the same degree for which a computation scheme can be found that achieves the same requirement.

Specifically, given any function $f$ with degree $d$, we aim to provide an explicit construction of an multilinear function, denoted by $f^{\prime}$, which achieves the same requirements. The construction satisfies certain properties to ensure this fact. Both the construction and the properties are formally stated in the following lemma (which is proved in Appendix H):

Assuming the correctness of Lemma 4, it suffices to prove that $f^{\prime}$ enables computation designs that tolerates at least the same number of stragglers, and provides at least the same level of data privacy, compared to that of $f$. We prove this fact by constructing such computing schemes for $f^{\prime}$ given any design for $f$.

Note that $f^{\prime}$ is defined as a linear combination of functions $f(\sum_{j\in\mathcal{S}}Z_{j})$, each of which is a composition of a linear map and $f$. Given the linearity of the encoding design, any computation scheme of $f$ can be directly applied to any of these functions, achieving the same resiliency and privacy requirements. Since the decoding functions are linear, the same scheme also applies to linear combinations of them, which includes $f^{\prime}$. Hence, the resiliency-privacy tradeoff achievable for $f$ can also be achieved by $f^{\prime}$. This concludes the proof.

H Proof of Lemma 4

We first prove that $f^{\prime}$ is multilinear with respect to the $d$ inputs. Recall that by definition, $f$ is a linear combination of monomials, and $f^{\prime}$ is constructed based on $f$ through a linear operation. By exploiting the commutativity of these these two linear relations, we only need to show individually that each monomial in $f$ is transformed into a multilinear function.

Then by viewing each subset $\mathcal{S}$ of $[d]$ as a map from $[d]$ to $\{0,1\}$, we haveHere we define $0^{0}=1$.

Recall that $f^{\prime}$ is a linear combination of $h^{\prime}_{k}$’s. Consequently, it is a multilinear function.

I Optimality in randomness

In this appendix, we prove the optimality of LCC in terms of the amount of randomness needed in data encoding, which is formally stated in the following theorem.

(Optimal randomness) Any linear encoding scheme that universally achieves a same tradeoff point specified in Theorem 1 for all linear functions $f$ (i.e., $(S,A,T)$ such that $K+T+S+2A=N$) must use an amount of randomness no less than that of LCC.

J Optimality of LCC for Linear Regression

In this section, we prove that the proposed LCC scheme achieves the minimum possible recovery threshold $R^{*}$ to within a factor of 2, for the linear regression problem discussed in Section 6.

As the first step, we prove a lower bound on $R^{*}$ for linear regression. More specifically, we show that for any coded computation scheme, the master always needs to wait for at least $\lceil\frac{n}{r}\rceil$ workers to be able to decode the final result, i.e., $R^{*}\geq\lceil\frac{n}{r}\rceil$. Before starting the proof, we first note that since here we consider a more general scenario where workers can compute any function on locally stored coded sub-matrices (not necessarily matrix-matrix multiplication), the converse result in Theorem 2 no longer holds.

To prove the lower bound, it is equivalent to show that, for any coded computation scheme and any subset $\mathcal{N}$ of workers, if the master can recover $\bm{X}^{\top}\bm{X}\bm{w}$ given the results from workers in $\mathcal{N}$, then we must have $|\mathcal{N}|\geq\lceil\frac{n}{r}\rceil$. Suppose the condition in the above statement holds, then we can find encoding, computation, and decoding functions such that for any possible values of $\bm{X}$ and $\bm{w}$, the composition of these functions returns the correct output.

Note that within a GD iteration, each worker performs its local computation only based on its locally stored coded sub-matrices and the weight vector $\bm{w}$. Hence, if the master can decode the final output from the results of the workers in a subset $\mathcal{N}$, then the composition of the decoding function and the computation functions of these workers essentially computes $\bm{X}^{\top}\bm{X}\bm{w}$, using only the coded sub-matrices stored at these workers and the vector $\bm{w}$. Hence, if any class of input values $\bm{X}$ gives the same coded sub-matrices for each worker in $\mathcal{N}$, then the product $\bm{X}^{\top}\bm{X}\bm{w}$ must also be the same given any $\bm{w}$.

Now we consider the class of input matrices $\bm{X}$ such that all coded sub-matrices stored at workers in $\mathcal{N}$ equal the values of the corresponding coded sub-matrices when $\bm{X}$ is zero. Since $\bm{0}^{\top}\bm{0}\bm{w}$ is zero for any $\bm{w}$, $\bm{X}^{\top}\bm{X}\bm{w}$ must also be zero for all matrices $\bm{X}$ in this class and any $\bm{w}$. However, for real matrices $\bm{X}=\bm{0}$ is the only solution to that condition. Thus, zero matrix must be the only input matrix that belongs to this class.

Recall that all the encoding functions are assumed to be linear. We consider the collection of all encoding functions that are used by workers in $\mathcal{N}$, which is also a linear map. As we have just proved, the kernel of this linear map is $\{\bm{0}\}$. Hence, its rank must be at least the dimension of the input matrix, which is $dm$. On the other hand, its rank is upper bounded by the dimension of the output, where each encoding function from a worker contributes at most $\frac{rdm}{n}$. Consequently, the number of workers in $\mathcal{N}$ must be at least $\lceil\frac{n}{r}\rceil$ to provide sufficient rank to support the computation.

Having proved that $R^{*}\geq\lceil\frac{n}{r}\rceil$, the factor of two characterization of LCC directly follows since $R^{*}\leq R_{\textup{LCC}}=2\lceil\tfrac{n}{r}\rceil-1<2\lceil\frac{n}{r}\rceil\leq 2R^{*}$.

Note that the converse bound proved above applies to the most general computation model, i.e., there are no assumptions made on the encoding functions or the functions that each worker computes. If additional requirements are taken into account, we can show that LCC achieves the exact optimum recovery threshold (e.g., see ).

K Complete Experimental Results

In this section, we present the complete experimental results using the LCC scheme proposed in the paper, the gradient coding (GC) scheme (the cyclic repetition scheme), the matrix-vector multiplication based (MVM) scheme , and the uncoded scheme for which there is no data redundancy across workers, measured from running linear regression on Amazon EC2 clusters.

In particular, experiments are performed for the following 3 scenarios.

Scenario 1 & 2: # of input data point $m=8000$, # of features $d=7000$.

Scenario 3: # of input data point $m=160000$, # of features $d=500$.

In scenarios 2 and 3, we artificially introduce stragglers by imposing a $0.5$ seconds delay on each worker with probability $5\%$ in each iteration.

We list the detailed breakdowns of the run-times in 3 experiment scenarios in Tables II, III, and IV respectively. In particular, the computation (comp.) time is measured as the summation of the maximum local processing time among all non-straggling workers, over 100 iterations. The communication (comm.) time is computed as the difference between the total run-time and the computation time.