# Coded sparse matrix computation schemes that leverage partial stragglers

Anindya Bijoy Das and Aditya Ramamoorthy
This work was supported in part by the National Science Foundation (NSF) under
grants CCF-1718470 and CCF-1910840. The material in this work has appeared in
part at the 2021 IEEE International Symposium on Information Theory,
Melbourne, Australia and at the 2018 IEEE Information Theory Workshop (ITW),
Guangzhou, China. Department of Electrical and Computer Engineering,
Iowa State University, Ames, IA 50011 USA
<EMAIL_ADDRESS>
###### Abstract

Distributed matrix computations over large clusters can suffer from the
problem of slow or failed worker nodes (called stragglers) which can dominate
the overall job execution time. Coded computation utilizes concepts from
erasure coding to mitigate the effect of stragglers by running “coded” copies
of tasks comprising a job; stragglers are typically treated as erasures. While
this is useful, there are issues with applying, e.g., MDS codes in a
straightforward manner. Several practical matrix computation scenarios involve
sparse matrices. MDS codes typically require dense linear combinations of
submatrices of the original matrices which destroy their inherent sparsity.
This is problematic as it results in significantly higher worker computation
times. Moreover, treating slow nodes as erasures ignores the potentially
useful partial computations performed by them. Furthermore, some MDS
techniques also suffer from significant numerical stability issues. In this
work we present schemes that allow us to leverage partial computation by
stragglers while imposing constraints on the level of coding that is required
in generating the encoded submatrices. This significantly reduces the worker
computation time as compared to previous approaches and results in improved
numerical stability in the decoding process. Exhaustive numerical experiments
on Amazon Web Services (AWS) clusters support our findings.

###### Index Terms:

Distributed computing, MDS Code, Stragglers, Condition Number, Sparsity.

##  I Introduction

Distributed computation plays a major role in several problems in machine
learning. For example, large scale matrix-vector multiplication is repeatedly
used in gradient descent which in turn plays a key role in high dimensional
machine learning problems. The size of the underlying matrices makes it
impractical to perform the computation on a single computer (both from a speed
and a storage perspective). Thus, the computation is typically subdivided into
smaller tasks that are run in parallel across multiple worker nodes.

In these systems the overall execution time is typically dominated by the
speed of the slowest worker. Thus, the presence of stragglers (as slow or
failed workers are called) can negatively impact the performance of
distributed computation. In recent years, techniques from coding theory
(especially maximum-distance-separable (MDS) codes) [1, 2, 3, 4] have been
used to mitigate the effect of stragglers for problems such as matrix-vector
and matrix-matrix multiplication. For instance, the work of [1] proposes to
partition the computation of $\mathbf{A}^{T}\mathbf{x}$ by first splitting
$\mathbf{A}=[\mathbf{A}_{0}\leavevmode\nobreak\ |\leavevmode\nobreak\
\mathbf{A}_{1}]$ into two block-columns (with an equal number of column
vectors) and assigning three workers, the task of computing
$\textbf{A}^{T}_{0}\textbf{x}$, $\textbf{A}^{T}_{1}\textbf{x}$ and
$\left(\textbf{A}_{0}+\textbf{A}_{1}\right)^{T}\textbf{x}$, respectively.
Evidently, the computational load on each node is half of the original job.
Furthermore, it is easy to see that $\mathbf{A}^{T}\mathbf{x}$ can be
recovered as soon as any two workers complete their tasks (with some minimal
post-processing). Thus, this system is resilient to one straggler. The work of
[3], poses the multiplication of two matrices in a form that is roughly
equivalent to a Reed-Solomon code. In particular, each worker node’s task
(which is multiplying smaller submatrices) can be imagined as a coded symbol.
As long as enough tasks are complete, the master node can recover the matrix
product by polynomial interpolation.

For such coded computing systems we can define a so-called recovery threshold.
It is the minimum value of $\tau$, such that the master node can recover the
result as long as any $\tau$ workers complete their tasks. Thus, at the top
level, in these systems stragglers are treated as the equivalent of erasures
in coding theory, i.e., the assumption is that no useful information can be
obtained from the stragglers.

While these are interesting ideas, there are certain issues that are ignored
in the majority of prior work (see [5, 6, 7, 8, 9] for some exceptions).
Firstly, several practical cases of matrix-vector or matrix-matrix
multiplication involve sparse matrices. Using MDS coding strategies in a
straightforward manner will often destroy the sparsity of the matrices being
processed by the worker nodes. In fact, as noted in [7], this can cause the
overall job execution time to actually go up rather than down. Secondly, in
the distributed computation setting, we make the observation that it is
possible to leverage partial computations that are performed by the
stragglers. Thus, a slow worker may not necessarily be a useless worker. Fig.
1 (which also appears in [10]) shows the variation of speed of different
t2.micro machines in AWS (Amazon Web Services) cluster, and it can be seen
that for a particular job, even the slowest worker node may have approximately
$60\%-70\%$ of the speed of the fastest worker.

$5$$10$$15$$20$$25$$30$$35$$40$$6$$6.5$$7$$7.5$$8$$8.5$Worker IndexTime
RequiredAverageBounds

Figure 1: Variation of worker speeds for the same job over 100 runs across
$40$ workers within AWS; the job involves multiplying two random matrices of
size $4000\times 4000$ twice. The average time is shown by the small circle
for each worker. The upper and lower edges indicate the maximum and minimum
time over the 100 runs. The required time exhibits a wide variation from
$5.85$ seconds to $8.71$ seconds.

In this work we propose schemes which are not only resilient to full
stragglers, but can also exploit slow workers by utilizing their partially
finished tasks. The works in [11] and [12] also address this issue but they
are applicable only for matrix-vector multiplication whereas in this work, we
propose schemes for matrix-matrix multiplication too. Furthermore, in several
of our schemes we can specify the number of block-columns of the individual
$\mathbf{A}$ and $\mathbf{B}$ matrices that are linearly combined to arrive at
the encoded matrices. This is especially useful in the case of sparse matrices
($\mathbf{A}$ and $\mathbf{B}$) that often appear in practical settings. Thus,
in short, our proposed approaches can leverage the partial computations of the
stragglers and exploit the sparsity of the input matrices, both of which can
enhance the overall speed of the whole system.

This paper is organized as follows. Section II describes the background and
related work and summarizes the contributions of our work. Section III
outlines some basic definitions and observations which are required for the
subsequent presentation. Section IV discusses our proposed $\beta$-level
coding schemes which constrain the level of coding in the encoded submatrices
while leveraging partial computations. Following this, Section V proposes
schemes for both matrix-vector and matrix-matrix multiplication which can be
optimal in terms of resilience to full stragglers and can improve the
utilization of the partial stragglers. Section VI discusses the experimental
performance of our proposed methods and shows the comparison with other
available approaches. We conclude the paper with a discussion about future
work in Section VII.

##  II Background and Related Work

Consider the case where a master node has a matrix $\mathbf{A}$ and either a
matrix $\mathbf{B}$ or a vector $\mathbf{x}$ and needs to compute either
$\mathbf{A}^{T}\mathbf{B}$ or $\mathbf{A}^{T}\mathbf{x}$. The computation
needs to be carried out in a distributed fashion over $n$ worker nodes. Each
worker receives the equivalent of a certain fraction (denoted by $\gamma_{A}$
and $\gamma_{B}$, respectively) of the columns of $\mathbf{A}$ and
$\mathbf{B}$ or the whole vector $\mathbf{x}$. The node is responsible for
computing its assigned submatrix-submatrix or submatrix-vector products.

We discuss the matrix-matrix scenario below where each worker node receives
coded versions of submatrices of $\mathbf{A}$ and $\mathbf{B}$
respectively111A general formulation need not restrict the assignment to coded
submatrices of $\mathbf{A}$ and $\mathbf{B}$. Nevertheless, all known schemes
thus far and our proposed schemes work with equal-sized submatrices, so we
present the formulation in this way.. The corresponding matrix-vector case can
be obtained as a special case. Consider a $p\times u$ and $p\times v$ block
decomposition of $\mathbf{A}$ and $\mathbf{B}$ respectively as shown below.

$\displaystyle\mathbf{A}$
$\displaystyle=\begin{bmatrix}\mathbf{A}_{0,0}&\dots&\mathbf{A}_{0,u-1}\\\
\vdots&\ddots&\vdots\\\
\mathbf{A}_{p-1,0}&\dots&\mathbf{A}_{p-1,u-1}\end{bmatrix},\;\;\;\textrm{and}\;\;\;\mathbf{B}=\begin{bmatrix}\mathbf{B}_{0,0}&\dots&\mathbf{B}_{0,v-1}\\\
\vdots&\ddots&\vdots\\\
\mathbf{B}_{p-1,0}&\dots&\mathbf{B}_{p-1,v-1}\end{bmatrix}.$

The master node creates coded submatrices by computing appropriate scalar
linear combinations of the $\mathbf{A}_{i,j}$ submatrices and respectively the
$\mathbf{B}_{i,j}$ submatrices. This implies that the master node only
performs scalar multiplications and additions. It is not responsible for any
of the computationally intensive matrix operations. Following this, it sends
the corresponding coded submatrices to each of the workers who perform the
matrix operations.

In this work we only consider a decomposition of $\mathbf{A}$ and $\mathbf{B}$
into block-columns, i.e., $p=1$. We assume that the storage fraction
$\gamma_{A}$ (or $\gamma_{B}$) can be expressed as $\ell_{A}/\Delta_{A}$
(likewise $\ell_{B}/\Delta_{B}$) where both $\ell_{A}$ and $\Delta_{A}$ (and
$\ell_{B}$ and $\Delta_{B}$) are integers. We assume that $\mathbf{A}$ and
$\mathbf{B}$ are large enough and satisfy divisibility constraints so that we
can choose any large enough value of $\Delta_{A}$ and $\Delta_{B}$ to
partition the columns of $\mathbf{A}$ and $\mathbf{B}$ into $\Delta_{A}$ and
$\Delta_{B}$ block-columns. These are denoted as
$\mathbf{A}_{0},\mathbf{A}_{1},\dots,\mathbf{A}_{\Delta_{A}-1}$ and
$\mathbf{B}_{0},\mathbf{B}_{1},\dots,\mathbf{B}_{\Delta_{B}-1}$. Each node is
assigned the equivalent of $\ell_{A}$ block-columns of $\mathbf{A}$ and
$\ell_{B}$ block-columns of $\mathbf{B}$. Each of those $\ell_{A}$ block-
columns from $\mathbf{A}$ will be multiplied with each of the $\ell_{B}$
block-columns from $\mathbf{B}$, so a particular worker node will compute, in
total, $\ell=\ell_{A}\ell_{B}$ block-products for matrix-matrix
multiplication. In case of matrix-vector multiplication, the worker node will
compute $\ell=\ell_{A}$ block products, where each of $\ell_{A}$ blocks from
$\mathbf{A}$ will be multiplied with $\mathbf{x}$.

The assignment can simply be subsets of
$\\{\mathbf{A}_{0},\mathbf{A}_{1},\dots,\mathbf{A}_{\Delta_{A}-1}\\}$ or
$\\{\mathbf{B}_{0},\mathbf{B}_{1},\dots,\mathbf{B}_{\Delta_{B}-1}\\}$; in this
case we call the solution “uncoded”. Alternatively, the assignment can be
suitably chosen functions of
$\\{\mathbf{A}_{0},\mathbf{A}_{1},\dots,\mathbf{A}_{\Delta_{A}-1}\\}$ or
$\\{\mathbf{B}_{0},\mathbf{B}_{1},\dots,\mathbf{B}_{\Delta_{B}-1}\\}$; in this
case we call the solution “coded”. The assignment also specifies a sequential
order from top to bottom in which each worker node needs to process its tasks.
This implies that if a node is currently processing the $i$-th assignment
($0\leq i\leq\ell-1$), then it has already processed assignments $0$ through
$i-1$. In this work, we assume that each time a node computes a product, it
transmits the result to the master node. As we shall show, the processing
order matters in this problem.

There are two requirements that our system needs to have. The master node
should be able to decode the intended result ($\mathbf{A}^{T}\mathbf{B}$ or
$\mathbf{A}^{T}\mathbf{x}$) from any $n-s$ workers for $s$ as large as
possible. i.e., $n-s$ is the recovery threshold of the scheme [3]. The second
requirement is that the master node should be able to recover
$\mathbf{A}^{T}\mathbf{B}$ or $\mathbf{A}^{T}\mathbf{x}$ as long as it
receives any $Q$ products from the worker nodes. This formulation subsumes
treating stragglers as non-working nodes. To our best knowledge, this second
requirement has not been examined systematically within the coded computation
literature, even though it is a natural constraint that allows for succinct
treatment of recovery in distributed computing clusters where the workers have
differing speeds.

######  Example 1.

Consider a system with $n=3$ worker nodes with $\gamma_{A}=2/3$. We partition
$\mathbf{A}$ into $\Delta_{A}=3$ block-columns and the assignment of block-
columns to each node is shown in Fig. 2 (this is an uncoded solution). We
emphasize that the order of the computation also matters here, i.e., worker
node $W_{0}$ (for example) computes $\mathbf{A}_{0}^{T}\mathbf{x}$ first and
then $\mathbf{A}_{1}^{T}\mathbf{x}$. For the specific assignment it is clear
that the computation is successful as long as any four block products are
returned by the workers. Thus, for this system $Q=4$.

$W_{0}$$W_{1}$$W_{2}$$\mathbf{A}_{0}^{T}\,\mathbf{x}$$\mathbf{A}_{1}^{T}\,\mathbf{x}$$\mathbf{A}_{1}^{T}\,\mathbf{x}$$\mathbf{A}_{2}^{T}\,\mathbf{x}$$\mathbf{A}_{2}^{T}\,\mathbf{x}$$\mathbf{A}_{0}^{T}\,\mathbf{x}$

Figure 2: Matrix $\mathbf{A}$ is partitioned into three submatrices. Each
worker is assigned two of those uncoded submatrices. Here $Q=4$.

On the other hand, Fig. 3 demonstrates a coded solution, where the bottom
assignment in the workers are some suitably chosen functions of the elements
of
$\\{\mathbf{A}_{0}^{T}\mathbf{x},\mathbf{A}_{1}^{T}\mathbf{x},\mathbf{A}_{2}^{T}\mathbf{x}\\}$.
For this assignment, it is obvious that the master node can recover
$\mathbf{A}^{T}\mathbf{x}$ as long as any three block products are returned by
the workers, so in this system $Q=3$.

$W_{0}$$W_{1}$$W_{2}$$\mathbf{A}_{0}^{T}\,\mathbf{x}$$\left(\mathbf{A}_{1}\,+\mathbf{A}_{2}\,\right)^{T}\mathbf{x}$$\mathbf{A}_{1}^{T}\,\mathbf{x}$$\left(\mathbf{A}_{2}\,+\mathbf{A}_{0}\,\right)^{T}\mathbf{x}$$\mathbf{A}_{2}^{T}\,\mathbf{x}$$\left(\mathbf{A}_{0}\,+\mathbf{A}_{1}\,\right)^{T}\mathbf{x}$

Figure 3: Matrix $\mathbf{A}$ is partitioned into three submatrices. Each
worker is assigned one uncoded and one coded task. Here $Q=3$.

For any time $t$, we let $w_{i}(t)$ represent the state of computation of the
$i$-th worker node, i.e., $w_{i}(t)$ is a non-negative integer such that
$0\leq w_{i}(t)\leq\ell$ which represents the number of tasks that have been
processed by worker node $i$. Thus, our system requirement states as long as
$\sum_{i=0}^{n-1}w_{i}(t)\geq Q$, the master node should be able to determine
$\mathbf{A}^{T}\mathbf{B}$ or $\mathbf{A}^{T}\mathbf{x}$. As $\Delta$, the
number of unknowns to be recovered, is a parameter that can be chosen, our
objective is to minimize the value of $Q/\Delta$ for such a system. For
matrix-vector multiplication, $\Delta=\Delta_{A}$, whereas for matrix-matrix
multiplication, $\Delta=\Delta_{A}\Delta_{B}$. This formulation minimizes the
worst case overall computation performed by the worker nodes.

###  II-A Related Work

Several coded computation schemes have been proposed for matrix multiplication
[1, 13, 3, 2, 14, 6, 7, 11, 15, 5], most of which are designed to mitigate the
full stragglers; see [16] for a tutorial overview. We illustrate the basic
idea below using the polynomial code approach of [3] for a system with $n=5$
workers where each of these worker nodes can store $\gamma_{A}=\frac{1}{2}$
fraction of matrix $\mathbf{A}$ and $\gamma_{B}=\frac{1}{2}$ fraction of
matrix $\mathbf{B}$. Consider $u=v=2$ and $p=1$, thus we partition both
$\mathbf{A}$ and $\mathbf{B}$ into two block-columns
$\mathbf{A}_{0},\mathbf{A}_{1}$ and $\mathbf{B}_{0},\mathbf{B}_{1}$
respectively. Next, we define two matrix polynomials as

$\displaystyle\mathbf{A}(z)$
$\displaystyle=\mathbf{A}_{0}+\mathbf{A}_{1}z\;\;\;\textrm{and}\;\;\;\mathbf{B}(z)=\mathbf{B}_{0}+\mathbf{B}_{1}z^{2};$
$\displaystyle\textrm{so}\;\mathbf{A}^{T}(z)\mathbf{B}(z)$
$\displaystyle=\mathbf{A}^{T}_{0}\mathbf{B}_{0}+\mathbf{A}_{1}^{T}\mathbf{B}_{0}z+\mathbf{A}_{0}^{T}\mathbf{B}_{1}z^{2}+\mathbf{A}_{1}^{T}\mathbf{B}_{1}z^{3}.$

The master node evaluates these polynomial $\mathbf{A}(z)$ and $\mathbf{B}(z)$
at distinct real values $z_{0},z_{1},\dots,z_{n-1}$, and sends the
corresponding matrices to worker node $W_{i}$. Each worker node computes the
product of its assigned submatrices. It follows that decoding at the master
node is equivalent to decoding a degree-3 real-valued polynomial. Thus, the
master node can recover $\mathbf{A}^{T}\mathbf{B}$ as soon as it receives the
results from any four workers, i.e., in this example, the recovery threshold
is, $\tau=4$. When $\gamma_{A}=1/k_{A}$ and $\gamma_{B}=1/k_{B}$ and $p=1$,
the work of [13] shows that their scheme has a threshold $\tau=k_{A}k_{B}$
which is optimal. Random coding solutions for this problem were investigated
in [17]. Approaches based on convolutional coding were presented in [10, 18].
In these schemes (analogous to linear block codes) there are systematic
workers that only contain uncoded assignments and parity workers that contain
coded assignments.

The case when $p>1$ was considered in the work of [2, 14, 13, 15]. Structuring
the computation in this manner increases the computational load on the workers
and the communication load from the workers to the master node but can reduce
the recovery threshold as compared to the case of $p=1$.

It is well-recognized that in several practical situations the underlying
matrices $\mathbf{A}$ and $\mathbf{B}$ are sparse. Computing the inner product
$\mathbf{a}^{T}\mathbf{x}$ of $n$-length vectors $\mathbf{a}$ and $\mathbf{x}$
where $\mathbf{a}$ has around $\delta n$ ($0<\delta\ll 1$) non-zero entries
takes $\approx 2\delta n$ floating point operations (flops) as compared to
$\approx 2n$ flops in the dense case. In general, the encoding process within
coded computation increases the number of non-zero entries in the resultant
encoded matrices. For instance, polynomial evaluations of degree $d$ will
increase the number of non-zero entries by approximately $d$ times. This
results in a $d$-fold increase in the worker computation times which can be
unacceptably high. Thus, it is important to consider schemes where the
encoding only combines a limited number of submatrices.

