1

Straggler Mitigation in Distributed Matrix Multiplication:
Fundamental Limits and Optimal Coding
∗

Qian Yu∗ , Mohammad Ali Maddah-Ali† , and A. Salman Avestimehr∗
Department of Electrical Engineering, University of Southern California, Los Angeles, CA, USA
† Nokia Bell Labs, Holmdel, NJ, USA

We consider the problem of massive matrix multiplication, which underlies many data analytic applications, in a large-scale
distributed system comprising a group of worker nodes. We target the stragglers’ delay performance bottleneck, which is due to
the unpredictable latency in waiting for slowest nodes (or stragglers) to finish their tasks. We propose a novel coding strategy,
named entangled polynomial code, for designing the intermediate computations at the worker nodes in order to minimize the
recovery threshold (i.e., the number of workers that we need to wait for in order to compute the final output). We demonstrate the
optimality of entangled polynomial code in several cases, and show that it provides orderwise improvement over the conventional
schemes for straggler mitigation. Furthermore, using bilinear complexity, we characterize the optimal recovery threshold among
all linear coding strategies within a factor of 2. In particular, while evaluating bilinear complexity is a well-known challenging
problem, we show that optimal recovery threshold for linear coding strategies can be approximated within a factor of 2 of this
fundamental quantity. Finally, we show that the techniques developed in this paper can also be extended to several other problems
such as coded convolution and fault tolerance computing, leading to tight characterizations.

I. I NTRODUCTION
Matrix multiplication is one of the key operations underlying many data analytics applications in various fields such as
machine learning, scientific computing, and graph processing. Many such applications require processing terabytes or even
petabytes of data, which needs massive computation and storage resources that cannot be provided by a single machine. Hence,
deploying matrix computation tasks on large-scale distributed systems has received wide interests [1]–[4].
There is, however, a major performance bottleneck that arises as we scale out computations across many distributed nodes:
stragglers’ delay bottleneck, which is due to the unpredictable latency in waiting for slowest nodes (or stragglers) to finish
their tasks [5]. The conventional approach for mitigating straggler effects involves injecting some form of “computation
redundancy" such as repetition (e.g., [6]). Interestingly, it has been shown recently that coding theoretic concepts can also play
a transformational role in this problem, by efficiently creating “computational redundancy” to mitigate the stragglers [7]–[10].

...

arXiv:1801.07487v1 [cs.IT] 23 Jan 2018

Abstract

Fig. 1: Overview of the distributed matrix multiplication problem. Each worker computes the product of the two stored encoded submatrices
(Ãi and B̃i ) and returns the result to the master. By carefully designing the coding strategy, the master can decode the multiplication result
of the input matrices from a subset of workers, without having to wait for stragglers (worker 1 in this example).

In this paper, we consider a general formulation of distributed matrix multiplication, study information-theoretic limits, and
develop optimal coding designs for straggler effect mitigation. We consider the canonical master-worker distributed setting,
where a group of N workers aim to collaboratively compute the product of two large matrices A and B, and return the result
C = A| B to the master. As shown in Figure 1, the two input matrices are partitioned (arbitrarily) into p-by-m and p-by-n
blocks of submatrices respectively, where all submatrices within the same input are of equal size. Each worker has a local
memory that can be used to store any coded function of each matrix, denoted by Ãi ’s and B̃i ’s, each with a size equal to that
of the corresponding submatrices. The workers then multiply their two stored (coded) submatrices and return the results to

2

the master. By carefully designing the coding functions, the master can decode the final result without having to wait for the
slowest workers, which providing robustness against stragglers.
Note that by allowing different values of parameters p, m, and n, we allow flexible partitioning of input matrices, which in
return enables different utilization of system resources (i.e., the required amount of storage at each worker and the amount of
communication from worker to master). Hence, considering the system constraints on available storage and communication
resources, one can choose p, m, and n accordingly. We aim to find optimal coding and computation designs for any choice of
parameters p, m and n, to provide optimum straggler effect mitigation for various situations.
With a careful design of the coded submatrices Ãi and B̃i at each worker, the master only needs results from the fastest
workers before it can recover the final output, which effectively mitigates straggler issues. To measure the robustness against
straggler effects of a given coding strategy, we use the metric recovery threshold, defined previously in [10], which is equal to
the minimum number of workers that the master needs to wait for in order to compute the output C. Given this terminology,
our main problem is as follows: What is the minimum possible recovery threshold and the corresponding coding scheme, for
any choice of parameters p, m, n, and N ?
We propose a novel coding technique, referred to as entangled polynomial code, which achieves the recovery threshold of
pmn + p − 1 for all possible parameter values. The construction of the entangled polynomial code is based on the observation
that when multiplying an m-by-p matrix and a p-by-n matrix, we essentially evaluate a subspace of bilinear functions, spanned
by the pairwise product of the elements from the two matrices. Although potentially there are a total of p2 mn pairs of elements,
at most pmn pairs are directly related to the matrix product, which is an order of p less. The particular structure of the proposed
code entangles the input matrices to the output such that the system almost avoids unnecessary multiplications and achieves a
recovery threshold in the order of pmn, while allowing robust straggler mitigation for arbitrarily large systems. This allows
orderwise improvement upon conventional uncoded approaches, random linear codes, and MDS-coding type approaches for
straggler mitigation [7], [8].
Entangled polynomial code generalizes our previously proposed polynomial code for distributed matrix multiplication [10],
which was designed for the special case of p = 1 (i.e., allowing only column-wise partitioning of matrices A and B). However,
as we move to arbitrary partitioning of the input matrices (i.e., arbitrary values of m, n, and p), a key challenge is to design
the coding strategy at each worker such that its computation best aligns with the final computation C. In particular, to recover
the product C, the master needs mn components that each involve summing p products of submatrices of A and B. Entangled
polynomial code effectively aligns the workers’ computations with the master’s need, which is its key distinguishing feature
from polynomial code.
We show that entangled polynomial code achieves the optimal recovery threshold among all linear coding strategies in the
cases of m = 1 or n = 1. It also achieves the optimal recovery threshold among all possible schemes within a factor of 2 when
m = 1 or n = 1.
Furthermore, for all partitionings of input matrices (i.e., all values of p, m, n, and N ), we characterize the optimal recovery
threshold among all linear coding strategies within a factor of 2 of R(p, m, n), which denotes the bilinear complexity of
multiplying an m-by-p matrix to a p-by-n matrix (see Definition 3 later in the paper). While evaluating bilinear complexity is a
well-known challenging problem in the computer science literature (see [11]), we show that the optimal recovery threshold for
linear coding strategies can be approximated within a factor of 2 of this fundamental quantity.
We establish this result by constructing a computation strategy, which achieves a recovery threshold of 2R(p, m, n) − 1 using
a variation of the entangled polynomial code. Specifically, this coding construction exploits the fact that any matrix multiplication
problem can be converted into a problem of computing the element-wise product of two arrays of length R(p, m, n). Then we
show that this augmented computing task can be optimally handled using a variation of the entangled polynomial code, and the
corresponding optimal code achieves the recovery threshold 2R(p, m, n) − 1.
Finally, we show that the coding construction and converse bounding techniques developed for proving the above results
can also be directly extended to several other problems. For example, we show that the converse bounding technique can be
extended to the problem of coded convolution, which was originally considered in [12]. We prove that the state-of-the-art
scheme we proposed in [10] for this problem is in fact optimal among all linear coding schemes. These techniques can also
be applied in the context of fault tolerance computing, where we provide tight characterizations on the maximum number of
detectable or correctable errors.
II. S YSTEM M ODEL AND P ROBLEM F ORMULATION
We consider a problem of matrix multiplication with two input matrices A ∈ Fs×r and B ∈ Fs×t , for some integers r, s, t
and a sufficiently large field F.1 We are interested in computing the product C , A| B in a distributed computing environment
1
1
with a master node and N worker nodes, where each worker can store pm
fraction of A and pn
fraction of B, based on some
integer parameters p, m, and n (see Fig. 1).
1 Here

