# Two Piggybacking Codes with Flexible Sub-Packetization to Achieve Lower
Repair Bandwidth

Hao Shi, Zhengyi Jiang, Zhongyi Huang, Bo Bai, Hanxu Hou
This paper was presented in part at the IEEE International Symposium on
Information Theory (ISIT), 2022 [1]. H. Shi, Z. Jiang and Z. Huang are with
the Department of Mathematics Sciences, Tsinghua University (E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>zhongyih@tsinghua.edu.cn). B. Bai and H. Hou are with the Theory Lab, Central
Research Institute, 2012 Labs, Huawei Tech. Co. Ltd. (E-mail:
<EMAIL_ADDRESS>hou.hanxu@huawei.com). This work was partially supported by
the National Key R&D Program of China (No. 2020YFA0712300), the National
Natural Science Foundation of China (No. 62071121).

###### Abstract

As a special class of array codes, $(n,k,m)$ piggybacking codes are MDS codes
(i.e., any $k$ out of $n$ nodes can retrieve all data symbols) that can
achieve low repair bandwidth for single-node failure with low sub-
packetization $m$. In this paper, we propose two new piggybacking codes that
have lower repair bandwidth than the existing piggybacking codes given the
same parameters. Our first piggybacking codes can support flexible sub-
packetization $m$ with $2\leq m\leq n-k$, where $n-k>3$. We show that our
first piggybacking codes have lower repair bandwidth for any single-node
failure than the existing piggybacking codes when $n-k=8,9$, $m=6$ and $30\leq
k\leq 100$. Moreover, we propose second piggybacking codes such that the sub-
packetization is a multiple of the number of parity nodes (i.e., $(n-k)|m$),
by jointly designing the piggyback function for data node repair and
transformation function for parity node repair. We show that the proposed
second piggybacking codes have lowest repair bandwidth for any single-node
failure among all the existing piggybacking codes for the evaluated parameters
$k/n=0.75,0.8,0.9$ and $n-k\geq 4$.

###### Index Terms:

Piggybacking codes, repair bandwidth, sub-packetization, single-node failure,
transformation.

##  I introduction

Maximum distance separable (MDS) array codes are widely employed in the modern
distributed storage systems because they provide the maximum data reliability
for a given level of storage overhead. An $(n,k,m)$ MDS array code encodes
$km$ data symbols into $nm$ coded symbols that are equally stored in $n$
nodes, where each node stores $m$ symbols. We call the number of symbols
stored in each node as the sub-packetization level. The $(n,k,m)$ MDS array
codes satisfy the MDS property that is any $k$ out of $n$ nodes can retrieve
all $km$ data symbols. The codes are referred to as systematic codes if the
$km$ data symbols are included in the first $k$ nodes of obtained $n$ nodes.
Reed-Solomon (RS) codes [2] are typical MDS array codes with $m=1$. In this
paper, we consider systematic MDS array codes that contain $k$ data nodes
which store the $km$ data symbols and $r=n-k$ parity nodes which store the
$rm$ parity symbols.

In modern distributed storage systems, node failures are common and single-
node failures occur most frequently among all failures [3, 4]. It is important
to repair the failed node with the repair bandwidth defined as the total
amount of symbols downloaded from other surviving nodes as small as possible
[5]. Recently many constructions of $(n,k,m)$ MDS array codes to achieve the
minimum repair bandwidth $\frac{dm}{d-k+1}$ from $d$ surviving nodes have been
proposed in [6, 7, 8, 9, 10, 11], all the high-code-rate (i.e.,$k/n>0.5$) MDS
array codes with the minimum repair bandwidth need an exponential sub-
packetization level in parameters $n$ and $k$ [12]. It is practical important
to design high-code-rate MDS array codes with repair bandwidth as small as
possible, for a given small sub-packetization level. HashTag Erasure Codes
(HTEC) [13] is a high-code-rate that have efficient repair method for data
nodes with sub-packetization level $2\leq m\leq r^{\lceil\frac{k}{r}\rceil}$,
however no efficient repair method for parity nodes and the required field
size should be large enough to keep the MDS property.

Piggybacking codes which were first proposed by Rashmi et al. in [14] are an
important class of MDS array codes that have both low repair bandwidth for
single-node failure and low sub-packetizaiton level. The central idea of
piggybacking codes is creating $m$ instances of RS codes as base codes and
designing ingenious piggyback function (i.e., a linear combination of some
selected symbols in some instances) which will be added to other instances.
Many follow-up piggybacking codes [15, 16, 17, 18, 19, 20] have been proposed
to reduce the repair bandwidth.

In this paper, we present two constructions of piggybacking codes that have
lower repair bandwidth than the existing piggybacking codes for the same
parameters. We summarize the main contributions as follows.

  1. 1.

First, we propose first piggybacking codes for $r\geq 4$ and $m\leq r$. We
show that our first piggybacking codes have lower repair bandwidth for any
single-node failure than all the existing piggybacking codes for the evaluated
parameters $r=8,9$, $m=6$ and $k=30,31,\ldots,100$.

  2. 2.

Second, we propose second piggybacking codes by jointly designing piggyback
function for data nodes repair and transformation function for parity nodes
repair, where the sub-packetization level is a multiple of the number of
parity nodes. The proposed second piggybacking codes have the lowest repair
bandwidth for any single-node failure among all the existing piggybacking
codes for the evaluated parameters $\frac{k}{n}=0.75,0.8,0.9$ and $r\geq 4$.

Note that a parallel work [20] also designs piggybacking codes to obtain low
repair bandwidth for $m\leq r$. The differences of codes [20] and our first
piggybacking codes are as follows. We design the piggyback function by
considering the repair bandwidth reduction for both data nodes and parity
nodes. While in [20], the piggyback functions for data nodes and parity nodes
are respectively designed. Because of the above difference, our codes have a
slightly lower repair bandwidth than that of codes in [20]. Please refer to
Section VI-A for the comparison.

The main differences between our first piggybacking codes and codes in our
conference version [1] are of two-folds. First, our first piggybacking codes
can support flexible sub-packetization $m$, i.e., $2\leq m\leq r$, while codes
in [1] only suitable for $m=r$. Second, the piggyback structure of our first
piggybacking codes can be jointly designed with the proposed transformation
function, while not for codes in [1].

Our second piggybacking codes is partially inspired by the generic
transformation in [8]. The difference is that new MDS array codes with
exponential sub-packetization level and optimal repair for any single-node
failure can be obtained in [8] by recursively applying the transformation for
MDS codes, while we use the transformation idea to design the transformation
function for parity nodes in order to reduce the repair bandwidth in the
meanwhile keeping the low repair bandwidth for data nodes. Note that it is not
natural to obtain repair bandwidth reduction when we design piggyback
functions for data nodes and transformation functions for parity nodes, since
both piggyback function and transformation function are added in the same
parity symbol. We need to carefully design the two functions to achieve lower
repair bandwidth. Moreover, we can’t design transformation functions for
parity nodes of piggybacking codes with invertible transformation functions
[14, 16, 1], because the invertible transformation structure will be destroyed
if the transformation idea is employed for parity nodes.

The rest of the paper is organized as follows. Section II gives the
construction for the first piggybacking codes. Section III presents the repair
method for the first piggybacking codes. Section IV gives the construction for
the second piggybacking codes. Section V presents the repair method for the
second piggybacking codes. Section VI evaluates the repair bandwidth for the
proposed piggybacking codes and the existing related piggybacking codes.
Section VII concludes the paper.

##  II Construction of the First Piggybacking Codes

Our first piggybacking codes can be represented by an $n\times m$ array, where
the $m$ symbols in each row are stored in a node and $m\leq r=n-k$. We label
the index of the $n$ rows in the array from $1$ to $n$ and the index of the
$m$ columns from 1 to $m$. Let
$\\{\bm{a}_{i}=(a_{i,1},a_{i,2},\ldots,a_{i,k})^{T}\\}^{m}_{i=1}$ be $m$
columns of the $k\times m$ data symbols and
$(a_{i,1},a_{i,2},\ldots,a_{i,k},f_{1}(\bm{a}_{i}),\ldots,f_{r}(\bm{a}_{i}))^{T}$
be codeword $i$ of the $\left(n,k\right)$ MDS codes over $\mathbb{F}_{q}$,
where $f_{j}(\bm{a}_{i})$ is the parity symbol $j$ in codeword $i$,
$i=1,2,\ldots,m$ and $j=1,2,\ldots,r$.

