Fundamental Limits of Coded Linear Transform

I Introduction

Classical approaches of distributed linear transforms rely on dividing the input matrix $\mathbf{A}$ equally among all available worker nodes, and the master node has to collect the results from all workers to output $\mathbf{y}$. As a result, a major performance bottleneck is the latency incurred in waiting for a few slow or faulty processors – called “stragglers” to finish their tasks . Recently, forward error correction and other coding techniques have shown to provide an effective way to deal with the “straggler” in the distributed computation tasks . By exploiting coding redundancy, the vector $\mathbf{y}$ is recoverable even if all workers have not finished their computation, thus reducing the delay due to straggle nodes. One main result in this paper is the development of optimal codes to deal with stragglers in computing distributed linear transforms, which provides an optimum recovery threshold and optimum computation redundancy.

What is the minimum recovery threshold and computation load for coded distributed linear transforms? Can we find an optimum computation strategy that achieves both optimality?

To that end, there have been works that have investigated the problems of reducing the recovery threshold and computational load for coded distributed linear transforms by leveraging ideas from coding theory. The first work proposes a maximum distance separable (MDS) code-based linear transform. We illustrate this approach using the following example. Consider a distributed system with $3$ workers, the coding scheme first splits the matrix $\mathbf{A}$ into two submatrices, i.e., $\mathbf{A}=[\mathbf{A}_{1};\mathbf{A}_{2}]$. Then each worker computes $\mathbf{A}_{1}\mathbf{x}$, $\mathbf{A}_{2}\mathbf{x}$ and $(\mathbf{A}_{1}+\mathbf{A}_{2})\mathbf{x}$. The master node can compute $\mathbf{A}\mathbf{x}$ as soon as any $2$ out of the $3$ workers finish, and therefore achieves a recovery threshold of $2$ and a computation load of $4$. More specifically, it is shown that MDS code achieves a recovery threshold of $\Theta(m)$ and computation load $O(mn)$. An improved scheme proposed in , referred to as the short MDS code, can offer a larger recovery threshold but with a constant reduction of computation load by imposing some sparsity of the encoded submatrices. More recently, the work in designs a type of polynomial code. It achieves the recovery threshold of $n$ that is independent of number of workers. However, it incurs a computation load of $mn$. In other words, each worker of polynomial code has to access the information of entire data matrix $\mathbf{A}$.

In this paper, we show that, given number of partitions $n$ and number of stragglers $s$, the minimum recovery threshold is $n$ and the minimum computation load is $n(s+1)$. We design a novel coded computation strategy, referred to as the $s$-diagonal code. It achieves both optimum recovery threshold and optimum computation load, which significantly improves the state-of-the-art. We also design a hybrid decoding algorithm between the peeling decoding and Gaussian elimination. We show that the decoding time is nearly linear time of the output dimension $O(r)$.

Moreover, we define a new probabilistic recovery threshold performance metric that allows the coded computation scheme to provide the decodability in a large percentage (with high probability) of straggling scenarios. Based on this new metric, we propose two kinds of random codes, $p$-Bernoulli code and $(d_{1},d_{2})$-cross code, which can probabilistically guarantee the same recovery threshold but with much less computation load.

In the $p$-Bernoulli code, each worker stores a weighted linear combination of several submatrices such that each $\mathbf{A}_{i}$ is chosen with probability $p$ independently. We show that, if $p=2\log(n)/n$, the $p$-Bernoulli code achieves the probabilistic recovery threshold of $n$ and a constant communication and computation load $O(n\log(n))$ in terms of the number of stragglers. In the $(d_{1},d_{2})$-cross code, each worker first randomly and uniformly chooses $d_{1}$ submatrices, and each submatrix is randomly and uniformly assigned to $d_{2}$ workers; then each worker stores a linear combination of the assigned submatrices and computes the corresponding linear transform. We show that, when the number of stragglers $s=\text{poly}(\log(n))$, the $(2,3)$-cross code, or when $s=O(n^{\alpha}),\alpha<1$, the $(2,2/(1-\alpha))$-cross code achieves the probabilistic recovery threshold of $n$ and a much lower communication and computation load $O(n)$. We compare our proposed codes and the existing codes in Fig. 1.

We finally implement and benchmark the constructed code in this paper on the Ohio Super Computing Center , and empirically demonstrate its performance gain compared with existing strategies.

II Problem Formulation

Given the above system model, we can formulate the coded distributed linear transform problem based on the following definitions.

This is a general definition of a large class of coded computation schemes. For example, in the polynomial code , the coding matrix $\mathbf{M}$ is the Vandermonde matrix. In the MDS type of codes , it is a specific form of corresponding generator matrix.

(Computation load) The computation load of strategy $\mathbf{M}$ is defined as $l(\mathbf{M})=\|\mathbf{M}\|_{0}$, the number of the nonzero elements of coding matrix.

III Diagonal Code and its Optimality