we consider the general class of fields, which includes finite fields, the field of real numbers, and the field of complex numbers.

3

s

r

s

t

Specifically, each worker i can store two coded matrices Ãi ∈ F p × m and B̃i ∈ F p × n , computed based on A and B
respectively. Each worker can compute the product C̃i , Ã|i B̃i , and return it to the master. The master waits only for the
results from a subset of workers before proceeding to recover the final output C using certain decoding functions.
Given the above system model, we formulate the distributed matrix multiplication problem based on the following terminology:
We define the computation strategy as a collection of 2N encoding functions, denoted by
f = (f0 , f1 , ..., fN −1 ),

g = (g0 , g1 , ..., gN −1 ),

(1)

that are used by the workers to compute each Ãi and B̃i , and a class of decoding functions, denoted by
d = {dK }K⊆{0,1,...,N −1} ,

(2)

that are used by the master to recover C given results from any subset K of the workers. Each worker i stores matrices
Ãi = fi (A),

B̃i = gi (B),

(3)

and the master can compute an estimate Ĉ of matrix C using results from a subset K of the workers by computing


Ĉ = dK {C̃i }i∈K .

(4)

For any integer k, we say a computation strategy is k-recoverable if the master can recover C given the computing results
from any k workers. Specifically, a computation strategy is k-recoverable if for any subset K of k users, the final output Ĉ
from the master equals C for all possible input values. We define the recovery threshold of a computation strategy, denoted by
K(f , g, d), as the minimum integer k such that computation strategy (f , g, d) is k-recoverable.
We aim to find a computation strategy that requires the minimum possible recovery threshold and allows efficient decoding
at the master. Among all possible computation strategies, we are particularly interested in a certain class of designs, referred to
as the linear codes and defined as follows:
Definition 1. For a distributed matrix multiplication problem of computing A| B using N workers, we say a computation
strategy is a linear code given parameters p, m, and n, if there is a partitioning of the input matrices A and B where each
matrix is divided into the following submatrices of equal sizes


A0,0
A0,1
···
A0,m−1
 A1,0
A1,1
···
A1,m−1 


(5)
A = .
,
.
..
.
..
..

 ..
.
Ap−1,0 Ap−1,1 · · · Ap−1,m−1


B0,0
B0,1
···
B0,n−1
 B1,0
B1,1
···
B1,n−1 


B = .
(6)
,
.
..
..
..
 ..

.
.
Bp−1,0

Bp−1,1

···

Bp−1,n−1

such that the encoding functions of each worker i can be written as
X
X
Ãi =
Aj,k aijk ,
B̃i =
Bj,k bijk ,
j,k

(7)

j,k

for some tensors a and b, and the decoding function given each subset K can be written as
X
Ĉj,k =
C̃i cijk ,

2

(8)

i∈K

for some tensor c. For brevity, we denote the set of linear codes as L.
The major advantage of linear codes is that they guarantee both the encoding and the decoding complexities of the scheme
scale linearly with respect to the size of the input matrices. Furthermore, as we have proved in [10], linear codes are optimal
for p = 1. Given the above terminology, we define the following concept.
Definition 2. For a distributed matrix multiplication problem of computing A| B using N workers, we define the optimum linear
∗
recovery threshold as a function of the problem parameters p, m, n, and N , denoted by Klinear
, as the minimum achievable
recovery threshold among all linear codes. Specifically,
∗
Klinear
,

2 Here

min

K(f , g, d).

(f ,g,d)∈L

Ĉj,k denotes the master’s estimate of the subblock of C that corresponds to

P

