$\displaystyle=(|\mathcal{S}|-z)\sum\limits_{\\!i\in\left[\binom{|\mathcal{S}|}{z}\right],k\in\mathcal{S}_{z}[i]}\bigg{|}\mathcal{V}_{\mathcal{S}_{z}[i]}^{\mathcal{S}\backslash\mathcal{S}_{z}[i]}\bigg{|}-(z-1)\sum\limits_{\\!i\in\left[\binom{|\mathcal{S}|}{z}\right],k\notin\mathcal{S}_{z}[i]}\bigg{|}\mathcal{V}_{\mathcal{S}_{z}[i]}^{\mathcal{S}\backslash\mathcal{S}_{z}[i]}\bigg{|}$
$\displaystyle=\tbinom{|\mathcal{S}|-1}{r}\frac{NQ}{\binom{K}{r}\binom{K}{s}}\tbinom{r}{|\mathcal{S}|-s}>0,\forall
k\in\mathcal{S},z=r,$ (70)

and $n_{k,z}^{\mathcal{S}}=0$ for $z\neq r$, which means the deficit condition
is satisfied according to (12).

Then, consider the feasible condition. In the round $z=r$ of cluster
$\mathcal{S}$, we can find a solution of (13) for Node $i$ as

$\displaystyle\beta_{j,\mathcal{S}_{1}}=\frac{(|\mathcal{S}|\\!-\\!1)}{z}|\mathcal{V}_{\mathcal{S}_{1}}^{\mathcal{S}\backslash\mathcal{S}_{1}}|=\frac{(|\mathcal{S}|\\!-\\!1)}{r}\frac{NQ}{\binom{K}{r}\tbinom{K}{s}}\binom{r}{|\mathcal{S}|-s},$
$\displaystyle\forall
j\in\mathcal{S}_{1},i\not\in\mathcal{S}_{1},\mathcal{S}_{1}\subseteq\mathcal{S},|\mathcal{S}_{1}|=z.$
(71)

The $\beta_{j,\mathcal{S}_{1}}$ above is a solution for Node $i\in\mathcal{S}$
since

$\displaystyle\sum_{\begin{subarray}{c}j:j\in
S_{1}\end{subarray}}\beta_{j,\mathcal{S}_{1}}=(|\mathcal{S}|\\!-\\!1)|\mathcal{V}_{\mathcal{S}_{1}}^{\mathcal{S}\backslash\mathcal{S}_{1}}|,\
\forall\mathcal{S}_{1}\subseteq\mathcal{S}\\!:\\!|\mathcal{S}_{1}|=z,i\not\in\mathcal{S}_{1},$
$\displaystyle\sum_{S_{1}:j\in\mathcal{S}_{1},i\not\in\mathcal{S}_{1}}\beta_{j,\mathcal{S}_{1}}=\tbinom{|\mathcal{S}|-2}{z-1}\frac{(|\mathcal{S}|-1)}{z}|\mathcal{V}_{\mathcal{S}_{1}}^{\mathcal{S}\backslash\mathcal{S}_{1}}|=\tbinom{|\mathcal{S}|-1}{z}|\mathcal{V}_{\mathcal{S}_{1}}^{\mathcal{S}\backslash\mathcal{S}_{1}}|=n_{j,z}^{\mathcal{S}},\forall
j\in\mathcal{S},j\neq i,$

which satisfies the feasible condition in (13).

As both feasible and deficit conditions are satisfied, our FSCT is optimal
according to Theorem 3.

###  D-B 3-node System

Similar to Appendix B-A, we only calculate the communication load in the round
2 of cluster $S=\\{1,2,3\\}$ in which we consider file sets
$\mathcal{S}_{12},\mathcal{S}_{13}$ and $\mathcal{S}_{23}$. Rewrite
$n_{k,z}^{\mathcal{S}}$ as $n_{k}$ for simplicity.

####  D-B1 Case1

If $S_{12}+S_{13}-S_{23}\geq 0$, according to (10), we can get all
$n_{1},n_{2},n_{3}$ below

$\displaystyle n_{1}=S_{12}+S_{13}-S_{23}>0$ $\displaystyle
n_{2}=S_{12}+S_{23}-S_{13}>0$ $\displaystyle n_{3}=S_{13}+S_{23}-S_{12}>0.$
(72)

By (43), Node $i$ will multicast $n_{i}$ LCs with size of $\frac{1}{2}$ IV, so
the communication load can be computed as:

$\displaystyle L$
$\displaystyle=2\left(S_{1}+S_{2}+S_{3}\right)+\frac{1}{2}(S_{12}+S_{13}+S_{23}).$
(73)

####  D-B2 Case2

If $S_{12}+S_{13}-S_{23}<0$, from (72), we can get

$\displaystyle(n_{1})^{+}=0$ $\displaystyle(n_{2})^{+}=S_{12}+S_{23}-S_{13}$
$\displaystyle(n_{3})^{+}=S_{13}+S_{23}-S_{12}.$ (74)

Now we show that the feasible condition is satisfied. Take Node 3 as an
example, the feasible condition of Node 3 in (13) will be