In this section, we first describe the optimum recovery threshold and optimum computation load. Then we introduce the $s$-diagonal code that exactly matches such lower bounds.

We first establish the information theoretical lower bound of the recovery threshold.

The proof is similar with the one in that uses the cut-set type argument around the master node. This bound implies that the optimum recovery threshold is independent of the number of workers. We next establish the lower bound of the computation load, i.e., the density of coding matrix $\mathbf{M}$.

The polynomial code achieves the optimum recover threshold of $n$. However, the coding matrix (Vandermonde matrix) is fully dense, i.e., $l(\mathbf{M})=nm$, and far beyond the above bound. The short MDS code can reduce the computation load but sacrifices the recovery threshold. Therefore, a natural question that arises is, can we design a code achieves both optimum recovery threshold and optimum computation load? We will answer this question in the sequel of this paper.

III-B Diagonal Code

Now we present the $s$-diagonal code that achieves both the optimum recovery threshold and optimum computation load for any given parameter values of $n$, $m$ and $s$.

($s$-diagonal code) Given parameters $m$,$n$ and $s$, the $s$-diagonal code is defined as

where each coefficient $m_{ij}$ is chosen from a finite set $S$ independently and uniformly at random.

The reason we name this code as the $s$-diagonal code is that the nonzero positions of the coding matrix $\mathbf{M}$ show the following diagonal structure.

where $*$ indicates nonzero entries of $\mathbf{M}$. Before we analyze the recovery threshold of the diagonal code, the following example provides an instantiation of the above construction for $n=4$, $s=1$ and $m=5$.

Example 1: ($1$-Diagonal code) Consider a distributed linear transform task $\mathbf{Ax}$ using $m=5$ workers. We evenly divide the matrix $\mathbf{A}$ along the row side into $4$ submatrices: $\mathbf{A}^{T}=[\mathbf{A}_{1}^{T},\mathbf{A}_{2}^{T},\mathbf{A}_{3}^{T},\mathbf{A}_{4}^{T}]$. Given this notation, we need to compute the following $4$ uncoded components.

Based on the definition of $1$-diagonal code, each worker stores the following submatrices,

Suppose that the first worker is straggler and master node receives results from worker $\{2,3,4,5\}$. According to the above coded computation strategy, we have

The coefficient matrix is an upper diagonal matrix, which is invertible since the elements in the main diagonal are nonzero. Then we can recover the uncoded components $\{\mathbf{A}_{i}\mathbf{x}\}$ by direct inversion of the above coefficient matrix. The decodability for the other $4$ possible scenarios can be proved similarly. Therefore, this code achieves the optimum recovery threshold of $4$. Besides, the total number of partial linear transforms is $8$, which also matches the lower bound of computation load.

III-C Optimality of Diagonal Code

The optimality of computation load of the $s$-diagonal code can be easily obtained by counting the number of nonzero elements of coding matrix $\mathbf{M}$. In terms of recovery threshold, we have the following result of the diagonal code

Let finite set $S$ satisfy $|S|\geq 2n^{2}C^{n}_{m}$, then the $s-$diagonal code achieves the recovery threshold of $n$.

For each subset $U\subseteq[m]$ with $|U|=n$, let $\mathbf{M}^{U}$ be a $n\times n$ submatrices consisting rows of $\mathbf{M}$ index by $U$. To prove $s$-diagonal code achieves the optimum recovery threshold of $n$, we need to show all the $n\times n$ submatrices $\mathbf{M}^{U}$ are full rank. We first define the following bipartite graph model between the set of $m$ workers $[m]$ and the set of $n$ data partitions $[n]$.

Based on the above definition, the coding matrix $\mathbf{M}$ of $s$-diagonal code can be obtained by assigning each intermediate $x_{ij}$ of Edmonds matrix $\mathbf{M}(\mathbf{x})$ a value from set $S$ independently and uniformly at random. Given the subset $U\subseteq[m]$ with $|U|=n$, define $G^{D}(U,V_{2})$ as a subgraph of $G^{D}(V_{1},V_{2})$ and $\mathbf{M}^{U}(\mathbf{x})$ as the corresponding Edmonds matrix. Then the probability that matrix $\mathbf{M}^{U}$ is full rank is equal to the probability that the determinant of the Edmonds matrix $\mathbf{M}^{U}(\mathbf{x})$ is nonzero at the given value $\mathbf{x}$. The following technical lemma provides a simple lower bound of the such an event.

A classic result in graph theory is that a bipartite graph $G^{D}(U,V_{2})$ contains a perfect matching if and only if the determinant of Edmonds matrix, i.e., $|\mathbf{M}^{U}(\mathbf{x})|$, is a nonzero polynomial. Combining this result with Schwartz-Zeppel Lemma, we can finally reduce the analysis of the full rank probability of the submatrix $\mathbf{M}^{U}$ to the probability that the subgraph $G^{D}(U,V_{2})$ contains a perfect matching.