######  Example 2.

Consider an example with two large sparse matrices $\mathbf{A}$ and
$\mathbf{B}$ both of whose sizes are $10,000\times 10,000$. Both of them have
sparsity $\sigma=3\%$, i.e., randomly chosen approximately $3\%$ entries of
$\mathbf{A}$ and $\mathbf{B}$ are non-zero (we have used MATLAB command sprand
for this example). We partition matrices $\mathbf{A}$ and $\mathbf{B}$ into
$4$ and $5$ block-columns, respectively. First we choose a block-column
$\mathbf{A}_{i}$ and a block-column $\mathbf{B}_{j}$, and next we obtain two
coded submatrices $\tilde{\mathbf{A}}_{i}$ and $\tilde{\mathbf{B}}_{j}$ which
are random linear combinations of the uncoded block-columns of $\mathbf{A}$
and $\mathbf{B}$, respectively. Table I shows that it is around $4$ times more
expensive to compute the coded product than the uncoded product, although the
sizes of the corresponding matrices are exactly the same. The reason is that
the number of non-zero entries in the coded submatrices have gone up
significantly.

Table I: Computation time for sparse matrix multiplication. We choose matrices $\mathbf{A}$ and $\mathbf{B}$ both of size $10,000\times 10,000$. Both of them have sparsity $\sigma=3\%$, thus randomly chosen $3\%$ entries of $\mathbf{A}$ and $\mathbf{B}$ are non-zero. Job | Required time
---|---
To compute $\mathbf{A}^{T}\mathbf{B}$ |  $9.41$ seconds
To compute (uncoded) $\mathbf{A}_{i}^{T}\mathbf{B}_{j}$ |  $0.58$ seconds
To compute (coded) $\tilde{\mathbf{A}}_{i}^{T}\tilde{\mathbf{B}}_{j}$ |  $2.13$ seconds

An important aspect of coded computation is “numerical stability” of the
recovered result. Indeed, while coded computation borrows techniques from
classical coding theory (over finite fields), it differs in the sense that the
coded submatrices and the decoding operates over the reals. Over finite
fields, the invertibility of a matrix is sufficient to solve a system of
equations. In contrast, over the reals if the corresponding matrix is ill-
conditioned, then the recovery will in general be inaccurate. It is well-
recognized that real Vandermonde matrices corresponding to polynomial
interpolation have condition numbers that grow exponentially in the matrix
sizes. This is a serious issue with the polynomial-based approaches of [3],
[19]. There have been some works that have addressed these issues [10, 12, 17,
20, 21, 22, 23] in part.

Yet another feature of the coded computation problem that distinguishes it
from classical codes is the processing order. The worker nodes process the
assigned tasks in a specific order, such that if a worker node is processing a
given task, it has already completed the previously assigned tasks. Thus, at
any given time the pattern of tasks that have been completed is restricted.
Interestingly, codes for such systems have been investigated in [24, 25].
These ideas were adapted for the distributed matrix-vector multiplication
problem in [12].

We note here that in principle using polynomial approaches can allow us to
address both the optimal threshold and the optimal $Q/\Delta=1$ by simply
placing multiple evaluations of the polynomials at distinct points within each
worker node. However, this approach is not practical, firstly because of
numerical stability issues. Secondly, as discussed above when considering
sparse $\mathbf{A}$ and $\mathbf{B}$ matrices, the polynomial approaches
result in dense coded submatrices which can cause an unacceptable increase in
the worker node computation times. Numerical experiments supporting these
conclusions can be found in Section VI.

###  II-B Summary of Contributions

The contributions of our work can be summarized as follows.

  * •

We present a fine-grained model of the distributed matrix-vector and matrix-
matrix multiplication that allows us to (i) leverage the slower workers using
their partial computations and (ii) impose constraints on what extent coding
is allowed in the solution. This allows us to capture a scenario where workers
have differing speeds and the intended result can be recovered as long as the
workers together complete a minimum number ($Q$) of the assigned tasks. This
applies to the practically important case where the underlying matrices are
sparse. The formulation leads to new questions within coded computing that to
our best knowledge have not been investigated before systematically within the
coded computing literature.

  * •

We present systematic methods for both matrix-vector and matrix-matrix
multiplication that address both the recovery threshold and the $Q/\Delta$
metric. For the uncoded assignment case, we present a lower bound on the
performance of any scheme that our constructions are able to match.

  * •

We have proposed two different schemes for distributed computations, first of
which is named as $\beta$-level coding. In this approach, we have used
resolvable combinatorial designs [26] to improve the recovery threshold and
the $Q/\Delta$ metric over the uncoded approach. We have shown that the
metrics can be further improved if we utilize certain relations among the
blocks of different parallel classes within the resolvable designs.

  * •

Prior work has demonstrated schemes with the optimal recovery threshold for
certain storage fractions. In this work we present novel schemes that retain
the optimal recovery threshold and also have low $Q/\Delta$ values.

  * •

Finally, we present exhaustive experimental comparisons that demonstrate the
benefit of our schemes while considering sparse matrices in terms of worker
node computation times and numerical stability.

In Table II, we present a summary of the properties and the advantages of both
of our proposed approaches, $\beta$-level coding and sparsely coded straggler
(SCS) optimal scheme. Moreover, a detailed comparison of the properties of our
methods with other available schemes is demonstrated in Table III.

It should be noted that there are other issues within coded matrix
computations. Several works [27], [28] have considered the issue of private
computation along with the straggler mitigation issue. Here the goal is that
no information about the matrices $\mathbf{A}$ or $\mathbf{B}$ can be obtained
from any set of at most $m$ workers. Another class of codes [29], [30] assumes
the workers to be heterogeneous and time-varying, so that the system may have
access to different number of workers at different moments where the workers
may have different speeds and/or different storage capacities. These issues
are out of the scope of this paper.

Table II: Comparison between our proposed approaches. Here $\gamma_{A}$ and $\gamma_{B}$ indicate the storage fractions for matrices $\mathbf{A}$ and $\mathbf{B}$, respectively, and $n$ denotes the total number of workers. Approach | Properties | Parameter Regime | Advantages
---|---|---|---
$\beta$-level |  Combine $\beta$ submatrices |  For $\gamma_{A}=\frac{a_{1}}{a_{2}}$ and $\gamma_{B}=\frac{b_{1}}{b_{2}}$, | Assigned submatrices
Coding |  of $\mathbf{A}$ (or $\mathbf{B}$) |  we need $\;n=ca_{2}b_{2}$ | are sparse
SCS Optimal | Majority of assigned |  For $\gamma_{A}=\frac{1}{k_{A}}$ and $\gamma_{B}=\frac{1}{k_{B}}$, | Optimal Recovery
Scheme | submatrices are uncoded |  where $k_{A}$ and $k_{B}$ are integers |  Threshold ($k_{A}k_{B}$)
Table III: Comparison with existing works. Codes | Mat-Mat | Optimal | Numerical | Partial | Sparsely
---|---|---|---|---|---
Mult? | Threshold? | Stability? | Comput? | Coded?
Repetition Codes | ✓ | ✗ | ✓ | ✗ | ✓
Rateless Codes [6] | ✗ | ✗ | ✓ | ✗ | ✗
Prod. Codes [31], Factored Codes [23] | ✓ | ✗ | ✓ | ✗ | ✗
Polynomial Codes [3] | ✓ | ✓ | ✗ | ✗ | ✗
Biv. Hermitian Poly. Code [32] | ✓ | ✓ | ✗ | ✓ | ✗
Dynamic Hetero.-Aware Code [29] | ✗ | ✗ | ✓ | ✓ | ✗
OrthoPoly [21], RKRP code[17] | ✓ | ✓ | ✓ | ✗ | ✗
Conv. Code [10], Circ. & Rot. Mat. [20] | ✓ | ✓ | ✓ | ✗ | ✗
C3LES [11] | ✗ | ✗ | ✓ | ✓ | ✓
$\beta$-level Coding (proposed) | ✓ | ✗ | ✓ | ✓ | ✓
SCS Optimal Scheme (proposed) | ✓ | ✓ | ✓ | ✓ | ✓

##  III Preliminaries

In this section we discuss some basic facts and observations that serve to
explain our proposed distributed matrix computation schemes. Suppose that a
given worker node is assigned encoded block-columns
$\tilde{\mathbf{A}}_{i},i=0,1,\dots,\ell_{A}-1$ and
$\tilde{\mathbf{B}}_{j},j=0,1,\dots,\ell_{B}-1$. The assignment also specifies
a top to bottom order. For the matrix-vector problem, the node processes them
simply in the order
$\tilde{\mathbf{A}}^{T}_{0}\mathbf{x},\tilde{\mathbf{A}}^{T}_{1}\mathbf{x},\dots,\tilde{\mathbf{A}}^{T}_{\ell_{A}-1}\mathbf{x}$.
On the other hand for the matrix-matrix problem the node computes in the order
$\tilde{\mathbf{A}}_{0}^{T}\tilde{\mathbf{B}}_{0},\tilde{\mathbf{A}}_{0}^{T}\tilde{\mathbf{B}}_{1},\dots,\tilde{\mathbf{A}}_{0}^{T}\tilde{\mathbf{B}}_{\ell_{B}-1},\tilde{\mathbf{A}}_{1}^{T}\tilde{\mathbf{B}}_{0},\dots,\tilde{\mathbf{A}}_{1}^{T}\tilde{\mathbf{B}}_{\ell_{B}-1},$
$\dots,\tilde{\mathbf{A}}_{\ell_{A}-1}^{T}\tilde{\mathbf{B}}_{0},\dots,\tilde{\mathbf{A}}_{\ell_{A}-1}^{T}\tilde{\mathbf{B}}_{\ell_{B}-1}$.

######  Definition 1.

A coding scheme for distributed matrix computation is said to be a
$\beta$-level coding scheme if the assigned block-columns are a linear
combination of exactly $\beta$ block-columns of $\mathbf{A}$ and $\mathbf{B}$.
The case of $\beta=1$ represents an uncoded scheme.

Our constructions leverage the properties of combinatorial structures known as
resolvable designs [26].

######  Definition 2.

A resolvable design is a pair $(\mathcal{X},\mathcal{A})$ where $\mathcal{X}$
is a set of elements (called points) and $\mathcal{A}$ is a family of non-
empty subsets of $\mathcal{X}$ (called blocks) that have the same cardinality.
A subset $\mathcal{P}\subset\mathcal{A}$ in a design
$(\mathcal{X},\mathcal{A})$ is called a parallel class if
$\cup_{\\{i:\mathcal{A}_{i}\in\mathcal{P}\\}}\mathcal{A}_{i}=\mathcal{X}$ and
if $\mathcal{A}_{i}\cap\mathcal{A}_{j}=\emptyset$ for
$\mathcal{A}_{i},\mathcal{A}_{j}\in\mathcal{P}$ when $i\neq j$. A partition of
$\mathcal{A}$ into several parallel classes is called a resolution and
$(\mathcal{X},\mathcal{A})$ is said to be a resolvable design if $\mathcal{A}$
has at least one resolution [26].

A resolvable design always exists if the cardinality of a block divides
$|\mathcal{X}|$.

######  Example 3.

Let $\mathcal{X}=\\{0,1,2,3\\}$ and
$\mathcal{A}=\\{\\{0,1\\},\\{0,2\\},\\{0,3\\},\\{1,2\\},\\{1,3\\},\\{2,3\\}\\}$.
Now $(\mathcal{X},\mathcal{A})$ forms a resolvable design with parallel
classes, $\mathcal{P}_{0}=\\{\\{0,1\\},\\{2,3\\}\\}$,
$\mathcal{P}_{1}=\\{\\{0,2\\},\\{1,3\\}\\}$ and
$\mathcal{P}_{2}=\\{\\{0,3\\},\\{1,2\\}\\}$.

We note that the specification of the “incidence relations” between the points
and blocks of a design can also be shown by means of an incidence matrix.

######  Definition 3.

The incidence matrix $\mathcal{N}$ of a design $(\mathcal{X},\mathcal{A})$ is
a $|\mathcal{X}|\times|\mathcal{A}|$ binary matrix such that the $(i,j)$-th
entry is a $1$ if the $i$-th point is a member of the $j$-th block and zero,
otherwise.

For example, the incidence matrix for the resolvable design in Example 3 is
given by

$\displaystyle\mathcal{N}=\begin{bmatrix}1&1&1&0&0&0\\\ 1&0&0&1&1&0\\\
0&1&0&1&0&1\\\ 0&0&1&0&1&1\\\ \end{bmatrix}.$

We will use a cyclic assignment of tasks extensively in our constructions. We
illustrate this by means of the following matrix-vector multiplication
example.

######  Example 4.

$W_{0}$$W_{1}$$W_{2}$$W_{3}$$W_{4}$$\mathbf{A}_{0}^{T}\,\mathbf{x}$$\mathbf{A}_{1}^{T}\,\mathbf{x}$$\mathbf{A}_{2}^{T}\,\mathbf{x}$$\mathbf{A}_{1}^{T}\,\mathbf{x}$$\mathbf{A}_{2}^{T}\,\mathbf{x}$$\mathbf{A}_{3}^{T}\,\mathbf{x}$$\mathbf{A}_{2}^{T}\,\mathbf{x}$$\mathbf{A}_{3}^{T}\,\mathbf{x}$$\mathbf{A}_{4}^{T}\,\mathbf{x}$$\mathbf{A}_{3}^{T}\,\mathbf{x}$$\mathbf{A}_{4}^{T}\,\mathbf{x}$$\mathbf{A}_{0}^{T}\,\mathbf{x}$$\mathbf{A}_{4}^{T}\,\mathbf{x}$$\mathbf{A}_{0}^{T}\,\mathbf{x}$$\mathbf{A}_{1}^{T}\,\mathbf{x}$

Figure 4: Partitioning matrix $\mathbf{A}$ into five submatrices and assigning
three uncoded tasks in a cyclic fashion to the workers. The system is
resilient to two stragglers and $Q=10$. The tasks enclosed in dots can be
processed without processing any copy of $\mathbf{A}_{4}^{T}\mathbf{x}$.

Consider an example of computing $\mathbf{A}^{T}\mathbf{x}$, where we have
$n=5$ workers and each worker can process $\gamma=3/5$ fraction of the total
job. We partition $\mathbf{A}$ into $\Delta=5$ block-columns:
$\mathbf{A}_{0},\mathbf{A}_{1},\dots,\mathbf{A}_{4}$. Let
$\mathcal{X}=\\{0,1,2,3,4\\}$. If we do not incorporate any coding among the
block-columns, then for $\beta=1$, we have the trivial parallel class
$\mathcal{P}=\\{\\{0\\},\\{1\\},\dots,\\{4\\}\\}$. Fig. 4 shows a cyclic
assignment of jobs where three uncoded submatrices are allocated to each of
the workers in a cyclic fashion according to the indices of three elements of
$\mathcal{P}$. It can be easily verified that the system is resilient to $s=2$
stragglers. In the sequel, our assignment can be coded as well.

More generally, suppose that we have $\Delta$ symbols denoted
$0,\dots,\Delta-1$, $n=\Delta$ worker nodes and $\ell$ symbols to be placed in
each worker node where $\ell\leq\Delta$. The symbols can be encoded block-
columns of $\mathbf{A}$ or the product of encoded block-columns of
$\mathbf{A}$ and $\mathbf{B}$. A cyclic assignment in this case assigns the
set $\\{j,j+1,\dots,j+\ell-1\\}\pmod{\Delta}$ to worker $W_{j}$; symbol $j$
appears at the top and sequentially symbol $(j+\ell-1)$ (the values are
reduced modulo $\Delta$) at the bottom. The node $W_{j}$ processes the tasks
specified by the symbols from top to bottom. Within a node, the position of a
symbol is denoted by an integer between $0$ and $\ell-1$, where $0$ denotes
the top and $\ell-1$ denotes the bottom.

######  Lemma 1.

The cyclic assignment satisfies the following properties.

  * •

Each symbol appears $\ell$ times across $n$ worker nodes. Furthermore, it
appears in each position $0,\dots,\ell-1$ exactly once, across all $n$
workers.

  * •

Let $\alpha_{c}$ be the maximum number of symbols that can be processed across
all worker nodes such that a specific symbol $j$ is processed exactly $c$
times (where $0\leq c\leq\ell$). Then,
$\alpha_{c}=\Delta\ell-\frac{\ell(\ell+1)}{2}+\sum_{i=0}^{c-1}(\ell-i)$,
independent of $j$.

###### Proof.

The first claim follows since $\ell\leq\Delta=n$ and symbol $j$, where $0\leq
j\leq\Delta-1$, appears in workers $j,j-1,j-2,\dots,j-\ell+1$ (indices reduced
modulo-$\Delta$).

For the second claim we proceed by contradiction. Suppose that there is a
symbol $j$ for which the condition is violated. From part $(a)$, symbol $j$
appears once in positions $0,\dots,\ell-1$ across the workers. Thus, one can
process at most
$(\Delta-\ell)\ell+\sum_{i=0}^{\ell-1}i=\Delta\ell-\frac{\ell(\ell+1)}{2}$
symbols without processing any copy of $j$. Following this, any symbol
processed will necessarily process symbol $j$. If we process the copy of $j$
at position $i$, we can process another $\ell-1-i$ symbols without processing
another copy of $j$. Therefore, the maximum number of symbols that can be
processed such that $c$ copies of $j$ are processed are
$\Delta\ell-\frac{\ell(\ell+1)}{2}+\sum_{i=0}^{c-1}(\ell-i)$. ∎

##  IV $\beta$-level Coding for Distributed Computations

We begin our discussion of $\beta$-level coding by considering the uncoded
$\beta=1$ case. In this scenario, the assignments are simply elements such as
$\mathbf{A}_{i}^{T}\mathbf{x}$ (in the matrix-vector case) or elements such as
$\mathbf{A}_{i}^{T}\mathbf{B}_{j}$ (in the matrix-matrix case). In the
discussion below we refer the assignment of “symbols” to treat both cases
together, where a symbol can either be of the form
$\mathbf{A}_{i}^{T}\mathbf{x}$ or $\mathbf{A}_{i}^{T}\mathbf{B}_{j}$. Note
that we can disregard the case when multiple copies of a symbol appear within
the same worker node. Consider a $\langle n,\ell,\Delta,r\rangle$-uncoded
system with $n$ workers each of which can process $\ell\geq 1$ symbols out of
a total of $\Delta$ symbols. We assume that each symbol appears $r$ times
across the different worker nodes, so $n\ell=\Delta r$. Now we show a lower
bound on the value of $Q$ for such a system.

######  Theorem 1.

For a $\langle n,\ell,\Delta,r\rangle$-uncoded system we have $Q\geq\Delta
r-\frac{r}{2}\,(\ell+1)+1$.

###### Proof.

For the system under consideration, let $Q_{j}$ represent the maximum number
of symbols that are processed in the worst case without processing symbol $j$
(see Fig. 4 for an example). It is evident in this case that
$Q=\max_{j=0,\dots,\Delta-1}Q_{j}+1$.