$\displaystyle\beta_{1,\\{1,2\\}}\leq 0$
$\displaystyle\beta_{1,\\{1,2\\}}+\beta_{2,\\{1,2\\}}\geq 2S_{12}$
$\displaystyle\beta_{2,\\{1,2\\}}\leq S_{12}+S_{23}-S_{13}.$ (75)

We can find that $\beta_{1,\\{1,2\\}}=0$ and
$2S_{12}\leq\beta_{2,\\{1,2\\}}\leq S_{12}+S_{23}-S_{13}$ is a solution to
(75). Since $S_{12}+S_{23}-S_{13}>2S_{12}$, the feasible condition is
satisfied. Thus, by (43), the communication load can be computed as

$\displaystyle L$
$\displaystyle=2\left(S_{1}+S_{2}+S_{3}\right)+(n_{1})^{+}+(n_{2})^{+}+(n_{3})^{+}$
$\displaystyle=2\left(S_{1}+S_{2}+S_{3}\right)+S_{23}.$ (76)

In [21], the authors proved that the communication load (73) and (76) are
coherent with (52) in Lemma 2, i.e., our communication load in Theorem 3 is
tight.

###  D-C Semi-Homogeneous System

For a semi-homogeneous system, according to the definition of
$\mathcal{V}_{\mathcal{S}_{z}[i]}^{\mathcal{S}\backslash\mathcal{S}_{z}[i]}$
(23),

$\displaystyle|\mathcal{V}_{\mathcal{S}_{z}[i]}^{\mathcal{S}\backslash\mathcal{S}_{z}[i]}|=\sum\limits_{s=|\mathcal{S}|-r}^{|\mathcal{S}|}\frac{\binom{r}{|\mathcal{S}|-s}}{\binom{K}{r}\binom{K}{s}}Q_{s}N,~{}\forall
i\in[\tbinom{|\mathcal{S}|}{z}],z=r,$ (77)

and
$|\mathcal{V}_{\mathcal{S}_{z}[i]}^{\mathcal{S}\backslash\mathcal{S}_{z}[i]}|=0$
for $z\neq r$. Then according to the definition of
$\bar{n}_{k,z}^{\mathcal{S}}$ (10), we obtain that for all $k\in\mathcal{S}$
and $z=r$,

$\displaystyle n_{k,z}^{\mathcal{S}}$
$\displaystyle=(|\mathcal{S}|-z)\sum\limits_{\\!i\in\left[\binom{|\mathcal{S}|}{z}\right],k\in\mathcal{S}_{z}[i]}\bigg{|}\mathcal{V}_{\mathcal{S}_{z}[i]}^{\mathcal{S}\backslash\mathcal{S}_{z}[i]}\bigg{|}-(z-1)\sum\limits_{\\!i\in\left[\binom{|\mathcal{S}|}{z}\right],k\notin\mathcal{S}_{z}[i]}\bigg{|}\mathcal{V}_{\mathcal{S}_{z}[i]}^{\mathcal{S}\backslash\mathcal{S}_{z}[i]}\bigg{|}$
$\displaystyle=\tbinom{|\mathcal{S}|-1}{r}\sum\limits_{s=|\mathcal{S}|-r}^{|\mathcal{S}|}\frac{\binom{r}{|\mathcal{S}|-s}}{\binom{K}{r}\binom{K}{s}}Q_{s}N>0,$

which means the deficit condition is satisfied.

Then, consider the feasible condition $\mathscr{E}_{2}(i,\mathcal{S},z)$. For
each Node $i\in\mathcal{S}$ in round $z=r$, similar to Appendix D-A, we can
find a solution of (13) for Node $i$ below

$\displaystyle\beta_{j,\mathcal{S}_{1}}$
$\displaystyle=\frac{(|\mathcal{S}|\\!-\\!1)}{z}|\mathcal{V}_{\mathcal{S}_{1}}^{\mathcal{S}\backslash\mathcal{S}_{1}}|=\frac{N(|\mathcal{S}|-1)}{r}\sum\limits_{s=|\mathcal{S}|-r}^{|\mathcal{S}|}\frac{\binom{r}{|\mathcal{S}|-s}}{\binom{K}{r}\binom{K}{s}}Q_{s},$
$\displaystyle\forall
j\in\mathcal{S}_{1},i\not\in\mathcal{S}_{1},\mathcal{S}_{1}\subseteq\mathcal{S},|\mathcal{S}_{1}|=z.$
(78)

The aforementioned $\beta_{j,\mathcal{S}_{1}}$ is a solution since

$\displaystyle\sum_{\begin{subarray}{c}j:j\in
S_{1}\end{subarray}}\beta_{j,\mathcal{S}_{1}}=(|\mathcal{S}|\\!-\\!1)|\mathcal{V}_{\mathcal{S}_{1}}^{\mathcal{S}\backslash\mathcal{S}_{1}}|,\
\forall S_{1}\subseteq\mathcal{S}\\!:\\!|S_{1}|=z,i\not\in\mathcal{S}_{1}$
$\displaystyle\sum_{\mathcal{S}_{1}:j\in\mathcal{S}_{1},i\not\in\mathcal{S}_{1}}\beta_{j,\mathcal{S}_{1}}=\tbinom{|\mathcal{S}|-2}{z-1}\frac{(|\mathcal{S}|-1)}{z}|\mathcal{V}_{\mathcal{S}_{1}}^{\mathcal{S}\backslash\mathcal{S}_{1}}|$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
=\tbinom{|\mathcal{S}|-1}{z}|\mathcal{V}_{\mathcal{S}_{1}}^{\mathcal{S}\backslash\mathcal{S}_{1}}|=n_{j,z}^{\mathcal{S}},\
\ \ \forall j\in\mathcal{S},j\neq i.$