The next technical lemma shows that for all subsets $U\subseteq[m]$, the subgraph $G^{D}(U,V_{2})$ exactly contains a perfect matching. Then utilizing the union bound, we conclude that, with probability at least $1/2$, all the $n\times n$ submatrices of $\mathbf{M}$ are full rank. Since we can generate the coding matrix $\mathbf{M}$ offline, with a few rounds of trials ($2$ in average), we can find a coding matrix with all $n\times n$ submatrices being full rank.

Construct bipartite graph $G^{D}(V_{1},V_{2})$ from Definition 5. For each $U\subseteq[m]$ with $|U|=n$, the subgraph $G^{D}(U,V_{2})$ contains a perfect matching.

The proof is mainly based on Hall’s marriage theorem. One special case of $s$-diagonal code is that all the nonzero elements of matrix $\mathbf{M}$ can be equal to $1$, when we are required to resist only one straggler.

Given the parameters $n$ and $m=n+1$, define the $1$-diagonal code:

It achieves the optimum computation load of $2n$ and optimum recovery threshold of $n$.

The $s$-diagonal code achieves both optimum recovery threshold of $n$ and computation load of $n(s+1)$. This result implies that the the average computation load, i.e., $n(s+1)/(n+s)$, will increase when number of stragglers increases. In the extreme case, the coding matrix $\mathbf{M}$ will degenerate to a fully dense matrix. The reason behind this phenomenon mainly derives from the pessimistic definition of the recovery threshold, which requires the coded computation scheme $\mathbf{M}$ to resist any $s$ stragglers. In the next section, we show that, if we relax requirement in Definition 2 to the probabilistic scenario, we can design a code with a computation load independent of the number of stragglers $s$.

IV Random Code: “Break” the Limits

In practice, the straggles randomly occur in each worker, and the probability that a specific straggling configuration happen is in low probability. We first demonstrate the main idea through the following motivating examples.

Example 2: Consider a distributed linear transform tasks with $n=20$ data partitions, $s=5$ stragglers and $m=25$ workers. The recovery threshold of $20$ implies that all $C_{25}^{20}=53130$ square $20\times 20$ submatrices are full rank. Suppose that a worker being a straggler is identically and independently Bernoulli random variable with probability $10\%$. Then, the probability that workers $\{1,2,3,4,5\}$ being straggler is $10^{-5}$. if there exists a scheme that can guarantee the master to decode the results in all configurations except straggling configurations $\{1,2,3,4,5\}$, we can argue that this scheme achieves a recovery threshold of $20$ with probability $1-10^{-5}$.

Based on the above two examples, the computation load can be reduced when we allow the coded computation strategy fails in some specific scenarios. Formally, we have the following definition of the probabilistic recovery threshold.

Instead of guaranteeing the recoverability of all the straggling configurations, new definition provides a probabilistic relaxation such that a small percentage of all the straggling configurations, i.e., vanishes as $n\rightarrow\infty$, are allowed to be unrecoverable. In the sequel, we show that, under such a relaxation, one can construct a coded computation scheme that achieves probabilistic recovery threshold of $n$ and a constant (regarding parameter $s$) computation load.

IV-B Construction of Random Code

Based on our previous analysis of the recovery threshold of $s-$diagonal code, we show that, for any subset $U\subseteq[m]$ with $|U|=n$, the probability that $\mathbf{M}^{U}$ is full rank is lower bounded by the probability (multiplied by $1-o(1)$) that the corresponding subgraph $G(U,V_{2})$ contains a perfect matching. This technical path motivates us to utilize the random proposal graph to construct the coded computation scheme. The first one is the following $p$-Bernoulli code, which is constructed from the ER random bipartite graph model .

($p$-Bernoulli code) Given parameters $m,n$, construct the coding matrix $\mathbf{M}$ as follows:

where $t_{ij}$ is picked independently and uniformly from the finite set $S$.

For any parameters $m,n$ and $s$, if $p=2\log(n)/n$, the $p$-Bernoulli code achieves the probabilistic recovery threshold of $n$.

This result implies that each worker of $p$-Bernoulli code requires accessing $2\log(n)$ submatrices in average, which is independent of number of stragglers. Note that the existing works in distributed functional computation proposes a random sparse code that also utilizes Bernoulli random variable to construct the coding matrix. There exist two key differences: (i) the elements of our matrix can be integer valued, while the random sparse code adopts real-valued matrix; (ii) the density of $p$-Bernoulli code is $2\log(n)$, while the density of the random sparse code is an unknown constant.

The second random code is the following $(d_{1},d_{2})$-cross code.

($(d_{1},d_{2})$-cross code) Given parameters $m,n$, construct the coding matrix $\mathbf{M}$ as follows: (1) Each row (column) independently and uniformly choose $d_{1}$ ($d_{2}$) nonzero positions; (2) For those nonzero positions, assign the value independently and uniformly from the finite set $S$.