We divide $n$ nodes into $L$ disjoint subsets
$\Phi_{1},\Phi_{2},\ldots,\Phi_{L}$, where $1\leq L<m$. Each of the first
$n-\lfloor\frac{n}{L}\rfloor L$ subsets has size $\lceil\frac{n}{L}\rceil$ and
each of the last $(\lfloor\frac{n}{L}\rfloor+1)L-n$ subsets has size
$\lfloor\frac{n}{L}\rfloor$, i.e., $|\Phi_{i}|=\lceil\frac{n}{L}\rceil$ for
$i=1,2,\ldots,n-\lfloor\frac{n}{L}\rfloor L$ and
$|\Phi_{i}|=\lfloor\frac{n}{L}\rfloor$ for $i=n-\lfloor\frac{n}{L}\rfloor
L+1,\ldots,L$. We can check that

$\lceil\frac{n}{L}\rceil(n-\lfloor\frac{n}{L}\rfloor
L)+\lfloor\frac{n}{L}\rfloor((\lfloor\frac{n}{L}\rfloor+1)L-n)=n,$

i.e., the $n$ nodes $\\{1,2,\ldots,n\\}$ are partitioned by the $L$ disjoint
subsets. In this paper, we consider high-code-rate and suppose that the $r$
parity nodes are in the subset $\Phi_{L}$, i.e.,

$\lfloor\frac{n}{L}\rfloor\geq r.$

For example, when $k=6$, $r=5$ and $L=2$, the $n=11$ nodes are divided into
$L=2$ subsets $\Phi_{1}=\\{1,2,3,4,5,6\\}$ and $\Phi_{2}=\\{7,8,9,10,11\\}$.

Recall that $|\Phi_{i}|\geq\lfloor\frac{n}{L}\rfloor\geq r\geq m$ and
$\Phi_{i}$ contains $|\Phi_{i}|$ nodes, where $i=1,2,\ldots,L$. For
$i=1,2,\ldots,L$, define the first $m-i$ symbols of each node in $\Phi_{i}$ as
Protect Symbols (PS) which will be added to some parity symbols as piggyback
function. In the following, we present a method of designing the $(r-1)L$
piggyback functions that are added to the $(r-1)L$ parity symbols such that
the number of PS used in computing each piggyback function as average as
possible.

The total number of PS in $\Phi_{i}$ is $p_{i}=|\Phi_{i}|(m-i)$. For
$i=1,2,\ldots,L$, denote the PS in column $j$ with $j=1,2,\ldots,m-i$ in row
$(\sum_{\alpha=1}^{i-1}|\Phi_{\alpha}|)+\ell$ with
$\ell=1,2,\ldots,|\Phi_{i}|$ as $t_{i,(\ell-1)(m-i)+j}$. For example, when
$i=1$, we have

$\displaystyle(t_{1,1},t_{1,2},\ldots,t_{1,m-1})=(a_{1,1},a_{2,1},\ldots,a_{m-1,1}),$
$\displaystyle(t_{1,m},t_{1,m+1},\ldots,t_{1,p_{1}})=(a_{1,2},a_{2,2},\ldots,a_{m-1,|\Phi_{1}|}).$

For $1\leq\alpha\leq r-1$ and $1\leq\beta<L$, let
$s_{\alpha,\beta}=1+\lfloor\frac{p_{\beta}-\alpha}{r-1}\rfloor$ and define the
piggyback function $g(\alpha,\beta)$ as,

$g(\alpha,\beta)=\sum_{\ell=1}^{s_{\alpha,\beta}}t_{\beta,(\ell-1)(r-1)+\alpha}.$
(1)

For $1\leq\alpha\leq r-1$ and $\beta=L$, we define the piggyback function
$g(\alpha,\beta)$ as,

$\displaystyle g(\alpha,\beta)$ $\displaystyle=$
$\displaystyle\sum_{\ell=1}^{s_{\alpha,\beta}}t_{\beta,(\ell-1)(r-1)+\alpha-((m-L)r\bmod(r-1))}$
$\displaystyle+$
$\displaystyle\sum_{x=1}^{r}\sum_{y=1}^{m-L}f_{x}(\bm{a}_{y})\big{(}\mathbf{I}[x+y=\alpha+1]+\mathbf{I}[x+y-(r-1)=\alpha+1]\big{)},$

where $\mathbf{I}[\cdot]$ is characteristic function (i.e., $\mathbf{I}[A]=1$
if $A$ is true, otherwise $\mathbf{I}[A]=0$) and

$s_{\alpha,L}=1+\lfloor\frac{(|\Phi_{L}|-r)(m-L)-\alpha+(m-L)r\bmod(r-1)}{r-1}\rfloor.$

Notice that we let $t_{L,\ell}=0$ if $\ell\leq 0$ in Eq. (II). We add the
piggyback function $g(\alpha,\beta)$ to the symbol in row $\alpha+k+1$ and
column $m+1-\beta$.

We denote the above designed piggybacking codes as $\mathcal{C}_{1}(n,k,m,L)$.
Fig. 1 shows the construction structure of $\mathcal{C}_{1}(n,k,m,L)$. When
$m=r$, the piggyback structure of our $\mathcal{C}_{1}(n,k,m=r,L)$ is quite
similar the conference version [1]. One difference is that invertible
transformation is used in codes [1], while not in our
$\mathcal{C}_{1}(n,k,m=r,L)$. This is why we can jointly design piggyback
function and transformation function for repair bandwidth reduction (please
refer to Section IV for details), however the jointly design is not suitable
for codes [1].

Figure 1: The construction structure of $\mathcal{C}_{1}(n,k,m,L)$.

######  Example 1.

Consider the example of $\mathcal{C}_{1}(11,6,4,2)$, which is shown in Fig. 2.
We divide the $n=11$ nodes into $L=2$ disjoint subsets,
$\Phi_{1}=\\{1,2,3,4,5,6\\}$ and $\Phi_{2}=\\{7,8,9,10,11\\}$. By Eq. (1) and
Eq. (II), we have

$\displaystyle g(1,1)$ $\displaystyle=$ $\displaystyle
a_{1,1}+a_{2,2}+a_{3,3}+a_{1,5}+a_{2,6},$ $\displaystyle g(2,1)$
$\displaystyle=$ $\displaystyle a_{2,1}+a_{3,2}+a_{1,4}+a_{2,5}+a_{3,6},$
$\displaystyle g(3,1)$ $\displaystyle=$ $\displaystyle
a_{3,1}+a_{1,3}+a_{2,4}+a_{3,5},$ $\displaystyle g(4,1)$ $\displaystyle=$
$\displaystyle a_{1,2}+a_{2,3}+a_{3,4}+a_{1,6},$ $\displaystyle g(1,2)$
$\displaystyle=$ $\displaystyle
f_{1}(\bm{a}_{1})+f_{4}(\bm{a}_{2})+f_{5}(\bm{a}_{1}),$ $\displaystyle g(2,2)$
$\displaystyle=$ $\displaystyle
f_{1}(\bm{a}_{2})+f_{2}(\bm{a}_{1})+f_{5}(\bm{a}_{2}),$ $\displaystyle g(3,2)$
$\displaystyle=$ $\displaystyle f_{2}(\bm{a}_{2})+f_{3}(\bm{a}_{1}),$
$\displaystyle g(4,2)$ $\displaystyle=$ $\displaystyle
f_{3}(\bm{a}_{2})+f_{4}(\bm{a}_{1}).$

Figure 2: The example of $\mathcal{C}_{1}(n=11,k=6,m=4,L=2)$.

According to the above definition of the piggyback function, we can easily
know that any two data symbols in the same row are not used to compute one
piggyback function because of $m\leq r$. In the next lemma, we show that this
is also true for parity nodes.

######  Lemma 2.

When $r\geq 4$, we have,

(i)

Any two parity symbols in the same row are not used to compute the same
piggyback function.

(ii)

Any parity symbol in a row used in computing a piggyback function is not in
the same row of the piggyback function.

###### Proof.

Since $|\Phi_{i}|\geq r\geq m$, the piggyback functions which are computed
from parity symbols are $g(\alpha,L)$ with $1\leq\alpha\leq r-1$.

Consider the first claim. Suppose that two parity symbols
$f_{x}(\bm{a}_{y_{1}})$ and $f_{x}(\bm{a}_{y_{2}})$ that are in the same row
which are used to compute the piggyback function $g(\alpha,L)$, where
$x\in\\{1,2,\ldots,r\\}$ and $1\leq y_{1}<y_{2}\leq m-L$, then