Our strategy is to calculate the average
$\overline{Q}=\frac{1}{\Delta}\sum_{j=0}^{\Delta-1}Q_{j}$ and use the simple
bound $Q\geq\overline{Q}+1$. Toward this end, note that for any uncoded
solution, we can calculate $\sum_{j=0}^{\Delta-1}Q_{j}$ in a different way.
For any worker $i$, there are $\ell$ assigned block-columns and the other
$\Delta-\ell$ do not appear in it. Thus, in the calculation of
$\sum_{j=0}^{\Delta-1}Q_{j}$, worker node $i$ contributes

$\displaystyle(\Delta-\ell)\ell+\sum\limits_{k=1}^{\ell}(k-1)\;\;\textrm{symbols},$

which is clearly independent of $i$. Therefore,

$\displaystyle\overline{Q}=n\;\frac{\left[\sum\limits_{k=1}^{\ell}(k-1)+(\Delta-\ell)\ell\right]}{\Delta}=n\ell-\frac{n\ell}{2\Delta}(\ell+1).$

Thus, we have the lower bound as

$\displaystyle Q\geq\Delta r-\frac{r}{2}\,(\ell+1)+1$ (1)

since $n\ell=\Delta r$. ∎

######  Remark 1.

In general, we are given the number of workers $n$ and the storage fraction
$\gamma$. The parameters $\Delta$ and $\ell$ can be treated as design
parameters. In this setting, from (1), we have

$\displaystyle\frac{Q}{\Delta}\geq
r-\frac{r}{2}\frac{\ell}{\Delta}-\frac{r}{2\Delta}+\frac{1}{\Delta};\;\;\;\textrm{but
$r=n\gamma$, thus}\;\;\;\frac{Q}{\Delta}\geq
n\gamma\left(1-\frac{\gamma}{2}\right)+\left(1-\frac{n\gamma}{2}\right)\frac{1}{\Delta}.$
(2)

If $r=n\gamma>2$, then the second term in the RHS above is negative and has an
inverse dependence on $\Delta$.

The lower bound in (1) is met with equality when we consider the cyclic
assignment scheme. For instance, Fig. 4 shows an example where $\Delta=n=5$,
and it can be verified that $Q=10$ and meets the lower bound in (1). A similar
result holds for the matrix-matrix case. These results are discussed in the
relevant parts of the remainder of this section.

###  IV-A Matrix-vector Multiplication

We consider a $\beta$-level coding matrix-vector scenario where the storage
fraction $\gamma=a_{1}/a_{2}$ for positive integers $a_{1}$ and $a_{2}$ with
$a_{1}\leq a_{2}$ such that $\gamma\leq\frac{1}{\beta}$. We assume that the
number of worker nodes $n=ca_{2}$ where $c$ is a positive integer.

We partition $\mathbf{A}$ into $\Delta$ block-columns where $\Delta$ is
divisible by $\beta$. Next, we pick a resolvable design
$(\mathcal{X},\mathcal{A})$ where $\mathcal{X}=\\{0,\dots,\Delta-1\\}$. The
size of the blocks in $\mathcal{A}$ is $\beta$. Let
$\mathcal{P}_{1},\mathcal{P}_{2},\dots$ denote distinct parallel classes of
this design. We will refer to the blocks of the design as meta-symbols (to
avoid potential confusion with the term block-columns which we also have used
extensively). Thus, the elements of a parallel class are meta-symbols.

The overall idea is to partition the set of worker nodes into $c$ groups
denoted $\mathcal{G}_{0},\dots,\mathcal{G}_{c-1}$. For each group we pick a
parallel class and place meta-symbols from the parallel class in a cyclic
fashion. The parallel classes for the different groups can be the same as
well. For each meta-symbol, we generate a coded block-column by choosing a
random linear combination of the $\beta$ block-columns within it. In the
discussion below we refer to the block-columns as “unknowns” as they need to
be decoded by the master nodes. A precise description appears in Algorithm 1.
We illustrate it by means of an example below.

Input : Matrix $\mathbf{A}$ and vector $\mathbf{x}$. Storage fraction
$\gamma=\frac{a_{1}}{a_{2}}\leq\frac{1}{\beta}$, $\beta$-allowed coding level,
and number of workers $n=ca_{2}$ where $c$ is a positive integer.

1 Set $\Delta=\beta a_{2}$. Partition $\mathbf{A}$ into $\Delta$ block-
columns;

2 Number of assigned blocks per worker, $\ell=\Delta\gamma$;

3 Assume $\mathcal{X}=\\{0,1,2,\dots,\Delta-1\\}$ and find $c$ parallel
classes $\mathcal{P}_{i}$ having a block size $\beta$, $i=0,1,\dots,c-1$;

4

5for  _$i\leftarrow 0$ to $c-1$_ do

6 Let the blocks of $\mathcal{P}_{i}$ be denoted as
$p_{0},p_{1},\dots,p_{\frac{\Delta}{\beta}-1}$ ;

7 for  _$j\leftarrow 0$ to $\frac{\Delta}{\beta}-1$_ do

8 Assign meta-symbols $p_{j},p_{j+1},\dots,p_{j+\ell-1}$ from top to bottom
(indices reduced modulo $a_{2}$) and vector $\mathbf{x}$ to worker
$\frac{\Delta}{\beta}i+j$;

9 For each meta-symbol choose a random linear combination of length-$\beta$ of
the constituent block-columns;

10

11 end for

12

13 end for

Output : Distributed matrix-vector multiplication scheme having $\beta$-level
coding.

Algorithm 1 $\beta$-level coding scheme for distributed matrix-vector
multiplication

$W_{0}$$W_{1}$$W_{2}$$W_{3}$$\\{0,1,2\\}$$\\{3,4,5\\}$$\\{6,7,8\\}$$\\{3,4,5\\}$$\\{6,7,8\\}$$\\{9,10,11\\}$$\\{6,7,8\\}$$\\{9,10,11\\}$$\\{0,1,2\\}$$\\{9,10,11\\}$$\\{0,1,2\\}$$\\{3,4,5\\}$

Figure 5: Job assignment for worker group $\mathcal{G}_{0}$ for $\beta$-level
matrix-vector multiplication scheme for $n=12$ with $\gamma_{A}=\frac{1}{4}$
and $\Delta_{A}=12$ using a single parallel class with $\beta=3$. The indices
$\\{i,j,k\\}$ indicates a random linear combination of the submatrices
$\mathbf{A}_{i},\mathbf{A}_{j}$ and $\mathbf{A}_{k}$. $\mathcal{G}_{1}$ and
$\mathcal{G}_{2}$ are assigned the same symbols as workers $0-3$ but with
different random coefficients.

######  Example 5.

Consider a scenario with $n=12$, $\gamma=1/4$ and $\beta=3$, and set
$\Delta=12$. We let $\mathcal{X}=\\{0,1,\dots,11\\}$ and pick
$\mathcal{P}=\\{\\{0,1,2\\},\\{3,4,5\\},\\{6,7,8\\},\\{9,10,11\\}\\}$. In this
example, all three groups use the same parallel class $\mathcal{P}$. As shown
in Fig. 5, in each group the meta-symbols are arranged in a cyclic fashion.
For each meta-symbol a random linear combination is chosen, e.g. in worker
$W_{0}$ the meta symbol $\\{0,1,2\\}$ will be replaced by
$\tilde{\mathbf{A}}_{0}=z_{0}\mathbf{A}_{0}+z_{1}\mathbf{A}_{1}+z_{2}\mathbf{A}_{2}$
where the $z_{i}$’s are chosen at random. This implies that $W_{0}$ is
responsible for computing $\tilde{\mathbf{A}}_{0}^{T}\mathbf{x}$, and the
unknowns $\mathbf{A}_{0}^{T}\mathbf{x},\mathbf{A}_{1}^{T}\mathbf{x}$ and
$\mathbf{A}_{2}^{T}\mathbf{x}$ can be decoded if three copies of the meta-
symbol $\\{0,1,2\\}$ are obtained from the workers as the corresponding
equations are linearly independent with probability 1.

######  Theorem 2.

Consider a distributed matrix-vector multiplication scheme for $n=ca_{2}$
workers where each worker can store $\gamma=\frac{a_{1}}{a_{2}}$ fraction of
matrix $\mathbf{A}$. Suppose that $c\geq\beta$ and we use the same parallel
class $\mathcal{P}$ over all the worker groups. Then, the scheme described in
Alg. 1 will be resilient to $s=c\ell-\beta$ stragglers, and
$Q=n\ell-\frac{c\ell(\ell+1)}{2}+\ell(\beta-1)+1$.

###### Proof.

Based on our construction we know that any meta-symbol $\in\mathcal{P}$ will
appear in $\ell$ distinct workers in each worker group consisting of
$\Delta/\beta=a_{2}$ workers (cf. Lemma 1). Thus there are $\frac{n}{a_{2}}=c$
such worker groups and it follows that there are a total of $c\ell$
appearances of that meta-symbol across all the worker nodes. Furthermore, each
meta-symbol corresponds to a random linear combination of the corresponding
unknowns (block-columns). As the choice of these random coefficients is made
from a continuous distribution, as long as any $\beta$ meta-symbols are
processed across all the worker nodes, the constituent unknowns will be
decodable with probability $1$. Thus, the scheme is resilient to the failure
of any $c\ell-\beta$ stragglers.

For the second claim, suppose that there exists a meta-symbol
$\star\in\mathcal{P}$ that is processed at most $\beta-1$ times when
$n\ell-\frac{c\ell(\ell+1)}{2}+\ell(\beta-1)+1$ meta-symbols have been
processed. For each worker group, the meta-symbol $\star$ appears in all the
positions $0,\dots,\ell-1$. Suppose that $\star$ appears $i$ times in
$\eta_{i}$ worker groups for $i=1,\dots,y$. Thus,
$\sum_{i=1}^{y}i\eta_{i}\leq\beta-1$ and the maximum number of meta-symbols
that can be processed is

$\displaystyle
Q{{}^{\prime}}=\sum_{i=1}^{y}\eta_{i}\alpha_{i}+(c-\sum_{i=1}^{y}\eta_{i})\alpha_{0}$

where $\alpha_{0}=\frac{\Delta}{\beta}\ell-\frac{\ell(\ell+1)}{2}$ and
$\alpha_{i}=\alpha_{0}+\sum_{j=0}^{i-1}(\ell-i)=\alpha_{0}+i\ell-\frac{i(i-1)}{2}$
as specified in Lemma 1 (by setting the number of symbols to $\Delta/\beta$).
Thus,

$\displaystyle
Q^{{}^{\prime}}=c\alpha_{0}+\ell\sum\limits_{i=1}^{y}i\eta_{i}-\sum\limits_{i=1}^{y}\eta_{i}\frac{i(i-1)}{2}\leq
c\alpha_{0}+\ell(\beta-1)$ (3)

since we have $\sum_{i=1}^{y}i\eta_{i}\leq\beta-1$. Equality holds in (3) if
we have $y=1$ and $\eta_{1}=\beta-1$.

In the worst case therefore, we can process $\alpha_{1}$ symbols from
$\beta-1$ groups and $\alpha_{0}$ symbols from the remaining groups. This
gives a total of

$(\beta-1)\alpha_{1}+(c-\beta+1)\alpha_{0}=n\ell-\frac{c\ell(\ell+1)}{2}+\ell(\beta-1)$

symbols, which is the same as the upper bound in (3). Thus if $Q\geq
n\ell-\frac{c\ell(\ell+1)}{2}+\ell(\beta-1)+1$ then we are guaranteed that
every meta-symbol is processed at least $\beta$ times. This concludes the
proof. ∎

It can be verified that the distributed matrix-vector multiplication scheme
shown in Fig. 5 is resilient to $s=c\ell-\beta=3\times 3-3=6$ stragglers and
has $Q=25$. Theorem 2 provides the value for $s$ and $Q$ for distributed
matrix-vector multiplication when $\beta\leq c$. In Appendix -A, we show the
calculation for $s$ and $Q$ for the case when $\beta>c$.

######  Remark 2.

The proposed $\beta$-level coding scheme leads to an algorithm for uncoded
matrix-vector multiplication when we set $\beta=1$ (see Fig. 4 for an
example). The ratio $Q/\Delta$ for the construction in Alg. 1 is lower in
general as compared to the scheme in [11]. For instance, with $n=10$ and
$\gamma=2/5$, Alg. 1 results in a scheme with $Q/\Delta=3.0$, whereas the [11]
scheme has $Q/\Delta=3.1$. The reduction is due to the lower value of $\Delta$
(cf. Remark 1).

######  Remark 3.

For $\beta>1$ the $Q/\Delta$ ratio can be reduced significantly as compared to
the uncoded ($\beta=1$) case. To see this consider $n=ca_{2}$ and
$\gamma=\frac{a_{1}}{a_{2}}$, where $c\geq\beta$. For the uncoded case, we set
$\Delta_{unc}=a_{2}$, and we have $Q_{unc}=n\ell-\frac{c\ell(\ell+1)}{2}+1$
where $\ell=a_{1}$. On the other hand for $\beta$-level coding, we set
$\Delta_{\beta}=\beta a_{2}$, and we have
$Q_{\beta}=n\ell-\frac{c\ell(\ell+1)}{2}+\ell(\beta-1)+1$ where $\ell=\beta
a_{1}$. This implies that

$\displaystyle\frac{Q_{unc}}{\Delta_{unc}}-\frac{Q_{\beta}}{\Delta_{\beta}}$
$\displaystyle=(\beta-1)\left(\gamma\left(\frac{ca_{1}}{2}-1\right)+\frac{1}{\beta
a_{2}}\right)>0.$

It turns out that the recovery threshold can be further reduced if we
judiciously choose different parallel classes for the different worker groups
in Alg. 1. Utilizing these parallel classes, we present a method that improves
on Theorem 2 if we assume the property that the blocks among different
parallel classes have intersection size to be at most one. Before stating the
theorem, we discuss the decodabilty of the approach since this is not as
straightforward as the single parallel class $\beta$-level coding.

To understand the decoding in this setting we consider a bipartite graph
$\mathbf{G}_{dec}=\mathcal{U}\cup\mathcal{V}$ whose vertex set consists of the
unknowns ($\mathcal{U}$) on the left and the processed meta-symbols
($\mathcal{V}$) on the right; an example is shown in Fig. 6. A meta-symbol is
connected to its constituent unknowns. Note that $\mathbf{G}_{dec}$ specifies
a system of equations in $\Delta$ unknowns and we need to argue that this
system is invertible. In the argument below, suppose that the random linear
coefficients of each meta-symbol are indeterminates and we argue that there
exists a matching in $\mathbf{G}_{dec}$ where all the unknowns in
$\mathcal{U}$ are matched.

$u_{0}$$u_{1}$$u_{2}$$u_{3}$$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$\mathcal{U}$Unknowns$\mathcal{V}$Symbols

Figure 6: For the case $\beta=2$, every symbol is a random linear combination
of two unknowns, thus there is a bipartite graph between the unknowns and
symbols.

Consider a set $\tilde{\mathcal{U}}$ of $d$ unknowns from $\mathbf{G}_{dec}$
and the corresponding neighborhood
$\tilde{\mathcal{V}}=\mathcal{N}(\tilde{\mathcal{U}})$. Suppose we have a set
of equations where these $d$ unknowns, namely $u_{0},u_{1},\dots,u_{d-1}$,
participate in $\ell_{0},\ell_{1},\dots,\ell_{d-1}$ equations. Thus the number
of outgoing edges from $\tilde{\mathcal{U}}$ is $\sum_{i=0}^{d-1}\ell_{i}$. On
the other hand, because of the structure of $\beta$-level coding approach, any
symbol in $\tilde{\mathcal{V}}$ has a degree $\beta$, thus the number of
incoming edges in $\tilde{\mathcal{V}}$ is $\beta|\tilde{\mathcal{V}}|$.

Now, suppose that a matching where all the elements of $\mathcal{U}$ are
matched does not exist. Hall’s marriage theorem [33] gives a necessary and
sufficient condition for the existence of the matching. Suppose that Hall’s
condition is violated for the set $\tilde{\mathcal{U}}$, i.e.,
$|\tilde{\mathcal{V}}|\leq d-1$. This means that

$\displaystyle\sum\limits_{i=0}^{d-1}\ell_{i}\;\leq\;\beta(d-1).$ (4)

######  Lemma 2.

Suppose that $\mathbf{G}_{dec}$ is such that each of $\Delta$ unknowns has at
least degree $1$ and at least $\Delta-1$ unknowns have degree at least $\beta$
each. Then, the master node can decode all the unknowns.

###### Proof.

First, consider $d=1$, so $|\tilde{\mathcal{U}}|=1$. Since each unknown has at
least degree $1$, thus $\sum_{i=0}^{d-1}\ell_{i}\geq 1>\beta(d-1)$. Next we
consider any set of $d\geq 2$ unknowns, where we know that at least $(d-1)$
unknowns have degree at least $\beta$. In that case,
$\sum_{i=0}^{d-1}\ell_{i}\geq 1+\beta(d-1)>\beta(d-1)$. Thus (4) cannot be
satisfied for any $d\geq 2$. So, there exists a matching in $\mathbf{G}_{dec}$
where all the unknowns are matched, hence the master node can decode all the
unknowns. ∎

Now we state the result when different parallel classes are utilized.

######  Theorem 3.

Consider $c$ distinct parallel classes (with block size $\beta$) such that the
size of the intersection between any two blocks from different parallel
classes is at most $1$. Using Alg. 1, the distributed matrix-vector
multiplication scheme can be resilient to at least $c\ell-\beta+\lambda$
stragglers, when $c\geq\beta+\lambda$ and $\lambda<\beta$.

###### Proof.

The main idea is to find the scenario where Lemma 2 can be directly
applicable. To establish that we consider two unknowns $u_{0}$ and $u_{1}$.
The event that a pair of unknowns belong to the same meta-symbol can happen
within at most one parallel class (in other words, within only one worker
group) according to our choices of parallel classes. Thus in the remaining
$(c-1)$ worker groups, those two unknowns exist in different meta-symbols. If
they appear in the same meta-symbol, then there are $\ell$ workers within the
worker group where they appear. On the other hand, if they appear in different
meta-symbols, then there are at least $\ell+1$ workers within the worker group
where either $u_{0}$ or $u_{1}$ or both appear as part of a meta-symbol.

So, the unknowns $u_{0}$ or $u_{1}$ or both participate in different meta-
symbols in at least in $\ell+(\ell+1)(c-1)$ workers. Now since we have
$c\ell-\beta+\lambda$ stragglers, using $c\geq\beta+\lambda$, we have still

$\displaystyle\ell+(\ell+1)(c-1)-\left(c\ell-\beta+\lambda\right)\geq
2\beta-1\;$

workers left. This means that either $u_{0}$ or $u_{1}$ or both exist in at
least $2\beta-1$ workers after the stragglers are removed. This in turn
implies that the corresponding $\mathbf{G}_{dec}$ has at least $2\beta-1$
edges emanating from the pair of unknowns $u_{0}$ and $u_{1}$, so that at
least one of them has degree $\geq\beta$. Thus Lemma 2 is satisfied and we can
decode all the unknowns. ∎

######  Example 6.

Consider a scenario with $n=20$ workers with $\gamma=\frac{1}{5}$, thus $c=4$,
and we apply $\beta$-level coding approach with $\beta=3$. In this regard, we
incorporate $four$ different parallel classes of block size $\beta=3$ obtained
from the solution of the famous Kirkman’s Schoolgirl problem [34], where any
two blocks from any two different parallel classes have an intersection size
at most $one$. It can be verified that the distributed matrix-vector
multiplication scheme will be resilient to at least $s=c\ell-\beta+1=10$
stragglers whereas the number of stragglers if we used the single parallel
class would have been $9$.