It is easy to see that the computation load of $(d_{1},d_{2})$-cross code is upper bounded by $d_{1}m+d_{2}n$. The next theorem shows that a constant choice of $d_{1}$ and $d_{2}$ can guarantee the probabilistic recovery threshold of $n$.

For any parameters $m,n$ and $s$, if $s=\text{poly}(\log(n))$, the $(2,3)$-cross code achieves the probabilistic recovery threshold of $n$. If $s=\Theta(n^{\alpha})$, $\alpha<1$, the $(2,2/(1-\alpha))$-cross code achieves the probabilistic recovery threshold of $n$.

The proof of this theorem is based on analyzing the existence of perfect matching in a random bipartite graph constructed as following: (i) each node in the left partition randomly and uniformly connects to $d_{1}$ nodes in the opposite class; (ii) each node in the right partition randomly and uniformly connects to $l$ nodes in the opposite class, where $l$ is chosen under a specific degree distribution. This random graph model can be regarded as a generalization of Walkup’s $2$-out bipartite graph model . The main technical difficulty in this case derives from the intrinsic complicated statistical model of node degree of right partition.

One straightforward construction is using the LDPC codes or rateless codes such as LT and raptor code . These codes can not only guarantee the probabilistic recovery threshold of $\Theta(n)$, but also provide a low computation load, i.e., $O(n\log(1/\epsilon))$ from raptor code. However, the desired performance of these codes requires the $n$ sufficiently large, i.e., $n>10^{5}$, which is impossible in distributed computation. For example, when $n=20$, the recovery threshold of LT code is roughly equal to $30$, which is much larger than the lower bound.

IV-C Numerical Results of Random Code

We examine the performance of proposed $p$-Bernoulli code and $(d_{1},d_{2})$-cross code in terms of convergence speed of full rank probability and computation load. In Fig. 4, we plot the percentage of full rank $n\times n$ square submatrix and the average computation load $l(\mathbf{M})/m$ of each scheme, based on $1000$ experimental run. Each column of the $(2,2.5)$-code independently and randomly chooses $2$ or $3$ nonzero elements with equal probability. It can be observed that the full rank probability of both $p$-Bernoulli code and $(d_{1},d_{2})$-cross code converges to $1$ quite fast. The $(d_{1},d_{2})$-cross code exhibits even faster convergence and much less computation load compared to the $p$-Bernoulli code. For example, when $n=20,s=4$, the $(2,2)$-cross code achieves the full rank probability of $0.86$ and average computation load $3.4$. This provides the evidence that $(d_{1},d_{2})$-cross code is useful in practice. Moreover, in the practical use of random code, one can run multiple rounds of trails to find a “best” coding matrix with even higher full rank probability and lower computation load.

V Fast Decoding Algorithm

(rooting step) If rank$(\mathbf{M}^{U})=n$, then for any $k_{0}\in\{1,2,\ldots,n\}$, we can recover a particular block $\mathbf{A}_{i}\mathbf{x}$ with column index $k_{0}$ in matrix $\mathbf{M}^{U}$ via the following linear combination.

Moreover, we can show that, for the $s$-diagonal code, when the position of blocks recovered from rooting step (13) is specifically designed, the Algorithm 1 requires at most $s$ rooting steps. This result provides an $O(rs)$ time decoding algorithm for $s$-diagonal code.

(Nearly linear time decoding of $s$-diagonal code) For $s$-diagonal code constructed in Definition 4 and any $n$ received results indexed by $U=\{i_{1},\ldots,i_{n}\}\subseteq[n+s]$ and $1\leq i_{1}\leq\cdots\leq i_{n}\leq n+s$. Let the index $k\in[n]$ be $i_{k}\leq n<i_{k+1}$. Recover the blocks indexed by $[n]\backslash\{i_{1},\ldots,i_{k}\}$ from rooting steps (13). Then the Algorithm 1 uses the at most $s$ times rooting steps and the total decoding time is $O(rs)$.

VI Experimental Results

In this section, we present the experimental results at OSC . We compare our proposed coding schemes including $s-$diagonal code and $(d_{1},d_{2})$-cross code against the following existing schemes in both single matrix vector multiplication and gradient descent: (i) uncoded scheme: the input matrix is divided uniformly across all workers without replication and the master waits for all workers to send their results; (ii) sparse MDS code : the generator matrix is a sparse random Bernoulli matrix with average computation overhead $\Theta(\log(n))$. (iii) polynomial code : coded matrix multiplication scheme with optimum recovery threshold and nearly linear decoding time; (iv) short dot code : append the dummy vectors to data matrix $\mathbf{A}$ before applying the MDS code, which provides some sparsity of encoded data matrix with cost of increased recovery threshold. (v) LT code : rateless code widely used in broadcast communication. It achieves average computation overhead $\Theta(\log(n))$ and a nearly linear decoding time using peeling decoder. To simulate straggler effects in large-scale system, we randomly pick $s$ workers that are running a background thread.