$\displaystyle x+y_{1}=\alpha+1,$ $\displaystyle x+y_{2}-r+1=\alpha+1.$

We have that $y_{2}-y_{1}=r-1$, which contradicts with $r\geq m$ and $L\geq
1$.

Consider the second claim. Suppose that the parity symbol $f_{x}(\bm{a}_{y})$
is used to compute the piggyback function $g(\alpha,\beta)$ in the same row,
we have $x=\alpha+1$, where $x\in\\{1,2,\ldots,r\\}$,
$y\in\\{1,2,\ldots,m-L\\}$, $x+y=\alpha+1$ or $x+y-(r-1)=\alpha+1$. We can
obtain that $y=0$ or $y=r-1$, which contradicts with $1\leq y\leq m-L$, $r\geq
m$ and $L\geq 1$. ∎

By Lemma 2, we can repair any single-node failure by employing the piggyback
functions to reduce repair bandwidth and we present the repair method in the
next section.

##  III Repair Method of Codes $\mathcal{C}_{1}(n,k,m,L)$

In this section, we present the repair method for any single-node failure of
the proposed code $\mathcal{C}_{1}(n,k,m,L)$ and show the repair bandwidth.

###  III-A Repair Method for Data Nodes

Suppose that node $t\in\Phi_{i}$ fails, where $t\in\\{1,2,\ldots,k\\}$ and
$i\in\\{1,2,\ldots,L\\}$, the repair method is as follows.

  1. 1.

We download $ki$ symbols in the last $i$ columns of the first $k+1$ rows
except row $t$ to recover the symbols $a_{m-i+1,t},\ldots,a_{m,t}$ and
$f_{x}(\bm{a}_{i})$ for $x=2,3,\ldots,r$.

  2. 2.

We download the parity symbols of which the corresponding piggyback functions
containing symbols of node $t$ and symbols contained by these piggyback
functions except symbols of node $t$, together with $f_{x}(\bm{a}_{i})$ for
$x=2,3,\ldots,r$, we can recover $a_{1,t},a_{2,t},\ldots,a_{m-i,t}.$

Consider the code $\mathcal{C}_{1}(11,6,4,2)$ in Example 1, we have $L=2$
disjoint subsets $\Phi_{1}=\\{1,2,3,4,5,6\\}$ and
$\Phi_{2}=\\{7,8,9,10,11\\}$.

Suppose that node $1$ fails, we can recover the five symbols

$a_{4,1},f_{2}(\bm{a}_{4}),f_{3}(\bm{a}_{4}),f_{4}(\bm{a}_{4}),f_{5}(\bm{a}_{4})$

by downloading the following six symbols

$a_{4,2},a_{4,3},a_{4,4},a_{4,5},a_{4,6},f_{1}(\bm{a}_{4}).$

Note that the erased three symbols $a_{1,1}$, $a_{2,1}$ and $a_{3,1}$ are used
in computing the three piggyback functions $g(1,1)$, $g(2,1)$ and $g(3,1)$,
respectively. We download the three parity symbols

$f_{2}(\bm{a}_{4})+g(1,1),f_{3}(\bm{a}_{4})+g(2,1),f_{4}(\bm{a}_{4})+g(3,1)$

and the following symbols

$a_{2,2},a_{3,3},a_{1,5},a_{2,6},a_{3,2},a_{1,2},a_{2,5},a_{3,6},a_{1,3},a_{2,4},a_{3,5}$

that are used in computing three piggyback functions $g(1,1)$, $g(2,1)$ and
$g(3,1)$, together with
$f_{2}(\bm{a}_{4}),f_{3}(\bm{a}_{4}),f_{4}(\bm{a}_{4})$, to recover the three
symbols $a_{1,1}$, $a_{2,1}$ and $a_{3,1}$. The repair bandwidth of node $1$
is $20$ symbols.

We can repair each of the other data nodes similarly and we can calculate that
the repair bandwidth of each node in $\\{2,5,6\\}$ is 20 symbols, the repair
bandwidth of each node in $\\{3,4\\}$ is 19 symbols.

###  III-B Repair Method for Parity Nodes

Suppose that node $t$ fails, where $t\in\\{k+1,k+2,\ldots,k+r\\}$ and
$t\in\Phi_{L}$, the repair method is given as follows.

  1. 1.

We download $kL$ symbols in the last $L$ columns of the first $k$ rows to
recover $f_{t-k}(\bm{a}_{j})$ with $j=m-L+1,m-L+2,\ldots,m$ and
$f_{x}(\bm{a}_{m-L+1})$ with $x=1,2,\ldots,t-k-1,t-k+1,\ldots,r$.

  2. 2.

Note that the $m-L$ erased symbols
$f_{t-k}(\bm{a}_{1}),f_{t-k}(\bm{a}_{2}),\ldots,f_{t-k}(\bm{a}_{m-L})$ are
used in computing the $m-L$ piggyback functions $g((t-k-1+s)\bmod(r-1),L)$
with $s=1,2,\ldots,m-L$. We can recover $m-L$ symbols
$f_{t-k}(\bm{a}_{1}),f_{t-k}(\bm{a}_{2}),\ldots,f_{t-k}(\bm{a}_{m-L})$ by
downloading the $m-L$ symbols
$f_{(t-k+s)\bmod(r-1)}(\bm{a}_{m-L+1})+g((t-k-1+s)\bmod(r-1),L)$ with
$s=1,2,\ldots,m-L$ and the symbols used in computing the piggyback functions
$g((t-k-1+s)\bmod(r-1),L)$ with $s=1,2,\ldots,m-L$.

  3. 3.

We can recover the last $L$ symbols in node $t$ by downloading the symbols
used in computing the $L$ piggyback functions added in node $t$, together with
the computed symbols in the first step.

Continue the code in Example 1. Suppose that parity $1$ fails. According to
the above repair method, in the first step, we can compute the four symbols
$f_{1}(\bm{a}_{3}),f_{1}(\bm{a}_{4}),f_{2}(\bm{a}_{3}),f_{3}(\bm{a}_{3})$ by
downloading the following 12 symbols

$\displaystyle a_{3,1},a_{3,2},a_{3,3},a_{3,4},a_{3,5},a_{3,6},$
$\displaystyle a_{4,1},a_{4,2},a_{4,3},a_{4,4},a_{4,5},a_{4,6}.$

By the second step, we can recover the erased two symbols
$f_{1}(\bm{a}_{1}),f_{1}(\bm{a}_{2})$ by downloading

$f_{4}(\bm{a}_{2}),f_{5}(\bm{a}_{1}),f_{2}(\bm{a}_{1}),f_{5}(\bm{a}_{1}),f_{2}(\bm{a}_{3})+g(1,2),f_{3}(\bm{a}_{3})+g(2,2),$

since

$\displaystyle g(1,2)=$ $\displaystyle
f_{1}(\bm{a}_{1})+f_{4}(\bm{a}_{2})+f_{5}(\bm{a}_{1}),$ $\displaystyle
g(2,2)=$ $\displaystyle
f_{1}(\bm{a}_{2})+f_{2}(\bm{a}_{1})+f_{5}(\bm{a}_{2}).$

There is no piggyback function added in the parity 1 and we have recovered the
last two symbols in parity 1, the third step is not necessary in repairing
parity 1.

Suppose that parity $2$ fails. By the first step, we can compute the four
symbols $f_{2}(\bm{a}_{3}),f_{2}(\bm{a}_{4})$,
$f_{3}(\bm{a}_{3}),f_{4}(\bm{a}_{3})$ by downloading the following 12 symbols

$\displaystyle a_{3,1},a_{3,2},a_{3,3},a_{3,4},a_{3,5},a_{3,6},$
$\displaystyle a_{4,1},a_{4,2},a_{4,3},a_{4,4},a_{4,5},a_{4,6}.$

By the second step, we recover two symbols
$f_{2}(\bm{a}_{1}),f_{2}(\bm{a}_{2})$ by downloading the following symbols

$f_{1}(\bm{a}_{2}),f_{5}(\bm{a}_{2}),f_{3}(\bm{a}_{1}),f_{3}(\bm{a}_{3})+g(2,2),f_{4}(\bm{a}_{3})+g(3,2).$

By the third step, we can recover the two symbols
$f_{2}(\bm{a}_{3})+g(1,2),f_{2}(\bm{a}_{4})+g(1,1)$ by downloading the symbols

$a_{1,1},a_{2,2},a_{1,5},a_{2,6},f_{2}(\bm{a}_{2}),f_{3}(\bm{a}_{1}),$