`

A`,j B`,k .

(9)

4

∗
Our goal is to characterize the optimum linear recovery threshold Klinear
, and to find computation strategies to achieve
such optimum threshold. Note that if the number of workers N is too small, obviously no valid computation strategy exists
even without requiring straggler tolerance. Hence, in the rest of the paper, we only consider the meaningful case where N is
large enough to support at least one valid computation strategy. Equivalently, N has to be at least the bilinear complexity of
multiplying an m-by-p matrix and a p-by-n matrix.
We are also interested in characterizing the minimum recovery threshold achievable using general coding strategies (including
non-linear codes). Similar to [10], we define this value as the optimum recovery threshold and denote it by K ∗ .

III. M AIN R ESULTS
We state our main results in the following theorems:
Theorem 1. For a distributed matrix multiplication problem of computing A| B using N workers, with parameters p, m, and
n, the following recovery threshold can be achieved by a linear code, referred to as the entangled polynomial code.3
Kentangled-poly , pmn + p − 1.

(10)

Furthermore, the entangled polynomial code can be decoded at the master node with at most the complexity of polynomial
interpolation given pmn + p − 1 points.
Remark 1. Compared to some other possible approaches, our proposed entangled polynomial code provides orderwise
improvement in the recovery threshold (see Fig. 2). One conventional approach (referred to as the uncoded repetition scheme)
is to let each worker store and multiply uncoded submatrices. With the additional computation redundancy through repetition,
the scheme can robustly tolerate some stragglers. However, its recovery threshold grows linearly with respect to the number of
workers. Another approach is to let each worker store two random linear combinations of the input submatrices (referred to as
the random linear code). With high probability, this achieves recovery threshold KRL , p2 mn, which does not scale with N .
However, to calculate C, we need the result of pmn sub-matrix multiplications. Indeed, the lack of structure in the random
coding forces the system to wait for p times more than what is essentially needed. One surprising aspect of the proposed
entangled polynomial code is that, due to its particular structure which aligns the workers’ computations with the master’s need,
it avoids unnecessary multiplications of submatrices. As a result, it achieves a recovery threshold that does not scale with N ,
and is orderwise smaller than that of the random linear code. Furthermore, it allows efficient decoding at the master, which
requires at most an almost linear complexity.
60
Uncoded Repitition
Short MDS
Random Linear Code
Entangled Polynomial Code (Optimal)

Recovery Threshold

50

40

bilinear
complexity

30

20

10

0

0

10

20

30

40

50

60

70

80

Number of Workers N

Fig. 2: Comparison of the recovery thresholds achieved by the uncoded repetition scheme, the random linear code, the short-MDS (or
short-dot) [7], [8] and our proposed entangled polynomial code, given problem parameters p = m = 3, n = 1. The entangled polynomial
code orderwise improves upon all other approaches. It also achieves the optimum linear recovery threshold in this scenario.

Remark 2. There have been several works in prior literature investigating the p = 1 case [7], [10], [13]. For this special case, the
entangled polynomial code reduces to our previously proposed polynomial code, which achieves the optimum recovery threshold
mn and orderwise improves upon other designs. On the other hand, there has been some investigation on matrix-by-vector type
multiplication [7], [8], which can be viewed as the special case of m = 1 or n = 1 in our proposed problem. The short-MDS
code (or short-dot) has been proposed, achieving a recovery threshold of N − b Np c + m, which scales linearly with N . Our
proposed entangled polynomial code also strictly and orderwise improves upon that (see Fig. 2).
3 For

N < pmn + p − 1, we define Kentangled-poly , N .

5

Our second result is the optimality of the entangled polynomial code when m = 1 or n = 1. Specifically, we prove that
entangled polynomial code is optimal in this scenario among all linear codes. Furthermore, if the base field F is finite, it also
achieves the optimum recovery threshold K ∗ within a factor of 2, with non-linear coding strategies into account.
Theorem 2. For a distributed matrix multiplication problem of computing A| B using N workers, with parameters p, m, and
n, if m = 1 or n = 1, we have
∗
Klinear
= Kentangled-poly .

(11)

Moreover, if the base field F is finite,
1
Kentangled-poly <K ∗ ≤ Kentangled-poly .
(12)
2
Remark 3. We prove Theorem 2 by first exploiting the algebraic structure of matrix multiplication to develop a linear algebraic
converse for equation (11), and then constructing an information theoretic converse to prove inequality (12). The linear algebraic
converse only relies on two properties of the matrix multiplication operation: 1) bilinearity, and 2) uniqueness of zero element.
This technique can be extended to any other bilinear operations with similar properties, such as convolution, as mentioned later
(see Theorem 4). On the other hand, the information theoretic converse is obtained through a cut-set type argument, which
allows a lower bound on the recovery thresholds even for non-linear codes.
Our final result on the main problem is characterizing the optimum linear recovery threshold K ∗ within a factor of 2 for all
possible p, m, n, and N , using the fundamental concept of bilinear complexity [11]:
Definition 3. We define the bilinear complexity of multiplying an m-by-p matrix and a p-by-n matrix, denoted by R(p, m, n),
as the minimum number of element-wise multiplication required to complete such an operation. Rigorously, R(p, m, n) denotes
the minimum integer R, such that we can find tensors a ∈ FR×p×m , b ∈ FR×p×n , and c ∈ FR×m×n , satisfying



X
X
X
X
Bj 00 k00 bij 00 k00  =
A`j B`k .
(13)
cijk 
Aj 0 k0 aij 0 k0  
i

j 0 ,k0

j 00 ,k00

`

for any input matrices A ∈ Fp×m , B ∈ Fp×n .
Using this concept, we state our result as follows.
Theorem 3. For a distributed matrix multiplication problem of computing A| B using N workers, with parameters p, m, and
n, the optimum linear recovery threshold is characterized by
∗
R(p, m, n) ≤ Klinear
≤ 2R(p, m, n) − 1,

(14)

where R(p, m, n) denotes the bilinear complexity of multiplying an m-by-p matrix and a p-by-n matrix.
Remark 4. The key idea of proving Theorem 3 is to first convert any matrix multiplication problem into computing the elementwise product of two vectors of length R(p, m, n). Then we show that an optimal computation strategy can be developed for this
augmented problem using similar ideas we developed for the entangled polynomial code. Similarly, factor-of-2 characterization
can also be obtained for non-linear codes, as discussed in Section VI.
The techniques we developed in this paper can also be extended to several other problems, such as coded convolution [12]
and fault tolerance computing [14], [15], leading to tight characterizations. For coded convolution, we present our result in the
following theorem.
1
Theorem 4. For the distributed convolution problem of computing a ∗ b using N workers that can each store m
fraction of a
1
∗
and n fraction of b, the optimum recovery threshold that can be achieved using linear codes, denoted by Kconv-linear , is exactly
characterized by the following equation
∗
Kconv-linear
= Kconv-poly , m + n − 1.

(15)

Remark 5. Theorem 4 is proved based on our previously developed coded computing scheme for convolution, which is a
variation of the polynomial code [10]. As mentioned before, we extend the proof idea of Theorem 2 to prove the matching
converse. This theorem proves the optimality of the computation scheme in [10] among all computation strategies where the
encoding functions are linear. For detailed problem formulation and proof, see Appendix A.
Our second extension is in the fault tolerance computing setting, where, unlike the straggler effects we studied in this paper,
arbitrary errors can be injected into the computation, and the master has no information about which subset of workers are
returning errors. We show that the techniques we developed for straggler mitigation can also be applied in this setting to improve
robustness against computing failures, and the optimality of any encoding function in terms of recovery threshold also preserves
when applied in the fault tolerance computing setting. As an example, we present the following theorem, demonstrating this
connection.

6

Theorem 5. For a distributed matrix multiplication problem of computing A| B using N workers, with parameters p, m, and
n, if m = 1, or n = 1, or p = 1, the entangled polynomial code can detect up to
∗
Edetect
= N − Kentangled-poly

(16)

errors, and correct up to
∗
Ecorrect
=



N − Kentangled-poly
2


(17)