We first use a matrix with $r=t=1048576$ and nnz$(\mathbf{A})=89239674$ from data sets , and evenly divide this matrix into $n=12$ and $20$ partitions. In Fig. 5, we report the job completion time under $s=2$ and $s=4$, based on $20$ experimental runs. It can be observed that both $(2,2)$-cross code outperforms uncoded scheme (in 50% the time), LT code (in 80% the time), sparse MDS code (in 60% the time), polynomial code (in 20% the time) and our $s$-diagonal code. Moreover, we have the following observations: (i)LT code performs better than sparse MDS code when number of stragglers $s$ is small, and worse when $s$ increases. (ii) the uncoded scheme is faster than the polynomial code, because the density of encoded data matrix is greatly increased, which leads to increased computation time per worker and additional I/O contention at the master node.

We further compare our proposed $s$-diagonal code with $(2,2)$-cross code versus the number of stragglers $s$. As shown in Fig. 5, when the number of stragglers $s$ increases, the job completion time of $s$-diagonal code increases while the $(2,2)$-cross code does not change. If the number of stragglers is smaller than $2$, the $s$-diagonal code performs better than $(2,2)$-cross code. Another interesting observation is that the irregularity of work load can decrease the I/O contention. For example, when $s=2$, the computation load of $2$-diagonal code is similar as $(2,2)$-cross code, which is equal to $36$ in the case of $n=12$. However, the $(2,2)$-cross code costs less time due to the unbalanced worker load.

VI-B Coded Gradient Descent

We first describe the gradient-based distributed algorithm to solve the following linear regression problem.

In the uncoded gradient descent, each worker $i$ first stores a submatrix $\mathbf{A}_{i}$; then during iteration $t$, each worker $i$ first computes a vector $\mathbf{A}_{i}^{\intercal}\mathbf{A}_{i}\mathbf{x}_{t}$ and returns it to the master node; the master node updates the weight vector $\mathbf{x}_{t}$ according to the above gradient descent step and assigns the new weight vector $\mathbf{x}_{t+1}$ to each worker. The algorithm terminates until the gradient vanish, i.e., $\|\mathbf{A}^{\intercal}(\mathbf{Ax}_{t}-\mathbf{b})\|\leq\epsilon$. In the coded gradient descent, each worker $i$ first stores several submatrices according to the coding matrix $\mathbf{M}$; during iteration $t$, each worker $i$ computes a linear combinations,

where $m_{ij}$ is the element of the coding matrix $\mathbf{M}$. The master node collects a subset of results, decodes the full gradient $\mathbf{A}^{\intercal}(\mathbf{Ax}_{t}-\mathbf{b})$ and updates the weight vector $\mathbf{x}_{t}$. Then continue to the next round.

We use a data from LIBSVM dataset repository with $r=19264097$ samples and $t=1163024$ features. We evenly divide the data matrix $\mathbf{A}$ into $n=12,20$ submatrices. In Fig. 6 , we plot the magnitude of scaled gradient $\|\eta\mathbf{A}^{\intercal}(\mathbf{Ax}-\mathbf{b})\|^{2}$ versus the running times of the above seven different schemes under $n=12,20$ and $s=2,4$. Among all experiments, we can see that $(2,2)$-cross code converges at least $20\%$ faster than sparse MDS code, $2$ times faster than both uncoded scheme and LT code and at least $4$ times faster than short dot and polynomial code. The $(2,2)$-cross code performs similar with $s$-diagonal code when $s=2$ and converges $30\%$ faster than $s$-diagonal code when $s=4$.

References

-C Proof of Theorem 2

Given the parameter $m$ and $n$, considering any coded computation scheme that can resist $s$ stragglers. We first define the following bipartite graph model between the $m$ workers $[m]$ and $n$ data partitions $[n]$, where we connect node $i\in[m]$ and node $j\in[n]$ if $m_{ij}\neq 0$ (worker $i$ has access to data block $\mathbf{A}_{j}$). The degree of worker node $i\in[m]$ is $\|\mathbf{M}_{i}\|_{0}$. We show that the degree of node $j\in[n]$ must be at least $s+1$. Suppose that it is less than $s+1$ and all its neighbors are stragglers. In this case, there exists no worker that is non-straggler and also access to $\mathbf{A}_{j}$(or the corresponding submatrix of coding matrix is rank deficient). It is contradictory to the assumption that it can resist $s$ stragglers.

Based on the above argument and the fact that, the sum of degrees of one partition is equal to the sum of degrees in another partition in the bipartite graph, we have

-D Proof of Lemma 2