Table IV compares experimental results for different matrix-vector
multiplication approaches in terms of number of stragglers and $Q/\Delta$
values. For every case, we observe a significant improvement of the metrics if
we incorporate multiple parallel classes instead of a single parallel class.
We note here that the $Q/\Delta$ was computed via computer experiments.

Table IV: Comparison of different metrics for different approaches. System | Metrics | Dense Codes |  $\beta$-level Coding |  $\beta$-level Coding
---|---|---|---|---
[3], [17], [21] | (Single parallel class) | (Multiple parallel classes)
$n=8$, $\gamma_{A}=\frac{1}{4}$ | $s$ | $4$ | $2$ | $3$
and $\;\beta=2$ | $Q/\Delta$ | $-$ | $13/8$ | $11/8$
$n=8$, $\gamma_{A}=\frac{1}{4}$ | $s$ | $4$ | $3$ | $4$
and $\;\beta=3$ | $Q/\Delta$ | $-$ | $19/12$ | $14/12$
$n=10$, $\gamma_{A}=\frac{1}{5}$ | $s$ | $5$ | $3$ | $4$
and $\;\beta=3$ | $Q/\Delta$ | $-$ | $25/15$ | $20/15$

The analysis in Theorem 3 above is somewhat loose as we only assume that the
intersection sizes between blocks from different parallel classes is at most
1. Indeed, exploiting more structure in the choice of the parallel classes can
yield better results, though the analysis becomes significantly harder. Here
we present a method that improves on Theorem 2 when
$c=\beta=2,\ell\leq\Delta/2-2$ and $\Delta\geq 8$. Let
$\mathcal{X}=\\{0,1,\dots,\Delta-1\\}$ where $\Delta=n=2a_{2}$. The block size
of the design is two and the parallel classes are given as follows.

$\displaystyle\mathcal{P}_{0}$
$\displaystyle=\left\\{\\{0,1\\},\\{2,3\\},\dots,\\{\Delta-2,\Delta-1\\}\right\\}$
$\displaystyle\textrm{and}\;\;\mathcal{P}_{1}$
$\displaystyle=\left\\{\\{0,5\\},\\{2,7\\},\dots,\\{\Delta-2,3\\}\right\\}.$
(5)

Thus, the $i$-th block in $\mathcal{P}_{0}$ and $\mathcal{P}_{1}$, for $0\leq
i\leq\Delta/2-1$ is given by $\\{2i,2i+1\\}$ and $\\{2i,2i+5\\}\pmod{\Delta}$,
respectively. We follow the Alg. 1 for the specification of the coding scheme.

######  Theorem 4.

Let $c=\beta=2$, $\ell\leq\Delta/2-2$ and $\Delta\geq 8$. If we use the
parallel classes in (IV-A), then the matrix-vector scheme described in Alg. 1
will be resilient to $s=2\ell-1$ stragglers, and $Q=n\ell-\ell(\ell+1)+1$.

###### Proof.

The detailed proof is discussed in Appendix -B ∎

###  IV-B Matrix-matrix Multiplication

Now we consider the case of matrix-matrix multiplication, where we assume that
each of the $n$ worker nodes can store $\gamma_{A}=\frac{a_{1}}{a_{2}}$ and
$\gamma_{B}=\frac{b_{1}}{b_{2}}$ fractions of matrices $\mathbf{A}$ and
$\mathbf{B}$. In this case, we consider $\beta_{A}$ and $\beta_{B}$-level
coding for $\mathbf{A}$ and $\mathbf{B}$, respectively so that
$\gamma_{A}\leq\frac{1}{\beta_{A}}$ and $\gamma_{B}\leq\frac{1}{\beta_{B}}$.
We partition matrices $\mathbf{A}$ and $\mathbf{B}$ into $\Delta_{A}$ and
$\Delta_{B}$ block-columns, respectively, and so, we have, in total,
$\Delta=\Delta_{A}\Delta_{B}$ unknowns. Next we assign
$\ell_{A}=\Delta_{A}\gamma_{A}$ block-columns from $\mathbf{A}$ and
$\ell_{B}=\Delta_{B}\gamma_{B}$ block-columns of $\mathbf{B}$ to each of the
workers. Thus each worker computes $\ell=\ell_{A}\ell_{B}$ submatrix products
according to the natural order discussed in Section III.

Once the matrices are decomposed into block-columns, we allow
$\beta_{A}$-level and $\beta_{B}$-level coding for matrices $\mathbf{A}$ and
$\mathbf{B}$, respectively. In this case we choose two separate resolvable
designs with block sizes $\beta_{A}$ and $\beta_{B}$ supported on point sets
$\\{0,1,\dots,\Delta_{A}-1\\}$ and $\\{0,1,\dots,\Delta_{B}-1\\}$
respectively. Furthermore, we assume that the number of worker nodes
$n=c\times a_{2}b_{2}$ where $c$ is a positive integer.

Input : Matrices $\mathbf{A}$ and $\mathbf{B}$, storage fractions of the
workers $\gamma_{A}=\frac{a_{1}}{a_{2}}$ $\gamma_{B}=\frac{b_{1}}{b_{2}}$,
$\beta_{A},\beta_{B}$-coding level for $\mathbf{A}$ and $\mathbf{B}$,
respectively, and number of worker nodes, $n=c\times a_{2}b_{2}$, where $c$ is
a positive integer.

1 Partition $\mathbf{A}$ into $\Delta_{A}=\beta_{A}a_{2}$ block-columns and
partition $\mathbf{B}$ into $\Delta_{B}=\beta_{B}b_{2}$ block-columns;

2

3$\Delta=\Delta_{A}\Delta_{B}$, $\ell_{A}=\Delta_{A}\gamma_{A}$,
$\ell_{B}=\Delta_{B}\gamma_{B}$, $\beta=\beta_{A}\beta_{B}$;

4 Assume $\mathcal{X}_{A}=\\{0,1,2,\dots,\Delta_{A}-1\\}$ and find parallel
classes $\mathcal{P}^{A}_{i}$ having block size $\beta_{A}$,
$i=0,1,\dots,c-1$;

5 Assume $\mathcal{X}_{B}=\\{0,1,2,\dots,\Delta_{B}-1\\}$ and find parallel
classes $\mathcal{P}^{B}_{i}$ having block size $\beta_{B}$,
$i=0,1,\dots,c-1$;

6

7for  _$i\leftarrow 0$ to $c-1$_ do

8 Let the blocks of $\mathcal{P}^{A}_{i}$ be denoted as
$p_{A_{0}},p_{A_{1}},\dots,p_{A_{\alpha_{A}-1}}$ ;

9 Let the blocks of $\mathcal{P}^{B}_{i}$ be denoted as
$p_{B_{0}},p_{B_{1}},\dots,p_{B_{\alpha_{B}-1}}$ ;

10

11 for  _$j\leftarrow 0$ to $\frac{\Delta}{\beta}-1$_ do

12 Assign sets $p_{A_{j}},p_{A_{j+1}},\dots,p_{A_{j+\ell_{A}-1}}$ from top to
bottom (indices reduced modulo $a_{2}$) to worker $\frac{\Delta}{\beta}i+j$;

13

14 $k\leftarrow\lfloor\frac{j}{a_{2}}\rfloor$, and assign sets
$p_{B_{k}},p_{B_{k+1}}$, $\dots$, $p_{B_{k+\ell_{B}-1}}$ from top to bottom
(indices reduced modulo $b_{2}$) to worker $\frac{\Delta}{\beta}i+j$;

15

16 Choose random linear combinations of the constituent block-columns of the
meta-symbols of $\mathcal{P}^{A}_{i}$ and $\mathcal{P}^{B}_{i}$ of length
$\beta_{A}$ and $\beta_{B}$ respectively;

17

18 end for

19

20 end for

Output : Distributed matrix-matrix multiplication scheme having $\beta$-level
coding.

Algorithm 2 $\beta$-level coding scheme for matrix-matrix multiplication

Let $\mathcal{P}^{A}$ and $\mathcal{P}^{B}$ denote parallel classes for the
matrices $\mathbf{A}$ and $\mathbf{B}$ respectively. As in the matrix-vector
scheme, the coding scheme is specified by the meta-symbols (blocks) of
$\mathcal{P}^{A}$ and $\mathcal{P}^{B}$. Let $\mathcal{N}_{A}$ and
$\mathcal{N}_{B}$ denote the corresponding incidence matrices of these
parallel classes. Recall that each meta-symbol is in one-to-one correspondence
with the columns of the incidence matrices. Consider the matrix
$\mathcal{N}_{AB}$ formed by considering pair-wise Kronecker products of
columns from $\mathcal{N}_{A}$ and $\mathcal{N}_{B}$. Then the rows of
$\mathcal{N}_{AB}$ correspond to unknowns of the form
$\mathbf{A}_{i}^{T}\mathbf{B}_{j}$ and the columns correspond to the support
of the random linear equations that are formed by considering the pairwise
products. We will refer to the meta-symbols of $\mathcal{N}_{AB}$ as product
meta-symbols and denote it by $\mathcal{P}^{AB}$. For example, suppose that
$\beta_{A}=\beta_{B}=2$ and consider two meta-symbols
$\\{0,1\\}\in\mathcal{P}^{A}$ and $\\{0,1\\}\in\mathcal{P}^{B}$. If these
symbols are placed in a worker, the corresponding product would be
$(x_{0}\mathbf{A}_{0}^{T}+x_{1}\mathbf{A}_{1}^{T})(y_{0}\mathbf{B}_{0}+y_{1}\mathbf{B}_{1})=x_{0}y_{0}\mathbf{A}_{0}^{T}\mathbf{B}_{0}+x_{0}y_{1}\mathbf{A}_{0}^{T}\mathbf{B}_{1}+x_{1}y_{0}\mathbf{A}_{1}^{T}\mathbf{B}_{0}+x_{1}y_{1}\mathbf{A}_{1}^{T}\mathbf{B}_{1}$
where $x_{0},x_{1},y_{0},y_{1}$ are chosen i.i.d. at random from a continuous
distribution. Thus, the coefficients of the corresponding equation can be
expressed as

$\displaystyle[x_{0}\leavevmode\nobreak\
x_{1}]\otimes[y_{0}\leavevmode\nobreak\ y_{1}]$ (6)

where $\otimes$ denotes the Kronecker product.

######  Claim 1.

If $\mathcal{N}_{A}$ (of size $\Delta_{A}\times\Delta_{A}/\beta_{A}$) and
$\mathcal{N}_{B}$ (of size $\Delta_{B}\times\Delta_{B}/\beta_{B}$) correspond
to incidence matrices of parallel classes, then $\mathcal{N}_{AB}$ also forms
a parallel class of size
$\Delta_{A}\Delta_{B}\times\Delta_{A}\Delta_{B}/\beta_{A}\beta_{B}$.

###### Proof.

Let $\mathbf{u}_{i}\otimes\mathbf{v}_{i}$ for $i=0,1$ denote two distinct
columns of $\mathcal{N}_{AB}$ such that $\mathbf{u}_{i}$ and $\mathbf{v}_{i}$
are columns in $\mathcal{N}_{A}$ and $\mathcal{N}_{B}$ respectively. Then,

$\displaystyle(\mathbf{u}_{0}\otimes\mathbf{v}_{0})^{T}(\mathbf{u}_{1}\otimes\mathbf{v}_{1})$
$\displaystyle=\mathbf{u}_{0}^{T}\mathbf{u}_{1}\times\mathbf{v}_{0}^{T}\mathbf{v}_{1}$
$\displaystyle=0$

since either $\mathbf{u}_{0}\neq\mathbf{u}_{1}$ or
$\mathbf{v}_{0}\neq\mathbf{v}_{1}$. Moreover, there are
$\frac{\Delta_{A}\Delta_{B}}{\beta_{A}\beta_{B}}$ distinct columns in
$\mathcal{N}_{AB}$ each with a support of size $\beta_{A}\beta_{B}$. This
implies that together all the product meta-symbols in $\mathcal{N}_{AB}$ cover
all the $\Delta_{A}\Delta_{B}$ points. ∎

As in the matrix-vector case, the scheme operates by placing cyclically
shifted meta-symbols from $\mathcal{P}^{A}$ with $\ell_{A}$ meta-symbols in
each worker for the first $\Delta_{A}/\beta_{A}$ workers. For these workers,
the assignment of meta-symbols from $\mathcal{P}^{B}$ is the same. For the
next set of $\Delta_{A}/\beta_{A}$ workers the assignment of meta-symbols from
$\mathcal{P}^{A}$ repeats; however, we now employ a cyclic shift for the
assignment of meta-symbols from $\mathcal{P}^{B}$. The complete algorithm is
specified in Alg. 2 and an example is depicted in Fig. 7. As before, a group
in this setting contains $\Delta/\beta$ workers and there a total of
$\frac{n}{\Delta/\beta}=c$ groups denoted $\mathcal{G}_{i},i=0,1,\dots,c-1$.
Let
$\mathcal{X}_{AB}=\\{\mathbf{A}_{0}^{T}\mathbf{B}_{0},\mathbf{A}_{0}^{T}\mathbf{B}_{1},\mathbf{A}_{0}^{T}\mathbf{B}_{2},\dots,\mathbf{A}_{\Delta_{A}-1}^{T}\mathbf{B}_{\Delta_{B}-1}\\}$
denote the set of unknowns. The product of two assigned coded block-columns
consists of a random linear combination of $\beta=\beta_{A}\beta_{B}$ unknowns
from $\mathcal{X}_{AB}$.

######  Example 7.

We consider an example with $n=36$ workers in Fig. 7, each of which can store
$\gamma_{A}=\gamma_{B}=\frac{1}{3}$ of each of matrices $\mathbf{A}$ and
$\mathbf{B}$, and $\beta_{A}=\beta_{B}=2$. We set $\Delta_{A}=\Delta_{B}=6$,
thus the cardinality of $\mathcal{X}_{AB}$ is $36$. In terms of indices, we
use the same parallel class, $\\{\\{0,1\\},\\{2,3\\},\\{4,5\\}\\}$ for both
$\mathbf{A}$ and $\mathbf{B}$. Finally we use random vectors of length
$\beta_{A}=\beta_{B}=2$ to obtain the symbols from the submatrices of the
elements of the parallel classes, $\mathcal{P}^{A}_{i}$ and
$\mathcal{P}^{B}_{i}$ in any worker group $\mathcal{G}_{i}$, for $i=0,1,2,3$,
as $c=36/9=4$.

$W_{0}$$W_{1}$$W_{2}$$W_{3}$$W_{4}$$W_{5}$$W_{6}$$W_{7}$$W_{8}$$\\{0,1\\}$$\\{2,3\\}$$\\{0,1\\}$$\\{2,3\\}$$\\{2,3\\}$$\\{4,5\\}$$\\{0,1\\}$$\\{2,3\\}$$\\{4,5\\}$$\\{0,1\\}$$\\{0,1\\}$$\\{2,3\\}$$\\{0,1\\}$$\\{2,3\\}$$\\{2,3\\}$$\\{4,5\\}$$\\{2,3\\}$$\\{4,5\\}$$\\{2,3\\}$$\\{4,5\\}$$\\{4,5\\}$$\\{0,1\\}$$\\{2,3\\}$$\\{4,5\\}$$\\{0,1\\}$$\\{2,3\\}$$\\{4,5\\}$$\\{0,1\\}$$\\{2,3\\}$$\\{4,5\\}$$\\{4,5\\}$$\\{0,1\\}$$\\{4,5\\}$$\\{0,1\\}$$\\{4,5\\}$$\\{0,1\\}$

Figure 7: Job assignment for worker group $\mathcal{G}_{0}$ for $\beta$-level
matrix-matrix multiplication scheme with $n=36$ with
$\gamma_{A}=\gamma_{B}=\frac{1}{3}$ and $\Delta_{A}=\Delta_{B}=6$ using a
single parallel class with $\beta_{A}=\beta_{B}=2$. The indices $\\{i,j\\}$ on
top and bottom parts indicate random linear combinations of the submatrices of
$\mathbf{A}$ and $\mathbf{B}$, respectively. $\mathcal{G}_{1}$,
$\mathcal{G}_{2}$ and $\mathcal{G}_{3}$ are assigned the same symbols as
workers $W_{0}-W_{8}$, but with different random coefficients.

######  Lemma 3.

The matrix-matrix multiplication scheme in Alg. 2 is such that there are
$\ell=\ell_{A}\ell_{B}$ symbols corresponding to any product meta-symbol
$\in\mathcal{P}_{i}^{AB}$ in a group $\mathcal{G}_{i}$. Furthermore, this
product meta-symbol appears in all locations $0,1,2,\dots,\ell-1$ within
$\mathcal{G}_{i}$.

###### Proof.

Any group $\mathcal{G}_{i}$ can be partitioned into
$\alpha_{B}=\frac{\Delta_{B}}{\beta_{B}}$ disjoint subgroups each of which
consists of $\alpha_{A}=\frac{\Delta_{A}}{\beta_{A}}$ workers. These subgroups
are denoted as $\mathcal{H}_{j}$ where in terms of group worker indices,
$\mathcal{H}_{j}=\\{j\alpha_{A},j\alpha_{A}+1,\dots,(j+1)\alpha_{A}-1\\}$, for
$j=0,1,\dots,\alpha_{B}-1$.

If meta-symbols $x\in\mathcal{P}_{i}^{A}$ and $y\in\mathcal{P}_{i}^{B}$ appear
at locations $i_{1}$ and $j_{1}$, respectively, $0\leq i_{1}\leq\ell_{A}-1$
and $0\leq j_{1}\leq\ell_{B}-1$, then the product meta-symbol $x\otimes y$
appears at location $i_{1}\ell_{B}+j_{1}$ in the ordering. In our case, meta-
symbol $x$ appears $\ell_{A}$ times within subgroup $\mathcal{H}_{j}$ at
distinct locations $0,\dots,\ell_{A}-1$. Thus, if meta-symbol
$y\in\mathcal{P}_{i}^{B}$ appears in $\mathcal{H}_{j}$ at location $j_{1}$
then the product meta-symbol $x\otimes y$ appears $\ell_{A}$ times at
locations
$j_{1},\ell_{B}+j_{1},2\ell_{B}+j_{1},\dots,(\ell_{A}-1)\ell_{B}+j_{1}$. The
result follows by realizing that there are $\ell_{B}$ subgroups where meta-
symbol $y$ appears. Moreover, $y\in\mathcal{P}_{i}^{B}$ appears at all
locations $0,\dots,\ell_{B}-1$ across these subgroups. ∎

######  Theorem 5.

If we use a single parallel class $\mathcal{P}_{A}$ for $\mathbf{A}$ and a
single parallel class $\mathcal{P}_{B}$ for $\mathbf{B}$ across all the worker
groups, then the scheme described in Alg. 2 will be resilient to
$s=c\ell-\beta$ stragglers and will have,
$Q=n\ell-\frac{c\ell(\ell+1)}{2}+\ell(\beta-1)+1$, where
$\ell=\ell_{A}\ell_{B}$ and $\beta=\beta_{A}\beta_{B}\leq c$.

###### Proof.

The proof is very similar to the proof of Theorem 2 once we use the fact that
each product meta-symbol appears in all locations $0,\dots,\ell-1$ within the
group in which it appears (cf. Lemma 3). ∎