errors. This can not be improved using any other linear coding strategies.
Remark 6. The proof idea for Theorem 5 is to connect the straggler mitigation problem and the fault tolerance problem by
extending the concept of Hamming distance to coded computing. Specifically, we map the straggler mitigation problem to the
problem of correcting erasure errors, and the fault tolerant problem to the problem of correcting arbitrary errors. The solution
to these two communication problems are deeply connected by the Hamming distance, and we show that this result extends to
coded computing (see Lemma 3 in Appendix B). Since the concept of Hamming distance is not exclusively defined for linear
codes, this connection also holds for arbitrary computation strategies. Furthermore, this approach can be easily extended to the
hybrid settings where both stragglers and computing errors exist, and similar results can be proved. The detailed formulation
and proof can be found in Appendix B.
In Section IV, we prove Theorem 1 by describing the entangled polynomial code. Then in Section V, we prove Theorem 2
by deriving the converses. Finally, we present the coding construction and converse for proving Theorem 3 in Section VI.
IV. E NTANGLED P OLYNOMIAL C ODE
In this section, we prove Theorem 1 by formally describing the entangled polynomial code and its decoding procedure. We
start with an illustrating example.
A. Illustrating Example
Consider a distributed matrix multiplication task of computing A| B using N = 5 workers that can each store half of the
rows (i.e., p = 2 and m = n = 1). We evenly divide each input matrix along the row side into 2 submatrices:
 
 
A0
B0
A=
,
B=
,
(18)
A1
B1
Given this notation, we essentially want to compute


C = A| B = A|0 B0 + A|1 B1 .

(19)

A|i Bi

A naive computation strategy is to let the 5 workers compute each
uncodedly with repetition. Specifically we can let 3
workers compute A|0 B0 and 2 workers compute A|1 B1 . However, this approach can only robustly tolerate 1 straggler, achieving
a recovery threshold of 4. Another naive approach is to use random linear codes, i.e., let each worker store a random linear
combination of A0 , A1 , and a combination of B0 , B1 . However, the resulting computation result of each worker is a random
linear combination of 4 variables A|0 B0 , A|0 B1 , A|1 B0 , and A|1 B1 , which also results in a recovery threshold of 4.
Surprisingly, there is a simple computation strategy for this example that achieves the optimum linear recovery threshold of
3. The main idea is to instead inject structured redundancy tailored to the matrix multiplication operation. We present this
proposed strategy as follows:
Suppose elements of A, B are in R. Let each worker i ∈ {0, 1, ..., 4} store the following two coded submatrices:
Ãi = A0 + iA1 ,

B̃i = iB0 + B1 .

(20)

To prove that this design gives a recovery threshold of 3, we need to find a valid decoding function for any subset of 3 workers.
We demonstrate this decodability through a representative scenario, where the master receives the computation results from
workers 1, 2, and 4, as shown in Figure 3. The decodability for the other 9 possible scenarios can be proved similarly.
According to the designed computation strategy, we have
   0


C̃1
1 11 12
A|0 B1
|
|
C̃2  = 20 21 22  A0 B0 + A1 B1  .
(21)
40 41 42
A|1 B0
C̃4
The coefficient matrix in the above equation is a Vandermonde matrix, which is invertible because its parameters 1, 2, 4 are
distinct in R. So one decoding approach is to directly invert equation (21), of which the returned result includes the needed
matrix C = A|0 B0 + A|1 B1 . This proves the decodability.
However, as we will explain in the general coding design, directly computing this inverse problem using the classical inversion
algorithm might be expensive in some more general cases. Quite interestingly, because of the algebraic structure we designed

7

Fig. 3: Example using entangled polynomial code, with 5 workers that can each store half of each input matrix. (a) Computation strategy:
each worker i stores A0 + iA1 and iB0 + B1 , and computes their product. (b) Decoding: master waits for results from any 3 workers, and
decodes the output using polynomial interpolation.

for the computation strategy (i.e., equation (20)), the decoding process can be viewed as a polynomial interpolation problem (or
equivalently, decoding a Reed-Solomon code).
Specifically, in this example each worker i returns
C̃i = Ã|i B̃i = A|0 B1 + i(A|0 B0 + A|1 B1 ) + i2 A|1 B0 ,

(22)

which is essentially the value of the following polynomial at point x = i:
h(x) , Ã|i B̃i = A|0 B1 + x(A|0 B0 + A|1 B1 ) + x2 A|1 B0 .

(23)

Hence, recovering C using computation results from 3 workers is equivalent to recovering the linear term coefficient of a
quadratic function given its values at 3 points. Later in this section, we will show that by mapping the decoding process to
polynomial interpolation, we can achieve almost-linear decoding complexity even for arbitrary parameter values.
B. General Coding Design
Now we present the entangled polynomial code, which achieves a recovery threshold pmn + p − 1 for any p, m, n and N
as stated in Theorem 1. 4 First of all, we evenly divide each input matrix into pm and pn submatrices according to equations
(5) and (6). We then assign each worker i ∈ {0, 1, ..., N − 1} an element in F, denoted by xi , and make sure that all xi ’s are
distinct. Under this setting, we define the following class of computation strategies.
Definition 4. Given parameters α, β, θ ∈ N, we define the (α, β, θ)-polynomial code as
Ãi =

p−1 m−1
X
X

Aj,k xjα+kβ
,
i

j=0 k=0

B̃i =

p−1 n−1
X
X

(p−1−j)α+kθ

Bj,k xi

,

∀ i ∈ {0, 1, ..., N − 1}.

(24)

j=0 k=0

In an (α, β, θ)-polynomial code, each worker essentially evaluates a polynomial whose coefficients are fixed linear combinations
of the products A|j,k Bj 0 ,k0 . Specifically, each worker i returns
C̃i = Ã|i B̃i =

p−1 m−1
p−1 n−1
X
X X
X

(p−1+j−j 0 )α+kβ+k0 θ

A|j,k Bj 0 ,k0 xi

.

(25)

j=0 k=0 j 0 =0 k0 =0

Consequently, when the master receives results from enough workers, it can recover all these linear combinations using
polynomial interpolation. Recall that we aim to recover


C0,0
C0,1
···
C0,n−1
 C1,0
C1,1
···
C1,n−1 


C= .
(26)
,
..
.
.
..
..
 ..

.
Cm−1,0 Cm−1,1 · · · Cm−1,n−1
4 For

N < pmn + p − 1, a recovery threshold of N is achievable by definition. Hence we focus on the case where N ≥ pmn + p − 1.

8

Pp−1
where each submatrix Ck,k0 , j=0 A|j,k Bj,k0 is also a fixed linear combination of these products. We design the values
of parameters (α, β, θ) such that all these linear combinations appear in (25) separately as coefficients of terms of different
degrees. Furthermore, we want to minimize the degree of the polynomial C̃i , in order to reduce the recovery threshold.
One design satisfying these properties is (α, β, θ) = (1, p, pm), i.e,
Ãi =