together with $a_{3,3}$ and $f_{2}(\bm{a}_{3}),f_{2}(\bm{a}_{4})$.

We can calculate that the repair bandwidth of parity 2 is $23$ symbols.
Similarly, we can show that the repair bandwidth of each node in parity
$\\{3,5\\}$ is $24$ symbols and the repair bandwidth of parity $4$ is $23$
symbols.

###  III-C Average Repair Bandwidth Ratio of $\mathcal{C}_{1}(n,k,m,L)$

In the following, we analyse the repair bandwidth of our codes
$\mathcal{C}_{1}(n,k,m,L)$. We define the average repair bandwidth ratio of
all nodes as the ratio of the average repair bandwidth of $n$ nodes to the
number of data symbols $kr$.

######  Lemma 3.

If $L$ is a factor of $n$, the lower bound $\gamma_{min}^{all}$ and the upper
bound $\gamma_{max}^{all}$ of the average repair bandwidth ratio of all nodes
of $\mathcal{C}_{1}(n,k,m,L)$ is

$\displaystyle\gamma_{min}^{all}=\frac{L+1}{2m}+\frac{(k+r)(m^{2}-m(L+1)+\frac{(L+1)(2L+1)}{6})}{Lmk(r-1)}+\frac{m-L}{km},$
$\displaystyle\gamma_{max}^{all}=\gamma_{min}^{all}+\frac{L(r-1)^{2}}{4(k+r)mk}.$

###### Proof.

Denote the number of symbols used in computing the piggyback function
$g(\alpha,r-m+\beta)$ as $n_{\alpha,\beta}$, where $\alpha=1,2,\ldots,r-1$ and
$\beta=1,2,\ldots,L$. According to the definition of the piggyback function in
Eq. (1) and Eq. (II), we can know that
$(n_{\alpha_{1},\beta}-n_{\alpha_{2},\beta})^{2}\in\\{0,1\\}$ for
$\alpha_{1}\neq\alpha_{2}\in\\{1,2,\ldots,r-1\\}$ and $\beta=1,2,\ldots,L$.

According to the repair methods in Section III-A and III-B, we need to
download $\sum_{\beta=1}^{L}|\Phi_{\beta}|k\beta$ symbols in repairing each of
the $n$ nodes in first step, download
$\sum_{\beta=1}^{L}\sum_{\alpha=1}^{r-1}n_{\alpha,\beta}^{2}$ symbols in
repairing each of the $n$ nodes in the second step and download $(m-L)(k+r)$
symbols in repairing each of the $r$ parity nodes in the third step in total.
Therefore, the average repair bandwidth ratio for all nodes $\gamma^{all}$ is

$\gamma^{all}=\frac{\sum_{\beta=1}^{L}(|\Phi_{\alpha}|k\beta+\sum_{\alpha=1}^{r-1}n_{\alpha,\beta}^{2})+(m-L)(k+r)}{(k+r)mk}.$

Since the equation

$(\sum_{\alpha=1}^{r-1}n_{\alpha,\beta})^{2}+\sum_{\alpha_{1}\neq\alpha_{2}\in\\{1,2,\ldots,r-1\\}}(n_{\alpha_{1},\beta}-n_{\alpha_{2},\beta})^{2}=(r-1)\sum_{\alpha=1}^{r-1}n^{2}_{\alpha,\beta}$

holds, we can obtain that

$\sum_{\alpha=1}^{r-1}n_{\alpha,\beta}^{2}=\frac{(\sum_{\alpha=1}^{r-1}n_{\alpha,\beta})^{2}+\sum_{\alpha_{1}\neq\alpha_{2}\in\\{1,2,\ldots,r-1\\}}(n_{\alpha_{1},\beta}-n_{\alpha_{2},\beta})^{2}}{r-1}$

for $\beta=1,2,\ldots,L$.

Let
$v_{\beta}=|\Phi_{\beta}|(m-\beta)-\lfloor\frac{|\Phi_{\beta}|(m-\beta)}{r-1}\rfloor(r-1)$,
where $\beta=1,2,\ldots,L$. Because of
$\sum_{\alpha=1}^{r-1}n_{\alpha,\beta}=|\Phi_{\beta}|(m-\beta)$ and
$\sum_{\alpha_{1},\alpha_{2}=1,\alpha_{1}\neq\alpha_{2}}^{r-1}(n_{\alpha_{1},\beta}-n_{\alpha_{2},\beta})^{2}=v_{\beta}(r-1-v_{\beta})$,
we can calculate that

$\sum_{\alpha=1}^{r-1}n_{\alpha,\beta}^{2}=\frac{(|\Phi_{\beta}|(m-\beta))^{2}+v_{\beta}(r-1-v_{\beta})}{r-1}.$

Therefore, we can get $0\leq v_{\beta}(r-1-v_{\beta})\leq(\frac{r-1}{2})^{2}$
and further obtain the lower bound and upper bound in the lemma. ∎

By Lemma 3, we can know
$|\gamma_{min}^{all}-\gamma^{all}|\leq|\gamma_{max}^{all}-\gamma_{min}^{all}|=\frac{L(r-1)^{2}}{4(k+r)mk}$.
When $k>>r$, we have $\frac{L(r-1)^{2}}{4(k+r)mk}\rightarrow 0$. Therefore, we
have $\gamma^{all}=\gamma_{min}^{all}$ when $k>>r$.

######  Lemma 4.

When $L$ is a factor of $n$ and $k>>r$, the minimum value of the average
repair bandwidth ratio $\gamma^{all}$ of $\mathcal{C}_{1}(n,k,m,L)$ is
achieved when $L=\sqrt{\frac{6m^{2}-6m+1}{3r-1}}$.

###### Proof.

When $k>>r$, we have $\gamma^{all}=\gamma^{all}_{min}$ . Then we can get

$\gamma^{all}=\frac{L+1}{2m}+\frac{m^{2}L-mL^{2}-mL+\frac{1}{3}L^{3}+\frac{1}{2}L^{2}+\frac{L}{6}}{L^{2}m(r-1)}.$

We can calculate that

$\frac{\partial\gamma^{all}}{\partial
L}=\frac{1}{2m}+\frac{\frac{1}{3}-\frac{m^{2}-m+\frac{1}{6}}{L^{2}}}{m(r-1)}=0,$

and further obtain

$L=\sqrt{\frac{6m^{2}-6m+1}{3r-1}}.$

If $L>\sqrt{\frac{6m^{2}-6m+1}{3r-1}}$, then
$\frac{\partial\gamma^{all}}{\partial L}>0$; if
$L<\sqrt{\frac{6m^{2}-6m+1}{3r-1}}$, then
$\frac{\partial\gamma^{all}}{\partial L}<0$; if
$L=\sqrt{\frac{6m^{2}-6m+1}{3r-1}}$, then
$\frac{\partial\gamma^{all}}{\partial L}=0$. Therefore, when
$L=\sqrt{\frac{6m^{2}-6m+1}{3r-1}}$, $\gamma^{all}$ achieves the minimum
value. ∎

Since $L$ is a positive integer, we take
$L=\lceil\sqrt{\frac{6m^{2}-6m+1}{3r-1}}\rceil$ or
$L=\lfloor\sqrt{\frac{6m^{2}-6m+1}{3r-1}}\rfloor$ to achieve the minimum
repair bandwidth.

##  IV The Second Piggybacking Codes

In this section, we present construction of the second piggybacking codes that
have lower repair bandwidth than all the existing piggybacking codes.

The second piggybacking codes is an $n\times m$ array, where $m=sr=s(n-k)$ and
$2\leq s\leq r$. We label the index of the $n$ rows from $1$ to $n$ and the
index of the $m$ columns from 1 to $m$. The first $k$ nodes are data nodes
that store data symbols and the last $r$ nodes are parity nodes that store
parity symbols. We divide the $k$ data nodes into $L$ disjoint subsets
$\Phi_{1},\Phi_{2},\ldots,\Phi_{L}$, where $1\leq L<s$. Each of the first
$k-\lfloor\frac{k}{L}\rfloor L$ subsets has size $\lceil\frac{k}{L}\rceil$ and
each of the last $(\lfloor\frac{k}{L}\rfloor+1)L-k$ subsets has size
$\lfloor\frac{k}{L}\rfloor$, i.e., $|\Phi_{i}|=\lceil\frac{k}{L}\rceil$ for
$i=1,2,\ldots,k-\lfloor\frac{k}{L}\rfloor L$ and
$|\Phi_{i}|=\lfloor\frac{k}{L}\rfloor$ for $i=k-\lfloor\frac{k}{L}\rfloor
L+1,\ldots,L$. We divide the $sr$ columns into $s$ disjoint subsets
$W_{\ell}=\\{(\ell-1)r+1,(\ell-1)r+2,\ldots,\ell r\\}$, where
$\ell=1,2,\ldots,s$. The construction of the second piggybacking codes is as
follows.

  1. 1.