It can be verified that the distributed scheme shown in Fig. 7 is resilient to
$s=c\ell-\beta=4\times 4-4=12$ stragglers and has $Q=117$. Theorem 5 provides
the value for $s$ and $Q$ for distributed matrix-matrix multiplication when
$\beta\leq c$. In Appendix -A, we explicitly calculate the values for $s$ and
$Q$ for the case when $\beta>c$.

######  Remark 4.

Similar to the matrix-vector case, the uncoded matrix-matrix multiplication
scheme can also be thought as a special case of $\beta$-level coding scheme
with $\beta=1$. The lower bound given in (1) is matched by the proposed scheme
here with $\beta_{A}=\beta_{B}=1$ (i.e., the uncoded scheme). An example
appears in Fig. 8 where we have $n=12$ workers and the master node can recover
the final product as soon as it receives $Q=52$ symbols across all the
workers.

$W_{0}$$W_{1}$$W_{2}$$W_{3}$$W_{4}$$W_{5}$$W_{6}$$W_{7}$$W_{8}$$W_{9}$$W_{10}$$W_{11}$$\mathbf{A}_{0}$$\mathbf{A}_{1}$$\mathbf{A}_{1}$$\mathbf{A}_{2}$$\mathbf{A}_{2}$$\mathbf{A}_{0}$$\mathbf{A}_{0}$$\mathbf{A}_{1}$$\mathbf{A}_{1}$$\mathbf{A}_{2}$$\mathbf{A}_{2}$$\mathbf{A}_{0}$$\mathbf{A}_{0}$$\mathbf{A}_{1}$$\mathbf{A}_{1}$$\mathbf{A}_{2}$$\mathbf{A}_{2}$$\mathbf{A}_{0}$$\mathbf{A}_{0}$$\mathbf{A}_{1}$$\mathbf{A}_{1}$$\mathbf{A}_{2}$$\mathbf{A}_{2}$$\mathbf{A}_{0}$$\mathbf{B}_{0}$$\mathbf{B}_{1}$$\mathbf{B}_{2}$$\mathbf{B}_{0}$$\mathbf{B}_{1}$$\mathbf{B}_{2}$$\mathbf{B}_{0}$$\mathbf{B}_{1}$$\mathbf{B}_{2}$$\mathbf{B}_{1}$$\mathbf{B}_{2}$$\mathbf{B}_{3}$$\mathbf{B}_{1}$$\mathbf{B}_{2}$$\mathbf{B}_{3}$$\mathbf{B}_{1}$$\mathbf{B}_{2}$$\mathbf{B}_{3}$$\mathbf{B}_{2}$$\mathbf{B}_{3}$$\mathbf{B}_{0}$$\mathbf{B}_{2}$$\mathbf{B}_{3}$$\mathbf{B}_{0}$$\mathbf{B}_{2}$$\mathbf{B}_{3}$$\mathbf{B}_{0}$$\mathbf{B}_{3}$$\mathbf{B}_{0}$$\mathbf{B}_{1}$$\mathbf{B}_{3}$$\mathbf{B}_{0}$$\mathbf{B}_{1}$$\mathbf{B}_{3}$$\mathbf{B}_{0}$$\mathbf{B}_{1}$

Figure 8: Uncoded matrix-matrix multiplication with $n=12$ and $s=5$ with
$\gamma_{A}=\frac{2}{3}$ and $\gamma_{B}=\frac{3}{4}$ where $\Delta_{A}=3$ and
$\Delta_{B}=4$.

In the matrix-matrix case for $\beta_{A}=2,\beta_{B}=1$ we can show that using
different parallel classes can improve the straggler resilience of the system.
The corresponding $Q$ analysis is harder to do and is part of future work.

######  Theorem 6.

Let $\ell_{A}\leq\frac{\Delta_{A}}{2}-2$ and $\Delta_{A}\geq 8$. If we use the
parallel classes in (IV-A) for encoding $\mathbf{A}$, then the matrix-matrix
multiplication scheme described in Alg. 2 will be resilient to $s=2\ell-1$
stragglers, when $\beta_{A}=2$ and $\beta_{B}=1$ such that $c=\beta=2$.

###### Proof.

Consider the set
$\mathcal{B}_{m}=\\{\mathbf{A}_{0}^{T}\mathbf{B}_{m},\mathbf{A}_{1}^{T}\mathbf{B}_{m},\dots,\mathbf{A}_{\Delta_{A}-1}^{T}\mathbf{B}_{m}\\}$,
i.e., the set of all unknowns corresponding to $\mathbf{B}_{m}$, for
$m=0,1,\dots,\Delta_{B}-1$, so $|\mathcal{B}_{m}|=\Delta_{A}$. As $\mathbf{B}$
is uncoded, the equations consisting of the unknowns in $\mathcal{B}_{m}$ are
disjoint of the equations consisting of the unknowns of $\mathcal{B}_{p}$,
($m\neq p$). Thus, we can form $\mathcal{G}_{dec}^{m}$ using the unknowns
corresponding to the set $\mathcal{B}_{m}$ and analyze the decoding using it.
The rest of the argument follows analogous to the proof of Theorem 4. ∎

###  IV-C Coded at bottom scheme

Intuitively, the $\beta$-level coding schemes can be improved if we allow for
the inclusion of some densely coded block-columns. We now consider a variant
of the uncoded scheme where such densely coded block-columns are added at the
end of uncoded computations. This improves both the straggler resilience and
the $Q$ value of the scheme.

We now assume that each node receives $\gamma=\gamma_{u}+\gamma_{c}$ fraction
of the columns of $\mathbf{A}$ and the vector $\mathbf{x}$. Here $\gamma_{u}$
corresponds to the storage fraction of the uncoded parts of $\mathbf{A}$,
whereas $\gamma_{c}$ corresponds to the coded portion. The coded blocks appear
at the bottom of each node. Thus, under normal operating circumstances (no
slow or failed nodes), the master node can simply decode the intended result
from the uncoded computations. If some nodes are operating slower than normal,
then the coded computations can be leveraged.

As in the uncoded setup let $\ell_{u}=\Delta\gamma_{u}$ be the number of
uncoded block-columns and $r_{u}$ be the replication factor. Likewise
$\ell_{c}=\Delta\gamma_{c}$ represents the number of coded blocks in each
worker. In this construction we set $\Delta=n$ so that $r_{u}=\ell_{u}$. In
this case, the results from Theorem 2 immediately imply that
$Q\geq\max(\Delta,\Delta r_{u}-\frac{r_{u}}{2}(\ell_{u}+1)+1)$. This follows
by applying $\beta=1$ to the uncoded part of the solution where
$r_{u}=\ell_{u}$. A construction that meets these bounds is outlined in
Algorithm 3. The algorithm uses a random matrix of dimension
$n\ell_{c}\times\Delta$.

Input : Matrix $\mathbf{A}$ and vector $\mathbf{x}$, $n$-number of worker
nodes, total storage capacity fraction $\gamma$, replication factor for
uncoded portion $r_{u}$.

1 Set $\Delta=n$, $\ell_{u}=r_{u}$, $\ell=\gamma\Delta$,
$\ell_{c}=\ell-\ell_{u}$;

2 Partition $\mathbf{A}$ into $\Delta$ block-columns
$\mathbf{A}_{0},\mathbf{A}_{1},\dots,\mathbf{A}_{\Delta-1}$;

3 for  _$i\leftarrow 0$ to $n-1$_ do

4 Define $T=\left\\{i,i+1,\dots,i+\ell_{u}-1\right\\}$ (mod $\Delta$);

5 Assign all $\mathbf{A}_{m}$’s sequentially from top to bottom to worker node
$i$, where $m\in T$;

6 Assign $\ell_{c}$ different random linear combinations of $\mathbf{A}_{m}$’s
for $m\notin T$;

7

8 end for

Output : Cyclic coded at the bottom scheme for matrix-vector multiplication.

Algorithm 3 Cyclic coded at the bottom scheme for distributed matrix-vector
multiplication

######  Theorem 7.

The scheme in Alg.3 satisfies $Q=\max(\Delta,\Delta
r_{u}-\frac{r_{u}}{2}(\ell_{u}+1)+1)$. Furthermore, it is resilient to
$\bigg{\lfloor}\frac{n^{2}\gamma_{c}+n\gamma_{u}-1}{n\gamma_{c}+1}\bigg{\rfloor}$
stragglers.

###### Proof.

The detailed proof is discussed in Appendix -C ∎

######  Example 8.

Consider the setting where we have $n=5$ workers with $\gamma=\frac{3}{5}$
where we set $\Delta=n=5$. Fig. 4 shows the job assignments according to the
uncoded scheme ($\beta=1$). According to Theorem 2 in Section IV, the system
is resilient to $\beta(n\gamma-1)=2$ stragglers and $Q=5\times 3-\frac{3\times
4}{2}+1=10$ which can be verified from Fig. 4.

Now we assume that the whole storage fraction can be distributed into an
uncoded storage fraction $\gamma_{u}=\frac{2}{5}$ and a coded storage fraction
$\gamma_{c}=\frac{1}{5}$. Using the coded scheme, we get the job assignments
shown in Fig. 9. This scheme is resilient to
$\bigg{\lfloor}\frac{n^{2}\gamma_{c}+n\gamma_{u}-1}{n\gamma_{c}+1}\bigg{\rfloor}=3$
stragglers and it can be verified from that $\mathbf{A}^{T}\mathbf{x}$ can be
computed once any $Q=\Delta r_{u}-\frac{r_{u}}{2}(\ell_{u}+1)+1=8$ block-
columns have been processed. Thus, we can conclude that introducing a single
coded block in each worker (at the bottom), helps to improve both $Q$ and the
straggler resilience of the system as compared to an uncoded system.

$W_{0}$$W_{1}$$W_{2}$$W_{3}$$W_{4}$$\mathbf{A}_{0}^{T}\,\mathbf{x}$$\mathbf{A}_{1}^{T}\,\mathbf{x}$$\mathbf{C}_{0}^{T}\,\mathbf{x}$$\mathbf{A}_{1}^{T}\,\mathbf{x}$$\mathbf{A}_{2}^{T}\,\mathbf{x}$$\mathbf{C}_{1}^{T}\,\mathbf{x}$$\mathbf{A}_{2}^{T}\,\mathbf{x}$$\mathbf{A}_{3}^{T}\,\mathbf{x}$$\mathbf{C}_{2}^{T}\,\mathbf{x}$$\mathbf{A}_{3}^{T}\,\mathbf{x}$$\mathbf{A}_{4}^{T}\,\mathbf{x}$$\mathbf{C}_{3}^{T}\,\mathbf{x}$$\mathbf{A}_{4}^{T}\,\mathbf{x}$$\mathbf{A}_{0}^{T}\,\mathbf{x}$$\mathbf{C}_{4}^{T}\,\mathbf{x}$

Figure 9: Partitioning matrix $A$ into five submatrices and assigning two
uncoded and one coded task to each of the five workers. The coded submatrix
assigned to $W_{i}$ is denoted as $\mathbf{C}_{i}$.

Similar schemes can be arrived at for the matrix-matrix case. We assume that
the uncoded storage fraction for $\mathbf{A}$ is
$\gamma_{Au}=\frac{a_{u}}{a_{2}}$ and the coded storage fraction is
$\gamma_{Ac}=\frac{a_{c}}{a_{2}}$, so that the total storage fraction is
$\gamma_{A}=\frac{a_{1}}{a_{2}}$. Each worker also receives
$\gamma_{B}=\frac{b_{1}}{b_{2}}$ fraction of the uncoded columns of matrix
$B$.

Input : Matrices $\mathbf{A}$ and $\mathbf{B}$, $n$-number of workers. Storage
fractions $\gamma_{Au}=\frac{a_{u}}{a_{2}}$ and
$\gamma_{Ac}=\frac{a_{c}}{a_{2}}$, so that $\gamma_{A}=\frac{a_{1}}{a_{2}}$
and $\gamma_{B}=\frac{b_{1}}{b_{2}}$.

1 Set $\Delta_{A}=a_{2}$, $\Delta_{B}=mb_{2}$, $m=\frac{n}{\left(a_{2}\times
b_{2}\right)}$. Partition $\mathbf{A}$ and $\mathbf{B}$ into $\Delta_{A}$ and
$\Delta_{B}$ block-columns, respectively;

2 for  _$i\leftarrow 0$ to $n-1$_ do

3 Define $T=\left\\{i,i+1,\dots,i+a_{u}-1\right\\}$ (mod $\Delta_{A}$);

4 Assign all $\mathbf{A}_{m}$’s sequentially from top to bottom to worker node
$i$, where $m\in T$;

5 Assign $a_{c}$ different random linear combinations of $\mathbf{A}_{m}$’s
for $m\notin T$;

6 $j\leftarrow\lfloor\frac{i}{a_{2}}\rfloor$ and assign
$\mathbf{B}_{j},\mathbf{B}_{j+1},\dots,\mathbf{B}_{j+mb_{1}-1}$ from top to
bottom (subscripts reduced modulo $\Delta_{B}$) to worker node $i$;

7

8 end for

Output : Cyclic coded at the bottom scheme for matrix-matrix multiplication.

Algorithm 4 Cyclic coded at the bottom scheme for distributed matrix-matrix
multiplication

######  Theorem 8.

The recovery threshold for the matrix-matrix multiplication scheme Alg. 4 is
given by, $\tau=n-ma_{2}b_{1}+\kappa_{min}$, where $\kappa_{min}$ is the
minimum positive integer for $\kappa$ satisfying the inequality

$\displaystyle\bigg{\lceil}\frac{\kappa}{mb_{1}}\bigg{\rceil}+\kappa a_{c}\geq
a_{2}-a_{u}+1.$

###### Proof.

The detailed proof is discussed in Appendix -D. ∎

######  Example 9.

$W_{0}$$W_{1}$$W_{2}$$W_{3}$$W_{4}$$W_{5}$$W_{6}$$W_{7}$$W_{8}$$W_{9}$$W_{10}$$W_{11}$$\mathbf{A}_{0}$$\mathbf{C}_{0}$$\mathbf{A}_{1}$$\mathbf{C}_{1}$$\mathbf{A}_{2}$$\mathbf{C}_{2}$$\mathbf{A}_{0}$$\mathbf{C}_{3}$$\mathbf{A}_{1}$$\mathbf{C}_{4}$$\mathbf{A}_{2}$$\mathbf{C}_{5}$$\mathbf{A}_{0}$$\mathbf{C}_{6}$$\mathbf{A}_{1}$$\mathbf{C}_{7}$$\mathbf{A}_{2}$$\mathbf{C}_{8}$$\mathbf{A}_{0}$$\mathbf{C}_{9}$$\mathbf{A}_{1}$$\mathbf{C}_{10}$$\mathbf{A}_{2}$$\mathbf{C}_{11}$$\mathbf{B}_{0}$$\mathbf{B}_{1}$$\mathbf{B}_{2}$$\mathbf{B}_{0}$$\mathbf{B}_{1}$$\mathbf{B}_{2}$$\mathbf{B}_{0}$$\mathbf{B}_{1}$$\mathbf{B}_{2}$$\mathbf{B}_{1}$$\mathbf{B}_{2}$$\mathbf{B}_{3}$$\mathbf{B}_{1}$$\mathbf{B}_{2}$$\mathbf{B}_{3}$$\mathbf{B}_{1}$$\mathbf{B}_{2}$$\mathbf{B}_{3}$$\mathbf{B}_{2}$$\mathbf{B}_{3}$$\mathbf{B}_{0}$$\mathbf{B}_{2}$$\mathbf{B}_{3}$$\mathbf{B}_{0}$$\mathbf{B}_{2}$$\mathbf{B}_{3}$$\mathbf{B}_{0}$$\mathbf{B}_{3}$$\mathbf{B}_{0}$$\mathbf{B}_{1}$$\mathbf{B}_{3}$$\mathbf{B}_{0}$$\mathbf{B}_{1}$$\mathbf{B}_{3}$$\mathbf{B}_{0}$$\mathbf{B}_{1}$

Figure 10: Coded matrix-matrix multiplication with $n=12$ with
$\gamma_{Au}=\frac{1}{3}$, $\gamma_{Ac}=\frac{1}{3}$ and
$\gamma_{B}=\frac{3}{4}$ where $\Delta_{A}=3$ and $\Delta_{B}=4$. The coded
submatrix for $\mathbf{A}$ assigned to $W_{i}$ is denoted as $\mathbf{C}_{i}$.

We consider the scenario as before, where $\gamma_{A}=\frac{2}{3}$ and
$\gamma_{B}=\frac{3}{4}$, and $n=12$, so $m=\frac{12}{3\times 4}=1$. According
to Alg. 4, we set $\ell_{A}=2$, $\Delta_{A}=3$ and $\ell_{B}=3$,
$\Delta_{B}=4$. So, we need to recover $\Delta=\Delta_{A}\Delta_{B}=12$ block
products. Figs. 8 and 10 show the job assignments to the workers for the
uncoded case and the proposed coded scheme, respectively. For the coded
scheme, we assume $\gamma_{Au}=\frac{1}{3}$ and $\gamma_{Ac}=\frac{1}{3}$, and
on the other hand, for the uncoded scheme, we have $\gamma_{Ac}=0$, so
$a_{c}=0$.

Now for the uncoded case, according to Theorem 5, the recovery threshold is
$\tau=n-(c\ell-\beta)=12-(1\times\ell_{A}\ell_{B}-1)=7$. On the other hand,
according to Theorem 8, the recovery threshold for the coded case is,
$\tau=n-ma_{2}b_{1}+\kappa=12-3\times 3+2=5$ since the minimum positive
integer $\kappa$ that satisfies
$\big{\lceil}\frac{\kappa}{3}\big{\rceil}+\kappa\geq 3$ is $2$.

We expect that the benefits of having densely coded block-columns at the
bottom should extend for the case of general $\beta>1$ and the $Q/\Delta$
analysis should be possible to perform for the matrix-matrix case. However,
this appears to be more challenging and will be investigated as part of future
work.

##  V Sparsely Coded Straggler (SCS) Optimal Matrix Computations

In this section, we develop schemes for distributed matrix computations which
perform optimally in terms of straggler resilience. For example, in matrix-
matrix multiplication case, if the storage fractions of each worker node are
$\gamma_{A}=1/k_{A}$ and $\gamma_{B}=1/k_{B}$ then it can be shown the lowest
possible threshold is $k_{A}k_{B}$ [3]. Similarly, for the matrix-vector
multiplication case the optimal threshold is $k_{A}$. Prior work has also
demonstrated schemes that achieve these thresholds. In what follows, we
present schemes that are similar in spirit to our constructions in Section IV
which are suitable for sparse matrices while continuing to enjoy the optimal
threshold $k_{A}k_{B}$. Moreover, unlike the previously available dense coded
approaches, our proposed sparsely coded straggler (SCS) optimal scheme can
utilize the partial computations of the slow workers and can provide
significantly small $Q/\Delta$.

###  V-A Matrix-vector Multiplication

In our proposed scheme in Alg. 5, we set $\Delta=\textrm{LCM}(n,k_{A})$ and
assign the uncoded jobs in such a way that all the workers are assigned the
uncoded jobs in an equal manner and the replication factor of the uncoded
symbols over all $n$ workers is, $r_{u}=1$. Thus each of the workers is
assigned $\Delta/n$ uncoded jobs and the rest
$\ell_{c}=\frac{\Delta}{k_{A}}-\frac{\Delta}{n}$ jobs are assigned using a
random linear encoding matrix, $\mathcal{R}$ of size $n\ell_{c}\times\Delta$.
Since any $(\Delta-\lambda)\times(\Delta-\lambda)$ submatrix of $\mathcal{R}$
is full rank with probability $1$, the master node can decode all the unknowns
if it receives any $\lambda$ uncoded symbols and any $\Delta-\lambda$ coded
symbols from all the workers. Thus we can say that $Q=\Delta$, and since each
worker stores $\Delta/k_{A}$ block-columns, we have the recovery threshold,
$\tau=\frac{\Delta}{\Delta/k_{A}}=k_{A}$.