p−1 m−1
X
X

Aj,k xj+kp
,
i

B̃i =

j=0 k=0

p−1 n−1
X
X

Bj,k xip−1−j+kpm .

(27)

j=0 k=0

Hence, each worker returns the value of the following degree pmn + p − 2 polynomial at point x = xi :
hi (x) , Ã|i B̃i =

p−1 m−1
p−1 n−1
X
X X
X

(p−1+j−j 0 )+kp+k0 pm

A|j,k Bj 0 ,k0 xi

,

(28)

j=0 k=0 j 0 =0 k0 =0

where each Ck,k0 is exactly the coefficient of the (p − 1 + kp + k 0 pm)-th degree term. Since all xi ’s are selected to be distinct,
recovering C given results from any pmn + p − 1 workers is essentially interpolating h(x) using pmn + p − 1 distinct points.
Because the degree of h(x) is pmn + p − 2, the output C can always be uniquely decoded.
rt
In terms of complexity, this decoding process can be viewed as interpolating a degree pmn + p − 2 polynomial for mn
2
times. It is well known that polynomial interpolation of degree k has a complexity of O(k log k log log k) [16]. Therefore,
decoding entangled polynomial code only requires at most a complexity of O(prt log2 (pmn) log log(pmn)), which is almost
linear to the input size of the decoder (Θ(prt) elements). This complexity can be reduced by simply swapping in any faster
polynomial interpolation algorithm or Reed-Solomon decoding algorithm. In addition, this decoding complexity can also be
further improved by exploiting the fact that only a subset of the coefficients are needed for recovering the output matrix.
V. C ONVERSES
In this section, we provide the proof of Theorem 2. We first prove equation (11) by developing a linear algebraic converse.
Then we prove inequality (12) through an information theoretic lower bound.
A. Maching Converses for Linear Codes
To prove equation (11), we start by developing a converse bound on recovery threshold for general parameter values, then
we specialize it to the settings where m = 1 or n = 1. We state this converse bound in the following lemma:
Lemma 1. For a distributed matrix multiplication problem with parameters p, m, n, and N , we have
∗
Klinear
≥ min{N, pm + pn − 1}.

(29)

When m = 1 or n = 1, the RHS of inequality (29) is exactly Kentangled-poly . Hence equation (11) directly follows from
Lemma 1. So it only suffices to prove Lemma 1, and we prove it as follows:
Proof. To prove Lemma 1, we only need to consider the following two scenarios:
∗
(1) If Klinear
= N , then (29) is trivial.
∗
∗
(2) If Klinear < N , then we essentially need to show that for any parameter values p, m, n, and N , we have Klinear
≥ pm+pn−1.
By definition, if such a linear recovery threshold is achievable, we can find a computation strategy, i.e., tensors a, b, and a class
of decoding functions d , {dK }, such that


 
 X

X
 = A| B
dK  
A|j 0 ,k0 aij 0 k0  
Bj 00 ,k00 bij 00 k00 
(30)
 0 0

00 00
j ,k

j ,k

i∈K

∗
for any input matrices A and B, and for any subset K of Klinear
workers.
We choose the values of A and B, such that each Aj,k and Bj,k satisfies

Aj,k = αjk Ac ,

(31)

Bj,k = βjk Bc ,

(32)

s

r

s

t

for some matrices α ∈ Fp×m , β ∈ Fp×n , and constants Ac ∈ F p × m , Bc ∈ F p × n satisfying A|c Bc 6= 0. Consequently, we have
 



 X

X
 = A| B
dK  
αj 0 k0 aij 0 k0  
βj 00 k00 bij 00 k00  A|c Bc
(33)
 0 0

00 00
j ,k

j ,k

i∈K

for all possible values of α, β, and K.
Fixing the value i, we can view each subtensor aijk as a vector of length pm, and each subtensor bijk as a vector of length
pn. For breivity, we denote each such vector by ai and bi respectively. Similarly, we can also view matrices α and β as vectors

9

of length pm and pn, and we denote these vectors by α and β. Furthermore, we can define dot products within these vector
spaces following the conventions. Using these notations, (33) can be written as

dK {(α · ai ) (β · bi ) A|c Bc }i∈K = A| B.
(34)
∗
Given the above definitions, we now prove that within each subset K of size Klinear
, the vectors {ai }i∈K span the space
F . Essentially, we need to prove that for a given subset K, there does not exist a non-zero α such that α · ai = 0 for all
i ∈ K. Assume the opposite that such an α exists so that α · ai is always 0, then the LHS of (34) becomes a fixed value. On
the other hand, since α is non-zero, we can always find different values of β such that α| β is variable. Recalling (31) and (32),
the RHS of (34) cannot be fixed if α| β is variable, which results in a contradiction.
Now we use this conclusion to prove (29). For any fixed K, let B be a subset of indices such that {ai }i∈B form a basis.
∗
Recall that we are considering the case where Klinear
< N , meaning that we can find a worker k̃ 6∈ K. For convenience, we
+
−
+
∗
define K = K ∪ {k̃}, and K , K \B. Obviously, |B| = pm, and |K− | = |K+ | − |B| = Klinear
+ 1 − pm. Hence, it suffices
−
pn
to prove that |K | ≥ pn, which only requires that {bi }i∈K− forms a basis of F . Equivalently, we only need to prove that
any β satisfying β · bi = 0 for any i ∈ K− must satisfy β = 0.
Recall that {ai }i∈B forms a basis, so we can find a matrix αi ∈ Fp×m for each i ∈ B such that αi · ai0 = δi,i0 .5 From
elementary linear algebra, the vectors {αi }i∈B also form a basis of Fpm . Correspondingly, their matrix version {αi }i∈B form
a basis of Fp×m .
∗
For any k ∈ B, we define Kk = K+ \{k}. Note that |Kk | = Klinear
, so equation (34) also holds for any subset Kk . Note that
−
if α = αk , and β satisfies β · bi = 0 for any i ∈ K , then the corresponding LHS of (34) remains fixed. As a result, A| B
must also be fixed. Similar to the above discussion, this requires that the value of αk| β be fixed. This value has to be 0 because
β = 0 satisfies our stated condition.
Now we have proved that any β satisfying β · bi = 0 must also satisfy αk| β = 0 for k ∈ B. Because {αk }k∈B form a basis
of Fp×m , such β acting on Fp×m through matrix product has to be the zero operator, so β = 0. As mentioned above, this
∗
results in Klinear
≥ pm + pn − 1, which completes the proof of Lemma 1 and equation (11).
pm