We create $m=sr$ instances of $\left(n,k\right)$ MDS code. Let
$(a^{(\ell)}_{i,1},a^{(\ell)}_{i,2},\ldots,a^{(\ell)}_{i,k},f_{1}(\bm{a}^{(\ell)}_{i}),\ldots,f_{r}(\bm{a}^{(\ell)}_{i}))^{T}$
be an instance of $\left(n,k\right)$ MDS code over $\mathbb{F}_{q}$ which is
in column $(\ell-1)r+i$ of the $n\times sr$ array, where
$\bm{a}^{(\ell)}_{i}=(a^{(\ell)}_{i,1},a^{(\ell)}_{i,2},\ldots,a^{(\ell)}_{i,k})^{T}$
are data symbols, $\ell=1,2,\ldots,s$ and $i=1,2,\ldots,r$.

  2. 2.

We take $i-1$ cyclic-shift for each column of the $r$ parity symbols
$(f_{1}(\bm{a}^{(\ell)}_{i}),f_{2}(\bm{a}^{(\ell)}_{i}),\ldots,f_{r}(\bm{a}^{(\ell)}_{i}))^{T}$
to obtain

$(f_{((1-i)\bmod r)+1}(\bm{a}^{(\ell)}_{i}),f_{((2-i)\bmod
r)+1}(\bm{a}^{(\ell)}_{i}),\ldots,f_{r}(\bm{a}^{(\ell)}_{i}),f_{1}(\bm{a}^{(\ell)}_{i}),f_{2}(\bm{a}^{(\ell)}_{i}),\ldots,f_{r+1-i}(\bm{a}^{(\ell)}_{i}))^{T},$

where $\ell=1,2,\ldots,s$ and $i=1,2,\ldots,r$.

  3. 3.

For $i=1,2,\ldots,L$, we define the first $(s-i)r$ symbols of the $|\Phi_{i}|$
nodes in $\Phi_{i}$ as Protect Symbols (PS). We can calculate that the total
number of PS in $\Phi_{i}$ is $p_{i}=|\Phi_{i}|(s-i)r$ and the total number of
PS in all $k$ data nodes are
$\sum_{i=1}^{L}p_{i}=\sum_{i=1}^{L}|\Phi_{i}|(s-i)r$. For $i=1,2,\ldots,L$,
denote the PS in column $j$ with $j=1,2,\ldots,(s-i)r$ in row
$(\sum_{\alpha=1}^{i-1}|\Phi_{\alpha}|)+\ell$ with
$\ell=1,2,\ldots,|\Phi_{i}|$ as $t_{i,(\ell-1)(s-i)r+j}$. For example, when
$i=1$, we have

$\displaystyle(t_{1,1},t_{1,2},\ldots,t_{1,(s-1)r})=(a^{(1)}_{1,1},a^{(1)}_{2,1},\ldots,a^{(s-1)}_{r,1}),$
$\displaystyle(t_{1,(s-1)r+1},\ldots,t_{1,p_{1}})=(a^{(1)}_{1,2},\ldots,a^{(s-1)}_{r,|\Phi_{1}|}).$

We define $(r-1)rL$ piggyback functions which will be added to the $(r-1)rL$
parity symbols in the last $L$ subsets $W_{i}$ with $i=s-L+1,s-L+2,\ldots,s$
such that the number of PS used in computing each piggyback function as
average as possible. For $i=1,2,\ldots,L$ and $j=1,2,\ldots,r(r-1)$, we define
the piggyback function $g(j,s-i+1)$ as

$g(j,s-i+1)=\sum_{\ell=1}^{s_{i,j}}t_{i,(\ell-1)(r-1)r+j},$ (3)

where $s_{i,j}=1+\lfloor\frac{p_{i}-j}{r(r-1)}\rfloor$ and the $r(r-1)L$
piggyback functions are added to the $r(r-1)L$ parity symbols in the last $L$
subsets $W_{\ell}$ with $\ell=s-L+1,s-L+2,\ldots,s$, which is shown in Fig. 3.
For notational convenience, denote the symbol in column $(\ell-1)r+i$ and row
$j$ of the obtained $n\times sr$ array as
$f^{\prime}_{x-k}(\bm{a}^{(\ell)}_{i})$, where $j=k+1,k+2,\ldots,k+r$,
$\ell=1,2,\ldots,s$ and $i=1,2,\ldots,r$.

Figure 3: Piggyback functions added to the symbols in $W_{\ell}$,
$\ell=s-L+1,s-L+2,\ldots,s$.

  4. 4.

We replace the symbol $f^{\prime}_{x}(\bm{a}^{(\ell)}_{i})$ in column
$(\ell-1)r+i$ and row $x+k$ by the transformation function
$f^{\prime\prime}_{x}(\bm{a}^{(\ell)}_{i})$ as follows,

$f^{\prime\prime}_{x}(\bm{a}^{(\ell)}_{i})=\begin{cases}f^{\prime}_{x}(\bm{a}^{(\ell)}_{i})+f^{\prime}_{i}(\bm{a}^{(\ell)}_{x})&\text{if}\quad
x<i,\\\ \theta_{x,i}\cdot
f^{\prime}_{i}(\bm{a}^{(\ell)}_{x})+f^{\prime}_{x}(\bm{a}^{(\ell)}_{i})&\text{if}\quad
x>i,\\\ f^{\prime}_{x}(\bm{a}^{(\ell)}_{i})&\text{if}\quad x=i,\end{cases}$
(4)

where $\theta_{x,i}\in\mathbb{F}_{q}\setminus\\{0,1\\}$ such that
$\theta_{x,i}-1$ is invertible, $x=1,2,\ldots,r$, $\ell=1,2,\ldots,s$ and
$j=1,2,\ldots,r$.

We denote the above construction of our second piggybacking codes as
$\mathcal{C}_{2}(n,k,m,L)$. In the construction of $\mathcal{C}_{2}(n,k,m,L)$,
we design the piggyback functions in step three to repair the single-node
failure of data nodes and employ the transformation functions designed in step
four to repair the single-node failure of parity nodes. The piggyback
structure of $\mathcal{C}_{2}(n,k,m,L)$ is similar to that of our first
piggybacking codes $\mathcal{C}_{1}(n,k,m,L)$. The difference is that the
piggyback functions of $\mathcal{C}_{2}(n,k,m,L)$ are designed for data node
repair, while the piggyback functions of $\mathcal{C}_{1}(n,k,m,L)$ are
designed for the repair of both data node and parity node.

Given that $x>i$, we have
$f^{\prime\prime}_{x}(\bm{a}^{(\ell)}_{i})=\theta_{x,i}\cdot
f^{\prime}_{x}(\bm{a}^{(\ell)}_{i})+f^{\prime}_{i}(\bm{a}^{(\ell)}_{x})$ and
$f^{\prime\prime}_{i}(\bm{a}^{(\ell)}_{x})=f^{\prime}_{i}(\bm{a}^{(\ell)}_{x})+f^{\prime}_{x}(\bm{a}^{(\ell)}_{i})$.
It is easy to check that we can compute $f^{\prime}_{i}(\bm{a}^{(\ell)}_{x})$
and $f^{\prime}_{x}(\bm{a}^{(\ell)}_{i})$ from
$f^{\prime\prime}_{x}(\bm{a}^{(\ell)}_{i})$ and
$f^{\prime\prime}_{i}(\bm{a}^{(\ell)}_{x})$. We can also compute
$f^{\prime\prime}_{i}(\bm{a}^{(\ell)}_{x})$ from any two out of the three
symbols

$f^{\prime}_{i}(\bm{a}^{(\ell)}_{x}),f^{\prime}_{x}(\bm{a}^{(\ell)}_{i}),f^{\prime\prime}_{x}(\bm{a}^{(\ell)}_{i}).$

######  Example 5.