Input : Matrix $\mathbf{A}$ and vector $\mathbf{x}$, $n$-number of worker
nodes, storage fraction $\gamma_{A}=\frac{1}{k_{A}}$.

1 Set $\Delta=\textrm{LCM}(n,k_{A})$. Partition $\mathbf{A}$ into $\Delta$
block-columns $\mathbf{A}_{0},\mathbf{A}_{1},\dots,\mathbf{A}_{\Delta-1}$;

2 Number of coded submatrices of $\mathbf{A}$ in each worker node,
$\ell_{c}=\frac{\Delta}{k_{A}}-\frac{\Delta}{n}$;

3 for  _$i\leftarrow 0$ to $n-1$_ do

4 $u\leftarrow i\times\frac{\Delta}{n}$;

5 Define $T=\left\\{u,u+1,\dots,u+\frac{\Delta}{n}-1\right\\}$ (mod $\Delta$);

6 Assign all $\mathbf{A}_{m}$’s sequentially from top to bottom to worker node
$i$, where $m\in T$;

7 Assign $\ell_{c}$ different random linear combinations of $\mathbf{A}_{m}$’s
for $m\notin T$;

8

9 end for

Output : $\langle n,\gamma_{A}\rangle$ SCS optimal-scheme for matrix-vector
multiplication with optimal $Q/\Delta$.

Algorithm 5 SCS Optimal scheme for matrix-vector multiplication

######  Example 10.

$W_{0}$$W_{1}$$W_{2}$$W_{3}$$W_{4}$$W_{5}$$\mathbf{A}_{0}^{T}\,\mathbf{x}$$\mathbf{A}_{1}^{T}\,\mathbf{x}$$\mathbf{C}_{0}^{T}\,\mathbf{x}$$\mathbf{A}_{2}^{T}\,\mathbf{x}$$\mathbf{A}_{3}^{T}\,\mathbf{x}$$\mathbf{C}_{1}^{T}\,\mathbf{x}$$\mathbf{A}_{4}^{T}\,\mathbf{x}$$\mathbf{A}_{5}^{T}\,\mathbf{x}$$\mathbf{C}_{2}^{T}\,\mathbf{x}$$\mathbf{A}_{6}^{T}\,\mathbf{x}$$\mathbf{A}_{7}^{T}\,\mathbf{x}$$\mathbf{C}_{3}^{T}\,\mathbf{x}$$\mathbf{A}_{8}^{T}\,\mathbf{x}$$\mathbf{A}_{9}^{T}\,\mathbf{x}$$\mathbf{C}_{4}^{T}\,\mathbf{x}$$\mathbf{A}_{10}^{T}\,\mathbf{x}$$\mathbf{A}_{11}^{T}\,\mathbf{x}$$\mathbf{C}_{5}^{T}\,\mathbf{x}$

Figure 11: Partitioning matrix $A$ into $\Delta=12$ submatrices and assigning
to $n=6$ workers each of which has been assigned two uncoded and one coded
task to be resilient to $s=2$ stragglers. The coded submatrix assigned to
$W_{i}$ is denoted as $\mathbf{C}_{i}$.

We consider an example in Fig. 11 with $n=6$ and $\gamma=\frac{1}{4}$, so
$k_{A}=4$. We set $\Delta=\textrm{LCM}(6,4)=12$, and
$\ell_{c}=\frac{12}{4}-\frac{12}{6}=1$. Thus, we assign two uncoded jobs and
one coded job to each worker where the coded job assignment would be
incorporated using a random matrix $\mathcal{R}$ of size $6\times 12$. In this
case, $Q=12$, thus $Q/\Delta=1$, and $\tau=4$.

######  Remark 5.

On the surface Fig. 11 may appear equivalent to a systematic version of the
RKRP coded scheme [17] with the same number of matrix partitions. However,
there is a significant difference that the idea in the RKRP coded scheme is to
assign the systematic versions to some workers and the coded versions to other
workers, whereas we assign the jobs in a symmetric fashion so that every
worker receives same number of uncoded and same number of coded jobs. If the
input matrices are sparse, then the parity workers in the RKRP coded scheme
will be significantly slower than the systematic workers.

###  V-B Matrix-matrix Multiplication

Input : Matrices $\mathbf{A}$ and $\mathbf{B}$, $n$-number of worker nodes,
storage fraction $\gamma_{A}=\frac{1}{k_{A}}$ and
$\gamma_{B}=\frac{1}{k_{B}}$. So, $s=n-k_{A}k_{B}$.

1 Set $\Delta_{A}=\textrm{LCM}(n,k_{A})$ and $\Delta_{B}=k_{B}$;

2 Partition $\mathbf{A}$ and $\mathbf{B}$ into $\Delta_{A}$ and $\Delta_{B}$
block-columns, and $\Delta=\Delta_{A}\Delta_{B}$;

3 Number of coded submatrices of $\mathbf{A}$ in each worker node,
$\ell_{c}=\frac{\Delta_{A}}{k_{A}}-\frac{\Delta}{n}$;

4 for  _$i\leftarrow 0$ to $n-1$_ do

5 $u\leftarrow i\times\frac{\Delta_{A}}{n}$;

6 Define $T=\left\\{u,u+1,\dots,u+\frac{\Delta}{n}-1\right\\}$ (modulo
$\Delta_{A}$);

7 Assign all $\mathbf{A}_{m}$’s sequentially from top to bottom to worker node
$i$, where $m\in T$;

8 Assign $\ell_{c}$ different random linear combinations of $\mathbf{A}_{m}$’s
for $m\notin T$;

9 Assign a single random linear combination of all block-columns of
$\mathbf{B}$;

10

11 end for

Output : $\langle n,\gamma_{A},\gamma_{B}\rangle$ SCS optimal-scheme for
distributed matrix-matrix multiplication.

Algorithm 6 SCS Optimal scheme for distributed matrix-matrix multiplication

We propose a matrix-matrix multiplication scheme in Alg. 6 with storage
fractions $\gamma_{A}=1/k_{A}$ and $\gamma_{B}=1/k_{B}$ and recovery threshold
$k_{A}k_{B}$. Furthermore, $Q/\Delta=1+(k_{B}-1)\ell_{c}/\Delta$, where
$\ell_{c}$ is the number of coded-coded matrix-matrix products assigned to
each worker node.

######  Theorem 9.

Alg. 6 proposes a distributed matrix-matrix multiplication scheme being
resilient to $s=n-k_{A}k_{B}$ stragglers.

###### Proof.

According to this scheme, we know that every worker is assigned
$\frac{\Delta_{A}}{k_{A}}$ block-columns (uncoded and coded) from $\mathbf{A}$
and one coded block-column from $\mathbf{B}$, which indicates that we can
obtain, in total, $\frac{\Delta_{A}}{k_{A}}$ products from each of the
workers. Thus from any $k_{A}k_{B}$ workers, the master node can obtain
$\frac{\Delta_{A}}{k_{A}}\times
k_{A}k_{B}=\Delta_{A}k_{B}=\Delta_{A}\Delta_{B}=\Delta$ products. A simple
counting argument applied to Alg. 6 shows that any uncoded block-column of
$\mathbf{A}$ appears exactly $k_{B}$ times over all $n$ workers.

In what follows we show that each of these block products corresponds to a
linearly independent equation where the variables are
$\mathbf{A}_{i}^{T}\mathbf{B}_{j}$ for
$i=0,1,\dots,\Delta_{A}-1,j=0,1,\dots,\Delta_{B}-1$. Let $e_{i}$ denote the
$i$-th unit vector of length $\Delta_{A}$, $i=0,\dots,\Delta_{A}-1$. It
follows that the product
$(\sum_{i=0}^{\Delta_{A}-1}u_{i}\mathbf{A}_{i})^{T}(\sum_{j=0}^{\Delta_{B}-1}v_{j}\mathbf{B}_{j})$
corresponds to the vector $\sum_{i=0}^{\Delta_{A}-1}u_{i}(e_{i}\otimes v$),
where $v$ is the vector $[v_{0}\leavevmode\nobreak\ v_{1}\leavevmode\nobreak\
\dots\leavevmode\nobreak\ v_{\Delta_{B}-1}]^{T}$ (cf. discussion around (6)).

Now, suppose that we consider a subset of $k=k_{A}k_{B}$ workers indexed by
the set $\mathcal{I}=\\{i_{0},i_{1},\dots,i_{k-1}\\}$. Within this worker node
set, let $\mathcal{J}_{i}$ denote the index set of the worker nodes where
$\mathbf{A}_{i}$ appears uncoded. The random encoding vectors for $\mathbf{A}$
and $\mathbf{B}$ in worker $W_{\ell}$ are denoted by $u^{(\ell,j)}$ (of length
$\Delta_{A}$) for $j=0,1,\dots,\ell_{c}-1$ and $v^{(\ell)}$ (of length
$\Delta_{B}$) respectively.

It follows that the products involving the uncoded block-column
$\mathbf{A}_{i}$ can be expressed as

$\displaystyle e_{i}\otimes v^{(\ell)}\text{\leavevmode\nobreak\
for\leavevmode\nobreak\ }\ell\in\mathcal{J}_{i}.$

Our first observation is that the collection of vectors $\\{e_{i}\otimes
v^{(\ell)}\\}$ for $\ell\in\mathcal{J}_{i},i=0,\dots,\Delta_{A}-1$ is linearly
independent. This follows because any linear combination of these vectors can
equivalently be expressed as

$\displaystyle\sum_{i=0}^{\Delta_{A}-1}\left(e_{i}\otimes\sum_{\ell\in\mathcal{J}_{i}}\alpha^{(i)}_{\ell}v^{(\ell)}\right)$

where $\alpha^{(i)}_{\ell}$’s are the linear combination coefficients and each
term in the above sum needs to be forced to zero. Note that
$|\mathcal{J}_{i}|\leq k_{B}$. Therefore, the vectors $v^{(\ell)}$ for
$\ell\in\mathcal{J}_{i}$ are linearly independent with probability 1, since
$v^{(\ell)}$ has length $\Delta_{B}=k_{B}$. Thus, there is no setting of
$\alpha^{(i)}_{\ell}$’s for which the above sum can be forced to the zero
vector.

The product of the coded $\mathbf{A}$ and $\mathbf{B}$ matrices can be
represented by $u^{(\ell,j)}\otimes v^{(\ell)}$ for $j=0,1,\dots,\ell_{c}-1$
and $\ell\in\mathcal{I}$. We will now show that the overall collection of
vectors that we obtain is linearly independent with probability 1. To see this
suppose that there exist coefficients $\alpha^{(i)}_{\ell}$’s and
$\kappa^{(j)}_{\ell}$’s not all zero such that

$\displaystyle\sum_{i=0}^{\Delta_{A}-1}e_{i}\otimes\sum_{\ell\in\mathcal{J}_{i}}\alpha^{(i)}_{\ell}v^{(\ell)}=\sum_{\ell\in\mathcal{I}}\sum_{j=0}^{\ell_{c}-1}\kappa^{(j)}_{\ell}u^{(\ell,j)}\otimes
v^{(\ell)}=\sum_{\ell\in\mathcal{I}}\sum_{j=0}^{\ell_{c}-1}\kappa^{(j)}_{\ell}\sum_{j_{1}=0}^{\Delta_{A}-1}u^{(\ell,j)}_{j_{1}}e_{j_{1}}\otimes
v^{(\ell)}.$

It can be observed that this decouples into finding solutions for

$\displaystyle
e_{i}\otimes\sum_{\ell\in\mathcal{J}_{i}}\alpha^{(i)}_{\ell}v^{(\ell)}=e_{i}\otimes\sum_{\ell\in\mathcal{I}}\sum_{j=0}^{\ell_{c}-1}\kappa^{(j)}_{\ell}u^{(\ell,j)}_{i}v^{(\ell)}$
(7)

where the $\alpha^{(i)}_{\ell}$ values on the LHS can be chosen freely given
the RHS. For a given choice of the $\kappa^{(j)}_{\ell}$’s the above equation
can definitely be satisfied if $|\mathcal{J}_{i}|=k_{B}$. If we
$|\mathcal{J}_{i}|<k_{B}$ then this may not be true depending on the values of
the $\kappa^{(j)}_{\ell}$’s.

The $n-k_{A}k_{B}$ stragglers together contain
$(n-k_{A}k_{B})\Delta_{A}k_{B}/n$ uncoded block-columns of $\mathbf{A}$. It is
not too hard to see that not all $\mathbf{A}_{i}$’s that appear within the
stragglers appear $k_{B}$ times within the stragglers (see Appendix -F). Thus,
the number of $\mathbf{A}_{i}$’s with $|\mathcal{J}_{i}|<k_{B}$ is
$\geq(n-k_{A}k_{B})\Delta_{A}/n+1$.

In the argument below we only consider the $\alpha^{(i)}_{\ell}$’s
corresponding to these uncoded block-columns and suppose that there is an
assignment of $\alpha^{(i)}_{\ell}$’s that satisfy (7). In this case the
problem of finding the corresponding $\kappa^{(j)}_{\ell}$’s is equivalent to
solving a block system of equations described below.

Let $\mathbf{A}_{\delta}$ be an uncoded block-column that appears less than
$k_{B}$ times in $\mathcal{I}$. The block row corresponding to it (cf. (7)) is
given by $\tilde{\mathbf{V}}\odot\tilde{\mathbf{U}}$ where

$\displaystyle\tilde{\mathbf{V}}=$
$\displaystyle\begin{bmatrix}\makebox[0.0pt][l]{$\smash{\overbrace{\phantom{\begin{matrix}v^{(i_{0})}\leavevmode\nobreak\
\dots\leavevmode\nobreak\
v^{(i_{0})}\end{matrix}}}^{\text{$\ell_{c}$}}}$}v^{(i_{0})}\leavevmode\nobreak\
\dots\leavevmode\nobreak\ v^{(i_{0})}|\leavevmode\nobreak\
\dots\leavevmode\nobreak\
|\makebox[0.0pt][l]{$\smash{\overbrace{\phantom{\begin{matrix}v^{(i_{k-1})}\leavevmode\nobreak\
\dots\leavevmode\nobreak\
v^{(i_{k-1})}\end{matrix}}}^{\text{$\ell_{c}$}}}$}v^{(i_{k-1})}\leavevmode\nobreak\
\dots\leavevmode\nobreak\ v^{(i_{k-1})}\end{bmatrix},\;\;\textrm{and}$
$\displaystyle\tilde{\mathbf{U}}=$
$\displaystyle[u^{(i_{0},0)}_{\delta}\leavevmode\nobreak\
\dots\leavevmode\nobreak\ u^{(i_{0},\ell_{c}-1)}_{\delta}|\leavevmode\nobreak\
\dots\leavevmode\nobreak\ |u^{(i_{k-1},0)}_{\delta}\leavevmode\nobreak\
\dots\leavevmode\nobreak\ u^{(i_{k-1},\ell_{c}-1)}_{\delta}]$

where $\odot$ represents the Khatri-Rao product that corresponds to column-
wise Kronecker products.

Appendix -E shows that the concatenation of block rows in
$\tilde{\mathbf{V}}\odot\tilde{\mathbf{U}}$ corresponding to the different
$\mathbf{A}_{\delta}$’s is such that any
$\ell_{c}k_{A}k_{B}\times\ell_{c}k_{A}k_{B}$ matrix is full rank with
probability-1. This implies that from the first $\ell_{c}k_{A}$ block rows we
can decode all the $\kappa^{(i)}_{\ell}$’s.

On the other hand the equations in (7) need to be satisfied for at least
$(n-k_{A}k_{B})\Delta_{A}/n+1$ different $\mathbf{A}_{i}$’s based on the
argument above. However

$\displaystyle(n-k_{A}k_{B})\frac{\Delta_{A}}{n}=\Delta_{A}-\frac{k_{A}k_{B}\Delta_{A}}{n}=k_{A}\left(\frac{\Delta_{A}}{k_{A}}-\frac{\Delta}{n}\right)=\ell_{c}k_{A}\;\;\;\;\textrm{and
thus,}\;\;(n-k_{A}k_{B})\Delta_{A}/n+1>\ell_{c}k_{A};$

This implies that there is at least one equation that need to be satisfied
with a fixed choice of the $\kappa^{(i)}_{\ell}$’s. But this probability is
zero since each of the remaining equations involve random
$u^{(\ell,i)}_{\delta}$ values that have not appeared in the first
$\ell_{c}k_{A}$ block rows. ∎

######  Theorem 10.

Alg. 6 proposes a distributed matrix-matrix multiplication scheme with
$Q=\Delta+(k_{B}-1)\ell_{c}$.

###### Proof.

As in the proof of the previous result, we let $u^{(\ell,j)}$ for
$j=0,\dots,\ell_{c}-1$ denote the $j$-th random encoding vector for
$\mathbf{A}$ in worker $W_{\ell}$ and $v^{(\ell)}$ the corresponding random
encoding vector for $\mathbf{B}$. We will demonstrate that the system of
equations that corresponding to decoding the
$\mathbf{A}_{i}^{T}\mathbf{B}_{j}$’s is nonsingular with probability 1. Let
$e_{i}$ denote the $i$-th unit vector of length $\Delta_{A}$. For a given
$\mathbf{A}_{i}$, suppose that it appears uncoded in $\mathcal{J}_{i}$ worker
nodes where $|\mathcal{J}_{i}|\leq k_{B}$ we obtain certain equations from the
uncoded part which correspond to $e_{i}\otimes v^{(\ell)}$ for
$\ell\in\mathcal{J}_{i}$. If $|\mathcal{J}_{i}|<k_{B}$ then it needs to use
the coded-coded products for decoding the unknowns corresponding to
$\mathbf{A}_{i}$.

The block system of equations under consideration corresponds to a
$\Delta_{A}k_{B}\times\Delta_{A}k_{B}$ square matrix with random entries. For
$\mathbf{A}_{i}$ such that $|\mathcal{J}_{i}|=k_{B}$ the matrix consists of a
$k_{B}\times k_{B}$ block on the diagonal with $k_{B}$ distinct vectors
$v^{(\ell)}$. This block is nonsingular with probability-1 owing to the random
choice of the $v^{(\ell)}$’s.

For the other $\mathbf{A}_{i}$’s where $|\mathcal{J}_{i}|<k_{B}$ we will
demonstrate a setting of the $u^{(\ell,j)}$’s such that the entire matrix is a
block diagonal matrix with $k_{B}\times k_{B}$ blocks of distinct $v^{(\ell)}$
vectors. This demonstrates that there exists a choice of random coefficients
for which the system of equations is nonsingular. Following this the result
holds with probability-1 when the choice is made at random.

Towards this end, suppose that the pattern of obtained products is such that
we get $\Delta-\lambda$ uncoded-coded products and $\lambda+(k_{B}-1)\ell_{c}$
coded-coded products. Without loss of generality we assume that we need to
decode the products that involve
$\mathbf{A}_{0},\mathbf{A}_{1},\dots,\mathbf{A}_{\delta-1}$ using the coded-
coded products. Furthermore we suppose that $\mathbf{A}_{i}$ appears
$k_{B}-\eta_{i}$ times within the uncoded-coded products, so that
$\eta_{0}+\eta_{1}+\dots+\eta_{\delta-1}=\lambda$.