Remark 7. Note that in the above proof, we never used the fact that the decoding functions are linear. Hence, the converse does
not require the linearity of the decoder. This fact will be used later in our discussion regarding the fault tolerance computing in
Appendix B.
B. Information Theoretic Converse for Nonlinear Codes
Now we prove inequality (12) through an information theoretic converse bound. Similar to the proof of equation (11), we
start by proving a general converse.
Lemma 2. For a distributed matrix multiplication problem with parameters p, m, n, and N , if the base field F is finite, we
have
K ∗ ≥ max{pm, pn}.

(35)

When m = 1 or n = 1, the RHS of inequality (35) is greater than 12 Kentangled-poly . Hence inequality (12) directly results from
Lemma 2, which we prove as follows.
Proof. Without loss of generality, we assume m ≥ n, and aim to prove K ∗ ≥ pm. Specifically, we need to show that, for any
computation strategy and any subset K of workers, if the master can recover C given the results from workers in K, then we
must have |K| ≥ pm.
Suppose the condition in the above statement holds. Given each input A, the workers can compute {Ãi }i∈K using the
encoding functions. On the other hand, for any possible value of B, the workers can compute {C̃i }i∈K based on B and {Ãi }i∈K .
Hence, if we view A as a random variable and {C̃i }i∈K as random functions of B, we have the following Markov chain:
A → {Ãi }i∈K → {C̃i }i∈K .

(36)

Because the master can decode C as a function of {C̃i }i∈K , it can also obtain C as a random function if the values of
{C̃i }i∈K for all B ∈ Fs×t are known. This random function is exactly a linear map from Fs×t to Fr×t , which returns the
matrix product of A| and the input. For breivity, we denote this function by Aop . Consequently, we have the following extended
Markov chain
A → {Ãi }i∈K → {C̃i }i∈K → Aop .

(37)

Given the basic property of matrix multiplication, there is a natural one-to-one correspondence between A and Aop . Hence,
the input matrix A can be exactly determined from Aop , i.e., H(A|Aop ) = 0. Using the data processing inequality, we also
5 Here

δi,j denotes the discrete delta function, i.e., δi,i = 1, and δi,j = 0 for i 6= j.

10

have H(A|{Ãi }i∈K ) = 0. Now let A be uniformly randomly sampled from Fs×r , and we have H(A) = sr log2 |F| bits. On the
sr
sr
other hand, each Ãi consists of pm
elements, which has an entropy of at most pm
log2 |F| bits. Consequently, we have
|K| ≥

H(A)
≥ pm.
max H(Ãi )

(38)

i∈K

This concludes the proof of Lemma 2 and inequality (12).
VI. FACTOR OF 2 CHARACTERIZATION OF O PTIMUM L INEAR R ECOVERY T HRESHOLD
In this section, we provide the proof of Theorem 3. Note that the converse bound in this theorem is a natural consequence of
Definition 3.6 Hence, we focus on proving the upper bound by developing an achievability scheme. Specifically, we need to
provide a computation strategy that achieves a recovery threshold of at most 2R(p, m, n) − 1 for all possible values of p, m, n,
and N . As we have explained in Section IV-B, a recovery threshold of N is always achievable, so we only need to focus on
the scenario where N ≥ 2R(p, m, n) − 1.
Our proof consists of 2 steps. In Step 1, we show that any matrix multiplication is essentially computing the element-wise
product of two vectors of length R(p, m, n). Then in Step 2, we show that we can find an optimal computation strategy for this
augmented computing task using similar ideas we developed for entangled polynomial code, which only requires a recovery
threshold of 2R(p, m, n) − 1.
For Step 1, recall the definition of bilinear complexity in Section III. We can always find tensors a ∈ FR(p,m,n)×p×m ,
b ∈ FR(p,m,n)×p×n , and c ∈ FR(p,m,n)×m×n such that any block of the final output C can be computed as
X
Cj,k =
cijk Ã|i,vec B̃i,vec ,
(39)
i

where Ãi,vec and B̃i,vec are linear combinations of the blocks of A and B, defined as
X
X
Ãi,vec ,
Aj,k aijk ,
B̃i,vec ,
Bj,k bijk .
j,k

(40)

j,k

This essentially converts matrix multiplication into a problem of computing the element-wise product of two “vectors” Ãi,vec
and B̃i,vec , each of length R(p, m, n). Specifically, the master only needs Ã|i,vec B̃i,vec for decoding the final output.
Now in Step 2, we want to find the optimum computation strategy for this augmented computation task. Specifically, given
two arbitrary vectors Ãi,vec and B̃i,vec of length R(p, m, n), we want to achieve a recovery threshold of 2R(p, m, n) − 1 for
computing their element-wise product using N workers, each of which can multiply two coded vectors of length 1.
This problem can be solved using similar techniques we developed for entangled polynomial code. The main coding idea
is to first view the elements in each vector as values of a degree R(p, m, n) − 1 polynomial at R(p, m, n) different points.
Specifically, given R(p, m, n) distinct elements in the field F, denoted by x0 , x1 , . . . , xR(p,m,n)−1 , we find polynomials f˜ and
g̃ of degree R(p, m, n) − 1, whose coefficients are matrices, such that
f˜(xi ) = Ãi,vec

(41)

g̃(xi ) = B̃i,vec .

(42)

Recall that we want to recover Ã|i,vec B̃i,vec , which is essentially recovering the values of the degree 2R(p, m, n) − 2 polynomial
h̃ , f˜| g̃ at these R(p, m, n) points. Earlier in this paper, we already developed a coding structure that allows us to recover
polynomials of this form. We now reuse the idea in this construction.
Let y0 , y1 , ..., yN −1 be distinct elements of F. We let each worker i store
Ãi = f˜(yi ),

(43)

B̃i = g̃(yi ),

(44)

which are linear combinations of the input submatrices. After computing the product, each worker essentially evaluates h̃(yi ).
Hence, from the results of any 2R(p, m, n) − 1 workers, the master can recover h̃, which has degree 2R(p, m, n) − 2, and
proceed with decoding the output matrix C. This construction achieves a recovery threshold of 2R(p, m, n) − 1, which proves
the upper bound in Theorem 3.
Remark 8. The computation strategy we developed in Step 2 provides a tight upper bound on the characterization of the
optimum linear recovery threshold for computing element-wise product of two arbitrary vectors using N machines. Its optimality
naturally follows from Theorem 2, given that the element-wise product of two vectors contains all the information needed
to compute the dot-product, which is a special case of matrix multiplication. We formally state this result in the following
corollary.
6 Rigorously,

it also requires the linear independence of the A|i Bj ’s, which can be easily proved.