A direct application of Hall’s theorem is: given a bipartite graph $G^{D}(V_{1},V_{2})$, for each $U\subseteq[m]$ with $|U|=n$, each subgraph $G^{D}(U,V_{2})$ contains a prefect matching if and only if every subset set $S\subseteq V_{1}$ such that $|N(S)|<|S|$, where the neighboring set $N(S)$ is defined as $N(S)=\{y|x,y\text{ are connected for some }x\in S\}$. This result is equivalent to the following condition: for each subset $I\subseteq[m]$,

where supp$(\mathbf{M_{i}})$ is defined as the support set: supp$(\mathbf{M_{i}})=\{j|m_{ij}\neq 0,j\in[n]\}$, $\mathbf{M_{i}}$ is $i$th row of the coding matrix $\mathbf{M}$. Suppose that the set $I=\{i_{1},i_{2},\ldots,i_{k}\}$ with $i_{1}<i_{2}<\ldots<i_{k}$ and $\text{supp}(\mathbf{M}_{i_{k_{1}}})\cap\text{supp}(\mathbf{M}_{i_{k_{2}}})\neq\emptyset$. Otherwise, we can divide the set into two parts $I_{l}=\{i_{1},i_{2},\ldots,i_{k_{1}}\}$ and $I_{r}=\{i_{k_{2}},i_{2},\ldots,i_{k}\}$ and prove the similar result in these two sets. Based on our construction of diagonal code, we have

The above, step (a) is based on the fact that $i_{k}-i_{1}\geq k$. Therefore, the lemma follows.

-E Proof of Corollary 1

To prove $1$-diagonal code achieves the recovery threshold of $n$, we need to show that, for each subset $U\subseteq[n+1]$ with $|U|=n$, submatrix $\mathbf{M}^{U}$ is full rank. Let $U=[n+1]\backslash\{k\}$, the submatrix $\mathbf{M}^{U}$ satisfies

where $\mathbf{E}$ is a $(k-1)$ dimensional square submatrix consists of first $(k-1)$ rows and columns, and $\mathbf{F}$ is a $(n-k+1)$ dimensional square submatrix consists of the last $(n-k+1)$ rows and columns. The matrix $\mathbf{E}$ is a lower diagonal matrix due to the fact that, for $i<j$,

The matrix $\mathbf{E}$ is a upper diagonal matrix due to the fact that, for $i>j$,

The above, (a) utilizes the fact that $(i+k)-(j+k-1)\geq 2$ when $i>j$. Based on the above analysis, we have

which implies that matrix $\mathbf{M}^{U}$ is full rank. Therefore, the corollary follows.

-F Proof of Theorem 4

Based on our analysis in Section III-C, the full rank probability of an $n\times n$ submatrix $\mathbf{M}^{U}$ can be lower bounded by a constant multiplying the probability of the existence of perfect matching in a bipartite graph.

Therefore, to prove that the $p$-Bernoulli code achieves the probabilistic recovery threshold of $n$, we need to show that each subgraph contains a perfect matching with high probability. Without loss of generality, we can define the following random bipartite graph model.

($p$-Bernoulli random graph) Graph $G^{b}(U,V_{2},p)$ initially contains the isolated nodes with $|U|=|V_{2}|=n$. Each node $v_{1}\in U$ and node $v_{2}\in V_{2}$ is connected with probability $p$ independently.

Clearly, the above model describes the support structure of each submatrix $\mathbf{M}^{U}$ of $p$-Bernoulli code. The rest is to show that, with specific choice of $p$, the subgraph $G^{b}(U,V_{2},p)$ contains a perfect matching with high probability.

The technical idea is to use the Hall’s theorem. Assume that the bipartite graph $G^{b}(U,V_{2},p)$ does not have a perfect matching. Then by Hall’s condition, there exists a violating set $S\subseteq U$ or $S\subseteq V_{2}$ such that $|N(S)|<|S|$. Formally, by choosing such $S$ of smallest cardinality, one immediate consequence is the following technical statement.

If the bipartite graph $G^{b}(U,V_{2},p)$ does not contain a perfect matching, then there exists a set $S\subseteq U$ or $S\subseteq V_{2}$ with the following properties.

For each node $t\in N(S)$, there exists at least two adjacent nodes in $S$.

Case 1: We consider $S\subseteq U$ and $|S|=1$. In this case, we have $|N(S)|=0$ and need to estimate the probability that there exists one isolated node in partition $U$. Let random variable $X_{i}$ be the indicator function of the event that node $v_{i}$ is isolated. Then we have the probability that

Let $X$ be the total number of isolated nodes in partition $U$. Then we have

The above, step (a) utilizes the assumption that $p=2\log(n)/n$ and the inequality that $(1+x/n)^{n}\leq e^{x}$.

Case 2: We consider $S\subseteq U$ and $2\leq|S|\leq n/2$. Let $E$ be the event that such an $S$ exists, we have

The above, step (a) is based on the inequality