Under this setting, there are at least
$(k_{B}-1)\ell_{c}+\lambda-(k_{B}-\eta_{0})\ell_{c}=(\eta_{0}-1)\ell_{c}+\lambda$
coded-coded products that can be obtained from worker nodes that do not
contain an uncoded copy of $\mathbf{A}_{0}$. Furthermore, these are spread out
in at least $\eta_{0}$ distinct worker nodes. Next, we pick $\eta_{0}$
encoding vectors for $\mathbf{A}$ from the $\eta_{0}$ distinct workers and set
them all to $e_{0}$. With this setting we obtain a $k_{B}\times k_{B}$ block
(corresponding to decoding
$\mathbf{A}_{0}^{T}\mathbf{B}_{j},j=0,\dots,\Delta_{B}-1$) that consists of
distinct $v^{(\ell)}$ vectors that are nonsingular with probability $1$.

At this point we are left with $(k_{B}-1)\ell_{c}+\lambda-\eta_{0}$ coded-
coded products. The argument can be repeated for $\mathbf{A}_{1}$ since there
are at least $(\eta_{1}-1)\ell_{c}+\lambda-\eta_{0}$ coded-coded products that
can be obtained from workers where $\mathbf{A}_{1}$ does not appear, which in
turn correspond to at least $\eta_{1}$ distinct workers. In this case we will
set the $\eta_{1}$ encoding vectors to $e_{1}$. The process can be continued
in this way until the coded-coded products are assigned to each of
$\mathbf{A}_{0},\mathbf{A}_{1},\dots,\mathbf{A}_{\delta-1}$.

At the end of the process we can claim that we have a block diagonal matrix
where each block is a $k_{B}\times k_{B}$ square matrix with distinct
$v^{(\ell)}$ vectors. Thus each block and consequently the entire system of
equations is nonsingular.

Finally, as there exists a choice of random values that makes the system of
equations nonsingular, it continues to be nonsingular with probability $1$
under a random choice.

∎

To summarize, Theorems 9 and 10 demonstrate that our proposed scheme has the
optimal threshold $k_{A}k_{B}$ and

$\displaystyle\frac{Q}{\Delta}$
$\displaystyle=1+\frac{(k_{B}-1)\ell_{c}}{\Delta}=1+\frac{(k_{B}-1)\left(\frac{\Delta_{A}}{k_{A}}-\frac{\Delta}{n}\right)}{\Delta}$
$\displaystyle=1+\frac{\Delta(k_{B}-1)\left(\frac{1}{k_{A}k_{B}}-\frac{1}{n}\right)}{\Delta}=1+\frac{(k_{B}-1)s}{nk_{A}k_{B}}\approx
1+\frac{s}{nk_{A}};$

if $k_{B}$ is significantly larger than $1$. Moreover in the practical cases,
we usually have $s<<nk_{A}$, thus in this SCS optimal scheme, we have
$Q/\Delta\approx 1$.

######  Example 11.

$W_{0}$$W_{1}$$W_{2}$$W_{3}$$W_{4}$$\mathbf{A}_{0}$$\mathbf{A}_{1}$$\mathbf{A}_{2}$$\mathbf{A}_{3}$$\sum\limits_{i=0}^{9}\mathbf{R}_{A}^{(0,i)}\mathbf{A}_{i}$$\sum\limits_{i=0}^{1}\mathbf{R}_{B}^{(0,i)}\mathbf{B}_{i}$$\mathbf{A}_{2}$$\mathbf{A}_{3}$$\mathbf{A}_{4}$$\mathbf{A}_{5}$$\sum\limits_{i=0}^{9}\mathbf{R}_{A}^{(1,i)}\mathbf{A}_{i}$$\sum\limits_{i=0}^{1}\mathbf{R}_{B}^{(1,i)}\mathbf{B}_{i}$$\mathbf{A}_{4}$$\mathbf{A}_{5}$$\mathbf{A}_{6}$$\mathbf{A}_{7}$$\sum\limits_{i=0}^{9}\mathbf{R}_{A}^{(2,i)}\mathbf{A}_{i}$$\sum\limits_{i=0}^{1}\mathbf{R}_{B}^{(2,i)}\mathbf{B}_{i}$$\mathbf{A}_{6}$$\mathbf{A}_{7}$$\mathbf{A}_{8}$$\mathbf{A}_{9}$$\sum\limits_{i=0}^{9}\mathbf{R}_{A}^{(3,i)}\mathbf{A}_{i}$$\sum\limits_{i=0}^{1}\mathbf{R}_{B}^{(3,i)}\mathbf{B}_{i}$$\mathbf{A}_{8}$$\mathbf{A}_{9}$$\mathbf{A}_{0}$$\mathbf{A}_{1}$$\sum\limits_{i=0}^{9}\mathbf{R}_{A}^{(4,i)}\mathbf{A}_{i}$$\sum\limits_{i=0}^{1}\mathbf{R}_{B}^{(4,i)}\mathbf{B}_{i}$

Figure 12: Matrix-matrix multiplication with $n=5$ and $s=1$ with
$\gamma_{A}=\gamma_{B}=\frac{1}{2}$. Here $\mathbf{R}_{A}$ and
$\mathbf{R}_{B}$ are random matrices whose superscripts indicate their
corresponding rows and columns.

We consider an example in Fig. 12 with $n=5$ and $k_{A}=k_{B}=2$, so the
system is resilient $s=5-4=1$ straggler. We set
$\Delta_{A}=\textrm{LCM}(n,k_{A})=10$ and $\Delta_{B}=k_{B}=2$, and in this
example, $Q=21$, thus $Q/\Delta=1.05$.

##  VI Numerical Experiments and Comparisons

In this section, we discuss the results of the numerical experiments for our
proposed approaches and compare them with other available methods. First we
compare all the approaches in terms of number of stragglers that a scheme can
be resilient to, and in terms of $Q$ values. Next we compare the approaches in
terms of the worker computation time and numerical stability during the
decoding process. Software code for recreating these experiments can be found
at [35].

###  VI-A Number of stragglers and Q value

Table V shows the comparison for matrix-vector multiplication for $n=30$
workers, each of which can store $\gamma_{A}=\frac{1}{10}$ fraction of matrix
$\mathbf{A}$. For the convolutional code approach, we assume $s=15$ so that
$n-s=15>\frac{1}{\gamma_{A}}=10$ which satisfies the required condition in
[10]. And for the coded at bottom approach, we assume
$\gamma_{u}=\frac{1}{15}$ and $\gamma_{c}=\frac{1}{30}$, so that
$\gamma=\gamma_{u}+\gamma_{c}$. Similarly, Table VI shows the comparison for
different approaches for matrix-matrix multiplication for $n=18$ workers, each
of which can store $\gamma_{A}=\frac{1}{3}$ and $\gamma_{B}=\frac{1}{3}$
fraction of matrices $\mathbf{A}$ and $\mathbf{B}$ respectively. Here we
assume $k_{A}=k_{B}=4>\frac{1}{\gamma_{A}}=\frac{1}{\gamma_{B}}=3$ for the
approach in [10].

Table V: Comparison of number of stragglers, $Q$ values, worker computation time (in $ms$) and worst case condition number$(\kappa_{worst})$ for matrix-vector multiplication for $n=30$ and $\gamma_{A}=\frac{1}{10}$ (*for convolutional code, we assumed $s=15$). Methods | Stragglers |  $\frac{Q}{\Delta}$ value |  Worker Computation Time |  $\kappa_{worst}$
---|---|---|---|---
Sparsity $98\%$ |  Sparsity $95\%$
Polynomial Code [3] | $20$ | $N/A$ | $62.8$ | $87.1$ | $5.99\times 10^{9}$
Ortho-Poly Code [21] | $20$ | $N/A$ | $62.3$ | $86.4$ | $4.34\times 10^{11}$
RKRP Code[17] | $20$ | $N/A$ | $62.9$ | $86.8$ | $5.44\times 10^{8}$
Convolutional Code* [10] | $15$ | $N/A$ | $63.1$ | $87.7$ | $6.24\times 10^{4}$
Uncoded [11] | $2$ | $85/30$ | $19.1$ | $32.9$ | $1.7321$
Uncoded (proposed) | $2$ | $84/30$ | $19.2$ | $33.1$ | $1.7321$
$\beta$-level coding ($\beta=2$) | $4$ | $81/30$ | $25.3$ | $40.2$ | $242.89$
$\beta$-level coding ($\beta=3$) | $6$ | $79/30$ | $29.2$ | $47.9$ | $1.53\times 10^{3}$
Coded at Bottom | $15$ | $58/30$ | $24.1$ | $37.8$ | $1.41\times 10^{3}$
Table VI: Comparison of number of stragglers, $Q$ values, worker computation time (in seconds) and worst case condition number $(\kappa_{worst})$ for matrix-matrix multiplication for $n=18$ and $\gamma_{A}=\gamma_{B}=\frac{1}{3}$ (*for convolutional code, $k_{A}=k_{B}=4$). Methods | Stragglers | $\frac{Q}{\Delta}$ value | Worker Computation Time | $\;\;\;\kappa_{worst}\;\;\;$
---|---|---|---|---
Sparsity $98\%$ |  Sparsity $95\%$
Polynomial Code [3] | $9$ | $N/A$ | $2.58$ | $10.16$ | $7.33\times 10^{6}$
Ortho-Poly Code [21] | $9$ | $N/A$ | $2.51$ | $10.08$ | $1.33\times 10^{7}$
RKRP Code[17] | $9$ | $N/A$ | $2.63$ | $10.23$ | $2.15\times 10^{5}$
Convolutional Code* [10] | $2$ | $N/A$ | $2.44$ | $10.19$ | $1.82\times 10^{3}$
Uncoded (proposed) | $1$ | $17/9$ | $0.69$ | $1.96$ | $1.41$
$\beta$-level coding ($\beta_{A}=\beta_{B}=2$) | $4$ | $16/9$ | $1.02$ | $3.68$ | $8.89\times 10^{3}$

In case of both matrix-vector and matrix-matrix multiplications, we know that
the dense coded approaches [3], [17], [10] and [21] are MDS but they do not
consider the partial computations of the slower workers. On the other hand,
our proposed approaches are able to utilize the partial computations of the
stragglers for both matrix-vector and matrix-matrix multiplications. We can
see that the $\beta$-level coding approaches, with $\beta=2$ or $3$, have
smaller $Q/\Delta$ values than the uncoded approaches, one of which is
introduced in [11] and the other is a special case of our proposed
$\beta$-level coding where $\beta=1$. We emphasize that a larger value of
$\beta$ or a larger value of $\gamma_{c}$ will provide smaller values of
$Q/\Delta$ for our proposed $\beta$-level coding approach and the coded-at the
bottom scheme, respectively. It should be noted that the approach in [10]
requires the condition $n-s>\frac{1}{\gamma}$ to be full-filled to be
resilient to $s$ stragglers, so as mentioned in Tables V and VI, this
convolutional code-based approach is resilient to less number of stragglers
than the other dense coded approaches.

###  VI-B Worker Computation Time

We compare the computation time required by the workers in case of different
approaches by experiments performed on an Amazon Web Services (AWS) cluster
where we choose a t2.2xlarge machine as the master node and t2.small machines
as the worker nodes, which are, in fact, responsible for computing the
submatrix products.

For matrix-vector multiplication, We choose a matrix $\mathbf{A}$ of size
$40,000\times 17,640$ and a vector $\mathbf{x}$ of length $40,000$, and the
job is to compute $\mathbf{A}^{T}\mathbf{x}$ in a distributed fashion. We
assume that the matrix $\mathbf{A}$ is sparse, which indicates that the most
of the entries of $\mathbf{A}$ are $zero$. For example, the sparsity of
$\mathbf{A}$ can be $98\%$ (or $95\%$), which indicates that randomly chosen
$2\%$ (or $5\%$) entries of matrix $\mathbf{A}$ are non-zero. We consider the
same scenario where we have $n=30$ workers, each of which can store
$\gamma_{A}=\frac{1}{10}$ fraction of matrix $\mathbf{A}$. The comparison
among different approaches for different sparsity values is shown in Table V.
Next a similar experiment is carried out for matrix-matrix multiplication
where both $\mathbf{A}$ and $\mathbf{B}$ are sparse and of sizes $12000\times
13680$ and $12000\times 10260$, respectively, and the corresponding results
are shown in Table VI.

From the experimental results shown in Tables V and VI, we can see that the
workers require much more time to complete their assigned jobs in case of the
dense coded approaches ([3], [17], [10] and [21]) than our proposed
approaches. The reason is that the dense coded approaches cannot preserve the
sparsity of the matrices $\mathbf{A}$ or $\mathbf{B}$, so the corresponding
coded submatrices are quite dense even if $A$ and $B$ are sparse. On the other
hand, our proposed approaches can preserve the sparsity in the submatrices,
and can complete the jobs $3\sim 4$ times faster than the available
approaches. It should be noted that a smaller value of $\beta$ or a smaller
value of $\gamma_{c}$ will lead to less worker computation time for our
proposed $\beta$-level coding approach and the coded at the bottom scheme,
respectively.

We note here that while there is a significant difference between the required
time of the dense coded approaches and our proposed approaches, this
difference can be much higher. For example, in Table V, we can see that the
polynomial code approach is around $3\sim 4$ times slower than the uncoded
approach, but the gap according to the theoretical analysis should be as large
as $10$ times, since $\gamma_{A}=1/10$. The reason underlying the smaller gap
is the use of two different commands in Python to compute products between the
matrix and the vector. Since the proposed uncoded or the $\beta$-level coding
approaches can preserve the sparsity up to certain level, we have leveraged
the sparse matrix-multiplication commands in these cases, whereas for the
dense coded approaches which cannot preserve the sparsity, regular matrix-
multiplication command provided better results. A more optimized sparse
matrix-multiplication scheme could result in bigger multiplicative gaps
between these approaches. Furthermore, the difference of the required time
would be certainly higher and more significant if the matrix sizes were higher
(for example, in millions). However, owing to the memory limitations of the
machines that we are using (in this case, t2.small), we cannot conduct
experiments with such large matrices.

###  VI-C Numerical Stability

Now we do another experiment to compare the numerical stability of different
schemes. We know that for decoding a system of equations, errors in the input
can get amplified by the condition number (ratio of maximum and minimum
singular values) of the associated decoding matrix; hence, a low condition
number is critical [10, 20]. For example, let us consider the polynomial codes
[3] for matrix vector multiplication, where each of $n$ workers can store
$\gamma=\frac{1}{k}$ fraction of matrix $\mathbf{A}$. Now partitioning
$\mathbf{A}$ into $\Delta=k$ submatrices lead to $\Delta$ unknowns,
$\mathbf{A}^{T}_{0}\mathbf{x},\mathbf{A}^{T}_{1}\mathbf{x},\dots,\mathbf{A}^{T}_{\Delta-1}\mathbf{x}$.
Now in order to assign the coded jobs to $n$ workers, we need to choose a
polynomial of degree $k-1$ and $n$ evaluation points, thus the coding matrix
is of size $n\times k$. Since the recovery threshold here is $\tau=k$, we are
interested in all choices of $k\times k$ submatrices of that $n\times k$
coding matrix. It can be shown that the system will be numerically more stable
in the worst case if the evaluation points are chosen uniformly spaced in
$[-1,1]$, rather than choosing the integers $1,2,\dots,n$ [15]. In other
words, choosing interpolation points uniformly spaced in $[-1,1]$ will lead to
a smaller worst case condition number $(\kappa_{worst})$.

In this experiment we compare the condition numbers for different approaches
in case of the worst choice of full stragglers. Tables V and VI show the
comparison of worst case condition numbers $(\kappa_{worst})$ for matrix-
vector and matrix-matrix multiplication, respectively, for the previously
chosen scenario. We can see that the dense coded approaches ([3], [17] and
[21]) have a very high worst case condition number, thus suffer from numerical
instability which leads to erroneous results. On the other hand, our proposed
$\beta$-level coding approach has a much smaller worst case condition number.
The reason is that even in the worst case, the decoding of some $\beta$
unknowns depends on a $\beta\times\beta$ system matrix whose entries are
randomly chosen. Thus a smaller $\beta$ leads to a smaller $\kappa_{worst}$,
for example, we can see that the uncoded case (same as the case with
$\beta=1$) is the scheme having the smallest $\kappa_{worst}$.

###  VI-D Comparison with the Proposed SCS Optimal Scheme

In this experiment, we compare the dense coded approaches with our proposed
SCS optimal coding scheme in terms of $Q$ values and worker computation time.
First we do the comparison for matrix-vector multiplication where we choose a
square sparse matrix $\mathbf{A}$ of size $27,720\times 27,720$, and a vector
$\mathbf{x}$ of length $27,720$. The job is to compute
$\mathbf{A}^{T}\mathbf{x}$ in a distributed system of $n=18$ workers, each of
which can store $\gamma_{A}=\frac{1}{15}$ fraction of matrix $\mathbf{A}$. We
consider two different choices of matrix $\mathbf{A}$. In the first case,
$\mathbf{A}$ is a band matrix [36] where the entries are non-zero along the
principal diagonal and in $1000$ other $k$-diagonals just above and below the
principal diagonal. In the second case, the entries are non-zero along the
principal diagonal and in $2000$ other randomly chosen $k$-diagonals. The
comparison is shown in Table VII where we can see that the proposed SCS
optimal scheme requires less time from the worker nodes in comparison to the
other dense coded approaches, which in fact, cannot leverage the sparsity of
matrix $\mathbf{A}$.

Next to show an example for distributed matrix-matrix multiplication, we
choose two random sparse matrices $\mathbf{A}$ and $\mathbf{B}$ of sizes
$12000\times 15000$ and $12000\times 13500$, where randomly chosen any $2\%$
and $5\%$ entries are non-zero. We consider a distributed system having $n=24$
workers, each of which can store $\gamma_{A}=\frac{1}{4}$ fraction of matrix
$\mathbf{A}$ and $\gamma_{B}=\frac{1}{5}$ fraction of matrix $\mathbf{B}$. The
comparison is shown in Table VIII which further confirms the superiority of
the proposed SCS optimal scheme in terms of workers’ computation speeds. The
major reason behind the enhancement of the speed in the SCS optimal scheme
lies in its ability to leverage the sparsity of the matrices up to certain
level, whereas the approaches in [3] or [21] use the dense linear combinations
of the submatrices which destroy the sparsity. The approaches in [10] and [17]
consider some parity worker nodes where all the assigned submatrices are
dense, which leads to high worker computation time for those workers. On the
other hand, in the proposed SCS optimal scheme the submatrices, obtained from
dense linear combinations, are assigned uniformly within the workers. This
removes the asymmetry between the worker node computation times.