11

Corollary 1. Consider the problem of computing the element-wise product of two vectors of length R using N workers, each
of which can store a linearly coded element of each vector and return their product to the master. The optimum linear recovery
∗
threshold, denoted as Ke-prod-linear
, is given by the following equation:7
∗
Ke-prod-linear
= min{N, 2R − 1}.

(45)

Remark 9. Note that Step 2 of this proof does not require the computation strategy to be linear. Hence, using exactly the same
coding approach, we can easily extend this result to non-linear codes, and prove a similar factor-of-2 characterization for the
optimum recovery threshold K ∗ , formally stated in the following corollary.
Corollary 2. For a distributed matrix multiplication problem with parameters p, m, and n, let N ∗ (p, m, n) denotes the minimum
number of workers such that a valid (possibly non-linear) computation strategy exists. Then for all possible values of N , we
have
N ∗ (p, m, n) ≤ K ∗ ≤ 2N ∗ (p, m, n) − 1.

(46)

VII. C ONCLUDING R EMARKS
In this paper, we studied the coded distributed matrix multiplication problem and proposed the entangled polynomial code,
which allows optimal straggler mitigation and orderwise improves upon the prior arts. Based on our proposed coding idea, we
proved a fundamental connection between the optimum linear recovery threshold and the bilinear complexity, which characterizes
the optimum linear recovery threshold within a factor of 2 for all possible parameter values. The techniques developed in this
paper can be directly applied to many other problems, including coded convolution and fault tolerance computing, providing
matching characterizations.
One interesting follow-up direction is to find better characterization of the optimum linear recovery threshold. Although this
problem is completely solved for cases including m = 1, n = 1, or p = 1, there is room for improvement in general cases.
Another interesting question is whether there exist non-linear coding strategies that strictly out-perform linear codes, especially
for the important case where the input matrices are large (s, r, t  p, m, n), while allowing for efficient decoding algorithms
with almost linear complexity.
A PPENDIX A
T HE O PTIMUM L INEAR R ECOVERY T HRESHOLD FOR C ODED C ONVOLUTION
In this appendix, we first provide the problem formulation for coded convolution, then we prove Theorem 4, which shows
the optimality of Polynomial Code for Coded Convolution.
A. System Model and Problem Formulation
Consider a convolution task with two input vectors
a = [a0 a1 ... am−1 ],

b = [b0 b1 ... bn−1 ],

(47)

where all ai ’s and bi ’s are vectors of length s over a sufficiently large field F. We want to compute c , a ∗ b using a master
and N workers. Each worker can store two vectors of length s, which are functions of a and b respectively. We refer to these
functions as the encoding functions, denoted by (f , g) similar to the matrix multiplication problem.
Each worker computes the convolution of its stored vectors, and returns it to the master. The master only waits for the
fastest subset of workers, before proceeding to decode c. Similar to the matrix multiplication problem, we define the recovery
threshold given the encoding functions, denoted by K(f , g), as the minimum number of workers that the master needs to wait
that guarantees the existence of valid decoding functions. We aim to characterize the optimum recovery threshold achievable by
∗
any linear encoding functions, denoted by Kconv-linear
, and identify an optimal computation strategie that achieves this optimum
threshold.
B. Proof of Theorem 4
Now we prove Theorem 4, which completely solves the above problem. As we have shown in [10], the recovery threshold
∗
stated in Theorem 4 is achievable using a variation of polynomial code. This result proves an upperbound of Kconv-linear
. It also
identifies an optimal computation strategy. Hence, in this section we focus on proving the matching converse.
Specifically, we aim to prove that given any problem parameters m, n, and N , for any computation strategy, if the encoding
functions (f , g) are linear, then its recovery threshold is at least m + n − 1. We prove it by contradiction.
Assume the opposite, then the master can recover c using results from a subset of at most m + n − 2 workers. We denote
this subset by K. Obviously, we can find a partition of K into two subsets, denoted by Ka and Kb , such that |Ka | ≤ m − 1 and
7 Obviously,

we need N ≥ R to guarantee the existence of a valid computation strategy.

12

|Kb | ≤ n − 1. Note that the encoding functions of workers in Ka collaboratively and linearly maps Fms to F(m−1)s , which has
a non-zero kernel. Hence, we can find a non-zero input vector a such that all workers in Ka returns 0. Similarly, we can find a
non-zero b such that all workers in Kb returns 0. Recall that Ka ∪ Kb = K. Consequently, when the master receives 0 from all
workers in K, the decoding function returns a ∗ b.
This convolution product must be the 0 vector, given that the workers return the same results under zero inputs. However,
note that the convolution operator has no zero-divisor. Either a or b has to be zero, which contradicts the non-zero assumptions.
Hence, we have K(f , g) ≥ m + n − 1. This concludes the proof of Theorem 4.
A PPENDIX B
A N E QUIVALENCE B ETWEEN FAULT T OLERANCE AND S TRAGGLER M ITIGATION
In this appendix, we start by formulating a fault tolerance computing problem for matrix multiplication, then we prove
Theorem 5 by building a connection between straggler mitigation and fault tolerance, by extending the concept of Hamming
distance to coded computing.
A. Problem Formulation
We consider a matrix multiplication problem with two input matrices A ∈ Fs×r and B ∈ Fs×t , and we are interested in
1
1
computing C , A| B using a master node and N worker nodes, where each worker can store pm
fraction of A and pn
fraction
s

r

s

t