The step (b) utilizes the fact that $p=2\log(n)/n$, $k\leq n/2$ and the inequality $(1+x/n)^{n}\leq e^{x}$; step (c) is based on the fact that $k(n-k+1)\geq 2(n-1)$ and $k(n-k)\geq 2(n-2)$, $n/(n-2)<5/3$ for $k\geq 2$ and $n\geq 5$. Utilizing the union bound to sum the results in case 1 and case 2, we can obtain that the probability that graph $G(U,V_{2},p)$ contains a perfect matching is at least

Therefore, incorporating this result into estimating (11), the theorem follows.

-G Proof of Theorem 5

To prove the $(d_{1},d_{2})$-cross code achieves the probabilistic recovery threshold of $n$, we need to show that each subgraph of the following random bipartite graph contains a perfect matching with high probability.

($(d_{1},d_{2})$-regular random graph) Graph $G^{c}(V_{1},V_{2},d_{1},d_{2})$ initially contains the isolated nodes with $|V_{1}|=m$ and $|V_{2}|=n$. Each node $v_{1}\in V_{1}$ ($v_{2}\in V_{2}$) randomly and uniformly connects to $d_{1}$ ($d_{2}$) nodes in $V_{1}$ ($V_{2}$).

The corresponding subgraph is defined as follows.

For each $U\subseteq V_{1}$ with $|U|=n$, the subgraph $G^{c}(U,V_{2},d_{1},\bar{d})$ is obtained by deleting the nodes in $V_{1}\backslash U$ and corresponding arcs.

Clearly, the above definitions of $(d_{1},d_{2})$-regular graph and corresponding subgraph describe the support structure of the coding matrix $\mathbf{M}$ and submatrix $\mathbf{M}^{U}$ of the $(d_{1},d_{2})$-cross code. Moreover, we have the following result regarding the structure of each subgraph $G^{c}(U,V_{2},d_{1},\bar{d})$

Claim. For each $U\subseteq V_{1}$ with $|U|=n$, the subgraph $G^{c}(U,V_{2},d_{1},\bar{d})$ can be constructed from the following procedure" (i) Initially, graph $G^{c}(U,V_{2},d_{1},\bar{d})$ contain the isolated nodes with $|U|=|V_{2}|=n$; (ii) Each node $v_{1}\in U$ randomly and uniformly connects to $d_{1}$ nodes in $V_{2}$; (iii) Each node $v_{2}\in V_{2}$ randomly and uniformly connects to $l$ nodes in $V_{1}$, where $l$ is chosen according to the distribution:

Then, the rest is to show that the subgraph $G^{c}(U,V_{2},d_{1},\bar{d})$ contains a perfect matching with high probability.

(Forbidden $k$-pair) For a bipartite graph $G(U,V_{2},d_{1},\bar{d})$, a pair $(A,B)$ is called a $k$-blocking pair if $A\subseteq U$ with $|A|=k$, $B\subseteq V_{2}$ with $|B|=n-k+1$, and there exists no arc between the nodes of sets $A$ and $B$. A blocking $k$-pair $(A,B)$ is called a forbidden pair if at least one of the following holds:

$2\leq k<(n+1)/2$, and for any $v_{1}\in A$ and $v_{2}\in V_{2}\backslash B$, $(A\backslash\{v_{1}\},B\cup\{v_{2}\})$ is not a $(k-1)$-blocking pair.

$(n+1)/2\leq k\leq n-1$, and for any $v_{1}\in U\backslash A$ and $v_{2}\in B$, $(A\cup\{v_{1}\},B\backslash\{v_{2}\})$ is not a $(k+1)$-blocking pair.

The following technical lemma modified from is useful in our proof.

If the graph $G^{c}(U,V_{2},d_{1},\bar{d})$ does not contain a perfect matching, then there exists a forbidden $k$-pair for some $k$.

One direct application of the Konig’s theorem to bipartite graph shows that $G^{c}(U,V_{2},d_{1},\bar{d})$ contains a perfect matching if and only if it does not contain any blocking $k$-pair. It is rest to show that the existence of a $k$-blocking pair implies that there exists a forbidden $l-$pair for some $l$. Suppose that there exists a $k$-blocking pair $(A,B)$ with $k<(n+1)/2$, and it is not a forbidden $k$-pair. Otherwise, we already find a forbidden pair. Then, it implies that there exists $v_{1}\in A$ and $v_{2}\in V_{2}\backslash B$ such that $(A\backslash\{v_{1}\},B\cup\{v_{2}\})$ is a $(k-1)$-blocking pair. Similarly, we can continue above argument on blocking pair $(A\backslash\{v_{1}\},B\cup\{v_{2}\})$ until we find a forbidden pair. Otherwise, we will find a $1-$blocking pair $(A^{\prime},B^{\prime})$, which is a contradiction to our assumption that each node $v_{1}\in U$ connects $d_{1}$ nodes in $V_{2}$. The proof for $k\geq(n+1)/2$ is same. ∎

Let $E$ be the event that graph $G(U,V_{2},d_{1},\bar{d})\text{ contains perfect matching}$. Based on the the results of Lemma 5, we have