Consider the example of $(n,k,m,L)=(12,8,16,2)$, the $k=8$ data nodes are
divided into two subsets $\Phi_{1}=\\{1,2,3,4\\}$ and
$\Phi_{2}=\\{5,6,7,8\\}$, and the $m=16$ columns are divided into four subsets
$W_{\ell}=\\{4(\ell-1)+1,4(\ell-1)+2,4(\ell-1)+3,4(\ell-1)+4\\}$ with
$\ell=1,2,3,4$. According to Eq. (3), the piggyback functions are defined as
follows.

$\displaystyle g(i,1)$ $\displaystyle=$ $\displaystyle
a^{(1)}_{i,1}+a^{(1)}_{i,2}+a^{(1)}_{i,3}+a^{(1)}_{i,4}\text{ for }i=1,2,3,4,$
$\displaystyle g(4+i,1)$ $\displaystyle=$ $\displaystyle
a^{(2)}_{i,1}+a^{(2)}_{i,2}+a^{(2)}_{i,3}+a^{(2)}_{i,4}\text{ for }i=1,2,3,4,$
$\displaystyle g(8+i,1)$ $\displaystyle=$ $\displaystyle
a^{(3)}_{i,1}+a^{(3)}_{i,2}+a^{(3)}_{i,3}+a^{(3)}_{i,4}\text{ for }i=1,2,3,4,$
$\displaystyle g(i,2)$ $\displaystyle=$ $\displaystyle
a^{(1)}_{i,5}+a^{(2)}_{i,6}+a^{(1)}_{i,8}\text{ for }i=1,2,3,4,$
$\displaystyle g(4+i,2)$ $\displaystyle=$ $\displaystyle
a^{(2)}_{i,5}+a^{(1)}_{i,7}+a^{(2)}_{i,8}\text{ for }i=1,2,3,4,$
$\displaystyle g(8+i,2)$ $\displaystyle=$ $\displaystyle
a^{(1)}_{i,6}+a^{(2)}_{i,7}\text{ for }i=1,2,3,4.$

The transformation functions are given in Eq. (4) with $x=1,2,3,4$,
$i=1,2,3,4$ and $\ell=1,2,3,4$, where the symbol
$f^{\prime}_{x}(\bm{a}_{i}^{(\ell)})$ is as follows,

$\displaystyle\left(f^{\prime}_{1}(\bm{a}_{1}^{(\ell)}),f^{\prime}_{2}(\bm{a}_{2}^{(\ell)})\right)=$
$\displaystyle\left(f_{1}(\bm{a}_{1}^{(\ell)}),f_{1}(\bm{a}_{2}^{(\ell)})\right),$
$\displaystyle\left(f^{\prime}_{3}(\bm{a}_{3}^{(\ell)}),f^{\prime}_{4}(\bm{a}_{4}^{(\ell)})\right)=$
$\displaystyle\left(f_{1}(\bm{a}_{3}^{(\ell)}),f_{1}(\bm{a}_{4}^{(\ell)})\right),$
$\displaystyle\left(f^{\prime}_{1}(\bm{a}_{2}^{(\ell)}),f^{\prime}_{1}(\bm{a}_{3}^{(\ell)})\right)=$
$\displaystyle\left(f_{4}(\bm{a}_{2}^{(\ell)})+g(1,5-\ell),f_{4}(\bm{a}_{3}^{(\ell)})+g(2,5-\ell)\right),$
$\displaystyle\left(f^{\prime}_{1}(\bm{a}_{4}^{(\ell)}),f^{\prime}_{2}(\bm{a}_{1}^{(\ell)})\right)=$
$\displaystyle\left(f_{4}(\bm{a}_{2}^{(\ell)})+g(3,5-\ell),f_{2}(\bm{a}_{1}^{(\ell)})+g(4,5-\ell)\right),$
$\displaystyle\left(f^{\prime}_{2}(\bm{a}_{3}^{(\ell)}),f^{\prime}_{2}(\bm{a}_{4}^{(\ell)})\right)=$
$\displaystyle\left(f_{4}(\bm{a}_{3}^{(\ell)})+g(5,5-\ell),f_{3}(\bm{a}_{4}^{(\ell)})+g(6,5-\ell)\right),$
$\displaystyle\left(f^{\prime}_{3}(\bm{a}_{1}^{(\ell)}),f^{\prime}_{3}(\bm{a}_{2}^{(\ell)})\right)=$
$\displaystyle\left(f_{3}(\bm{a}_{1}^{(\ell)})+g(7,5-\ell),f_{2}(\bm{a}_{2}^{(\ell)})+g(8,5-\ell)\right),$
$\displaystyle\left(f^{\prime}_{3}(\bm{a}_{4}^{(\ell)}),f^{\prime}_{4}(\bm{a}_{1}^{(\ell)})\right)=$
$\displaystyle\left(f_{4}(\bm{a}_{4}^{(\ell)})+g(9,5-\ell),f_{4}(\bm{a}_{1}^{(\ell)})+g(10,5-\ell)\right),$
$\displaystyle\left(f^{\prime}_{4}(\bm{a}_{2}^{(\ell)}),f^{\prime}_{4}(\bm{a}_{3}^{(\ell)})\right)=$
$\displaystyle\left(f_{3}(\bm{a}_{2}^{(\ell)})+g(11,5-\ell),f_{2}(\bm{a}_{3}^{(\ell)})+g(12,5-\ell)\right),$

where $\ell=1,2,3,4$ and $g(\cdot,x)=0$ for $x\geq 3$.

The code $\mathcal{C}_{2}(12,8,16,2)$ is shown in Fig. 4.

Figure 4: Code $\mathcal{C}_{2}(12,8,16,2)$.

##  V Repair Method of $\mathcal{C}_{2}(n,k,m,L)$

In this section, we present repair method for any single-node erasure of
$\mathcal{C}_{2}(n,k,m,L)$.

###  V-A Repair Method for Data Node

The repair method for data node of $\mathcal{C}_{2}(n,k,m,L)$ is quite similar
to that of $\mathcal{C}_{1}(n,k,m,L)$, because the two codes have the same
structure of piggyback function. The difference is that the piggyback function
of $\mathcal{C}_{1}(n,k,m,L)$ is computed from both data symbols and parity
symbols, while the piggyback function of $\mathcal{C}_{2}(n,k,m,L)$ is
computed from only data symbols. Suppose that data node $t\in\Phi_{u}$ fails,
where $t\in\\{1,2,\ldots,k\\}$ and $u\in\\{1,2,\ldots,L\\}$, the repair method
is as follows.

  1. 1.

Recall that there is one parity symbol in each column which is not added by
piggyback function. We can recover the last $ur$ erased symbols in node $t$ by
downloading $(k-1)ur$ data symbols in the last $ur$ columns in the first $k$
rows except row $t$ and downloading the $ur$ parity symbols in the last $ur$
columns of without attaching piggyback function.

  2. 2.

We download the parity symbols of which the corresponding piggyback functions
are computed from the symbols in node $t$, together with
$f_{x}(\bm{a}^{(\ell)}_{i})$ with $x=1,2,\ldots,r$, $i=1,2,\ldots,r$ and
$\ell=s-u+1,\ldots,s$, to recover the first $(s-u)r$ symbols in node $t$.

Continue the code in Example 5. Suppose that node $t=1$ fails, we have $u=1$
and we can recover the last four symbols $a^{(4)}_{i,1}$ with $i=1,2,3,4$ in
node $1$ and the 16 parity symbols $f_{x}(\bm{a}^{(4)}_{i})$ with $x=1,2,3,4$
and $i=1,2,3,4$, by downloading the 28 symbols $a^{(4)}_{i,j}$ with
$j=2,3,\ldots,8$ and $i=1,2,3,4$, and the four parity symbols

$f_{1}({\bm{a}}^{(4)}_{1}),f_{1}({\bm{a}}^{(4)}_{2}),f_{1}({\bm{a}}^{(4)}_{3}),f_{1}({\bm{a}}^{(4)}_{4}).$

Then we download the following 12 parity symbols