Table VII: Comparison of $Q$ values, worker computation time (in $ms$) and worst case condition number $(\kappa_{worst})$ for matrix-vector multiplication for $n=18,\gamma_{A}=\frac{1}{15}$ (*for convolutional code, we assume $\gamma_{A}=\frac{1}{10}$). Methods | No of Stragglers | $\frac{Q}{\Delta}$ value | Worker Computation Time | $\;\;\;\kappa_{worst}\;\;\;$
---|---|---|---|---
Band |  Random
Polynomial Code [3] | $3$ | $N/A$ | $29.7$ | $30.2$ | $4.03\times 10^{7}$
Ortho-Poly Code [21] | $3$ | $N/A$ | $30.1$ | $29.8$ | $2.13\times 10^{4}$
RKRP Code[17] | $3$ | $N/A$ | $29.3$ | $30.0$ | $6.35\times 10^{3}$
Convolutional Code* [10] | $3$ | $N/A$ | $35.2$ | $34.7$ | $1.21\times 10^{3}$
SCS Optimal Scheme | $3$ | $1$ | $14.8$ | $20.3$ | $6.81\times 10^{4}$
Table VIII: Comparison of $Q$ values, worker computation time (in seconds) and worst case condition number $(\kappa_{worst})$ for matrix-matrix multiplication for $n=24,\gamma_{A}=\frac{1}{4}$ and $\gamma_{B}=\frac{1}{5}$ (*for convolutional code, we assume $\gamma_{A}=\frac{2}{5}$ and $\gamma_{B}=\frac{1}{3}$). The values in the parentheses for the SCS optimal scheme shows the time required for uncoded and coded portions, respectively. Methods | No of Stragglers | $\frac{Q}{\Delta}$ value | Worker Computation Time | $\;\;\;\kappa_{worst}\;\;\;$
---|---|---|---|---
Sparsity $98\%$ |  Sparsity $95\%$
Polynomial Code [3] | $4$ | $N/A$ | $3.11$ | $8.29$ | $2.40\times 10^{10}$
Ortho-Poly Code [21] | $4$ | $N/A$ | $3.08$ | $8.16$ | $1.96\times 10^{6}$
RKRP Code[17] | $4$ | $N/A$ | $3.15$ | $8.22$ | $2.83\times 10^{5}$
Convolutional Code* [10] | $4$ | $N/A$ | $5.16$ | $10.92$ | $2.65\times 10^{4}$
SCS Optimal Scheme | $4$ | $7/6$ | $1.93$ | $4.76$ | $4.93\times 10^{6}$
$(0.91+1.02)$ | $(3.71+1.05)$

Now, similar to the most of the dense coded approaches [3], [21], [17], our
proposed SCS optimal scheme is also resilient to $s=n-k_{A}k_{B}$ stragglers,
where $\gamma_{A}=\frac{1}{k_{A}}$ and $\gamma_{B}=\frac{1}{k_{B}}$. We point
out that we did not compare with the approach in [7] since their approach does
not respect the storage constraints for the matrices at each worker node and
only has a high-probability guarantee on the recovery threshold. Similarly we
did not compare with [32] which assumes heterogeneous workers, but we note
that this approach provides with a value of $Q/\Delta$ to be $11/10$ for the
example shown in Table VIII. Now, in the dense coded approaches, we can decode
all $\Delta=k_{A}k_{B}$ unknowns from any $k_{A}k_{B}$ submatrix block
products, and in that sense we have $\frac{Q}{\Delta}=1$. But it does not
necessarily mean that those scheme can utilize the partial computations done
by the slower workers, since in those cases the master requires $k_{A}k_{B}$
workers to finish their jobs, and discard the computations done by others.

However, one can still use those approaches to utilize the partial
computations, by partitioning the matrices into more submatrices. We can
consider the an example of $n=10$ workers with $\gamma_{A}=\gamma_{B}=1/3$ and
$98\%$ sparse matrices $\mathbf{A}$ and $\mathbf{B}$, both having size
$12,000\times 12,000$. Now we can partition matrix $\mathbf{A}$ into
$\Delta_{A}=3$ or $\Delta_{A}=9$ submatrices for the dense coded approaches.
We can see the comparison of $\kappa_{worst}$ and worker computation time in
Table IX for these two values of $\Delta_{A}$. In case of $\Delta_{A}=9$, we
will require polynomials of higher degrees (for [3] or [21]) or more random
coefficients (for [17]) than in the case of $\Delta_{A}=3$. It leads to a very
high condition number ($\approx 10^{13}$) which will make the whole system
numerically unstable. Besides, a larger $\Delta_{A}$ would make the
submatrices even denser, which will lead to higher worker computation time for
the workers. The case is similar for the work in [32] which uses larger
$\Delta_{A}$ and $\Delta_{B}$ to utilize the partial computations. On the
other hand, in the proposed SCS optimal scheme, uncoded submatrices are placed
at the top, and coded submatrices are placed at the bottom. Moreover the coded
jobs are allocated uniformly among all the workers which does not let the
worker computation time go high for any particular worker.

Table IX: Comparison of the $Q/\Delta$ values, worker computation time (in seconds) and worst case condition numbers for matrix-matrix multiplication for $n=10,\gamma_{A}=\gamma_{B}=\frac{1}{3}$, so $s=1$. Methods |  | W/o Partial Computations |  | W/ Partial Computations
---|---|---|---|---
|  $\frac{Q}{\Delta}$ value | $\kappa_{worst}$ | Worker time |  |  $\frac{Q}{\Delta}$ value | $\kappa_{worst}$ | Worker time
Poly Code [3] |  | N/A | $8.8\times 10^{3}$ | $2.46$ |  | $1$ | $1.86\times 10^{13}$ | $7.09$
Ortho-Poly [21] |  | N/A | $16.66$ | $2.49$ |  | $1$ | $4.33\times 10^{5}$ | $7.06$
RKRP Code[17] |  | N/A | $11.96$ | $2.41$ |  | $1$ | $1.16\times 10^{4}$ | $7.14$
SCS Optimal Scheme |  | - | - | - |  | $1.02$ | $2.15\times 10^{3}$ | $2.04$

##  VII Conclusions and Future Work

In this work we have presented several coded matrix computation schemes that
(i) leverage partial computations by stragglers and (ii) impose constraints on
the extent to which coding is allowed in the solution.

The second feature is especially valuable in the practical case of
computations with sparse matrices and provides significant reductions in
worker node computation time and better numerical stability as compared to the
previous schemes. Prior work has demonstrated schemes with optimal recovery
threshold in certain cases. We present schemes that match the optimal
threshold while enjoying lower worker node computation times and improved
numerical stability. Exhaustive numerical experiments corroborate our
findings.

There are several opportunities for future work. We have demonstrated that
carefully chosen different parallel classes provide improved recovery
thresholds and $Q/\Delta$ metrics for the matrix-vector problem. We expect
that this should help even in the case of matrix multiplication. Schemes that
apply for a larger range of storage fractions are also of interest. In this
work we defined the value of $Q$ as the worst case number of symbols that
allows for recovering the intended result. Analysis and constructions for the
random case may be of interest.

##  VIII Acknowledgments

The authors acknowledge interesting conversations with Dr. Li Tang and his
participation in [11].

###  -A Properties of $\beta$-level Coding when $\beta>c$

In Section IV, we have discussed $\beta$-level coding for distributed matrix
computations when $c\geq\beta$ and here we prove the properties of
$\beta$-level coding when $\beta>c$. The difference is that the constraint
$c\geq\beta$ ensures that we will have at least $\beta$ worker groups, whereas
it is not the case when $\beta>c$.

####  -A1 Matrix-vector Multiplication

Suppose that we have $n=ca_{2}$ workers, each of which can store
$\gamma=\frac{a_{1}}{a_{2}}$ fraction of matrix $\mathbf{A}$. To incorporate
$\beta$-level coding, matrix $\mathbf{A}$ is partitioned into $\Delta=\beta
a_{2}$ block-columns, and thus each worker will be assigned
$\ell=\Delta\gamma=\beta a_{1}$ jobs. It should be noted that we have
$\frac{n}{\Delta/\beta}=c$ worker groups among the workers because of the
cyclic fashion of job assignments.

######  Lemma 4.

If we use a single parallel class in Alg. 1, then the number of stragglers
will be $s=c\ell-\beta$ and we will have

$\displaystyle
Q=c\left[\frac{\Delta}{\beta}\ell-\frac{\ell(\ell+1)}{2}\right]+c\sum\limits_{i=0}^{c_{1}-1}(\ell-i)+c_{2}(\ell-
c_{1})+1$

where $c_{1}=\lfloor\frac{\beta-1}{c}\rfloor$ and $c_{2}=\beta-1-cc_{1}$.

###### Proof.

The straggler resilience follows similar to the proof of Theorem 2 by counting
the number of occurrences of the meta-symbols.

For the $Q$ analysis, assume that there exists a meta-symbol $\star$ that
appears at most $\beta-1$ times among the acquired $Q$ symbols where $Q$ is
defined in the theorem statement. We have $c$ worker groups and in each group,
$\star$ appears in positions $0,1,2,\dots,\ell-1$.

Now we know that we can process
$\alpha_{0}=\left[\frac{\Delta}{\beta}\ell-\frac{\ell(\ell+1)}{2}\right]$
meta-symbols from each of the worker groups without processing $\star$. Any
additional processing will necessarily process $\star$. Suppose we choose any
particular worker, where the position index of $\star$ is $i$. In that case,
we can acquire at most $\ell-1-i$ more symbols from that particular worker
without any more appearances of $\star$. Thus, the maximum number of meta-
symbols that can be processed for each additional appearance of $\star$ can be
expressed by the following vector.

$\displaystyle\mathbf{z}=\left(\makebox[0.0pt][l]{$\smash{\underbrace{\phantom{\begin{matrix}\ell,\ell,\dots,\ell\end{matrix}}}_{\text{$c$}}}$}\ell,\ell,\dots,\ell,\makebox[0.0pt][l]{$\smash{\underbrace{\phantom{\begin{matrix}\ell-1,\dots,\ell-1\end{matrix}}}_{\text{$c$}}}$}\ell-1,\dots,\ell-1,\dots,\makebox[0.0pt][l]{$\smash{\underbrace{\phantom{\begin{matrix}1,1,\dots,1\end{matrix}}}_{\text{$c$}}}$}1,1,\dots,1\right).$

Here $\mathbf{z}$ is a non-increasing sequence, so in order to obtain the
maximum number of symbols where the meta-symbol $\star$ appears at most
$\beta-1$ times, we need to acquire symbols sequentially as mentioned in
$\mathbf{z}$. Let $c_{1}=\lfloor\frac{\beta-1}{c}\rfloor$ and
$c_{2}=\beta-1-cc_{1}$. Thus we can choose the first $cc_{1}+c_{2}=\beta-1$
workers (as mentioned in $\mathbf{z}$) so that we can have $Q^{{}^{\prime}}$
symbols where $\star$ appears exactly $\beta-1$ times, so

$\displaystyle
Q^{{}^{\prime}}=c\alpha_{0}+c\sum\limits_{i=0}^{c_{1}-1}(\ell-i)+c_{2}(\ell-
c_{1});$

which indicates that $Q=Q^{{}^{\prime}}+1$ symbols ensures that $\star$ will
appear at least $\beta$ times. This leads to a contradiction and concludes the
proof. ∎

####  -A2 Matrix-matrix Multiplication

The argument is almost the same for the matrix-matrix case with appropriate
definitions for $\ell$ and $\beta$. Specifically, recall that $n=c\times
a_{2}b_{2}$, and $\Delta_{A}=\beta_{A}a_{2}$ and $\Delta_{B}=\beta_{B}b_{2}$.
Thus, we have $\frac{n}{\Delta/\beta}=c$ worker groups, where
$\Delta=\Delta_{A}\Delta_{B}$ and $\beta=\beta_{A}\beta_{B}$. In each worker,
we assign $\ell_{A}=\Delta_{A}\gamma_{A}$ and $\ell_{B}=\Delta_{B}\gamma_{B}$
coded submatrices of $\mathbf{A}$ and $\mathbf{B}$, respectively and set
$\ell=\ell_{A}\ell_{B}$. Following this, we can obtain the number of
stragglers as $s=c\ell-\beta$ and

$\displaystyle
Q=c\left[\frac{\Delta}{\beta}\ell-\frac{\ell(\ell+1)}{2}\right]+c\sum\limits_{i=0}^{c_{1}-1}(\ell-i)+c_{2}(\ell-
c_{1})+1.$

###  -B Proof of Theorem 4

###### Proof.

Straggler Resilience: To prove the straggler resilience, we note that if there
are at $2\ell-1$ stragglers it is evident that $\mathbf{G}_{dec}$ formed by
the remaining meta-symbols is such that each unknown has degree at least one.
Let $X_{i}$ and $X_{j}$ denote the subset of worker nodes where unknowns
$\mathbf{A}_{i}^{T}\mathbf{x}$ and $\mathbf{A}_{j}^{T}\mathbf{x}$ appear
within a meta-symbol, so that $|X_{i}|=|X_{j}|=2\ell$. Furthermore,
$|X_{i}\cap X_{j}|\leq 2\ell-2$. To see this we note that if $\\{i,j\\}$
appear together w.l.o.g. in $\mathcal{G}_{0}$ then $|X_{i}\cap
X_{j}|=\ell+\ell-2$ as this implies that they appear together in exactly
$\ell-2$ workers in $\mathcal{G}_{1}$ (since $\ell\leq\Delta/2-2$). On the
other hand if $i$ and $j$ do not appear together in either $\mathcal{G}_{0}$
or $\mathcal{G}_{1}$ then they appear together in the workers of each group at
most $\ell-1$ times, so the claim holds. Thus,

$\displaystyle|X_{i}\cup X_{j}|$ $\displaystyle=|X_{i}|+|X_{j}|-|X_{i}\cap
X_{j}|$ $\displaystyle\geq 2\ell+2.$

Now suppose by way of contradiction that we have two unknowns
$\mathbf{A}_{i}^{T}\mathbf{x}$ and $\mathbf{A}_{j}^{T}\mathbf{x}$ (where
$i<j$) both of which appear exactly once across the remaining $n-2\ell+1$
workers. The preceding argument shows that if $2\ell-1$ workers are stragglers
then unknowns $\mathbf{A}_{i}^{T}\mathbf{x}$ or $\mathbf{A}_{j}^{T}\mathbf{x}$
or both appear in at least three nodes, i.e., at least one of them appears at
least twice. This contradicts our original assumption. By Lemma 2 the decoding
is successful.

Value of $Q$: Note that
$\alpha_{0}=\frac{\Delta}{2}\ell-\frac{\ell(\ell+1)}{2}$ denotes the maximum
number of meta-symbols that can be processed within a group such that a
specific meta-symbol is not processed (cf. Lemma 1). This implies that at most
$2\alpha_{0}$ meta-symbols can be processed without processing any specific
unknown. Let $\rho_{0}$ and $\rho_{1}$ denote the number of meta-symbols
processed in the two groups $\mathcal{G}_{0}$ and $\mathcal{G}_{1}$ where we
assume w.l.o.g. that $\rho_{0}\geq\rho_{1}$.

  * •

Case 1: Suppose that $\rho_{0}\geq\alpha_{0}+\ell+1$. Lemma 1 implies that
each meta-symbol $\in\mathcal{P}_{0}$ is processed at least twice in
$\mathcal{G}_{0}$ . Then by Lemma 2, the decoding is successful.

  * •

Case 2: If $\alpha_{0}+2\leq\rho_{0}\leq\alpha_{0}+\ell$, we claim that at
most one meta-symbol in $\mathcal{G}_{0}$ is processed once. The other meta-
symbols are processed at least twice. To see this, consider two meta-symbols
$(2i,2i+1)$ and $(2j,2j+1)$ in $\mathcal{G}_{0}$ such that $j>i$ such that
$(2i,2i+1)$ is processed only once. If $j-i\geq 2$ then there are at least two
workers in $\mathcal{G}_{0}$ where the meta-symbol $(2j,2j+1)$ appears but
$(2i,2i+1)$ does not. Therefore, if at least $\alpha_{0}+1$ meta-symbols are
processed in $\mathcal{G}_{0}$, then $(2j,2j+1)$ appears at least twice. On
the other hand if $j=i+1$ then there is only one worker where $(2j,2j+1)$
appears but $(2i,2i+1)$ does not. Thus, if $\alpha_{0}+1$ meta-symbols are
processed then we have processed $(2j,2j+1)$ at least once. The
$\alpha_{0}+2$-th meta-symbol cannot be $(2i,2i+1)$ since by assumption it is
processed only once, thus it has to be $(2j,2j+1)$ (since $j=i+1$).

Now, we argue either unknown $\mathbf{A}_{2i}^{T}\mathbf{x}$ or
$\mathbf{A}_{2i+1}^{T}\mathbf{x}$ appear within the meta-symbols in
$\mathcal{G}_{1}$. Towards this end, we note that there are exactly two
workers in $\mathcal{G}_{1}$ where $\mathbf{A}_{2i+1}^{T}\mathbf{x}$ appears
but $\mathbf{A}_{2i}^{T}\mathbf{x}$ does not. Therefore, at most
$\alpha_{0}-(2\ell-1)$ meta-symbols can be processed in $\mathcal{G}_{1}$
while avoiding both the unknowns $\mathbf{A}_{2i}^{T}\mathbf{x}$ and
$\mathbf{A}_{2i+1}^{T}\mathbf{x}$.

This implies that the total number of meta-symbols that can be processed such
that at least two unknowns appear only once in $G_{dec}$ is at most
$2\alpha_{0}-\ell+1<Q$.

  * •

Case 3: If $\rho_{0}=\alpha_{0}+1$, then we can have two meta-symbols
$(2i,2i+1)$ and $(2i+2,2i+3)$ that appear exactly once in $\mathcal{G}_{0}$.
It can be verified that none of the unknowns
$\mathbf{A}_{2i}^{T}\mathbf{x},\dots,\mathbf{A}_{2i+3}^{T}\mathbf{x}$ appear
together in a meta-symbol in $\mathcal{G}_{1}$ since $\Delta\geq 8$. Thus, if
we process $\rho_{1}=\alpha_{0}$ symbols in $\mathcal{G}_{1}$, then we can
avoid at most one unknown from the set
$\\{\mathbf{A}_{2i}^{T}\mathbf{x},\dots,\mathbf{A}_{2i+3}^{T}\mathbf{x}\\}$.
It follows that at most one unknown appears once in $G_{dec}$ and by Lemma 2,
the decoding is successful.

∎

###  -C Proof of Theorem 7

###### Proof.

We need to show that for any pattern of $Q$ symbols the master node can decode
$\mathbf{A}^{T}\mathbf{x}$. Towards this end, from Theorem 2 (setting
$\beta=1$ and $\ell=\ell_{u}=r_{u}$), we know that any pattern of $Q$ uncoded
symbols allows the recovery of all $\Delta$ unknowns. In other words for any
computation state vector $\mathbf{w}(t)=[w_{0}(t)\leavevmode\nobreak\
w_{2}(t)\leavevmode\nobreak\ \dots\leavevmode\nobreak\ w_{n-1}(t)]$ such that
$w_{i}(t)\leq\ell_{u}$ and $\sum_{i=0}^{n-1}w_{i}(t)\geq Q$, the master node
can decode. Now, consider a vector $\mathbf{w}^{\prime}(t)$ such that
(w.l.o.g.) $w^{\prime}_{0}(t),\dots,w^{\prime}_{\alpha-1}(t)\geq\ell_{u}+1$
and $w^{\prime}_{\alpha}(t),\dots,w^{\prime}_{n-1}(t)\leq\ell_{u}$ and
$\sum_{i=0}^{n-1}w^{\prime}_{i}(t)\geq Q$, i.e., the first $\alpha$ worker
nodes process coded blocks whereas the others do not. It is not too hard to
determine a different vector $\tilde{\mathbf{w}}(t)$ with the following
properties.

$\displaystyle\tilde{w}_{i}(t)$
$\displaystyle=\begin{cases}\ell_{u}&\leavevmode\nobreak\ 1\leq