of B. Similar to the straggler mitigation problem, each worker i can store two coded matrices Ãi ∈ F p × m and B̃i ∈ F p × n ,
computed based on A and B respectively. Each worker can compute the product C̃i , Ã|i B̃i , and return it to the master. Unlike
the straggler setting, the master waits for all workers before proceeding to recover the final output C. However, a subset of
workers can return error results, and the master has no information on which subset of results are false. Under this setting, the
master wants to: (1) determine if there is an error in the workers’ outputs, and (2) try to recover the final output C using the
possibly false computing results from the workers.
Given the above system model, we formulate this fault tolerance computing problem based on the following terminology.
Similar to our main problem in this paper, we define the encoding functions and denote them by (f , g). We also define the
decoding function for the master, however in this problem it can either return an estimate of C, or report an error. We only
consider the valid decoding functions, which always correctly decodes C when no worker is making mistakes.
For any integer E, we say the encoding functions can detect E errors if we can find a decoding function that either returns
the correct value of C or reports an error, when no more than E workers are making mistakes. Moreover, we say the encoding
functions can correct E errors, if the decoding function always correctly decodes C. We denote the maximum possible integer
E given these two criterions by Edetect (f , g) and Ecorrect (f , g) respectively.
We aim to find encoding functions that allows detecting and correcting the maximum possible number of errors. Among all
possible computation strategies, we are particularly interested in the linear codes, as defined in Section II. Given the above
terminology, we define the following concepts.
Definition 5. For a distributed matrix multiplication problem of computing A| B using N workers, we define the maximum
∗
∗
detectable errors and the maximum detectable errors for linear codes, denoted by Edetect
and Ecorrect
respectively, as the
maximum possible values of Edetect (f , g) and Ecorrect (f , g) over the set of all encoding functions that are linear codes.
∗
∗
Our goal is to characterize the values of Edetect
and Ecorrect
, and to find optimal computation strategies to achieve these values.
We are also interested in extending these characterizations to non-linear codes.
B. Proof of Theorem 5
We start by defining some concepts, which allows connecting the fault tolerance computing problem to the straggler mitigation
problem.
Definition 6. We define the Hamming distance of any encoding functions (f , g), denoted by d(f , g), as the maximum integer
d such that for any two pairs of input matrices whose products C are different, at least d workers compute different values of
C̃i .
Definition 7. We define the Recovery threshold of any encoding functions (f , g), denoted by K(f , g), as the minimum possible
recovery threshold given any decoding functions.
We prove that all these three mentioned criterion for designing encoding functions are directly connected by the Hamming
distance, which is formally stated as follows.
Lemma 3. For any (possibly non-linear) computation strategy, we have
K(f , g) = N − d(f , g) + 1,
Edetect (f , g) = d(f , g) − 1,


d(f , g) − 1
Ecorrect (f , g) =
.
2

(48)
(49)
(50)

13

Remark 10. Lemma 3 essentially indicates that optimizing the straggler mitigation performance over any class of coding designs
is equivalently optimizing its performance in the fault tolerance setting. Furthermore, all these previously mentioned metrics can
be simultaneously optimized by the codes with the maximum possible Hamming distance. Hence, there is no tension among
these metrics. This result bridges the rich literature of coding theory and distributed computing.
Proof of Lemma 3. Lemma 3 is a direct consequence of the classical coding theory, given that mitigating straggler effects is
essentially correcting erasure errors, and tolerating false results in computing is essentially correcting arbitrary error. Hence, we
only provide the proof of (48), where equations (49) and (50) can be proved using similar approaches.
Specifically, we want to prove that for any integer K, a recovery threshold of K is achievable by some encoding functions if
and only if their Hamming distance is greater or equal to N − K + 1. If K is achievable, it means that we can find decoding
functions that uniquely determines the value of C given results from any K workers. Equivalently, for distinct values of C, at
least N − K + 1 workers has to return distinct results. Recall that the recovery threshold is the minimum of such integer K,
and the Hamming distance is the maximum integer that corresponds to N − K + 1. We have K(f , g) = N − d(f , g) + 1.
Now we continue to prove Theorem 5 using Lemma 3. As mentioned in Remark 7, the proof of Theorem 2 essentially
completely characterizes the optimum recovery threshold over all linear encoding functions for m = 1 or n = 1, which is given
by Kentangled-poly . On the other hand, this optimum threshold also coincide with Kentangled-poly for p = 1, which can be easily
proved based on our prior results in [10]. Hence, using Lemma 3, we directly obtain that if m = 1 or n = 1 or p = 1, we have
∗
Edetect
= N − Kentangled-poly ,


N − Kentangled-poly
∗
Ecorrect
=
.
2

(51)
(52)

This concludes the proof of Theorem 5.
R EFERENCES
[1] L. E. Cannon, A Cellular Computer to Implement the Kalman Filter Algorithm. PhD thesis, Bozeman, MT, USA, 1969. AAI7010025.
[2] J. Choi, D. W. Walker, and J. J. Dongarra, “Pumma: Parallel universal matrix multiplication algorithms on distributed memory concurrent computers,”
Concurrency: Practice and Experience, vol. 6, no. 7, pp. 543–570, 1994.
[3] R. A. Van De Geijn and J. Watts, “Summa: scalable universal matrix multiplication algorithm,” Concurrency: Practice and Experience, vol. 9, no. 4,
pp. 255–274, 1997.
[4] E. Solomonik and J. Demmel, “Communication-optimal parallel 2.5d matrix multiplication and lu factorization algorithms,” in Proceedings of the 17th
International Conference on Parallel Processing - Volume Part II, Euro-Par’11, (Berlin, Heidelberg), pp. 90–109, Springer-Verlag, 2011.
[5] J. Dean and L. A. Barroso, “The tail at scale,” Communications of the ACM, vol. 56, no. 2, pp. 74–80, 2013.
[6] M. Zaharia, A. Konwinski, A. D. Joseph, R. H. Katz, and I. Stoica, “Improving MapReduce performance in heterogeneous environments,” OSDI, vol. 8,
p. 7, Dec. 2008.
[7] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding up distributed machine learning using codes,” e-print arXiv:1512.02673,
2015.
[8] S. Dutta, V. Cadambe, and P. Grover, “Short-dot: Computing large linear transforms distributedly using coded short dot products,” in Advances In Neural
Information Processing Systems, pp. 2092–2100, 2016.
[9] R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, “Gradient coding,” arXiv preprint arXiv:1612.03301, 2016.
[10] Q. Yu, M. Maddah-Ali, and S. Avestimehr, “Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,” in Advances in
Neural Information Processing Systems 30, pp. 4406–4416, Curran Associates, Inc., 2017.
[11] M. Bläser, Fast Matrix Multiplication. No. 5 in Graduate Surveys, Theory of Computing Library, 2013.
[12] S. Dutta, V. Cadambe, and P. Grover, “Coded convolution for parallel and distributed computing within a deadline,” in 2017 IEEE International Symposium
on Information Theory (ISIT), pp. 2403–2407, June 2017.
[13] K. Lee, C. Suh, and K. Ramchandran, “High-dimensional coded matrix multiplication,” in 2017 IEEE International Symposium on Information Theory
(ISIT), pp. 2418–2422, June 2017.
[14] K.-H. Huang and J. A. Abraham, “Algorithm-based fault tolerance for matrix operations,” IEEE Transactions on Computers, vol. C-33, pp. 518–528, June
1984.
[15] J.-Y. Jou and J. A. Abraham, “Fault-tolerant matrix arithmetic and signal processing on highly concurrent computing structures,” Proceedings of the IEEE,
vol. 74, pp. 732–741, May 1986.
[16] K. S. Kedlaya and C. Umans, “Fast polynomial factorization and modular composition,” SIAM Journal on Computing, vol. 40, no. 6, pp. 1767–1802,
2011.