As both feasible and deficit conditions are satisfied, our FSCT is optimal
according to Theorem 3.

Figure 6:  Structure of decoding matrix $\mathbf{M}$, which contains $R$ rows
and $C$ columns. Each dashed box represents an element of the matrix
$\mathbf{M}$. $\mathbf{M}$ is divided into submatrices $M_{\sigma_{i},m}$ with
$\sigma_{i}\in\mathcal{S}\backslash\\{\sigma_{k}\\}$ and
$m\in[\tbinom{|\mathcal{S}|-1}{z}]$. The large grey rectangles are submatrices
$M_{\sigma_{i},c}$ with $\sigma_{i}\in\mathcal{H}_{m}$ whose elements are all
randomly generated and the large white rectangles are submatrices with
$\sigma_{i}\not\in\mathcal{H}_{m}$ whose elements are all zero. The numbers in
the boxes are row and column bin indices. The numbers along with the row and
column indicate the row index and column index of the matrix respectively. For
example, the submatrix $M_{\sigma_{j},m}$ has
$\bar{n}_{\sigma_{j},z}^{\mathcal{S}}$ rows and
$|\mathcal{V}_{\mathcal{H}_{m}}^{\mathcal{S}\backslash\mathcal{H}_{m}}|$
columns. The right-side numbers are the indices of sub-bins partitioned based
on the solution of the feasible conditions:
{$\beta_{\sigma_{i},\mathcal{T}}\in\mathbb{Q}^{+}:\sigma_{i}\in\mathcal{T},\sigma_{k}\not\in\mathcal{T},\mathcal{T}\subseteq\mathcal{S},|\mathcal{T}|=z$}
and $\beta_{\sigma_{i},\mathcal{T}}=0$ if $\sigma_{i}\not\in\mathcal{T}$. For
example, the $\sigma_{j}$-th row bin of the matrix is partitioned into
$\binom{|\mathcal{S}|-1}{z}$ sub-bins where the $l$-th part for
$l\in[\binom{|\mathcal{S}|-1}{z}]$ contains
$\beta_{\sigma_{j},\mathcal{H}_{l}}$ rows. The cyan points (and the red point)
in the figure are the elements we choose for the non-zero path
$(m_{i_{1},1},m_{i_{2},2},\cdots,m_{i_{C},C}):m_{i_{c},c}\neq 0$ for
$c\in[C]$. For example, we can choose the element in the $p$-th row of the
$m$-th sub-bin in the $\sigma_{j}$-th row bin for the $c$-th column, where $m$
is the index that $\sum_{i=1}^{m-1}{U}_{\mathcal{H}_{i}}+1\leq
c\leq\sum_{i=1}^{m}{U}_{\mathcal{H}_{i}}$,
$\sigma_{j}=k_{t}\in\mathcal{H}=\\{k_{1},\cdots,k_{z}\\}$, which satisfy
$\\!\\!\\!\\!\\!\\!\\!\sum\limits_{\sigma_{i}\in{\\{k_{1},\cdots,k_{t-1}\\}}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\beta_{\sigma_{i},\mathcal{H}_{m}}\\!+\\!1\leq
c\\!-\\!\sum_{i=1}^{m-1}\\!\\!{U}_{\mathcal{H}_{i}}\leq\\!\\!\\!\\!\\!\\!\\!\\!\\!\sum\limits_{\sigma_{i}\in{\\{k_{1},\cdots,k_{t}\\}}}\\!\\!\\!\\!\\!\\!\\!\\!\beta_{\sigma_{i},\mathcal{H}_{m}}$,
and
$p=c-\sum_{i=1}^{m-1}|\mathcal{U}_{\mathcal{H}_{j}}^{\mathcal{S}\backslash\mathcal{H}_{j}}|-\\!\\!\\!\\!\\!\\!\sum\limits_{\sigma_{i}\in{\\{k_{1},\cdots,k_{t-1}\\}}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\beta_{\sigma_{i},\mathcal{H}_{m}}$,
which is the red point in the figure.

##  Appendix E Correctness of FSCT

For cluster
$\mathcal{S}=\\{\sigma_{1},\sigma_{2},\cdots,\sigma_{|\mathcal{S}|}\\}$, we
prove that each receiver $\sigma_{k}$ in the round $z$ can successfully decode
its desired IV segments by jointly solving the LCs sent from other nodes in
$\mathcal{S}\backslash\\{\sigma_{k}\\}$.

We index the $\binom{|\mathcal{S}|-1}{z}$ subsets of $\mathcal{S}$ of size $z$
which do not contain Node $\sigma_{k}$ (i.e.,
$\\{\mathcal{T}:\mathcal{T}\subseteq\mathcal{S},|\mathcal{T}|=z,\sigma_{k}\not\in\mathcal{T}\\}$)
as $\\{\mathcal{H}_{1},\cdots,\mathcal{H}_{\binom{|\mathcal{S}|-1}{z}}\\}$.
Note that FSCT cuts each IV into $|\mathcal{S}|-1$ segments in cluster
$\mathcal{S}$. For convenience, we use ${U}_{\mathcal{H}_{i}}$ to denote the
number of _segments_ generated from IVs in
$\mathcal{V}_{\mathcal{H}_{i}}^{\mathcal{S}\backslash\mathcal{H}_{i}}$. Recall
that after receiving the message blocks from other nodes in $\mathcal{S}$,
i.e.,
$\\{X_{k,z}^{\mathcal{S}}[{i}]:k\in\mathcal{S}\backslash\\{\sigma_{k}\\},i\in[\bar{n}_{k,z}^{\mathcal{S}}]\\}$,
receiver $\sigma_{k}\in\mathcal{S}$ first removes the local segments
$\Big{\\{}{U}_{\mathcal{T}}^{\mathcal{S}\backslash\mathcal{T}}:\mathcal{T}\subseteq\mathcal{S},|\mathcal{T}|=z,\sigma_{k}\in\mathcal{T}\Big{\\}}$
from the messages to generate
$R\triangleq\sum_{k\in\mathcal{S}\backslash\\{\sigma_{k}\\}}\bar{n}_{k,z}^{\mathcal{S}}$
numbers of LCs consisting of
$C\triangleq\sum_{i=1}^{\binom{|\mathcal{S}|-1}{z}}{U}_{\mathcal{H}_{i}}$
unknown variables. Let matrix $\mathbf{M}\in\mathbb{R}_{R\times C}$ denote the
coefficient matrix of received LCs after removing local segments, which is
shown in Fig. 6.

The $R$ rows of the $\mathbf{M}$ will be divided into $|\mathcal{S}|-1$ _row
bin_ , with the row bin indices
$\sigma_{1},\ldots,\sigma_{k-1},\sigma_{k+1}\ldots,\sigma_{|\mathcal{S}|}$.
Each row bin $\sigma_{i}$ contains $n_{\sigma_{i},z}^{\mathcal{S}}$ rows,
which represent the number of LCs sent by Node $\sigma_{i}$ in round $z$ of
cluster $\mathcal{S}$. Each row bin $\sigma_{i}$, for
$i\in\mathcal{S}\backslash\\{k\\}$, is further partitioned into
$\binom{|\mathcal{S}|-1}{z}$ sub-bins, indexed as
$\\{1,2,\cdots,\binom{|\mathcal{S}|-1}{z}\\}$, with the $l$-th sub-bin
($l\in[\tbinom{|\mathcal{S}|-1}{z}]$) containing
$\beta_{\sigma_{i},\mathcal{H}_{l}}$ rows, where
$\beta_{\sigma_{i},\mathcal{H}_{l}}$ is the non-negative solution of (13):
{$\beta_{\sigma_{i},\mathcal{T}}\in\mathbb{Q}^{+}:\sigma_{i}\in\mathcal{T},\sigma_{k}\not\in\mathcal{T},\mathcal{T}\subseteq\mathcal{S},|\mathcal{T}|=z$},
and let $\beta_{\sigma_{i},\mathcal{T}}=0$ if $\sigma_{i}\not\in\mathcal{T}$.
Note that from the second constraint
$\sum_{\mathcal{T}:\sigma_{i}\in\mathcal{T},\sigma_{k}\not\in\mathcal{T}}\beta_{\sigma_{i},\mathcal{T}}\leq\bar{n}_{\sigma_{i},z}^{\mathcal{S}}$
in (13), we can guarantee that there are enough rows to do partition, and the
residual rows after the partition can be brought into the last sub-bin.

The $C$ columns of the $\mathbf{M}$ can be divided into
$\binom{|\mathcal{S}|-1}{z}$ _column bin_ , and the $m$-th column bin contains
$|U_{\mathcal{H}_{m}}|$ columns which represent the number of segments in
$\mathcal{V}_{\mathcal{H}_{m}}^{\mathcal{S}\backslash\mathcal{H}_{m}}$.

Now we split the matrix $\mathbf{M}$ into
$\binom{|\mathcal{S}|-1}{z}\times(|\mathcal{S}|-1)$ submatrices
$\\{M_{\sigma_{i},m}:\sigma_{i}\in\mathcal{S}\backslash\\{\sigma_{k}\\},m\in[\binom{|\mathcal{S}|-1}{z}]\\}$
based on the row and column bins as shown in Fig. 6. Submatrix
$M_{\sigma_{i},m}$ has $\bar{n}_{\sigma_{i},z}^{\mathcal{S}}$ rows and
$|U_{\mathcal{H}_{m}}|$ columns. If $\sigma_{i}\in\mathcal{H}_{m}$, then the
elements of submatrix $M_{\sigma_{i},m}$ are the coefficients of the LCs for
sending the segments in
$\mathcal{V}_{\mathcal{H}_{m}}^{\mathcal{S}\backslash\mathcal{H}_{m}}$ by Node
$\sigma_{i}$ (highlight as the grey rectangles in Fig. 6). If
$\sigma_{i}\not\in\mathcal{H}_{m}$, since Node $\sigma_{i}$ did not encode
these segments, the elements of $M_{\sigma_{i},m}$ are all zero (highlight as
the white rectangles in Fig. 6). Note that the transmission strategy of FSCT
guarantees that the feasible condition is satisfied in each round $z$ of
cluster $\mathcal{S}$ as stated in Section VI-A1.

Now we need to prove that the linear system is solvable. The main idea is that
we first find a non-zero path $(m_{i_{1},1},m_{i_{2},2},\cdots,$
$m_{i_{C},C})$ where $m_{i_{c},c}\neq 0$ for all $c\in[C]$ and $m_{i_{c},c}$
is the element in row $i_{c}$ and column $c$ of $\mathbf{M}$ with all $i_{c}$
different, then select $C$ rows from $\mathbf{M}$ to form a square matrix
$(\mathbf{M})^{{}^{\prime}}$ with non-zero diagonal elements, and finally we
view the determinant of $(\mathbf{M})^{{}^{\prime}}$ as a non-zero polynomial
of $(m_{i_{1},1},m_{i_{2},2},\cdots,m_{i_{C},C})$ [48] so that
$(\mathbf{M})^{{}^{\prime}}$ is invertible with high probability by Schwartz-
Zippel Lemma [49].

Suppose the column $c\in[C]$ is in the $m$-th column bin. Then, it must
satisfy

$\displaystyle\sum_{i=1}^{m-1}{U}_{\mathcal{H}_{i}}+1\leq
c\leq\sum_{i=1}^{m}{U}_{\mathcal{H}_{i}}.$

For this $m$, we can find $\mathcal{H}_{m}$ and represent its indices as
$\mathcal{H}_{m}=\\{k_{1},\cdots,k_{z}\\}$. Now we choose the row bin

$\displaystyle\sigma_{j}=k_{t}\in\mathcal{H}_{m}$ (79a) such that
$\displaystyle\sum_{\sigma_{i}\in{\\{k_{1},\cdots,k_{t-1}\\}}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\beta_{\sigma_{i},\mathcal{H}_{m}}\\!+\\!1\leq
c\\!-\\!\sum_{i=1}^{m-1}\\!\\!{U}_{\mathcal{H}_{i}}\leq\\!\\!\\!\\!\\!\\!\\!\\!\\!\sum_{\sigma_{i}\in{\\{k_{1},\cdots,k_{t}\\}}}\\!\\!\\!\\!\\!\\!\\!\\!\beta_{\sigma_{i},\mathcal{H}_{m}}.~{}~{}$
(79b)

Note that by the first constraint in (13), there always exists such
$k_{t}\in\\{k_{1},\cdots,k_{z}\\}$. Then, we choose the $m$-th sub-bin of the
row bin $\sigma_{j}$, which contains $\beta_{\sigma_{j},\mathcal{H}_{m}}$
rows. Finally, we choose the $p$-th row of the $m$-th sub-bin, where

$\displaystyle
p=c-\sum_{i=1}^{m-1}|\mathcal{U}_{\mathcal{H}_{j}}^{\mathcal{S}\backslash\mathcal{H}_{j}}|-\\!\\!\\!\\!\\!\\!\sum_{\sigma_{i}\in{\\{k_{1},\cdots,k_{t-1}\\}}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\beta_{\sigma_{i},\mathcal{H}_{m}}$
(80)

Thus, for each element $m_{i_{c},c},c\in[C]$ in the path, we choose $i_{c}$ as
the $p$-th row of the $m$-th sub-bin of the row bin $\sigma_{j}$, i.e.,

$\displaystyle
i_{c}=\sum\limits_{\sigma_{i}\in\\{\sigma_{1},\cdots,\sigma_{j}\\}}\bar{n}_{\sigma_{i},z}^{\mathcal{S}}+\sum\limits_{i=1}^{m-1}\beta_{\sigma_{j},\mathcal{H}_{i}}+p,$
(81)

where $m,\sigma_{j},p$ are defined above.

The choice above will lead to a unique row $i_{c}$ for each column $c$, i.e.,
$i_{a}\neq i_{b}$ if $a\neq b$ for all $a,b\in[C]$. If $i_{a}=i_{b}$, $m,t,p$
in (81) for $i_{a},i_{b}$ will be the same. As
$a=b=p+\sum_{i=1}^{m-1}{U}_{\mathcal{H}_{i}}+\\!\\!\\!\\!\\!\\!\\!\\!\sum\limits_{\sigma_{i}\in{\\{k_{1},\cdots,k_{t-1}\\}}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\beta_{\sigma_{i},\mathcal{H}_{m}}$,
we can imply that $i_{a}\neq i_{b}$ for $a\neq b$.

Each element $m_{i_{c},c}$ is valid and randomly generated. From (79b) and
(80), we have $1\leq p\leq\beta_{\sigma_{j},\mathcal{H}_{m}}$. Hence,

$\displaystyle
i_{c}\geq\sum\limits_{\sigma_{i}\in\\{\sigma_{1},\cdots,\sigma_{j}\\}}\bar{n}_{\sigma_{i},z}^{\mathcal{S}}+\sum\limits_{i=1}^{m}\beta_{\sigma_{j},\mathcal{H}_{i}}+1,$
(82)

and

$\displaystyle
i_{c}\leq\sum\limits_{\sigma_{i}\in\\{\sigma_{1},\cdots,\sigma_{j}\\}}\bar{n}_{\sigma_{i},z}^{\mathcal{S}}+\sum\limits_{i=1}^{m}\beta_{\sigma_{j},\mathcal{H}_{i}}.$
(83)

Thus, $m_{i_{c},c}$ is in the submatrix $M_{\sigma_{j},m}$ with
$\sigma_{j}\in\mathcal{\mathcal{missing}}{H}_{m}$, which implies $m_{i_{c},c}$
is randomly generated for each $c$.

After we find the non-zero path
$(m_{i_{1},1},m_{i_{2},2},\cdots,m_{i_{C},C}):m_{i_{c},c}\neq 0$, we select
$C$ rows from $\mathbf{M}$ to form a square matrix
$(\mathbf{M})^{{}^{\prime}}$ with no non-zero elements along the diagonal:

  * •

The $c$-th row of $(\mathbf{M})^{{}^{\prime}}$ is the $(i_{c})$-th row of
$\mathbf{M}$.

  * •

The diagonal elements of $(\mathbf{M})^{{}^{\prime}}$:
$m_{c,c}^{{}^{\prime}}=m_{i_{c},c}$ is randomly generated.

View the determinant of $(\mathbf{M})^{{}^{\prime}}$ as a non-zero functions
of
$(m^{{}^{\prime}}_{1,1},m^{{}^{\prime}}_{2,2},\cdots,m^{{}^{\prime}}_{C,C})$.
By the Schwartz-Zippel Lemma, the probability of $(\mathbf{M})^{{}^{\prime}}$
being invertible is high as the field size is sufficiently large.

TABLE VI: List of notations in Appendix E Notation | Description
---|---
$\\{\mathcal{H}_{1},\cdots,\mathcal{H}_{\binom{|\mathcal{S}|-1}{z}}\\}$ | Subsets of $\mathcal{S}$ of size $z$ not containing $\sigma_{k}$, i.e., $\\{\mathcal{T}:\mathcal{T}\subseteq\mathcal{S},|\mathcal{T}|=z,\sigma_{k}\not\in\mathcal{T}\\}$
${U}_{\mathcal{H}_{i}}$ | Number of _segments_ generated from IVs in $\mathcal{V}_{\mathcal{H}_{i}}^{\mathcal{S}\backslash\mathcal{H}_{i}}$, i.e., ${U}_{\mathcal{H}_{i}}=(|\mathcal{S}|-1)\big{|}\mathcal{V}_{\mathcal{H}_{i}}^{\mathcal{S}\backslash\mathcal{H}_{i}}\big{|}$
$R$ | Total number of LCs of $(z,\mathcal{S})$-mapped IVs received by Node $\sigma_{k}$ , i.e., $R=\sum_{k\in\mathcal{S}\backslash\\{\sigma_{k}\\}}\bar{n}_{k,z}^{\mathcal{S}}$
$C$ | Number of unknown segments related to $(z,\mathcal{S})$-mapped IVs, i.e., $C=\sum_{i=1}^{\binom{|\mathcal{S}|-1}{z}}{U}_{\mathcal{H}_{i}}$
| $\beta_{\sigma_{i},\mathcal{H}_{l}}$
---
for $\sigma_{i}\in\mathcal{S}\backslash\sigma_{k}$,
$l\\!\in\\![\tbinom{|\mathcal{S}|-1}{z}]$
Non-negative solution of feasible condition (13)
| Row bin $\sigma_{i}$
---
for $\sigma_{i}\in\mathcal{S}\backslash\sigma_{k}$
| Row
$\sum\limits_{\sigma_{j}\in\mathcal{S}\backslash\sigma_{k},j<i}\bar{n}_{j,z}^{\mathcal{S}}+1$
to Row $\sum\limits_{\sigma_{j}\in\mathcal{S}\backslash\sigma_{k},j\leq
i}\bar{n}_{j,z}^{\mathcal{S}}$
---
| Sub-bin $l$ of row bin $\sigma_{i}$
---
for $i\in[|\mathcal{S}|]\backslash k$, $l\in[\binom{|\mathcal{S}|-1}{z}]$
| Row
$\sum\limits_{\sigma_{j}\in\mathcal{S}\backslash\sigma_{k},j<i}\\!\\!\\!\\!\bar{n}_{j,z}^{\mathcal{S}}\\!\\!+\\!\sum\limits_{n=1}^{l}\beta_{\sigma_{i},\mathcal{H}_{n}}\\!\\!+\\!1$
to Row
$\sum\limits_{\sigma_{j}\in\mathcal{S}\backslash\sigma_{k},j<i}\\!\\!\\!\\!\bar{n}_{j,z}^{\mathcal{S}}\\!\\!+\\!\sum\limits_{n=1}^{l+1}\beta_{\sigma_{i},\mathcal{H}_{n}}\\!\\!$
---
| Column bin $m$
---
for $m\in[\binom{|\mathcal{S}|-1}{z}]$
| Column $\sum\limits_{i=1}^{m-1}{U}_{\mathcal{H}_{i}}+1$ to column
$\sum\limits_{i=1}^{m}{U}_{\mathcal{H}_{i}}$
---

## References

  * [1] J. Dean and S. Ghemawat, “Mapreduce: Simplified data processing on large clusters,” in OSDI’04: Sixth Symposium on Operating System Design and Implementation, (San Francisco, CA), pp. 137–150, 2004.
  * [2] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica, “Spark: Cluster computing with working sets,” in Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, HotCloud’10, (USA), p. 10, USENIX Association, 2010.
  * [3] F. Ahmad, S. Chakradhar, A. Raghunathan, and T. Vijaykumar, “Tarazu: Optimizing mapreduce on heterogeneous clusters,” International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS, vol. 47, 04 2012.
  * [4] Z. Zhang, L. Cherkasova, and B. Loo, “Performance modeling of mapreduce jobs in heterogeneous cloud environments,” pp. 839–846, 06 2013.
  * [5] S. Li, M. A. Maddah-Ali, Q. Yu, and A. S. Avestimehr, “A fundamental tradeoff between computation and communication in distributed computing,” IEEE Transactions on Information Theory, vol. 64, no. 1, pp. 109–128, 2018.
  * [6] J. S. Ng, W. Y. B. Lim, N. C. Luong, Z. Xiong, A. Asheralieva, D. Niyato, C. Leung, and C. Miao, “A comprehensive survey on coded distributed computing: Fundamentals, challenges, and networking applications,” IEEE Communications Surveys Tutorials, vol. 23, no. 3, pp. 1800–1837, 2021.
  * [7] G. Yanfei, J. Rao, D. Cheng, and X. Zhou, “ishuffle: Improving hadoop performance with shuffle-on-write,” IEEE Transactions on Parallel and Distributed Systems, vol. 28, pp. 1–1, 01 2016.
  * [8] H. Tang, H. Hu, K. Yuan, and Y. Wu, “Communication-efficient coded distributed multi - task learning,” in 2021 IEEE Global Communications Conference (GLOBECOM), pp. 1–6, 2021.
  * [9] N. Woolsey, X. Wang, R.-R. Chen, and M. Ji, “Flcd: A flexible low complexity design of coded distributed computing,” IEEE Transactions on Cloud Computing, 2021.
  * [10] Y. H. Ezzeldin, M. Karmoose, and C. Fragouli, “Communication vs distributed computation: An alternative trade-off curve,” in 2017 IEEE Information Theory Workshop (ITW), pp. 279–283, 2017.
  * [11] E. Parrinello, E. Lampiris, and P. Elia, “Coded distributed computing with node cooperation substantially increases speedup factors,” 02 2018.
  * [12] K. Konstantinidis and A. Ramamoorthy, “Leveraging coding techniques for speeding up distributed computing,” in 2018 IEEE Global Communications Conference (GLOBECOM), pp. 1–6, 2018.
  * [13] S. Gupta and V. Lalitha, “Locality-aware hybrid coded mapreduce for server-rack architecture,” in 2017 IEEE Information Theory Workshop (ITW), pp. 459–463, 2017.
  * [14] K. Konstantinidis and A. Ramamoorthy, “Resolvable designs for speeding up distributed computing,” IEEE/ACM Transactions on Networking, vol. 28, no. 4, pp. 1657–1670, 2020.
  * [15] J. Jiang and L. Qu, “Cascaded coded distributed computing schemes based on placement delivery arrays,” IEEE Access, vol. 8, pp. 221385–221395, 2020\.
  * [16] Q. Yan, X. Tang, and Q. Chen, “Placement delivery array and its applications,” in 2018 IEEE Information Theory Workshop (ITW), pp. 1–5, 2018.
  * [17] V. Ramkumar and P. V. Kumar, “Coded mapreduce schemes based on placement delivery array,” in 2019 IEEE International Symposium on Information Theory (ISIT), pp. 3087–3091, 2019.
  * [18] A. R. Elkordy, S. Li, M. A. Maddah-Ali, and A. S. Avestimehr, “Compressed coded distributed computing,” IEEE Transactions on Communications, vol. 69, no. 5, pp. 2773–2783, 2021.
  * [19] D. Alistarh, D. Grubic, J. Z. Li, R. Tomioka, and M. Vojnovic, “Qsgd: Communication-efficient sgd via gradient quantization and encoding,” in Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, (Red Hook, NY, USA), p. 1707–1718, Curran Associates Inc., 2017.
  * [20] L. Song, C. Fragouli, and T. Zhao, “A pliable index coding approach to data shuffling,” IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1333–1353, 2020.
  * [21] M. Kiamari, C. Wang, and A. S. Avestimehr, “On heterogeneous coded distributed computing,” in GLOBECOM 2017 - 2017 IEEE Global Communications Conference, pp. 1–7, 2017.
  * [22] N. Woolsey, R.-R. Chen, and M. Ji, “Coded distributed computing with heterogeneous function assignments,” in ICC 2020 - 2020 IEEE International Conference on Communications (ICC), pp. 1–6, 2020.
  * [23] N. Woolsey, R.-R. Chen, and M. Ji, “Cascaded coded distributed computing on heterogeneous networks,” in 2019 IEEE International Symposium on Information Theory (ISIT), pp. 2644–2648, 2019.
  * [24] F. Xu, S. Shao, and M. Tao, “New results on the computation-communication tradeoff for heterogeneous coded distributed computing,” IEEE Transactions on Communications, vol. 69, no. 4, pp. 2254–2270, 2021.
  * [25] M. A. Maddah-Ali and U. Niesen, “Decentralized coded caching attains order-optimal memory-rate tradeoff,” IEEE/ACM Transactions on Networking, vol. 23, no. 4, pp. 1029–1040, 2015.
  * [26] S. Li, Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “A scalable framework for wireless distributed computing,” IEEE/ACM Transactions on Networking, vol. 25, no. 5, pp. 2643–2654, 2017.
  * [27] J. Wang, M. Kolar, and N. Srerbo, “Distributed multi-task learning,” in Artificial intelligence and statistics, pp. 751–760, PMLR, 2016.
  * [28] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2856–2867, 2014.
  * [29] U. Niesen and M. A. Maddah-Ali, “Coded caching with nonuniform demands,” IEEE Transactions on Information Theory, vol. 63, no. 2, pp. 1146–1158, 2017\.
  * [30] J. Hachem, N. Karamchandani, and S. N. Diggavi, “Coded caching for multi-level popularity and access,” IEEE Transactions on Information Theory, vol. 63, no. 5, pp. 3108–3141, 2017.
  * [31] J. Zhang, X. Lin, and X. Wang, “Coded caching under arbitrary popularity distributions,” IEEE Transactions on Information Theory, vol. 64, no. 1, pp. 349–366, 2018.
  * [32] S. Jin, Y. Cui, H. Liu, and G. Caire, “Structural properties of uncoded placement optimization for coded delivery,” arXiv preprint, 2017.  2201.06300.
  * [33] C.-H. Chang, C.-C. Wang, and B. Peleato, “On coded caching for two users with overlapping demand sets,” in ICC 2020 - 2020 IEEE International Conference on Communications (ICC), pp. 1–6, 2020.
  * [34] S. Wang and B. Peleato, “Coded caching with heterogeneous user profiles,” in 2019 IEEE International Symposium on Information Theory (ISIT), pp. 2619–2623, 2019.
  * [35] C. Zhang, S. Wang, V. Aggarwal, and B. Peleato, “Coded caching with heterogeneous user profiles,” IEEE Transactions on Information Theory, pp. 1–1, 2022.
  * [36] A. Sengupta and R. Tandon, “Improved approximation of storage-rate tradeoff for caching with multiple demands,” IEEE Transactions on Communications, vol. 65, no. 5, pp. 1940–1955, 2017.
  * [37] M. Ji, A. Tulino, J. Llorca, and G. Caire, “Caching-aided coded multicasting with multiple random requests,” in 2015 IEEE Information Theory Workshop (ITW), pp. 1–5, 2015.
  * [38] J. Zhang, X. Lin, and C.-C. Wang, “Closing the gap for coded caching with distinct file sizes,” in 2019 IEEE International Symposium on Information Theory (ISIT), pp. 687–691, 2019.
  * [39] A. M. Ibrahim, A. A. Zewail, and A. Yener, “Coded caching for heterogeneous systems: An optimization perspective,” IEEE Transactions on Communications, vol. 67, no. 8, pp. 5321–5335, 2019.
  * [40] Q. Wang, Y. Cui, S. Jin, J. Zou, C. Li, and H. Xiong, “Optimization-based decentralized coded caching for files and caches with arbitrary sizes,” IEEE Transactions on Communications, vol. 68, no. 4, pp. 2090–2105, 2020.
  * [41] C.-H. Chang and C.-C. Wang, “Coded caching with full heterogeneity: Exact capacity of the two-user/two-file case,” in 2019 IEEE International Symposium on Information Theory (ISIT), pp. 6–10, 2019.
  * [42] A. M. Daniel and W. Yu, “Optimization of heterogeneous coded caching,” IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1893–1919, 2020\.
  * [43] Q. Yu, S. Li, M. A. Maddah-Ali, and A. S. Avestimehr, “How to optimally allocate resources for coded distributed computing?,” in 2017 IEEE International Conference on Communications (ICC), pp. 1–7, 2017.
  * [44] S. Boyd and L. Vandenberghe, Convex Optimization.  Cambridge University Press, 2004.
  * [45] I. Gohberg and V. Olshevsky, “Fast algorithms with preprocessing for matrix-vector multiplication problems,” Journal of Complexity, vol. 10, 12 1994.
  * [46] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, Third Edition.  01 2009.
  * [47] C. D. Meyer, Matrix Analysis and Applied Linear Algebra.  USA: Society for Industrial and Applied Mathematics, 2000.
  * [48] M. C. Tsakiris, L. Peng, A. Conca, L. Kneip, Y. Shi, and H. Choi, “An algebraic-geometric approach for linear regression without correspondences,” IEEE Transactions on Information Theory, vol. 66, no. 8, pp. 5130–5144, 2020.
  * [49] R. Demillo and R. Lipton, “A probabilistic remark on algebraic program testing.,” Inf. Process. Lett., vol. 7, pp. 193–195, 06 1978.