The above, $A$ and $B$ are defined as node sets such that $A\subseteq U$ with $|A|=k$ and $B\subseteq V_{2}$ with $|B|=n-k+1$. The $\alpha(k)$ and $\beta(k)$ are defined as follows.

From the Definition 12, it can be obtained the following estimation of probability $\beta(k)$.

The first factor gives the probability that there exists no arc from nodes of $A$ to nodes of $B$. The second factor gives the probability that there exists no arc from nodes of $B$ to nodes of $A$. The summation operation in the second factor comes from conditioning such probability on the distribution (29). Based on the Chu-Vandermonde identity, one can simplify $\beta(k)$ as

In the above, step (a) is based on fact that $(1+x/n)^{n}\leq e^{x}$ and parameters $c_{1}$ and $c_{2}$ are defined as

Combining the equations (35)-(38), we can obtain that

The constant $c_{3}$ is given by $c_{3}=e^{d_{1}^{2}+13d_{1}/12+d_{2}+1/3}/2\pi$. The third term satisfies

which is based on the fact that, if $d_{2}>2$, the function

is monotonically decreasing when $k\leq(d_{2}n-2m)/(d_{2}-2)$ and increasing when $k\geq(d_{2}n-2m)/(d_{2}-2)$. If $d_{2}=2$, it is monotonically increasing for $k\geq 0$.

We then estimate the conditional probability $\alpha(k)$. Given a blocking pair $A\subseteq U$ with $|A|=k$ and $B\subseteq V_{2}$ with $|B|=n-k+1$, and a node $v_{i}\in A$, let $E_{i}$ be the set of nodes in $V_{2}\backslash B$ on which $d_{1}$ arcs from node $v_{i}$ terminate. Let $E^{\prime}$ be the set of nodes $v$ in $V_{2}\backslash B$ such that at least $2$ arcs leaving from $v$ to nodes in $A$. Then we have the following technical lemma.

Given a blocking pair $A\subseteq U$ with $|A|=k$ and $B\subseteq V_{2}$ with $|B|=n-k+1$, if $(A,B)$ is $k$-forbidden pair, then

Suppose that there exists node $v\in V_{2}\backslash(E^{*}\cup B)$, then there exists no arc from $A$ to $v$ and there exists at most $1$ arc from $v$ to $A$. If such an arc exists, let $v^{\prime}$ be the corresponding terminating node in $A$. Then we have $(A\backslash\{v^{\prime}\},B\cup\{v\})$ is a blocking pair, which is contradictory to the definition of forbidden pair. If such an arc does not exist, let $v^{\prime}$ be the an arbitrary node in $A$. Then we have $(A\backslash\{v^{\prime}\},B\cup\{v\})$ is a blocking pair, which is also contradictory to the definition of forbidden pair. ∎

The lemma 6 implies that we can upper bound the conditional probability by

where $P_{1}$ and $P_{2}$ is defined as: for any node $v\in V_{2}\backslash B$,

The above, step (a) utilizes Chu-Vandermonde identity twice; step (b) is adopts the inequality (34); step (c) is based on the fact that if $n$ is sufficiently large, $(1-x/n)^{n}\geq c_{5}e^{-x}$, where $c_{5}$ is a constant. Combining the above estimation of $P_{1}$ and $P_{2}$, we have the following upper bound of $\alpha(k)$.

We finally estimate the probability that the graph $G^{c}(U,V_{2},d_{1},\bar{d})$ contains a perfect matching under the following two cases.

Case 1: The number of stragglers $s=\text{poly}(\log(n))$. Let $d_{1}=2,d_{2}=3$. Based on the estimation (40), we have

Combining the above results with the estimation of $\beta(k)$, we have

The above, step (a) utilizes the estimation of $\alpha(k)$ in (43); step (b) is based on estimating the tail of the summation as geometric series $(1-c_{6}/e^{2})^{k-1}$.

Case 2: The number of stragglers $s=\Theta(n^{\alpha})$, $\alpha<1$. Let $d_{1}=2,d_{2}=2/(1-\alpha)$. For $2\leq k\leq n-2$, we have

Combining the above results with the estimation of $\beta(k)$, we have

If $\alpha\geq 1/2$, we can directly obtain that $\gamma(k)\leq\frac{c_{3}e^{-2}}{n}$. If $\alpha<1/2$, we have

Therefore, in both cases, incorporating the above results into estimating (11), the theorem follows.

-H Proof of Theorem 6

Based on our construction, the cardinality of the set

Since $n<i_{k+1}<\cdots<i_{n}\leq n+s$, we have $n-k\leq s$. We next show, after we recover the blocks indexed by $[n]\backslash\{i_{1},\ldots,i_{k}\}$, the rest blocks can be recovered by peeling decoding without rooting steps. Combining these results together, the total number of rooting steps is at most $s$.