$\displaystyle
f^{\prime}_{1}(\bm{a}^{(4)}_{2})+f^{\prime}_{2}(\bm{a}^{(4)}_{1}),f^{\prime}_{1}(\bm{a}^{(4)}_{3})+f^{\prime}_{3}(\bm{a}^{(4)}_{1}),$
$\displaystyle
f^{\prime}_{2}(\bm{a}^{(4)}_{3})+f^{\prime}_{3}(\bm{a}^{(4)}_{2}),f^{\prime}_{2}(\bm{a}^{(4)}_{4})+f^{\prime}_{4}(\bm{a}^{(4)}_{2}),$
$\displaystyle
f^{\prime}_{4}(\bm{a}^{(4)}_{3})+f^{\prime}_{3}(\bm{a}^{(4)}_{4}),f^{\prime}_{1}(\bm{a}^{(4)}_{4})+f^{\prime}_{4}(\bm{a}^{(4)}_{1}),$
$\displaystyle\theta_{4,1}\cdot
f^{\prime}_{1}(\textbf{a}^{(4)}_{4})+f^{\prime}_{4}(\textbf{a}^{(4)}_{1}),\theta_{2,1}\cdot
f^{\prime}_{1}(\bm{a}^{(4)}_{2})+f^{\prime}_{2}(\bm{a}^{(4)}_{1}),$
$\displaystyle\theta_{3,1}\cdot
f^{\prime}_{1}(\bm{a}^{(4)}_{3})+f^{\prime}_{3}(\bm{a}^{(4)}_{1}),\theta_{3,2}\cdot
f^{\prime}_{2}(\bm{a}^{(4)}_{3})+f^{\prime}_{2}(\bm{a}^{(4)}_{3}),$
$\displaystyle\theta_{4,2}\cdot
f^{\prime}_{2}(\textbf{a}^{(4)}_{4})+f^{\prime}_{4}(\textbf{a}^{(4)}_{2}),\theta_{4,3}\cdot
f^{\prime}_{3}(\textbf{a}^{(4)}_{4})+f^{\prime}_{4}(\textbf{a}^{(4)}_{3}),$

and the $36$ data symbols $a^{(\ell)}_{i,j}$ with $\ell=1,2,3$, $i=1,2,3,4$
and $j=2,3,4$ to recover the first 12 data symbols in node $1$. The repair
bandwidth of node $1$ is $80$ symbols. Similarly, we can calculate that the
repair bandwidth of each node in $\\{2,3,4\\}$ is 80 symbols, the repair
bandwidth of each node in $\\{5,8\\}$ is 90 symbols, and the repair bandwidth
of each node in $\\{6,7\\}$ is 86 symbols.

###  V-B Repair Process for Parity Node

Suppose that node $t$ fails, where $t\in\\{k+1,k+2,\ldots,k+r\\}$. The repair
method of node $t$ is as follow.

  1. 1.

We compute the $sr$ symbols $f_{x}({\bm{a}}^{(\ell)}_{t-k})$ with
$\ell=1,2,\ldots,s$ and $x=1,2,\ldots,r$ by downloading the $sk$ symbols in
the first $k$ rows in columns $(\ell-1)r+t-k$ with $\ell=1,2,\ldots,s$.

  2. 2.

We recover the erased $sr$ symbols
$f^{\prime\prime}_{t-k}({\bm{a}}^{(\ell)}_{i})$ with $\ell=1,2,\ldots,s$ and
$i=1,2,\ldots,r$ by downloading the data symbols which are used in computing
the piggyback functions located in the $r$ rows $k+1,k+2,\ldots,k+r$ in the
$L$ columns $(\ell-1)r+t-k$ with $\ell=s-L+1,s-L+2,\ldots,s$ and downloading
the $s(r-1)$ symbols $f^{\prime\prime}_{x}({\bm{a}}^{(\ell)}_{t-k})$ with
$\ell=1,2,\ldots,s$ and $x=1,2,\ldots,t-k-1,t-k+1,\ldots,r$.

Continue the code in Example 5. Suppose that node $t=k+1$ fails, we download
$32$ data symbols $a^{(\ell)}_{1,j}$ with $\ell=1,2,3,4$ and $j=1,2,\ldots,8$
to calculate $f_{x}({\bm{a}}^{(\ell)}_{1})$ with $x=1,2,3,4$ and
$\ell=1,2,3,4$. Then we download the following 20 data symbols

$\displaystyle
a^{(1)}_{4,1},a^{(1)}_{4,2},a^{(1)}_{4,3},a^{(1)}_{4,4},a^{(2)}_{3,1},a^{(2)}_{3,2},a^{(2)}_{3,3},a^{(2)}_{3,4},$
$\displaystyle
a^{(3)}_{2,1},a^{(3)}_{2,2},a^{(3)}_{2,3},a^{(3)}_{2,4},a^{(1)}_{4,5},a^{(2)}_{4,6},a^{(1)}_{4,8},a^{(2)}_{3,5},$
$\displaystyle a^{(1)}_{3,7},a^{(2)}_{3,8},a^{(1)}_{2,6},a^{(2)}_{2,7},$

to calculate the piggyback functions

$g(4,1),g(7,1),g(10,1),g(4,2),g(7,2),g(10,2).$

Together with $f_{x}({\bm{a}}^{(\ell)}_{1})$ for $x=1,2,3,4$ and
$\ell=1,2,3,4$, and the above 6 piggyback functions, we can recover all the
symbols in node $t$ by downloading the following symbols.

$\displaystyle
f^{\prime}_{1}(\textbf{a}^{(3)}_{2})+f^{\prime}_{2}(\textbf{a}^{(3)}_{1}),f^{\prime}_{1}(\textbf{a}^{(3)}_{3})+f^{\prime}_{3}(\textbf{a}^{(3)}_{1}),$
$\displaystyle
f^{\prime}_{1}(\textbf{a}^{(3)}_{4})+f^{\prime}_{4}(\textbf{a}^{(3)}_{1}),f^{\prime}_{1}(\textbf{a}^{(4)}_{2})+f^{\prime}_{2}(\textbf{a}^{(4)}_{1}),$
$\displaystyle
f^{\prime}_{1}(\textbf{a}^{(4)}_{3})+f^{\prime}_{3}(\textbf{a}^{(4)}_{1}),f^{\prime}_{1}(\textbf{a}^{(4)}_{4})+f^{\prime}_{4}(\textbf{a}^{(4)}_{1}).$

###  V-C Repair Bandwidth of $\mathcal{C}_{2}(n,k,m,L)$

When $L$ is a factor of $k$, with similar proof in Lemma 3, we can show the
bounds of repair bandwidth of data nodes of $\mathcal{C}_{2}(n,k,m,L)$ in the
next lemma and we omit the proof.

######  Lemma 6.

If $L$ is a factor of $k$, the lower bound $\gamma_{min}^{sys}$ and the upper
bound $\gamma_{max}^{sys}$ of the average repair ratio of data nodes of
$\mathcal{C}_{2}(n,k,m,L)$ is

$\displaystyle\gamma_{min}^{sys}=\frac{L+1}{2s}+\frac{(s^{2}-s(L+1)+\frac{(L+1)(2L+1)}{6})}{Ls(r-1)}+\frac{(r-1)(L-3)}{2ksr},$
$\displaystyle\gamma_{max}^{sys}=\gamma_{min}^{all}+\frac{L(r-1)}{4sk^{2}}.$

By Lemma 6, we have
$|\gamma_{sys}-\gamma_{min}^{sys}|\leq|\gamma_{max}^{sys}-\gamma_{min}^{sys}|=\frac{L(r-1)}{4sk^{2}}$.
When $k\to\infty$, we have $\gamma^{sys}=\gamma^{sys}_{min}$. Therefore, we do
not distinguish between $\gamma^{sys}$ and $\gamma^{sys}_{min}$ in the rest of
the paper.

Similar to the proof of Lemma 4, we can also show that the minimum value of
average repair bandwidth ratio $\gamma^{sys}$ is achieved when
$L=\sqrt{\frac{6s^{2}-6s+1}{3r-1}}$.

######  Lemma 7.

If $L$ is a factor of $k$, the average repair bandwidth ratio of parity nodes
for codes $\mathcal{C}_{2}(n,k,m,L)$ is

$\gamma_{parity}=\frac{2}{r}+\frac{1}{k}-\frac{1}{kr}-\frac{L+1}{2sr}.$ (5)

###### Proof.

According to the repair methods in Section V-B, we need to download
$\sum_{i=1}^{r}sk$ symbols in repairing each of the $r$ parity nodes in the
first step. In the second step, we need to download
$\sum_{i=1}^{r}s(r-1)+2\sum_{i=1}^{L}|\Phi_{i}|r(s-i)$ in repairing each of
the $r$ parity nodes. Therefore, we can calculate that

$\gamma^{parity}=\frac{\sum_{i=1}^{r}s(k+r-1)+\sum_{i=1}^{L}|\Phi_{i}|r(s-i)}{skr^{2}}.$

Because $L$ is a factor of $k$, we have $|\Phi_{i}|=\frac{k}{L}$ for
$i=1,2,\ldots,L$, and further obtain that

$\gamma_{parity}=\frac{2}{r}+\frac{1}{k}-\frac{1}{kr}-\frac{L+1}{2sr}.$

∎

##  VI Comparison

In this section, we evaluate the average repair bandwidth of all $n$ nodes for
our two codes and the existing piggybacking codes with low repair bandwidth.

###  VI-A Piggybacking Codes with $m<r$

Figure 5: The average repair bandwidth ratio of all nodes for the proposed
codes $\mathcal{C}_{1}$, REPB codes [15], codes $\mathcal{C}_{3}$ [20] and
codes $\mathcal{C}$ [21], where $r=8,9$, $m=6$ and $k=30,31,\ldots,100$.

First, we evaluate $\mathcal{C}_{1}(n,k,m,L)$ and the existing piggybacking
codes [15, 20, 21] such that the sub-packetization is no larger than $r$.
Denote the codes in [20] as $\mathcal{C}_{3}(n,k,m)$, the MDS codes (the first
codes) in [21] as $\mathcal{C}$, the codes in [15] as REPB.

Fig. 5 shows the evaluations for $r=8,9$, $m=6$ and $k=30,31,\ldots,100$. Note
that the codes in our conference paper [1] can only support the parameter
$m=r$ and do not draw the points for codes [1] in Fig. 5. The results in Fig.
5 demonstrate that our codes $\mathcal{C}_{1}(n,k,m,L)$ have lower repair
bandwidth than all existing piggybacking codes when $m<r$ for all the
evaluated parameters.

###  VI-B Piggybacking Codes with $m\geq r$

Figure 6: The average repair bandwidth ratio of all nodes for the proposed
codes $\mathcal{C}_{2}$, OOP codes [16], codes $\mathcal{C}_{4}$ [1] and codes
$\mathcal{C}_{5}$ [19], where $r=4,5,6,7,\ldots,20$, code rate
$\frac{k}{n}=0.75,0.8,0.9$ and $m=6r,r^{2}$.

In the following, we evaluate $\mathcal{C}_{2}(n,k,m,L)$ and the existing
piggybacking codes with $m\geq r$.

We label the codes in [1] as $\mathcal{C}_{4}$, the codes in [19] as
$\mathcal{C}_{5}$. Fig. 6 shows the average repair bandwidth ratio of all
nodes for our codes $\mathcal{C}_{2}(n,k,m,L)$ and the existing piggybacking
codes, including OOP, $\mathcal{C}_{4}$ and $\mathcal{C}_{5}$ when
$r=4,5,\ldots,20$, $\frac{k}{n}=0.75,0.8,0.9$ and $m=6r,r^{2}$. The results
show that our codes $\mathcal{C}_{2}(n,k,m,L)$ have lower repair bandwidth
than the other codes for all the evaluated parameters. The essential reason of
lower repair bandwidth of our $\mathcal{C}_{2}(n,k,m,L)$ is that we jointly
design the piggyback function for data node repair and the transformation
function for parity node repair.

##  VII Conclusion

In this paper, we design two classes of piggybacking codes with flexible sub-
packetization level. The first piggybacking codes $\mathcal{C}_{1}$ have the
lower repair bandwidth for single-node failure than all exsiting piggybacking
codes with $m\leq r$ for all the evaluated parameters. Our second piggybacking
codes can support sub-packetization $m=sr$ with $2\leq s\leq r$ that have the
lowest average repair bandwidth for all nodes among all existing piggybacking
codes for the evaluated parameters. The piggybacking codes constructions by
jointly designing piggyback functions and transformation functions to support
more larger sub-packetization, say $m=sr$ with $s>r$, to further reduce repair
bandwidth is one of our future work.

## References

  * [1] H. Shi, H. Hou, Y. S. Han, P. P.-C. Lee, Z. Jiang, Z. Huang, and B. Bai, “New piggybacking codes with lower repair bandwidth for any Single-Node failure,” in 2022 IEEE International Symposium on Information Theory (ISIT) (ISIT 2022), Espoo, Finland, June 2022.
  * [2] I. S. Reed and G. Solomon, “Polynomial Codes over Certain Finite Fields,” Journal of the Society for Industrial & Applied Mathematics, vol. 8, no. 2, pp. 300–304, 1960.
  * [3] M. Sathiamoorthy, M. Asteris, D. Papailiopoulos, A. G. Dimakis, and D. Borthakur, “Xoring elephants: Novel erasure codes for big data,” VLDB Endowment, 2013.
  * [4] K. V. Rashmi, N. B. Shah, D. Gu, H. Kuang, D. Borthakur, and K. Ramchandran, “A solution to the network challenges of data recovery in erasure-coded distributed storage systems: A study on the facebook warehouse cluster,” Usenix Hotstorage, 2013.
  * [5] A. Dimakis, P. Godfrey, Y. Wu, M. Wainwright, and K. Ramchandran, “Network Coding for Distributed Storage Systems,” IEEE Trans. Information Theory, vol. 56, no. 9, pp. 4539–4551, Sep. 2010.
  * [6] K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction,” IEEE Trans. Information Theory, vol. 57, no. 8, pp. 5227–5239, August 2011.
  * [7] H. Hou, K. W. Shum, M. Chen, and H. Li, “BASIC Codes: Low-Complexity Regenerating Codes for Distributed Storage Systems,” IEEE Trans. Information Theory, vol. 62, no. 6, pp. 3053–3069, 2016.
  * [8] J. Li, X. Tang, and C. Tian, “A Generic Transformation to Enable Optimal Repair in MDS codes for Distributed Storage Systems,” IEEE Trans. Information Theory, vol. 64, no. 9, pp. 6257–6267, 2018.
  * [9] H. Hou, P. Lee, and Y. S. Han, “Toward optimality in both repair and update via generic mds code transformation,” in 2020 IEEE International Symposium on Information Theory (ISIT), 2020.
  * [10] H. Hou and P. Lee, “Binary mds array codes with optimal repair,” IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1405–1422, 2020.
  * [11] M. Ye and A. Barg, “Explicit Constructions of High-Rate MDS Array Codes with Optimal Repair Bandwidth,” IEEE Trans. Information Theory, vol. 63, no. 4, pp. 2001–2014, 2017.
  * [12] S. B. Balaji and P. V. Kumar, “A tight lower bound on the sub- packetization level of optimal-access msr and mds codes,” in Proc. IEEE Int. Symp. Inf. Theory, 2018, pp. 2381–2385.
  * [13] K. Kralevska, D. Gligoroski, R. E. Jensen, and H. Overby, “Hashtag erasure codes: From theory to practice,” IEEE, no. 4, 2018.
  * [14] K. V. Rashmi, N. B. Shah, and K. Ramchandran, “A piggybacking design framework for read-and download-efficient distributed storage codes,” IEEE Transactions on Information Theory, vol. 63, no. 9, pp. 5802–5820, 2017.
  * [15] S. Yuan, Q. Huang, and Z. Wang, “A Repair-Efficient Coding for Distributed Storage Systems Under Piggybacking Framework,” IEEE Trans. Communications, vol. 66, no. 8, pp. 3245–3254, 2018.
  * [16] G. Y. Li, X. Lin, and X. Tang, “An Efficient One-to-One Piggybacking Design for Distributed Storage Systems,” IEEE Trans. Communications, vol. 67, no. 12, pp. 8193–8205, 2019.
  * [17] C. Shangguan and G. Ge, “A new piggybacking design for systematic mds storage codes,” Designs, Codes and Cryptography, vol. 87, 12 2019.
  * [18] Z. Jiang, H. Hou, Y. S. Han, Z. Huang, B. Bai, and G. Zhang, “An efficient piggybacking design with lower repair bandwidth and lower sub-packetization,” in Proc. IEEE Int. Symp. Inf. Theory, 2021, pp. 2328–2333.
  * [19] R. Sun, L. Zhang, and J. Liu, “A new piggybacking design with low repair bandwidth and complexity,” IEEE Communications Letters, vol. 25, no. 7, pp. 2099–2103, 2021.
  * [20] K. Wang and Z. Zhang, “An Efficient Piggybacking Design Framework with Sub-packetization $l\leq r$ for All-Node Repair,” arXiv e-prints, p. arXiv:2205.09659, May 2022.
  * [21] Z. Jiang, H. Hou, Y. S. Han, P. P. C. Lee, B. Bai, and Z. Huang, “Two New Piggybacking Designs with Lower Repair Bandwidth,” arXiv e-prints, p. arXiv:2205.14555, May 2022.