# Repairing with Zero Skip Cost

Wenqin Zhang1, Yeow Meng Chee2, Son Hoang Dau3, Tuvi Etzion24, Han Mao Kiah5,
Yuan Luo1

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>5Corresponding author: Wenqin Zhang. The work was supported in part by
National Key $R\&D$ Program of China under Grant 2022YFA1005000, National
Natural Science Foundation of China under Grant 62171279, and Fundings of
SJTU-Alibaba Joint Research Lab on Cooperative Intelligent Computing. The work
of Son Hoang Dau was supported by ARC DECRA DE180100768. The work of Han Mao
Kiah was supported by the Ministry of Education, Singapore, under its MOE AcRF
Tier 2 Award under Grant MOE-T2EP20121-0007 and MOE AcRF Tier 1 Award under
Grant RG19/23. 1School of Electronic Information and Electrical Engineering,
Shanghai Jiao Tong University, Shanghai, China  2Dept. of Industrial Systems
Engineering and Management, National University of Singapore  3School of
Computing Technologies, RMIT University, Melbourne, VIC, Australia  4Computer
Science Faculty, Technion, Israel Institute of Technology,  5School of
Physical and Mathematical Sciences, Nanyang Technological University,
Singapore

###### Abstract

To measure repair latency at helper nodes, we introduce a new metric called
skip cost that quantifies the number of contiguous sections accessed on a
disk. We provide explicit constructions of zigzag codes and fractional
repetition codes that incur zero skip cost.

##  I Introduction

In a distributed storage system, a file is represented as
${\boldsymbol{x}}\in\mathbb{F}^{k}$ for a finite field $\mathbb{F}$. To
protect against node failures, the data is encoded into a codeword
${\boldsymbol{c}}=(c_{1},\ldots,c_{n})$, where $n$ is larger than $k$ and each
codesymbol $c_{i}$ is kept in node $i$. Traditionally, erasure coding is
employed, enabling the recovery of the file ${\boldsymbol{x}}$ by contacting a
subset of these nodes. In the case of maximum distance-separable (MDS) codes,
an optimal strategy exists, allowing one to recover ${\boldsymbol{x}}$ from
any $k$ nodes.

However, in the scenario of a single node failure, this approach is
suboptimal, as we download $k$ codesymbols to recover just one codesymbol.
Therefore, in [1], the notion of repair bandwidth was introduced as a metric
to measure the performance of a distributed storage system. Essentially, the
repair bandwidth quantifies the total amount of information downloaded from
helper nodes to repair any failed node. Following this seminal work, numerous
coding proposals emerged and we direct the reader to [2, 3, 4] for detailed
surveys.

Apart from repair bandwidth, additional factors contribute to latency in the
repair process. For example, the notion of access-optimality was consider in
[5] and [6], while here we introduce another metric. Specifically, in [7], the
access latency at the helper nodes is attributed to two factors: data access
time and data processing time. Now, the latter was addressed in earlier works
where the concept of repair-by-transfer was introduced [8]. In the repair-by-
transfer framework, a failed node is repaired through a simple transfer of
data without the need for processing at the helper nodes111In [8], a more
stringent requirement is placed, where the failed node performs no
computation. We relax this condition for this work, focusing on reducing the
delay at the helper nodes.. Here, we investigate two classes of codes
exhibiting this property: zigzag codes [9] and fractional repetition codes
[10]. On a more significant note, [7] characterized data access time not only
by the amount of data read (typically known as I/O costs), but also the number
of contiguous sections accessed on a disk222In fact, this issue was raised
during a Huawei Industry Session during ISIT 2023. Dr Wu discussed this in his
presentation “Coding Challenges for Future Storage”.. In this work, we propose
a novel metric named skip cost to quantify this notion.

To illustrate this metric, we consider the toy examples presented in Fig. 1.
In (a), we have five nodes ${\boldsymbol{a}}^{(0)}$, ${\boldsymbol{a}}^{(1)}$,
${\boldsymbol{a}}^{(2)}$, ${\boldsymbol{p}}^{(0)}$ and
${\boldsymbol{p}}^{(1)}$. When ${\boldsymbol{a}}^{(2)}$ fails, the contents
highlighted in  blue are read (see Section III for details of the repair
procedure). Notably, in node ${\boldsymbol{a}}^{(0)}$, the read contents are
not contiguous and we quantify the gap as skip cost one. Summing up the skip
costs across all helper nodes, we say that the skip cost of the repair is
four. In contrast, (b) illustrates an example of our proposed code
construction. In this case, the repair bandwidth remains the same, but we see
that all read contents are contiguous. Consequently, the skip cost is zero.

In this work, we present explicit constructions of array codes with zero skip
cost. Before delving into technical descriptions of our contributions, we
establish some notations.

(a) $(4\times 5,3)$-array code with skip cost four.

| ${\boldsymbol{a}}^{(0)}$ | ${\boldsymbol{a}}^{(1)}$ | ${\boldsymbol{a}}^{(2)}$ | ${\boldsymbol{p}}^{(0)}$ | ${\boldsymbol{p}}^{(1)}$
---|---|---|---|---|---
| $\spadesuit$ | $\heartsuit$ | $\clubsuit$ | ${\boldsymbol{S}}_{0}=({\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}})$ | ${\boldsymbol{S}}_{1}=({\boldsymbol{0}},{\boldsymbol{e}}_{1},{\boldsymbol{e}}_{2})$
$00$ | $00_{\spadesuit}$ | $00_{\heartsuit}$ | $00_{\clubsuit}$ | $00_{\spadesuit}\boxplus 00_{\heartsuit}\boxplus 00_{\clubsuit}$ | $00_{\spadesuit}\boxplus 10_{\heartsuit}\boxplus 01_{\clubsuit}$
$01$ | $01_{\spadesuit}$ | $01_{\heartsuit}$ | $01_{\clubsuit}$ | $01_{\spadesuit}\boxplus 01_{\heartsuit}\boxplus 01_{\clubsuit}$ | $01_{\spadesuit}\boxplus 11_{\heartsuit}\boxplus 00_{\clubsuit}$
$10$ | $10_{\spadesuit}$ | $10_{\heartsuit}$ | $10_{\clubsuit}$ | $10_{\spadesuit}\boxplus 10_{\heartsuit}\boxplus 10_{\clubsuit}$ | $10_{\spadesuit}\boxplus 00_{\heartsuit}\boxplus 11_{\clubsuit}$
$11$ | $11_{\spadesuit}$ | $11_{\heartsuit}$ | $11_{\clubsuit}$ | $11_{\spadesuit}\boxplus 11_{\heartsuit}\boxplus 11_{\clubsuit}$ | $11_{\spadesuit}\boxplus 01_{\heartsuit}\boxplus 10_{\clubsuit}$

(b) $(4\times 6,3)$-array code code with skip cost zero.

| ${\boldsymbol{a}}^{(0)}$ | ${\boldsymbol{a}}^{(1)}$ | ${\boldsymbol{a}}^{(2)}$ | ${\boldsymbol{p}}^{(0)}$ | ${\boldsymbol{p}}^{(1)}$ | ${\boldsymbol{p}}^{(2)}$
---|---|---|---|---|---|---
| $\spadesuit$ | $\heartsuit$ | $\clubsuit$ | ${\boldsymbol{S}}_{0}=({\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}})$ | ${\boldsymbol{S}}_{1}=({\boldsymbol{0}},{\boldsymbol{e}}_{2},{\boldsymbol{d}}_{1})$ | ${\boldsymbol{S}}_{1}=({\boldsymbol{0}},{\boldsymbol{d}}_{1},{\boldsymbol{d}}_{2})$
$00$ | $00_{\spadesuit}$ | $00_{\heartsuit}$ | $00_{\clubsuit}$ | $00_{\spadesuit}\boxplus 00_{\heartsuit}\boxplus 00_{\clubsuit}$ | $00_{\spadesuit}\boxplus 01_{\heartsuit}\boxplus 10_{\clubsuit}$ | $00_{\spadesuit}\boxplus 10_{\heartsuit}\boxplus 11_{\clubsuit}$
$01$ | $01_{\spadesuit}$ | $01_{\heartsuit}$ | $01_{\clubsuit}$ | $01_{\spadesuit}\boxplus 01_{\heartsuit}\boxplus 01_{\clubsuit}$ | $01_{\spadesuit}\boxplus 00_{\heartsuit}\boxplus 11_{\clubsuit}$ | $01_{\spadesuit}\boxplus 11_{\heartsuit}\boxplus 10_{\clubsuit}$
$10$ | $10_{\spadesuit}$ | $10_{\heartsuit}$ | $10_{\clubsuit}$ | $10_{\spadesuit}\boxplus 10_{\heartsuit}\boxplus 10_{\clubsuit}$ | $10_{\spadesuit}\boxplus 11_{\heartsuit}\boxplus 00_{\clubsuit}$ | $10_{\spadesuit}\boxplus 00_{\heartsuit}\boxplus 01_{\clubsuit}$
$11$ | $11_{\spadesuit}$ | $11_{\heartsuit}$ | $11_{\clubsuit}$ | $11_{\spadesuit}\boxplus 11_{\heartsuit}\boxplus 11_{\clubsuit}$ | $11_{\spadesuit}\boxplus 10_{\heartsuit}\boxplus 01_{\clubsuit}$ | $11_{\spadesuit}\boxplus 01_{\heartsuit}\boxplus 00_{\clubsuit}$

Figure 1: (a) Example of a $(4\times 5,3)$-MDS array code constructed in [9].
Suppose information node ${\boldsymbol{a}}^{(2)}$ (highlighted in red) fails.
We contact nodes ${\boldsymbol{a}}^{(0)}$, ${\boldsymbol{a}}^{(1)}$,
${\boldsymbol{p}}^{(0)}$ and ${\boldsymbol{p}}^{(1)}$ and read the contents in
blue. Here, the skip cost is $4\times 1=4$. (b) Example of a $(4\times
6,3)$-MDS array code described by Construction A with $m=2$ (see Section III).
Suppose information node ${\boldsymbol{a}}^{(2)}$ (highlighted in red) fails.
We contact nodes ${\boldsymbol{a}}^{(0)}$, ${\boldsymbol{a}}^{(1)}$,
${\boldsymbol{p}}^{(0)}$ and ${\boldsymbol{p}}^{(1)}$ and read the contents in
blue. Here, the skip cost is zero. Note that we use ${\boldsymbol{x}}_{i}$ to
represent the information symbol $a_{\boldsymbol{x}}^{(i)}$, while the ‘sum’
${\boldsymbol{x}}_{i}\boxplus{\boldsymbol{y}}_{j}\boxplus{\boldsymbol{z}}_{k}$
indicates that the corresponding codesymbol is a linear combination of
$a_{\boldsymbol{x}}^{(i)}$, $a_{\boldsymbol{y}}^{(j)}$, and
$a_{\boldsymbol{z}}^{(k)}$.

##  II Problem Statement

For integers $i$ , $j$ with $i<j$, we let $[i,j]$ and $[i]$ denote the sets of
integers $\\{i,i+1,i+2,\ldots,j\\}$ and $\\{1,2,\ldots,i\\}$, respectively.
Furthermore, $\mathbb{F}_{q}$ denotes the finite field with $q$.

Throughout this paper, we consider array codes, where each codeword is
represented as an $M\times N$-array over $\mathbb{F}_{q}$, whose rows and
columns are indexed by $[M]$ and $[N]$, respectively. Specifically, each
codeword is of the form
${\boldsymbol{C}}=\left[{\boldsymbol{b}}^{(1)},{\boldsymbol{b}}^{(2)},\ldots,{\boldsymbol{b}}^{(N)}\right]$,
where ${\boldsymbol{b}}^{(j)}=\left(b_{1}^{(j)},\ldots,b_{M}^{(j)}\right)$
belongs to $\mathbb{F}_{q}^{M}$. Here, we say that we have $N$ nodes with each
node storing $M$ packets or code symbols.

If the codewords form an $\mathbb{F}_{q}$-linear subspace of dimension $Mk$,
we say that the code is an $(M\times N,k)$-array code. Consider any codeword
${\boldsymbol{C}}$. If we can recover all $N$ columns of ${\boldsymbol{C}}$
from any subset of $k$ columns, we say the code is maximum distance separable
(MDS).

When a node containing ${\boldsymbol{b}}$ fails, we contact certain helper
nodes ${\mathcal{H}}$ and download a certain portion of their contents to
repair the failed node, that is, to recover ${\boldsymbol{b}}$. The amount of
information downloaded from the helper nodes is called the repair bandwidth.
For an $(M\times N,k)$-array code, [1] demonstrated that if
$|{\mathcal{H}}|=d$, then it is necessary to download at least $1/(d-k+1)$
fraction of the contents stored on each helper node. This lower bound is
commonly referred to as the cutset bound and most work seeks to achieve this
bound.

In addition to this bound, this paper considers the repair-by-transfer
framework, where the content downloaded is precisely the information read from
each helper node. Besides minimizing the amount of information read, we
introduce another metric, called skip cost.

######  Definition 1 (Skip Cost).

Consider a tuple ${\boldsymbol{b}}=(b_{1},b_{2},\ldots,b_{M})$ and suppose
that we read $t$ packets ${\sf R}=\\{b_{i_{1}},\ldots,b_{i_{t}}\\}$ where
$i_{1}<\cdots<i_{t}$. We define the skip cost of ${\sf R}$ with respect to
${\boldsymbol{b}}$ is ${\sf cost}({\sf R},{\boldsymbol{b}})\triangleq
i_{t}-i_{1}-(t-1)$. So, if the indices in ${\sf R}$ are consecutive, then its
skip cost is zero, which is clearly optimal.

An array code has a repair scheme with skip cost $\sigma$ if for any codeword
node ${\boldsymbol{b}}$, there exists a collection of helper nodes
${\mathcal{H}}$ and corresponding reads ${\sf
R}_{\boldsymbol{h}}~{}({\boldsymbol{h}}\in{\mathcal{H}})$ such that

  1. (i)

we can determine ${\boldsymbol{b}}$ from
$\bigcup_{{\boldsymbol{h}}\in{\mathcal{H}}}{\sf R}_{h}$, and

  2. (ii)

the total skip cost is at most $\sigma$, that is,
$\sum_{{\boldsymbol{h}}\in{\mathcal{H}}}{\sf cost}({\sf
R}_{h},{\boldsymbol{h}})\leq\sigma$.

In this paper, we consider two classes of array codes with good repair-by-
transfer schemes: zigzag codes and fractional repetition codes, proposed in
[9] and [10], respectively.

###  II-A Zigzag Codes

Zigzag codes are a special class of MDS array codes designed by Tamo et al.
[9] that have an optimal rebuilding ratio. Specifically, these codes are
$(M\times N,k)$-MDS array codes where the first $k$ columns or nodes are
systematic nodes and we focus only the failure of single systematic nodes. The
rebuilding ratio of a code is then given by the maximum fraction of contents
downloaded from a helper node to repair any systematic node. Following the
cutset bound, when the number of helper nodes is $d$, then the rebuilding
ratio is necessarily at least $1/(d-k+1)$. Formally, we have the following
result from [9].

######  Theorem 1 ([9]).

Fix $r$. For a sufficiently large field, there exists an $(M\times N,k)$-MDS
array code with $N-k=r$ and an optimal rebuilding ratio $1/r$. Here, the
number of helper nodes is $N-1$.

Now, as we see in Section III (see Remark 1), the repair scheme for these
codes incurs a significant skip cost. Hence, in the same section, we design a
new class of zigzag codes that incurs zero skip cost. Unfortunately, our array
codes suffer a reduction in coding rates. Nevertheless, our codes retain
valuable properties such as optimal rebuilding ratio and optimal update333As
defined in [9], a code has optimal update if whenever an information symbol is
altered, only the information symbol itself and one symbol from each parity
node are updated..

###  II-B Fractional Repetition Codes

(a) $(4\times 14)$-array code with locality two and skip cost two.

1 | 1 | 1 | 1 | 1 | 1 | 1 | 5 | 3 | 3 | 2 | 7 | 3 | 3
---|---|---|---|---|---|---|---|---|---|---|---|---|---
2 | 2 | 2 | 3 | 6 | 4 | 4 | 6 | 4 | 4 | 4 | 4 | 2 | 2
3 | 5 | 7 | 5 | 3 | 5 | 7 | 7 | 7 | 5 | 6 | 5 | 7 | 5
4 | 6 | 8 | 7 | 8 | 8 | 6 | 8 | 8 | 6 | 8 | 2 | 6 | 8

(b) $(4\times 14)$-array code with locality two and skip cost zero.

${\mathcal{B}}_{1}$ | ${\mathcal{B}}_{2}$
---|---
$1_{0}$ | $1_{0}$ | $1_{0}$ | $1_{0}$ | $1_{1}$ | $1_{1}$ | $1_{1}$ | $1_{1}$ | $1_{0}$ | $1_{0}$ | $1_{0}$ | $2_{0}$ | $2_{0}$ | $3_{0}$
$2_{0}$ | $2_{0}$ | $2_{1}$ | $2_{1}$ | $2_{0}$ | $2_{0}$ | $1_{1}$ | $2_{1}$ | $1_{1}$ | $1_{1}$ | $1_{1}$ | $2_{1}$ | $2_{1}$ | $3_{1}$
$3_{0}$ | $3_{1}$ | $3_{0}$ | $3_{1}$ | $3_{0}$ | $3_{1}$ | $3_{0}$ | $3_{1}$ | $2_{0}$ | $3_{0}$ | $4_{0}$ | $3_{0}$ | $4_{0}$ | $4_{0}$
$4_{0}$ | $4_{1}$ | $4_{1}$ | $4_{0}$ | $4_{1}$ | $4_{0}$ | $4_{0}$ | $4_{1}$ | $2_{1}$ | $3_{1}$ | $4_{1}$ | $3_{1}$ | $4_{1}$ | $4_{1}$

Figure 2: (a) Example of a $(4\times 14)$-array code built using a ${\rm
SQS}(8)$. Suppose the node highlighted in red fails. We read the contents in
blue and the skip cost is $2\times 1=2$. (b) Example of a ($4\times 14$)-array
code described by Construction D with $|V|=8$ (see Section IV). Here, due to
the space constrained, we use the notation $a_{b}$ to denote $(a,b)$.

Suppose the node highlighted in red fails. We read the contents in blue and
the skip cost is zero.

After the introduction of the repair-by-transfer framework in [8], El Rouayheb
and Ramchandran [10] introduced a novel class of array codes that uses table-
based repair. Known as DRESS (Distributed Replication based Exact Simple
Storage) codes, these codes comprise two main components: an outer MDS code
and an inner repetition code known as fractional repetition code. Typically,
fractional repetition codes are constructed using combinatorial designs, and
in-depth discussions can be found in [10, 11, 12, 13, 14].

Here, we formally describe how a set system can be used to construct an array
code. Let $V$ be a set of points and ${\mathcal{B}}$ be a collection of
subsets defined over $V$. For ${\boldsymbol{b}}\in{\mathcal{B}}$, we refer to
${\boldsymbol{b}}$ as a block. Then $(V,{\mathcal{B}})$ is known as a set
system.

Suppose further that $|V|=n$, $|{\mathcal{B}}|=N$ and $|{\boldsymbol{b}}|=M$
for all ${\boldsymbol{b}}\in{\mathcal{B}}$. In addition, we also consider an
$[n,k]$-MDS outer code444In the rest of the paper, we omit specifying the
dimension $k$ of the outer code, as it does not influence the repair costs..
In a DRESS code, a file ${{\boldsymbol{x}}}$ is broken up into $n$ coded
packets and stored in $|{\mathcal{B}}|=N$ nodes such that any $k$ packets
suffices to restore ${{\boldsymbol{x}}}$. Here, the packets of the file
${{\boldsymbol{x}}}$ and the storage nodes are indexed by $V$ and
${\mathcal{B}}$, respectively. Then for a block
${\boldsymbol{b}}\in{\mathcal{B}}$, we store the packets
$\\{{{\boldsymbol{x}}}_{v}:v\in{\boldsymbol{b}}\\}$ in the node
${\boldsymbol{b}}$ and we obtain an $(M\times N)$-array code. For example, the
$(4\times 14)$-array codes displayed in Fig. 2 are constructed using set
systems with eight points, $14$ blocks, and with constant block size four.

As before, we are interested in the event when a single node fails. In the
case of DRESS codes, the repair process for the failed node or block involves
downloading the coded packets replicated in other nodes. To further reduce
repair latency, we limit the number of helper nodes, imposing locality
requirements on the repair process.

Now, given certain locality requirements, we observe that the order in which
the points or packets are arranged in each node has an impact on skip cost. In
Fig. 2(a), when the node $(2,4,6,8)$ fails, a skip cost of two is necessary to
recover the points $2$, $4$, $6$, and $8$ from two helper nodes. In contrast,
with the arrangement of points in Fig. 2(b), we can achieve both locality two
and skip cost zero, regardless of the failed node. For convenience, we say
that a set system has locality $d$ and skip cost $\sigma$ if the corresponding
array code admits a repair scheme that repairs with at most $d$ helpers and
skip cost $\sigma$.

Next, we observe that both set systems in Figure 2 are Steiner quadruple
systems (SQS) of order eight, and these designs shall be our main object of
study555A SQS is a special class of three-designs as each triple appears
exactly once among all blocks. Now, a two-design is defined to be a set system
where every pair appears exactly once among all blocks. In this case, during
recovery, at most one point can be downloaded from every helper node. Then the
skip cost is trivially zero. Therefore, we study the next non-trivial case:
SQS. .

######  Definition 2.

A Steiner quadruple systems of order $v$, or ${\rm SQS}(v)$, is a set system
$(V,{\mathcal{B}})$ such that

  1. (i)

$|V|=v$ and $|{\boldsymbol{b}}|=4$ for all ${\boldsymbol{b}}\in{\mathcal{B}}$.

  2. (ii)

Every subset $T$ of $V$ with $|T|=3$ is contained in exactly one block in
${\mathcal{B}}$.

Hanani then demonstrated the existence of such quadruple systems for all
admissible parameters.

######  Theorem 2 (Hanani [15]).

A ${\rm SQS}(v)$ exists if and only if $v\geq 4$ and $v\equiv 2$ or
$4\pmod{6}$.

In Section IV, we show that at least two thirds of these quadruple systems
have locality two and skip cost zero. Specifically, we show the following
result.

######  Theorem 3.

There exists a ${\rm SQS}(v)$ with locality two and skip cost zero if $v\geq
4$ and $v\equiv 4,8,10,16,20,22,28,\text{ or }32\pmod{36}$ and
$v\in\\{14,26,34,38\\}$.

Therefore, we have an ${\rm SQS}(v)$ with locality two and skip cost zero for
all admissible parameters at most 50. We conjecture that a ${\rm SQS}(v)$ with
locality two and skip cost zero exists for all admissible parameters.

##  III Zigzag Codes with Zero Skip Cost

In this section, we present three classes of MDS array codes with a repair
scheme that incurs zero skip cost. Our initial construction, Construction A,
serves to demonstrate the main ideas underlying the placement of parity
symbols. Subsequently, we refine our approach. Specifically, we achieve a
higher code rate in Construction B and later eliminate the dependency of
number of information symbols and sub-packetization level in Construction C.

Although our placement of parity code symbols shares similarities with that of
Tamo-Wang-Bruck, specific differences enable us to achieve zero skip cost
during the repair process.

Construction A. Let $m\geq 2$ and set $k=m+1$. We present an $(M\times
N,k)$-MDS array code with $M=2^{m}$ packets and $N=2k=2(m+1)$ nodes. Of these
$N$ nodes, $k=m+1$ of them are systematic nodes
${\boldsymbol{a}}^{(0)},{\boldsymbol{a}}^{(1)}\ldots,{\boldsymbol{a}}^{(m)}$,
while the remaining $k=m+1$ are parity nodes
${\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(1)},\ldots,{\boldsymbol{p}}^{(m)}$.
Now, instead of indexing the rows with $[M]$, we index them using the
$M=2^{m}$ bitstrings in $\mathbb{F}_{2}^{m}$. Here, the rows are arranged in
lexicographic order. Moreover, for convenience, we introduce the following
notation for certain vectors in $\mathbb{F}_{2}^{m}$:

  * •

${\boldsymbol{0}}$ denotes the zero vector;

  * •

For $i\in[m]$, we use ${\boldsymbol{e}}_{i}$ to denote the vector whose $i$-th
entry is one and other entries are $0$.

  * •

For $i\in[m]$, we use ${\boldsymbol{d}}_{i}$ to denote the vector whose first
$i$ entries are one and other entries are $0$. In other words,
${\boldsymbol{d}}_{i}={\boldsymbol{e}}_{1}+\cdots+{\boldsymbol{e}}_{i}$.

  * •

Finally, we use ${\mathcal{U}}$ and ${\mathcal{L}}$ denotes the set of
bitstrings starting with zero and one, respectively. Given the lexicographic
order, we observe that the first and second halves of the array are indexed by
strings in ${\mathcal{U}}$ and ${\mathcal{L}}$, respectively.

Contents of systematic columns: For $j\in[0,m]$, we simply set
${\boldsymbol{a}}^{(j)}=\left(a^{(j)}_{{\boldsymbol{x}}}\right)_{{\boldsymbol{x}}\in\mathbb{F}_{2}^{m}}$.

Contents of parity columns: For $j\in[0,m]$, we set
${\boldsymbol{p}}^{(j)}=\left(p^{(j)}_{{\boldsymbol{x}}}\right)_{{\boldsymbol{x}}\in\mathbb{F}_{2}^{m}}$
and our task is to determine the parity sum $p^{(j)}_{{\boldsymbol{x}}}$ in
terms of the $a^{(j)}_{\boldsymbol{x}}$’s. Now, in what follows, each parity
sum in ${\boldsymbol{p}}^{(j)}$ is a linear combination $m+1$ information
symols and is determined by an $(m+1)$-tuple ${\boldsymbol{S}}_{j}$.

  * •

Set ${\boldsymbol{S}}_{0}$ to be $({\boldsymbol{0}},\ldots,{\boldsymbol{0}})$
and for $j\in[m]$, we set
$S_{j}=\left({\boldsymbol{0}},{\boldsymbol{e}}_{j+1},{\boldsymbol{e}}_{j+2},\ldots,{\boldsymbol{e}}_{m},{\boldsymbol{d}}_{1},{\boldsymbol{d}}_{2},\ldots,{\boldsymbol{d}}_{j}\right)$.

  * •

Now, we use the tuple ${\boldsymbol{S}}_{j}$ to generate a parity column
${\boldsymbol{p}}^{(j)}$. If
${\boldsymbol{S}}_{j}=({\boldsymbol{v}}_{0},\ldots,{\boldsymbol{v}}_{m})$ and
we consider row ${\boldsymbol{x}}$, we set
${\boldsymbol{u}}_{i}={\boldsymbol{x}}+{\boldsymbol{v}}_{i}$ and define
$p^{(j)}_{{\boldsymbol{x}}}=\sum^{m}_{i=0}\alpha^{(i,j)}_{{\boldsymbol{x}}}a^{(i)}_{{\boldsymbol{u}}_{i}}$
for some choice of coefficients
$\alpha^{(i,j)}_{{\boldsymbol{x}}}\in\mathbb{F}_{q}$

  * •

For example, for the first parity column ${\boldsymbol{p}}^{(0)}$, we have
that ${\boldsymbol{S}}_{0}=({\boldsymbol{0}},\ldots,{\boldsymbol{0}})$. Then
for row ${\boldsymbol{x}}$, the parity sum is
$p^{(0)}_{{\boldsymbol{x}}}=\alpha^{(0,0)}_{{\boldsymbol{x}}}a^{(0)}_{{\boldsymbol{x}}}+\cdots+\alpha^{(m,0)}_{{\boldsymbol{x}}}a^{(m)}_{{\boldsymbol{x}}}$.
In other words, $p^{(0)}_{{\boldsymbol{x}}}$ is a linear combination of the
$(m+1)$ information symbols in the same row.

Repair of Information Node $s$ for $s\in[0,m]$:

  * •

If $s\in[m]$, set helper nodes to be
${\mathcal{H}}=\\{{\boldsymbol{a}}^{(i)}:i\in[0,m]\setminus\\{s\\}\\}\cup\\{{\boldsymbol{p}}^{(m-s)},{\boldsymbol{p}}^{(m-s+1)}\\}$.

    * –

From ${\boldsymbol{a}}^{(i)}$ with $i<s$, we read ${\sf
R}_{{\boldsymbol{a}}^{(i)}}=\\{a^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$.

    * –

From ${\boldsymbol{a}}^{(i)}$ with $i>s$, we read ${\sf
R}_{{\boldsymbol{a}}^{(i)}}=\\{a^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}\\}$.

    * –

From ${\boldsymbol{p}}^{(i)}$ with $i\in\\{m-s,m-s+1\\}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(i)}}=\\{p^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$.

  * •

If $s=0$, set helper nodes to be
${\mathcal{H}}=\\{{\boldsymbol{a}}^{(i)}:i\in[m]\\}\cup\\{{\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(m)}\\}$.

    * –

From ${\boldsymbol{a}}^{(i)}$ with $i\in[m]$, we read ${\sf
R}_{{\boldsymbol{a}}^{(i)}}=\\{a^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$.

    * –

From ${\boldsymbol{p}}^{(0)}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(0)}}=\\{p^{(0)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$.

    * –

From ${\boldsymbol{p}}^{(m)}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(m)}}=\\{p^{(m)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}\\}$.

######  Theorem 4.

The repair scheme for Construction A is correct. That is, for $s\in[0,m]$, we
are able to determine ${\boldsymbol{a}}^{(s)}$ from all reads. Moreover, the
repair scheme has zero skip cost and optimal rebuilding ratio $1/2$.

###### Proof.

We prove for the case $s\in[m]$ and the cases $s=0$ can be similarly proved.

Recall that the reads from ${\boldsymbol{p}}^{(m-s)}$ and
${\boldsymbol{p}}^{(m-s+1)}$ are

$\displaystyle{\sf R}_{{\boldsymbol{p}}^{(m-s)}}$
$\displaystyle=\left\\{\sum_{i=0}^{m}\alpha_{\boldsymbol{x}}^{(i,j)}a^{(i)}_{{\boldsymbol{u}}_{i}}:{\boldsymbol{x}}\in{\mathcal{U}}\right\\},$
$\displaystyle{\sf R}_{{\boldsymbol{p}}^{(m-s+1)}}$
$\displaystyle=\left\\{\sum_{i=0}^{m}\alpha_{\boldsymbol{x}}^{(i,j)}a^{(i)}_{{\boldsymbol{u}}_{i}}:{\boldsymbol{x}}\in{\mathcal{U}}\right\\}.$

Here, let ${\mathcal{I}}_{1}$ and ${\mathcal{I}}_{2}$ be the information
symbols involved in the reads ${\sf R}_{{\boldsymbol{p}}^{(m-s)}}$ and ${\sf
R}_{{\boldsymbol{p}}^{(m-s+1)}}$, respectively.

For $s\in[m-1]$, we observe that

$\displaystyle{\boldsymbol{S}}_{m-s}$
$\displaystyle=({\boldsymbol{0}},{\boldsymbol{e}}_{m-s+1},\ldots,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\boldsymbol{e}}_{m}},\ldots,{\boldsymbol{d}}_{m-s-1}),$
$\displaystyle{\boldsymbol{S}}_{m-s+1}$
$\displaystyle=({\boldsymbol{0}},{\boldsymbol{e}}_{m-s+2},\ldots,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\boldsymbol{d}}_{1}},\ldots,{\boldsymbol{d}}_{m-s}),$

for $s=m$,
${\boldsymbol{S}}_{0}=({\boldsymbol{0}},{\boldsymbol{0}},\ldots,{\boldsymbol{0}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\boldsymbol{0}}})$,
${\boldsymbol{S}}_{1}=({\boldsymbol{0}},{\boldsymbol{e}}_{2},\ldots,{\boldsymbol{e}}_{m},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\boldsymbol{d}}_{1}})$,
where the highlighted positions in blue are the $s$-th entries. Using this
observation, we claim the following.

  * •

${\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}$ contains all information symbols
$a^{(s)}_{\boldsymbol{x}}$ with ${\boldsymbol{x}}\in\mathbb{F}_{2}^{m}$.
Indeed, if ${\boldsymbol{x}}\in{\mathcal{U}}$, since
${\boldsymbol{x}}+{\boldsymbol{e}}_{m}\in{\mathcal{U}}$, we have that
$a^{(s)}_{\boldsymbol{x}}\in{\mathcal{I}}_{1}$. Similarly, if
${\boldsymbol{x}}\in{\mathcal{L}}$, since
${\boldsymbol{x}}+{\boldsymbol{d}}_{1}\in{\mathcal{U}}$, we have that
$a^{(s)}_{\boldsymbol{x}}\in{\mathcal{I}}_{2}$.

  * •

If $i<s$, then ${\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}$ contains exactly all
information symbols $a^{(i)}_{\boldsymbol{x}}$ with
${\boldsymbol{x}}\in{\mathcal{U}}$. Indeed, in both ${\boldsymbol{S}}_{m-s}$
and ${\boldsymbol{S}}_{m-s+1}$, the $i$-th entries belong to ${\mathcal{U}}$.
Hence, we have that $a^{(i)}_{{\boldsymbol{u}}_{i}}$ always belong to
${\mathcal{U}}$.

  * •

If $i>s$, then ${\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}$ contains exactly all
information symbols $a^{(i)}_{\boldsymbol{x}}$ with
${\boldsymbol{x}}\in{\mathcal{L}}$. As before, we observe that in both
${\boldsymbol{S}}_{m-s}$ and ${\boldsymbol{S}}_{m-s+1}$, the $i$-th entries
belong to ${\mathcal{L}}$. Hence, we have that
$a^{(i)}_{{\boldsymbol{u}}_{i}}$ always belong to ${\mathcal{L}}$.

Therefore, using the reads ${\sf R}_{{\boldsymbol{a}}^{(i)}}~{}(i\neq s)$, we
eliminate all information symbols $a^{(i)}_{\boldsymbol{x}}$ with $i\neq s$
from the corresponding check sums and recover ${\boldsymbol{a}}^{(s)}$.

For the case of $s=0$, the reads from ${\boldsymbol{p}}^{(0)}$ and
${\boldsymbol{p}}^{(m)}$ are

$\displaystyle{\sf R}_{{\boldsymbol{p}}^{(0)}}$
$\displaystyle=\left\\{\sum_{i=0}^{m}\alpha_{\boldsymbol{x}}^{(i,j)}a^{(i)}_{{\boldsymbol{u}}_{i}}:{\boldsymbol{x}}\in{\mathcal{U}}\right\\},$
$\displaystyle{\sf R}_{{\boldsymbol{p}}^{(m)}}$
$\displaystyle=\left\\{\sum_{i=0}^{m}\alpha_{\boldsymbol{x}}^{(i,j)}a^{(i)}_{{\boldsymbol{u}}_{i}}:{\boldsymbol{x}}\in{\mathcal{L}}\right\\}.$

Here, let ${\mathcal{I}}_{1}$ and ${\mathcal{I}}_{2}$ be the information
symbols involved in the reads ${\sf R}_{{\boldsymbol{p}}^{(0)}}$ and ${\sf
R}_{{\boldsymbol{p}}^{(m)}}$, respectively.

For $s=0$, we observe that

$\displaystyle{\boldsymbol{S}}_{0}$
$\displaystyle=({\boldsymbol{0}},{\boldsymbol{0}},\ldots,{\boldsymbol{0}}),$
$\displaystyle{\boldsymbol{S}}_{m}$
$\displaystyle=({\boldsymbol{0}},{\boldsymbol{d}}_{1},\ldots,{\boldsymbol{d}}_{m-s}),$

  * •

Obviously, ${\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}$ contains all information
symbols $a^{(0)}_{\boldsymbol{x}}$ with
${\boldsymbol{x}}\in\mathbb{F}_{2}^{m}$.

  * •

If $i>0$, then ${\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}$ contains exactly all
information symbols $a^{(i)}_{\boldsymbol{x}}$ with
${\boldsymbol{x}}\in{\mathcal{U}}$. Indeed, in both ${\boldsymbol{S}}_{0}$ and
${\boldsymbol{S}}_{m}$, the $i$-th entries belong to ${\mathcal{U}}$. Hence,
we have that $a^{(i)}_{{\boldsymbol{u}}_{i}}$ always belong to
${\mathcal{U}}$.

Therefore, using the reads ${\sf R}_{{\boldsymbol{a}}^{(i)}}~{}(i\neq s)$, we
eliminate all information symbols $a^{(i)}_{\boldsymbol{x}}$ with $i\neq s$
from the corresponding check sums and recover ${\boldsymbol{a}}^{(s)}$.

Finally, to check that skip cost is zero, we observe that we always download
symbols in all rows in either ${\mathcal{U}}$ or ${\mathcal{L}}$, which are
consecutive. This also means that the rebuilding ratio is $1/2$. This is
optimal as the number of helper nodes is $m+2=k+1$. ∎

We illustrate Construction A with an example.

######  Example 1.

Let $m=2$. Hence, $M=4$, $N=6$ with three information nodes and three parity
nodes. We present the placement of the codesymbols in Fig. 1(b). To reduce
clutter and confusion, we index the information nodes with the symbols
$\\{\spadesuit,\heartsuit,\clubsuit\\}$ in place of $\\{0,1,2\\}$.
Additionally, instead of writing $a^{(i)}_{\boldsymbol{x}}$, we write it as
${\boldsymbol{x}}_{i}$. In other words, $00_{\spadesuit}$ represents the
information symbol $a^{(\spadesuit)}_{00}$. For the parity symbols, we use
${\boldsymbol{x}}_{i}\boxplus{\boldsymbol{y}}_{j}\boxplus{\boldsymbol{z}}_{k}$
to represent a linear combination of $a_{\boldsymbol{x}}^{(i)}$,
$a_{\boldsymbol{y}}^{(j)}$, and $a_{\boldsymbol{z}}^{(k)}$.

We illustrate the repair scheme assuming that the information node
corresponding to $\heartsuit$ (or $s=1$) has failed. According to our scheme,
the helper information nodes are $\spadesuit$ and $\clubsuit$, while the
helper parity nodes are ${\boldsymbol{p}}^{(1)}$ and ${\boldsymbol{p}}^{(2)}$.
Specifically, the reads from the parity nodes contain the following
information symbols.

  * •

From ${\boldsymbol{p}}^{(1)}$, we obtain

${\mathcal{I}}_{1}\triangleq\\{00_{\spadesuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}01_{\heartsuit}},10_{\clubsuit}\\}\cup\\{01_{\spadesuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}00_{\heartsuit}},11_{\clubsuit}\\}\,.$

  * •

From ${\boldsymbol{p}}^{(2)}$, we obtain

${\mathcal{I}}_{2}\triangleq\\{00_{\spadesuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}10_{\heartsuit}},11_{\clubsuit}\\}\cup\\{01_{\spadesuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}11_{\heartsuit}},10_{\clubsuit}\\}\,.$

Indeed, we check that

${\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}=\\{{\boldsymbol{x}}_{\spadesuit}:{\boldsymbol{x}}\in{\mathcal{U}}\\}\cup\\{{\boldsymbol{x}}_{\heartsuit}:{\boldsymbol{x}}\in{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{F}_{2}^{2}}\\}\cup\\{{\boldsymbol{x}}_{\clubsuit}:{\boldsymbol{x}}\in{\mathcal{L}}\\}\,,$

which corroborates with the claims in the proof of Theorem 4. Since we
download the information symbols
$\\{{\boldsymbol{x}}_{\spadesuit}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$ and
$\\{{\boldsymbol{x}}_{\clubsuit}:{\boldsymbol{x}}\in{\mathcal{L}}\\}$ from
${\boldsymbol{a}}^{(0)}$ and ${\boldsymbol{a}}^{(2)}$, respectively, we
recover all values in
$\\{{\boldsymbol{x}}_{\heartsuit}:{\boldsymbol{x}}\in{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{F}_{2}^{2}}\\}$,
i.e., ${\boldsymbol{a}}^{(1)}$. Since we download contents from rows in either
${\mathcal{U}}$ or ${\mathcal{L}}$, the skip cost is zero. In Fig. 1(b), we
illustrate the repair scheme of another information node corresponding to
$\clubsuit$ and the skip cost is zero too. ∎

It remains to choose the coefficients $\alpha^{(i,j)}_{\boldsymbol{x}}$ so as
to achieve the MDS property. As the proof is technical and similar to that in
[9], we defer the proof of the following proposition to Appendix A.

######  Proposition 1.

Fix $m$ and set $t=\lceil\frac{k}{2}\rceil$. If $q>2^{m}\binom{k-1}{t-1}^{2}$,
then there exist coefficients $\alpha^{(i,j)}_{\boldsymbol{x}}$ that belong to
$\mathbb{F}_{q}$ for $i,j\in[0,m]$ and ${\boldsymbol{x}}\in\mathbb{F}_{2}^{m}$
such that we can recover ${\boldsymbol{a}}^{(i)}~{}(i\in[0,m])$ from any
$k=m+1$ nodes.

######  Remark 1.

As mentioned earlier, the class of zigzag codes was proposed in [9]. Of
significance, we compare Construction A with Construction 1 in [9], which also
have a rebuilding ratio $1/2$. Similar to our construction, Construction 1
results in an array code with $2^{m}$ rows and $(m+1)$ information nodes.
However, Construction 1 uses only two parity check nodes
${\boldsymbol{p}}^{(0)}$ and ${\boldsymbol{p}}^{(1)}$ with corresponding
${\boldsymbol{S}}_{0}=({\boldsymbol{0}},\ldots,{\boldsymbol{0}})$ and
${\boldsymbol{S}}_{1}=({\boldsymbol{0}},{\boldsymbol{e}}_{1},\ldots,{\boldsymbol{e}}_{m})$
(see Fig. 1(a)). Notably, Construction 1 incurs a higher skip cost as
illustrated in Fig. 1(a). Generally, when $m$ is even, the skip cost is
$(m+2)\left(\sum^{m-1}_{i=0}2^{i}(2^{m-1-i}-1)+2^{m-1}\right)$; while when $m$
is odd, the skip cost is
$(m+2)\left(\sum^{m-1}_{i=0}2^{i}(2^{m-1-i}-1)+2^{m-1}-1\right)$. In both
cases, the skip cost is at least $m^{2}2^{m-1}$.

In contrast, Construction A has skip cost zero, but uses a significantly
higher number of redundant nodes. It remains open whether we can achieve
higher rates with zero skip cost and the same rebuilding ratio.

Next, we present another class of MDS array codes with zero skip cost.
Furthermore, the code rate is approximately $2/3$ for large values of $k$.

Construction B. Let $m\geq 2$ and set $k=m+1$. We present an $(M\times
N,k)$-MDS array code with $M=2^{m}$ packets and
$N=k+\left\lceil\frac{k}{2}\right\rceil+1=m+2+\left\lceil\frac{m+1}{2}\right\rceil$
nodes. Let $m^{\prime}=\left\lceil\frac{m+1}{2}\right\rceil$. Of these $N$
nodes, $k=m+1$ of them are systematic nodes
${\boldsymbol{a}}^{(0)},{\boldsymbol{a}}^{(1)}\ldots,{\boldsymbol{a}}^{(m)}$,
while the remaining $m^{\prime}$ are parity nodes
${\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(1)},\ldots,{\boldsymbol{p}}^{(m^{\prime})}$.
Now, instead of indexing the rows with $[M]$, we index them using the
$M=2^{m}$ bitstrings in $\mathbb{F}_{2}^{m}$. Here, the rows are arranged in
lexicographic order. Moreover, for convenience, we introduce the following
notation for certain vectors in $\mathbb{F}_{2}^{m}$:

  * •

As with Construction A, we use the notation ${\mathcal{U}}$ and
${\mathcal{L}}$ for the set of bitstrings starting with zero and one,
respectively. Furthermore, we use ${\mathcal{U}}^{\prime}$ denotes the set of
bitstrings starting with $``00"$ and $``11"$ and
${\mathcal{L}}^{\prime}=\mathbb{F}_{2}^{m}\setminus{\mathcal{U}}^{\prime}$.
Given the lexicographic order, we observe that the first and second halves of
the array are indexed by strings in ${\mathcal{U}}$ and ${\mathcal{L}}$,
respectively. In addition, the first quarter and the last quarter of the array
are indexed by strings in ${\mathcal{U}}^{\prime}$, the middle of the array is
indexed by strings in ${\mathcal{L}}^{\prime}$.

Contents of systematic columns: For $j\in[0,m]$, we simply set
${\boldsymbol{a}}^{(j)}=\left(a^{(j)}_{{\boldsymbol{x}}}\right)_{{\boldsymbol{x}}\in\mathbb{F}_{2}^{m}}$.

Contents of parity columns: For $j\in[0,m^{\prime}]$, we set
${\boldsymbol{p}}^{(j)}=\left(p^{(j)}_{{\boldsymbol{x}}}\right)_{{\boldsymbol{x}}\in\mathbb{F}_{2}^{m}}$
and our task is to determine the parity sum $p^{(j)}_{{\boldsymbol{x}}}$ in
terms of the $a^{(j)}_{\boldsymbol{x}}$’s. Now, in what follows, each parity
sum in ${\boldsymbol{p}}^{(j)}$ is a linear combination $m+1$ information
symbols and is determined by an $(m+1)$-tuple ${\boldsymbol{S}}_{j}$.

  * •

Set ${\boldsymbol{S}}_{0}$ to be $({\boldsymbol{0}},\ldots,{\boldsymbol{0}})$
and
$S_{1}=\\{{\boldsymbol{0}},\bf{\boldsymbol{d}}_{m},{\boldsymbol{e}}_{2},{\boldsymbol{e}}_{3},\ldots,{\boldsymbol{e}}_{m}\\}$.

  * •

For $j\in[2,m^{\prime}-1]$, we set

$S_{j}=\\{{\boldsymbol{0}},{\boldsymbol{e}}_{m-2j+3},{\boldsymbol{e}}_{m-2j+4},\ldots,{\boldsymbol{e}}_{m},\underbrace{{\boldsymbol{d}}_{m}}_{2j-th},{\boldsymbol{e}}_{2},\ldots,{\boldsymbol{e}}_{m-2j+2}\\},$

where ${\boldsymbol{d}}_{m}$ is the $2j$-th element of set
${\boldsymbol{S}}_{j}$. For example, if $j=2$, we have
${\boldsymbol{S}}_{2}=\\{{\boldsymbol{0}},{\boldsymbol{e}}_{m-1},{\boldsymbol{e}}_{m},\bf
d_{m},{\boldsymbol{e}}_{2},\ldots,e_{m-2}\\}$; if $j=3$,
${\boldsymbol{S}}_{3}=\\{{\boldsymbol{0}},{\boldsymbol{e}}_{m-3},{\boldsymbol{e}}_{m-2},{\boldsymbol{e}}_{m-1},{\boldsymbol{e}}_{m},\bf
d_{m},{\boldsymbol{e}}_{2},\ldots,e_{m-4}\\}$.

  * •

For the last parity columns,
$S_{m^{\prime}}=\\{{\boldsymbol{0}},{\boldsymbol{d}}_{2},{\boldsymbol{d}}_{3},\ldots,{\boldsymbol{d}}_{m},{\boldsymbol{d}}_{1}\\}$.

In particular, if $m^{\prime}=2$, we choose
$S_{1}=\\{{\boldsymbol{0}},\bf{\boldsymbol{d}}_{m},{\boldsymbol{e}}_{2},{\boldsymbol{e}}_{3},\ldots,{\boldsymbol{e}}_{m}\\}$
and
$S_{2}=\\{{\boldsymbol{0}},{\boldsymbol{d}}_{2},{\boldsymbol{d}}_{3},\ldots,{\boldsymbol{d}}_{m},{\boldsymbol{d}}_{1}\\}$.

  * •

Similar to the Construction A, we use the tuple ${\boldsymbol{S}}_{j}$ to
generate a parity column ${\boldsymbol{p}}^{(j)}$. If
${\boldsymbol{S}}_{j}=({\boldsymbol{v}}_{0},\ldots,{\boldsymbol{v}}_{m})$ and
we consider row ${\boldsymbol{x}}$, we set
${\boldsymbol{u}}_{i}={\boldsymbol{x}}+{\boldsymbol{v}}_{i}$ and define
$p^{(j)}_{{\boldsymbol{x}}}=\sum^{m}_{i=0}\alpha^{(i,j)}_{{\boldsymbol{x}}}a^{(i)}_{{\boldsymbol{u}}_{i}}$
for some choice of coefficients
$\alpha^{(i,j)}_{{\boldsymbol{x}}}\in\mathbb{F}_{q}$

Repair of Information Node $s$ for $s\in[0,m]$:

  * •

If $s\in[m-1]$ satisfies $2\nmid s$, set helper nodes to be
${\mathcal{H}}=\\{{\boldsymbol{a}}^{(i)}:i\in[0,m]\setminus\\{s\\}\\}\cup\\{{\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(\frac{s+1}{2})}\\}$.

    * –

From ${\boldsymbol{a}}^{(i)}$, we read ${\sf
R}_{{\boldsymbol{a}}^{(i)}}=\\{a^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$.

    * –

From ${\boldsymbol{p}}^{(i)}$ with $i\in\\{0,\frac{s+1}{2}\\}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(i)}}=\\{p^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$.

  * •

If $s\in[m-1]$ satisfies $2\mid s$, set helper nodes to be
${\mathcal{H}}=\\{{\boldsymbol{a}}^{(i)}:i\in[0,m]\setminus\\{s\\}\\}\cup\\{{\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(\frac{s}{2})}\\}$.

    * –

From ${\boldsymbol{a}}^{(i)}$, we read ${\sf
R}_{{\boldsymbol{a}}^{(i)}}=\\{a^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}^{\prime}\\}$.

    * –

From ${\boldsymbol{p}}^{(i)}$ with $i\in\\{0,\frac{s}{2}\\}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(i)}}=\\{p^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}^{\prime}\\}$.

  * •

If $s=0$, set the helper nodes to be
${\mathcal{H}}=\\{{\boldsymbol{a}}^{(i)}:i\in[m]\\}\cup\\{{\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(m^{\prime})}\\}$.

    * –

From ${\boldsymbol{a}}^{(i)}$ with $i\in[m]$, we read ${\sf
R}_{{\boldsymbol{a}}^{(i)}}=\\{a^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$.

    * –

From ${\boldsymbol{p}}^{(0)}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(0)}}=\\{p^{(0)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$.

    * –

From ${\boldsymbol{p}}^{(m^{\prime})}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(m)}}=\\{p^{(m^{\prime})}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}\\}$.

  * •

If $s=m$, set the helper nodes to be
${\mathcal{H}}=\\{{\boldsymbol{a}}^{(i)}:i\in[m]\\}\cup\\{{\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(m^{\prime})}\\}$.

    * –

From ${\boldsymbol{a}}^{(i)}$ with $i\in[m]$, we read ${\sf
R}_{{\boldsymbol{a}}^{(i)}}=\\{a^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}^{\prime}\\}$.

    * –

From ${\boldsymbol{p}}^{(i)}$ with $i\\{0,m^{\prime}\\}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(m^{\prime})}}=\\{p^{(0)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}^{\prime}\\}$.

The construction of systematic columns is similar to the Construction A. The
difference between Construction A and Construction B is the construction of
the parity columns.

######  Theorem 5.

The repair scheme for Construction B is correct. That is, for $s\in[0,m]$, we
are able to determine ${\boldsymbol{a}}^{(s)}$ from all reads. Moreover, the
repair scheme has zero skip cost and optimal rebuilding ratio $1/2$.
Additionally, the code rate of MDS array codes from Construction B is
$\frac{m+1}{m+2+\lceil\frac{m+1}{2}\rceil}$, which is approximately $2/3$.

###### Proof.

We will give the proof of the case $s\in[2,m-1]$, the other cases of
$s\in\\{0,m\\}$can be proved similarly. The proof of case $s\in[1,m-1]$ will
be divided into two subcases.

Case(1): For the case $2\nmid s$, we read the symbols from
${\boldsymbol{p}}^{(0)}$ and ${\boldsymbol{p}}^{\frac{(s+1)}{2})}$ are

$\displaystyle{\sf R}_{{\boldsymbol{p}}^{(0)}}$
$\displaystyle=\left\\{\sum_{i=0}^{m}\alpha_{\boldsymbol{x}}^{(i,j)}a^{(i)}_{{\boldsymbol{u}}_{i}}:{\boldsymbol{x}}\in{\mathcal{U}}\right\\},$
$\displaystyle{\sf R}_{{\boldsymbol{p}}^{(s+1)/2}}$
$\displaystyle=\left\\{\sum_{i=0}^{m}\alpha_{\boldsymbol{x}}^{(i,j)}a^{(i)}_{{\boldsymbol{u}}_{i}}:{\boldsymbol{x}}\in{\mathcal{U}}\right\\}.$

Here, let ${\mathcal{I}}_{1}$ and ${\mathcal{I}}_{2}$ be the information
symbols involved in the reads ${\sf R}_{{\boldsymbol{p}}^{(0)}}$ and ${\sf
R}_{{\boldsymbol{p}}^{(s+1)/2}}$, respectively.

We observe that

$\displaystyle{\boldsymbol{S}}_{0}$
$\displaystyle=({\boldsymbol{0}},{\boldsymbol{0}},\ldots,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{{\boldsymbol{0}}}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{{\boldsymbol{0}}}},\ldots,{\boldsymbol{0}}),$
(1) $\displaystyle{\boldsymbol{S}}_{\frac{s+1}{2}}$
$\displaystyle=\\{{\boldsymbol{0}},{\boldsymbol{e}}_{m-s+2},{\boldsymbol{e}}_{m-s+3},\ldots,{\boldsymbol{e}}_{m},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\boldsymbol{d}}_{m}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\boldsymbol{e}}_{2}},\ldots,{\boldsymbol{e}}_{m-s+1}\\}.$
(2)

when $s=1$,
${\boldsymbol{S}}_{0}=({\boldsymbol{0}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\boldsymbol{0}}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\boldsymbol{0}}},\ldots,{\boldsymbol{0}})$
and
$S_{1}=\\{{\boldsymbol{0}},\bf{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\boldsymbol{d}}_{m}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\boldsymbol{e}}_{2}},{\boldsymbol{e}}_{3},\ldots,{\boldsymbol{e}}_{m}\\}$,
where the highlighted positions in blue are the $s$-th entries. Hence, with a
similar discussion as Theorem 4, we have the following.

  * •

${\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}$ contains all information symbols
$a^{(s)}_{\boldsymbol{x}}$ with ${\boldsymbol{x}}\in\mathbb{F}_{2}^{m}$.

  * •

If $i\in\\{0,\ldots,k\\}\setminus s$, then
${\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}$ contains exactly all information
symbols $a^{(i)}_{\boldsymbol{x}}$ with ${\boldsymbol{x}}\in{\mathcal{U}}$.
Indeed, in both ${\boldsymbol{S}}_{0}$ and ${\boldsymbol{S}}_{(s+1)/2}$, the
$i$-th entries belong to ${\mathcal{U}}$. Hence, we have that
$a^{(i)}_{{\boldsymbol{u}}_{i}}$ always belong to ${\mathcal{U}}$.

Case(2): For the case $2\nmid s$, we read the symbols from
${\boldsymbol{p}}^{(0)}$ and ${\boldsymbol{p}}^{\frac{(s+1)}{2})}$ are

$\displaystyle{\sf R}_{{\boldsymbol{p}}^{(0)}}$
$\displaystyle=\left\\{\sum_{i=0}^{m}\alpha_{\boldsymbol{x}}^{(i,j)}a^{(i)}_{{\boldsymbol{u}}_{i}}:{\boldsymbol{x}}\in{\mathcal{L}}^{\prime}\right\\},$
$\displaystyle{\sf R}_{{\boldsymbol{p}}^{(s+1)/2}}$
$\displaystyle=\left\\{\sum_{i=0}^{m}\alpha_{\boldsymbol{x}}^{(i,j)}a^{(i)}_{{\boldsymbol{u}}_{i}}:{\boldsymbol{x}}\in{\mathcal{L}}^{\prime}\right\\}.$

From equations (1) and (2), the highlighted positions in red are the s-th
entries. Hence, with a similar discussion as Theorem 4, we have the following.

  * •

${\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}$ contains all information symbols
$a^{(s)}_{\boldsymbol{x}}$ with ${\boldsymbol{x}}\in\mathbb{F}_{2}^{m}$. Here,
for a ${\boldsymbol{x}}\in{\mathcal{U}}^{\prime}$, if
${\boldsymbol{y}}\in{\mathcal{U}}^{\prime}$, we have
${\boldsymbol{x}}+{\boldsymbol{y}}\in{\mathcal{U}}^{\prime}$; if
${\boldsymbol{y}}\in{\mathcal{L}}^{\prime}$, we have
${\boldsymbol{x}}+{\boldsymbol{y}}\in{\mathcal{L}}^{\prime}$. Similarly, for a
${\boldsymbol{x}}\in{\mathcal{L}}^{\prime}$, if
${\boldsymbol{y}}\in{\mathcal{L}}^{\prime}$, we have
${\boldsymbol{x}}+{\boldsymbol{y}}\in{\mathcal{U}}^{\prime}$. Obviously,
$\\{{\boldsymbol{e}}_{m-s+2},\ldots,{\boldsymbol{e}}_{m},{\boldsymbol{d}}_{m},{\boldsymbol{e}}_{3},\ldots,{\boldsymbol{e}}_{m-s+1}\\}\subseteq{\mathcal{U}}^{\prime}$,
and ${\boldsymbol{e}}_{2}\in{\mathcal{L}}^{\prime}$.

  * •

If $i\in\\{0,\ldots,k\\}\setminus s$, then
${\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}$ contains exactly all information
symbols $a^{(i)}_{\boldsymbol{x}}$ with
${\boldsymbol{x}}\in{\mathcal{L}}^{\prime}$. Indeed, in both
${\boldsymbol{S}}_{0}$ and ${\boldsymbol{S}}_{(s+1)/2}$, the $i+1$-th entries
belong to ${\mathcal{L}}^{\prime}$. Hence, we have that
$a^{(i)}_{{\boldsymbol{u}}_{i}}$ always belong to ${\mathcal{L}}^{\prime}$.

The cases $s\in\\{0,m\\}$ can be proved in a similar way. Therefore, using the
reads ${\sf R}_{{\boldsymbol{a}}^{(i)}}~{}(i\neq s)$, we eliminate all
information symbols $a^{(i)}_{\boldsymbol{x}}$ with $i\neq s$ from the
corresponding check sums and recover ${\boldsymbol{a}}^{(s)}$.

It is clear that the skip cost of this repair scheme is zero, as we
consistently download symbols from all consecutive rows in either
${\mathcal{U}}$ or ${\mathcal{L}}^{\prime}$. Consequently, the rebuilding
ratio stands at $\frac{m+1}{m+2+\lceil\frac{m+1}{2}\rceil}$. As $m$ increases,
the rebuilding ratio approaches $\frac{2}{3}$. Furthermore, this is optimal as
the number of helper nodes is $m+2=k+1$.

∎

| ${\boldsymbol{a}}^{(0)}$ | ${\boldsymbol{a}}^{(1)}$ | ${\boldsymbol{a}}^{(2)}$ | ${\boldsymbol{a}}^{(3)}$ | ${\boldsymbol{p}}^{(0)}$ | ${\boldsymbol{p}}^{(1)}$ | ${\boldsymbol{p}}^{(2)}$
---|---|---|---|---|---|---|---
| $\spadesuit$ | $\heartsuit$ | $\clubsuit$ | $\diamondsuit$ | ${\boldsymbol{S}}_{0}=({\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}})$ | ${\boldsymbol{S}}_{1}=({\boldsymbol{0}},{\boldsymbol{d}}_{3},{\boldsymbol{e}}_{2},{\boldsymbol{e}}_{3})$ | ${\boldsymbol{S}}_{2}=({\boldsymbol{0}},{\boldsymbol{d}}_{2},{\boldsymbol{d}}_{3},{\boldsymbol{d}}_{1})$
$000$ | $000_{\spadesuit}$ | $000_{\heartsuit}$ | $000_{\clubsuit}$ | $000_{\diamondsuit}$ | $000_{\spadesuit}\boxplus 000_{\heartsuit}\boxplus 000_{\clubsuit}\boxplus 000_{\diamondsuit}$ | $000_{\spadesuit}\boxplus 111_{\heartsuit}\boxplus 010_{\clubsuit}\boxplus 001_{\diamondsuit}$ | $000_{\spadesuit}\boxplus 110_{\heartsuit}\boxplus 111_{\clubsuit}\boxplus 100_{\diamondsuit}$
$001$ | $001_{\spadesuit}$ | $001_{\heartsuit}$ | $001_{\clubsuit}$ | $001_{\diamondsuit}$ | $001_{\spadesuit}\boxplus 001_{\heartsuit}\boxplus 001_{\clubsuit}\boxplus 001_{\diamondsuit}$ | $001_{\spadesuit}\boxplus 110_{\heartsuit}\boxplus 011_{\clubsuit}\boxplus 000_{\diamondsuit}$ | $001_{\spadesuit}\boxplus 111_{\heartsuit}\boxplus 110_{\clubsuit}\boxplus 101_{\diamondsuit}$
$010$ | $010_{\spadesuit}$ | $010_{\heartsuit}$ | $010_{\clubsuit}$ | $010_{\diamondsuit}$ | $010_{\spadesuit}\boxplus 010_{\heartsuit}\boxplus 010_{\clubsuit}\boxplus 010_{\diamondsuit}$ | $010_{\spadesuit}\boxplus 101_{\heartsuit}\boxplus 000_{\clubsuit}\boxplus 011_{\diamondsuit}$ | $010_{\spadesuit}\boxplus 100_{\heartsuit}\boxplus 101_{\clubsuit}\boxplus 110_{\diamondsuit}$
$011$ | $011_{\spadesuit}$ | $011_{\heartsuit}$ | $011_{\clubsuit}$ | $011_{\diamondsuit}$ | $011_{\spadesuit}\boxplus 011_{\heartsuit}\boxplus 011_{\clubsuit}\boxplus 011_{\diamondsuit}$ | $011_{\spadesuit}\boxplus 100_{\heartsuit}\boxplus 001_{\clubsuit}\boxplus 010_{\diamondsuit}$ | $011_{\spadesuit}\boxplus 101_{\heartsuit}\boxplus 100_{\clubsuit}\boxplus 111_{\diamondsuit}$
$100$ | $100_{\spadesuit}$ | $100_{\heartsuit}$ | $100_{\clubsuit}$ | $100_{\diamondsuit}$ | $100_{\spadesuit}\boxplus 100_{\heartsuit}\boxplus 100_{\clubsuit}\boxplus 100_{\diamondsuit}$ | $100_{\spadesuit}\boxplus 011_{\heartsuit}\boxplus 110_{\clubsuit}\boxplus 101_{\diamondsuit}$ | $100_{\spadesuit}\boxplus 010_{\heartsuit}\boxplus 011_{\clubsuit}\boxplus 000_{\diamondsuit}$
$101$ | $001_{\spadesuit}$ | $101_{\heartsuit}$ | $101_{\clubsuit}$ | $101_{\diamondsuit}$ | $101_{\spadesuit}\boxplus 101_{\heartsuit}\boxplus 101_{\clubsuit}\boxplus 101_{\diamondsuit}$ | $101_{\spadesuit}\boxplus 010_{\heartsuit}\boxplus 111_{\clubsuit}\boxplus 100_{\diamondsuit}$ | $101_{\spadesuit}\boxplus 011_{\heartsuit}\boxplus 010_{\clubsuit}\boxplus 001_{\diamondsuit}$
$110$ | $110_{\spadesuit}$ | $110_{\heartsuit}$ | $110_{\clubsuit}$ | $110_{\diamondsuit}$ | $110_{\spadesuit}\boxplus 110_{\heartsuit}\boxplus 110_{\clubsuit}\boxplus 110_{\diamondsuit}$ | $110_{\spadesuit}\boxplus 001_{\heartsuit}\boxplus 100_{\clubsuit}\boxplus 111_{\diamondsuit}$ | $110_{\spadesuit}\boxplus 000_{\heartsuit}\boxplus 001_{\clubsuit}\boxplus 010_{\diamondsuit}$
$111$ | $111_{\spadesuit}$ | $111_{\heartsuit}$ | $111_{\clubsuit}$ | $111_{\diamondsuit}$ | $111_{\spadesuit}\boxplus 111_{\heartsuit}\boxplus 111_{\clubsuit}\boxplus 111_{\diamondsuit}$ | $111_{\spadesuit}\boxplus 000_{\heartsuit}\boxplus 101_{\clubsuit}\boxplus 110_{\diamondsuit}$ | $111_{\spadesuit}\boxplus 001_{\heartsuit}\boxplus 000_{\clubsuit}\boxplus 011_{\diamondsuit}$
Figure 3:  Example of a $(8\times 7,4)$-MDS array code described by
Construction B with $m=3$ (see Section III). Suppose information node
${\boldsymbol{a}}^{(2)}$ (highlighted in red) fails. We contact nodes
${\boldsymbol{a}}^{(0)}$, ${\boldsymbol{a}}^{(1)}$, ${\boldsymbol{a}}^{(3)}$,
${\boldsymbol{p}}^{(0)}$ and ${\boldsymbol{p}}^{(1)}$ and read the contents in
blue. Here, the skip cost is zero.

######  Example 2.

Let $m=3$. Hence, $M=8$ and $N=7$. We consider MDS array code with four
systematic information columns three parity columns is as follows. The
placement of codesymbols is presented as Fig 3. Similar to the Example 1, we
index the information nodes with use the symbols
$\\{\spadesuit,\heartsuit,\clubsuit,\diamondsuit\\}$ in place of
$\\{0,1,2,3\\}$. Additionally, instead of writing $a^{(i)}_{\boldsymbol{x}}$,
we write it as $\boldsymbol{x}_{i}$. In other words, $000_{\spadesuit}$
represents the information symbol $a^{(\spadesuit)}_{000}$. For the parity
symbols, we use
${\boldsymbol{x}}_{i}\boxplus{\boldsymbol{y}}_{j}\boxplus{\boldsymbol{z}}_{k}\boxplus{\boldsymbol{w}}_{t}$
to represent a linear combination of $a_{\boldsymbol{x}^{(i)}}$,
$a_{\boldsymbol{y}^{(j)}}$, $a_{\boldsymbol{z}^{(k)}}$, and
$a_{\boldsymbol{w}^{(t)}}$ .

Assume that the information node corresponding to $\clubsuit$ (or $s=1$) in
Fig. 3(a) has failed. From our scheme, the helper information nodes are
$\spadesuit$, $\heartsuit$, and $\diamondsuit$, while the helper parity nodes
are ${\boldsymbol{p}}^{(0)}$ and ${\boldsymbol{p}}^{(1)}$. Specifically, the
reads from the parity nodes contain the following information symbols.

  * •

From $\boldsymbol{p}^{(0)}$, we obtain

$\displaystyle\mathcal{I}_{1}$ $\displaystyle\triangleq$
$\displaystyle\\{010_{\spadesuit},010_{\heartsuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}010_{\clubsuit}},010_{\diamondsuit}\\}\cup\\{011_{\spadesuit},011_{\heartsuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}011_{\clubsuit}},011_{\diamondsuit}\\}\cup\\{100_{\spadesuit},100_{\heartsuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}100_{\clubsuit}},100_{\diamondsuit}\\}\cup\\{101_{\spadesuit},101_{\heartsuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}101_{\clubsuit}},101_{\diamondsuit}\\}$

  * •

From $\boldsymbol{p}^{(1)}$, we obtain

$\displaystyle\mathcal{I}_{2}$ $\displaystyle\triangleq$
$\displaystyle\\{010_{\spadesuit},101_{\heartsuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}000_{\clubsuit}},011_{\diamondsuit}\\}\cup\\{011_{\spadesuit},100_{\heartsuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}001_{\clubsuit}},010_{\diamondsuit}\\}\
\cup\\{100_{\spadesuit},011_{\heartsuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}110_{\clubsuit}},101_{\diamondsuit}\\}\cup\\{101_{\spadesuit},010_{\heartsuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}111_{\clubsuit}},100_{\diamondsuit}\\}$

Indeed, we check that

$\mathcal{I}_{1}\cup\mathcal{I}_{2}=\\{\boldsymbol{x}_{\spadesuit}:\boldsymbol{x}\in\mathcal{L}^{\prime}\\}\cup\\{\boldsymbol{x}_{\heartsuit}:\boldsymbol{x}\in\mathcal{L}^{\prime}\\}\cup\\{\boldsymbol{x}_{\clubsuit}:\boldsymbol{x}\in\mathbb{F}_{2}^{3}\\}\cup\\{\boldsymbol{x}_{\diamondsuit}:x\in\mathcal{L^{\prime}}\\},$

which corroborates with the claims in the proof of Theorem 5. Since we
download the information symbols
$\\{\boldsymbol{x}_{\spadesuit}:\boldsymbol{x}\in\mathcal{L^{\prime}}\\}$ ,
$\\{\boldsymbol{x}_{\heartsuit}:\boldsymbol{x}\in\mathcal{L^{\prime}}\\}$ and
$\\{\boldsymbol{x}_{\diamondsuit}:\boldsymbol{x}\in\mathcal{L^{\prime}}\\}$
from $\boldsymbol{a}^{(0)}$, $\boldsymbol{a}^{(1)}$, and
$\boldsymbol{a}^{(3)}$ respectively, we recover all values in
$\\{\boldsymbol{x}_{\clubsuit}:\boldsymbol{x}\in\mathbb{F}_{2}^{3}\\}$, i.e.,
$\boldsymbol{a}^{(2)}$. Since we download contents from rows
$\mathcal{L^{\prime}}$, the skip cost is zero.

Similarly, if information node $\heartsuit$ (${\boldsymbol{a}}^{(1)}$) is
erased. From Fig. 3, the helper information nodes are $\spadesuit$,
$\clubsuit$, and $\diamondsuit$, while the helper parity nodes also are
${\boldsymbol{p}}^{(0)}$ and ${\boldsymbol{p}}^{(1)}$. The reads from the
parity nodes contain the following information symbols.

  * •

From $\boldsymbol{p}^{(0)}$, we obtain

$\displaystyle\mathcal{I}_{1}$ $\displaystyle\triangleq$
$\displaystyle\\{000_{\spadesuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}000_{\heartsuit}},000_{\clubsuit},000_{\diamondsuit}\\}\cup\\{001_{\spadesuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}001_{\heartsuit}},001_{\clubsuit},001_{\diamondsuit}\\}\cup\\{010_{\spadesuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}010_{\heartsuit}},010_{\clubsuit},010_{\diamondsuit}\\}\cup\\{011_{\spadesuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}011_{\heartsuit}},011_{\clubsuit},011_{\diamondsuit}\\}$

  * •

From $\boldsymbol{p}^{(1)}$, we obtain

$\displaystyle\mathcal{I}_{2}$ $\displaystyle\triangleq$
$\displaystyle\\{000_{\spadesuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}111_{\heartsuit}},010_{\clubsuit},001_{\diamondsuit}\\}\cup\\{001_{\spadesuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}110_{\heartsuit}},011_{\clubsuit},000_{\diamondsuit}\\}\
\cup\\{010_{\spadesuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}101_{\heartsuit}},000_{\clubsuit},011_{\diamondsuit}\\}\cup\\{011_{\spadesuit},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}100_{\heartsuit}},001_{\clubsuit},010_{\diamondsuit}\\}$

Indeed, we check that

$\mathcal{I}_{1}\cup\mathcal{I}_{2}=\\{\boldsymbol{x}_{\spadesuit}:\boldsymbol{x}\in\mathcal{U}\\}\cup\\{\boldsymbol{x}_{\heartsuit}:\boldsymbol{x}\in\mathbb{F}_{2}^{3}\\}\cup\\{\boldsymbol{x}_{\clubsuit}:\boldsymbol{x}\in\mathcal{U}\\}\cup\\{\boldsymbol{x}_{\diamondsuit}:x\in\mathcal{U}\\}.$

Combining with nodes $\boldsymbol{p}^{(0)}$ and $\boldsymbol{p}^{(1)}$, it is
clear that we can recover all values in
$\\{\boldsymbol{x}_{\heartsuit}:\boldsymbol{x}\in\mathbb{F}_{2}^{3}\\}$ by
downloading the information symbols
$\\{\boldsymbol{x}_{\spadesuit}:\boldsymbol{x}\in\mathcal{L^{\prime}}\\}$,
$\\{\boldsymbol{x}_{\clubsuit}:\boldsymbol{x}\in\mathcal{L^{\prime}}\\}$, and
$\\{\boldsymbol{x}_{\diamondsuit}:\boldsymbol{x}\in\mathcal{L^{\prime}}\\}$
from $\boldsymbol{a}^{(0)}$, $\boldsymbol{a}^{(2)}$, and
$\boldsymbol{a}^{(3)}$.

Additionally, if node $\boldsymbol{a}^{(0)}$ is failed, we repair it by
reading $\\{p_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$ and
$\\{p_{\boldsymbol{x}}:x\in{\mathcal{L}}\\}$ from parity nodes
$\boldsymbol{p}^{(0)}$, $\boldsymbol{p}^{(2)}$ and
$\\{\boldsymbol{x}_{\heartsuit}:\boldsymbol{x}\in\mathcal{U}\\}$,
$\\{\boldsymbol{x}_{\clubsuit}:\boldsymbol{x}\in\mathcal{U}\\}$, and
$\\{\boldsymbol{x}_{\diamondsuit}:\boldsymbol{x}\in\mathcal{U}\\}$ from
$\boldsymbol{a}^{(0)}$, $\boldsymbol{a}^{(2)}$, and $\boldsymbol{a}^{(3)}$. If
node $\boldsymbol{a}^{(3)}$ is failed, we repair it by reading
$\\{p_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}^{\prime}\\}$ and
$\\{p_{\boldsymbol{x}}:x\in{\mathcal{L}}^{\prime}\\}$ from parity nodes
$\boldsymbol{p}^{(0)}$, $\boldsymbol{p}^{(2)}$ and
$\\{\boldsymbol{x}_{\heartsuit}:\boldsymbol{x}\in\mathcal{L^{\prime}}\\}$,
$\\{\boldsymbol{x}_{\clubsuit}:\boldsymbol{x}\in\mathcal{L^{\prime}}\\}$, and
$\\{\boldsymbol{x}_{\diamondsuit}:\boldsymbol{x}\in\mathcal{L^{\prime}}\\}$
from $\boldsymbol{a}^{(0)}$, $\boldsymbol{a}^{(2)}$, and
$\boldsymbol{a}^{(3)}$. Obviously, our repair scheme for each information node
have zero skip cost. ∎

Now, lower sub-packetization levels simplify implementation while distributing
the responsibility of providing repair information for a failed node across
multiple nodes. Consequently, large-scale distributed storage systems require
MDS array codes with small sub-packetization levels. Therefore, in the next
construction, we focus on MDS array codes with any information columns $k$ for
a fixed subpacketization level $M$. In other words, we construct MDS array
codes with small sub-packetization and zero skip cost.

We retain the previous notation $\mathcal{U}$, $\mathcal{U}^{\prime}$,
$\mathcal{L}$, and $\mathcal{L}^{\prime}$ in Construction B for the sake of
simplicity. Next, we present a generalization of Construction B, wherein the
number of information nodes $k$ does not depend on the sub-packetization $M$.

Construction C. Let $m\geq 2$ and $k\geq 2$ be positive integers. We present
an $(M\times N,k)$-MDS array code with $M=2^{m}$ packets and
$N=k+\left\lceil\frac{k}{2}\right\rceil+1$ nodes. Let
$m^{\prime}=\left\lceil\frac{k}{2}\right\rceil$. Of these $N$ nodes, $k$ of
them are systematic nodes
${\boldsymbol{a}}^{(0)},{\boldsymbol{a}}^{(1)}\ldots,{\boldsymbol{a}}^{(k-1)}$,
while the remaining $m^{\prime}$ are parity nodes
${\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(1)},\ldots,{\boldsymbol{p}}^{(m^{\prime})}$.

Contents of systematic columns: For $j\in[0,k-1]$, we simply set
${\boldsymbol{a}}^{(j)}=\left(a^{(j)}_{{\boldsymbol{x}}}\right)_{{\boldsymbol{x}}\in\mathbb{F}_{2}^{m}}$.

Contents of parity columns: For $j\in[0,m^{\prime}]$, we set
${\boldsymbol{p}}^{(j)}=\left(p^{(j)}_{{\boldsymbol{x}}}\right)_{{\boldsymbol{x}}\in\mathbb{F}_{2}^{m}}$.
Now, in what follows, each parity sum in ${\boldsymbol{p}}^{(j)}$ is a linear
combination $k$ information symbols and is determined by an $k$-tuple
${\boldsymbol{S}}_{j}$ for $j\in[m^{\prime}]$.

  * •

Set ${\boldsymbol{S}}_{0}$ to be $({\boldsymbol{0}},\ldots,{\boldsymbol{0}})$.

  * •

For $j\in[1,m^{\prime}-1]$, we set

$S_{j}=\\{{\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}},\ldots,{\boldsymbol{0}},\underbrace{{\boldsymbol{d}}_{m}}_{2j-th},{\boldsymbol{e}}_{2},{\boldsymbol{0}},\ldots,{\boldsymbol{0}}\\},$

where ${\boldsymbol{d}}_{m}$ is the $2j$-th element of set
${\boldsymbol{S}}_{j}$. For example, if $j=2$, we have
${\boldsymbol{S}}_{2}=\\{{\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}},\bf
d_{m},{\boldsymbol{e}}_{2},\ldots,{\boldsymbol{0}}\\}$; if $j=3$,
${\boldsymbol{S}}_{3}=\\{{\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}},\bf
d_{m},{\boldsymbol{e}}_{2},{\boldsymbol{0}},\ldots,{\boldsymbol{0}}\\}$.

  * •

For the last parity columns,
$S_{m^{\prime}}=\\{{\boldsymbol{0}},{\boldsymbol{d}}_{2},{\boldsymbol{d}}_{2},\ldots,{\boldsymbol{d}}_{2},{\boldsymbol{d}}_{1}\\}$.

In particular, if $m^{\prime}=2$, we choose
$S_{1}=\\{{\boldsymbol{0}},\bf{\boldsymbol{d}}_{m},{\boldsymbol{e}}_{2},{\boldsymbol{0}}\\}$
and
$S_{2}=\\{{\boldsymbol{0}},{\boldsymbol{d}}_{2},{\boldsymbol{d}}_{2},{\boldsymbol{d}}_{1}\\}$.

  * •

Similar to the Construction A, we use the tuple ${\boldsymbol{S}}_{j}$ to
generate a parity column ${\boldsymbol{p}}^{(j)}$. If
${\boldsymbol{S}}_{j}=({\boldsymbol{v}}_{0},\ldots,{\boldsymbol{v}}_{k-1})$
and we consider row ${\boldsymbol{x}}$, we set
${\boldsymbol{u}}_{i}={\boldsymbol{x}}+{\boldsymbol{v}}_{i}$ and define
$p^{(j)}_{{\boldsymbol{x}}}=\sum^{m}_{i=0}\alpha^{(i,j)}_{{\boldsymbol{x}}}a^{(i)}_{{\boldsymbol{u}}_{i}}$
for some choice of coefficients
$\alpha^{(i,j)}_{{\boldsymbol{x}}}\in\mathbb{F}_{q}$

Repair of Information Node $s$ for $s\in[0,k-1]$:

  * •

If $s\in[k-2]$ satisfies $2\nmid s$, set helper nodes to be
${\mathcal{H}}=\\{{\boldsymbol{a}}^{(i)}:i\in[0,k-1]\setminus\\{s\\}\\}\cup\\{{\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(\frac{s+1}{2})}\\}$.

    * –

From ${\boldsymbol{a}}^{(i)}$, we read ${\sf
R}_{{\boldsymbol{a}}^{(i)}}=\\{a^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$.

    * –

From ${\boldsymbol{p}}^{(i)}$ with $i\in\\{0,\frac{s+1}{2}\\}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(i)}}=\\{p^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$.

  * •

If $s\in[k-2]$ satisfies $2\mid s$, set helper nodes to be
${\mathcal{H}}=\\{{\boldsymbol{a}}^{(i)}:i\in[0,k-1]\setminus\\{s\\}\\}\cup\\{{\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(\frac{s}{2})}\\}$.

    * –

From ${\boldsymbol{a}}^{(i)}$, we read ${\sf
R}_{{\boldsymbol{a}}^{(i)}}=\\{a^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}^{\prime}\\}$.

    * –

From ${\boldsymbol{p}}^{(i)}$ with $i\in\\{0,\frac{s}{2}\\}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(i)}}=\\{p^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}^{\prime}\\}$.

  * •

If $s=0$, set the helper nodes to be
${\mathcal{H}}=\\{{\boldsymbol{a}}^{(i)}:i\in[k-1]\\}\cup\\{{\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(m^{\prime})}\\}$.

    * –

From ${\boldsymbol{a}}^{(i)}$ with $i\in[k-1]$, we read ${\sf
R}_{{\boldsymbol{a}}^{(i)}}=\\{a^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$.

    * –

From ${\boldsymbol{p}}^{(0)}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(0)}}=\\{p^{(0)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$.

    * –

From ${\boldsymbol{p}}^{(m^{\prime})}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(m^{\prime})}}=\\{p^{(m^{\prime})}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}\\}$.

  * •

If $s=m$, set the helper nodes to be
${\mathcal{H}}=\\{{\boldsymbol{a}}^{(i)}:i\in[k-1]\\}\cup\\{{\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(m^{\prime})}\\}$.

    * –

From ${\boldsymbol{a}}^{(i)}$ with $i\in[k-1]$, we read ${\sf
R}_{{\boldsymbol{a}}^{(i)}}=\\{a^{(i)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}^{\prime}\\}$.

    * –

From ${\boldsymbol{p}}^{(i)}$ with $i\\{0,m^{\prime}\\}$, we read ${\sf
R}_{{\boldsymbol{p}}^{(m^{\prime})}}=\\{p^{(0)}_{\boldsymbol{x}}:{\boldsymbol{x}}\in{\mathcal{L}}^{\prime}\\}$.

######  Theorem 6.

The repair scheme for Construction C is correct. That is, for $s\in[0,k-1]$,
we are able to determine ${\boldsymbol{a}}^{(s)}$ from all reads. Moreover,
the repair scheme has zero skip cost and optimal rebuilding ratio $1/2$.
Additionally, the code rate of MDS array codes from Construction C is
$\frac{k}{k+1+\lceil\frac{k}{2}\rceil}$, which is approximately $2/3$.

###### Proof.

The proof is similar to the proof of Theorem 5 so the proof is omitted. ∎

${\boldsymbol{a}}^{(0)}$ | ${\boldsymbol{a}}^{(1)}$ | ${\boldsymbol{a}}^{(2)}$ | ${\boldsymbol{a}}^{(3)}$ | ${\boldsymbol{a}}^{(4)}$ | ${\boldsymbol{a}}^{(5)}$ | ${\boldsymbol{p}}^{(0)}$ | ${\boldsymbol{p}}^{(1)}$ | ${\boldsymbol{p}}^{(2)}$ | ${\boldsymbol{p}}^{(4)}$
---|---|---|---|---|---|---|---|---|---
${\boldsymbol{S}}_{0}=({\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}})$ | ${\boldsymbol{S}}_{1}=({\boldsymbol{0}},{\boldsymbol{d}}_{2},{\boldsymbol{e}}_{2},{\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}})$ | ${\boldsymbol{S}}_{2}=({\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{0}},{\boldsymbol{d}}_{2},{\boldsymbol{e}}_{2},{\boldsymbol{0}})$ | ${\boldsymbol{S}}_{2}=({\boldsymbol{0}},{\boldsymbol{d}}_{2},{\boldsymbol{d}}_{2},{\boldsymbol{d}}_{2},{\boldsymbol{d}}_{2},{\boldsymbol{d}}_{1})$
$00_{0}$ | $00_{1}$ | $00_{2}$ | $00_{3}$ | $00_{4}$ | $00_{5}$ | $00_{0}\boxplus\cdots\boxplus 00_{5}$ | $00_{0}\boxplus 11_{1}\boxplus 01_{2}\boxplus 00_{3}\boxplus 00_{4}\boxplus 00_{5}$ | $00_{0}\boxplus 00_{1}\boxplus 00_{2}\boxplus 11_{3}\boxplus 01_{4}\boxplus 00_{5}$ | $00_{0}\boxplus 11_{1}\boxplus 11_{2}\boxplus 11_{3}\boxplus 11_{4}\boxplus 10_{5}$
$01_{0}$ | $01_{1}$ | $01_{2}$ | $01_{3}$ | $01_{4}$ | $01_{5}$ | $01_{0}\boxplus\cdots\boxplus 01_{5}$ | $01_{0}\boxplus 10_{1}\boxplus 00_{2}\boxplus 01_{3}\boxplus 01_{4}\boxplus 01_{5}$ | $01_{0}\boxplus 01_{1}\boxplus 01_{2}\boxplus 10_{3}\boxplus 00_{4}\boxplus 01_{5}$ | $01_{0}\boxplus 10_{1}\boxplus 10_{2}\boxplus 10_{3}\boxplus 10_{4}\boxplus 11_{5}$
$10_{0}$ | $10_{1}$ | $10_{2}$ | $10_{3}$ | $10_{4}$ | $10_{5}$ | $10_{0}\boxplus\cdots\boxplus 10_{5}$ | $10_{0}\boxplus 01_{1}\boxplus 11_{2}\boxplus 10_{3}\boxplus 10_{4}\boxplus 10_{5}$ | $10_{0}\boxplus 10_{1}\boxplus 10_{2}\boxplus 01_{3}\boxplus 11_{4}\boxplus 10_{5}$ | $10_{0}\boxplus 01_{1}\boxplus 01_{2}\boxplus 01_{3}\boxplus 01_{4}\boxplus 00_{5}$
$11_{0}$ | $11_{1}$ | $11_{2}$ | $11_{3}$ | $11_{4}$ | $11_{5}$ | $11_{0}\boxplus\cdots\boxplus 11_{5}$ | $11_{0}\boxplus 00_{1}\boxplus 10_{2}\boxplus 11_{3}\boxplus 11_{4}\boxplus 11_{5}$ | $11_{0}\boxplus 11_{1}\boxplus 11_{2}\boxplus 00_{3}\boxplus 10_{4}\boxplus 11_{5}$ | $11_{0}\boxplus 00_{1}\boxplus 00_{2}\boxplus 00_{3}\boxplus 00_{4}\boxplus 01_{5}$
Figure 4: Example of a $(4\times 10,6)$-MDS array code described by
Construction C with $m=2$ (see Section III). Suppose information node
${\boldsymbol{a}}^{(2)}$ (highlighted in red) fails. We contact nodes
${\boldsymbol{a}}^{(i)}$ for $i\in\\{0,1,3,4,5\\}$, ${\boldsymbol{p}}^{(0)}$
and ${\boldsymbol{p}}^{(1)}$ and read the contents in blue. Here, the skip
cost is zero.

######  Example 3.

Let $m=2$ and set $k=6$. Hence, $M=4$, $N=10$. We consider an MDS array code
with six systematic information columns three parity columns. The placement of
codesymbols is presented as Fig 4. Similarly to Example 1, we index the
information nodes using the symbols $a^{(i)}_{\boldsymbol{x}}$ for
$i\in\\{0,\ldots,5\\}$. Furthermore, instead of writing
$a^{(i)}_{\boldsymbol{x}}$, we write it as $\boldsymbol{x}_{i}$. For example,
$00_{0}$ represents the information symbol in information nodes $a^{(0)}$.

Assume that the information node ${\boldsymbol{a}}^{(2)}$ in Fig. 4 has
failed. In our scheme, the helper information nodes are
${\boldsymbol{a}}^{(i)}$ for $i\in\\{0,1,3,4,5\\}$ while the helper parity
nodes are ${\boldsymbol{p}}^{(0)}$ and ${\boldsymbol{p}}^{(1)}$. Specifically,
the reads from the parity nodes contain the following information symbols.

  * •

From $\boldsymbol{p}^{(0)}$, we obtain

$\displaystyle\mathcal{I}_{1}$
$\displaystyle\triangleq\\{01_{0},01_{1},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}01_{2}},01_{3},01_{4},01_{5}\\}\cup\\{10_{0},10_{1},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}01_{2}},10_{3},10_{4},10_{5}\\}$

  * •

From $\boldsymbol{p}^{(1)}$, we obtain

$\displaystyle\mathcal{I}_{2}$
$\displaystyle\triangleq\\{01_{0},10_{1},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}00_{2}},01_{3},01_{4},01_{5}\\}\cup\\{10_{0},01_{1},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}11_{2}},10_{3},10_{4},10_{5}\\}$

Indeed, we check that

${\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}=\\{{\boldsymbol{x}}_{i}:{\boldsymbol{x}}\in{\mathcal{L}}^{\prime},i\in[0,5]\setminus\\{2\\}\\}\cup\\{{\boldsymbol{x}}_{2}:{\boldsymbol{x}}\in{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{F}_{2}^{2}}\\}\,,$

Since we download the information symbols
$\\{{\boldsymbol{x}}_{i}:{\boldsymbol{x}}\in{\mathcal{U}}\\}$ from
${\boldsymbol{a}}^{(i)}$ for $i\in[0,5]\setminus\\{2\\}$, respectively, we
recovered all the values in
$\\{{\boldsymbol{x}}_{2}:{\boldsymbol{x}}\in{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{F}_{2}^{2}}\\}$,
i.e., ${\boldsymbol{a}}^{(2)}$. Since we download content only from the rows
in ${\mathcal{L}}^{\prime}$, the skip cost is zero.

Similarly, if the information node ${\boldsymbol{a}}^{(1)}$ is erased. From
Fig. 4, the helper information nodes are ${\boldsymbol{a}}^{(i)}$ for
$i\in[0,5]\setminus\\{1\\}$ , while the helper parity nodes are also
${\boldsymbol{p}}^{(0)}$ and ${\boldsymbol{p}}^{(1)}$.

  * •

From $\boldsymbol{p}^{(0)}$, we obtain

$\displaystyle\mathcal{I}_{1}$
$\displaystyle\triangleq\\{00_{0},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}00_{1}},00_{2},00_{3},00_{4},00_{5}\\}\cup\\{01_{0},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}01_{1}},01_{2},01_{3},01_{4},01_{5}\\}$

  * •

From $\boldsymbol{p}^{(1)}$, we obtain

$\displaystyle\mathcal{I}_{2}$
$\displaystyle\triangleq\\{00_{0},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}11_{1}},01_{2},00_{3},00_{4},00_{5}\\}\cup\\{01_{0},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}10_{1}},00_{2},01_{3},01_{4},01_{5}\\}$

By downloading the information symbols
$\\{\boldsymbol{x}_{i}:\boldsymbol{x}\in\mathcal{U}\\}$ from
${\boldsymbol{a}}^{(i)}$ for $i\in[0,5]\setminus\\{1\\}$, it is clear that we
can recover all values in
$\\{\boldsymbol{x}_{1}:\boldsymbol{x}\in\mathbb{F}_{2}^{2}\\}$. Furthermore,
we can check the repair scheme of other information nodes according to Fig. 4,
and their skip costs are zero also. ∎

##  IV SQS-Based Fractional Repetition Codes with Zero Skip Cost

In this section, we study fractional repetition codes with repair schemes that
incur zero skip cost. As discussed in Section II-B, to construct the resulting
array code, it suffices to specify the order of points in each block.
Therefore, in what follows, instead of writing blocks as unordered sets, we
write each block explicitly as a tuple.

Also, as previously discussed, we focus on fractional repetition codes
resulting from Steiner quadruple systems. Here, we describe two constructions.
In Section IV-A, we look at recursive constructions that yield two infinite
classes of SQS with zero skip cost. Later, in Section IV-B, we use the method
of differences to construct more SQS with other parameters. Here, our SQS
satisfy a more stringent property where every point-pair appears in at least
two different blocks.

###  IV-A Recursive Constructions

Here, our constructions follow closely the original proof by Hanani in 1960
[15]. Specifically, in that paper, Hanani provided six recursive constructions
that build a larger SQS from smaller ones. Here, we make modifications to two
of these recursive constructions so that the resulting SQS has locality two
and skip cost zero.

Construction D (Doubling Construction). Let $(V,{\mathcal{B}})$ be an ${\rm
SQS}(v)$ with $V=[v]$. We construct a ${\rm SQS}(2v)$-design on the point set
$[v]\times\\{0,1\\}$. The collection of blocks comprise two groups:

  * •

${\mathcal{B}}_{1}$ is the collection
$\\{((v_{1},i_{1}),(v_{2},i_{2}),(v_{3},i_{3}),(v_{4},i_{4})):\\{v_{1},v_{2},v_{3},v_{4}\\}~{}\in~{}{\mathcal{B}},~{}\sum_{j=1}^{4}i_{j}=0\pmod{2}\\}$.
In other words, ${\mathcal{B}}_{1}$ contains $8|{\mathcal{B}}|$ blocks.

  * •

${\mathcal{B}}_{2}$ is the collection
$\\{((v_{1},0),(v_{1},1),(v_{2},0),(v_{2},1)):\\{v_{1},v_{2}\\}\text{ is a
two-subset of }V\\}$. In other words, ${\mathcal{B}}_{2}$ contains
$\binom{N}{2}$ blocks.

Note that for any 3 elements
$\\{(v_{1},i_{1}),(v_{2},i_{2}),(v_{3},i_{3})\\}$, if $v_{1}\neq v_{2}\neq
v_{3}\neq v_{4}$ it is included in ${\mathcal{B}}_{1}$, and otherwise it is
included in ${\mathcal{B}}_{2}$. Hence, every subset of ${\rm SQS}(2v)$
containing $3$ element is contained in exactly one block.

Repair of Block ${\boldsymbol{b}}\in{\mathcal{B}}_{1}$: Then
${\boldsymbol{b}}$ is of the form
$((v_{1},i_{1}),(v_{2},i_{2}),(v_{3},i_{3}),(v_{4},i_{4}))$. Then we pick the
following reads and blocks.

  * •

${\sf R}_{1}=\\{(v_{1},i_{1}),(v_{2},i_{2})\\}$ in block
$((v_{1},i_{1}),(v_{2},i_{2}),(v_{3},1-i_{3}),(v_{4},1-i_{4}))$;

  * •

${\sf R}_{2}=\\{(v_{3},i_{3}),(v_{4},i_{4})\\}$ in block
$((v_{1},1-i_{1}),(v_{2},1-i_{2}),(v_{3},i_{3}),(v_{4},i_{4}))$.

Repair of Block ${\boldsymbol{b}}\in{\mathcal{B}}_{2}$: Then
${\boldsymbol{b}}$ is of the form $((v_{1},0),(v_{1},1),(v_{2},0),(v_{2},1))$.
Let $v_{3}\notin\\{v_{1},v_{2}\\}$ and we pick the following reads and blocks.

  * •

${\sf R}_{1}=\\{(v_{1},0),(v_{1},1)\\}$ in block
$((v_{1},0),(v_{1},1),(v_{3},0),(v_{3},1))$;

  * •

${\sf R}_{2}=\\{(v_{2},0),(v_{2},1)\\}$ in block
$((v_{3},0),(v_{3},1),(v_{2},0),(v_{2},1))$.

######  Theorem 7.

The repair scheme for Construction D is correct. That is, for
${\boldsymbol{b}}\in{\mathcal{B}}$, we are able to determine
${\boldsymbol{b}}$ from all reads. Moreover, the repair scheme has locality
two and skip cost zero.

###### Proof.

In all cases, we simply check that ${\sf R}_{1}\cup{\sf
R}_{2}={\boldsymbol{b}}$. The locality and skip cost properties are readily
verified. ∎

######  Example 4.

Let $v=4$ with $V=[4]$. Clearly, if ${\mathcal{B}}$ has the single block
$(1,2,3,4)$, we have an ${\rm SQS}(4)$. Construction D builds an ${\rm
SQS}(8)$. Then we have eight and six blocks in ${\mathcal{B}}_{1}$ and
${\mathcal{B}}_{2}$, respectively. We present the placement of the 14 blocks
in Fig. 2(b).

We illustrate the repair scheme assuming that the node / block
$(1_{0},1_{1},2_{0},2_{1})$ has failed. Since the block belongs to
${\mathcal{B}}_{2}$, we pick $v_{3}=3$ and read

  * •

${\sf R}_{1}=\\{1_{0},1_{1}\\}$ from the block $(1_{0},1_{1},3_{0},3_{1})$;

  * •

${\sf R}_{2}=\\{2_{0},2_{1}\\}$ from the block $(2_{0},2_{1},3_{0},3_{1})$.

For both blocks, we see the repair has zero skip cost.

In Fig. 2(b), we illustrate the repair for a block from ${\mathcal{B}}_{1}$
and we see that the skip cost is zero too. ∎

Similarly, we modify another Hanani’s recursive construction. Unfortunately,
the repair scheme becomes significantly involved as we have more cases to
handle. Also, due to space constraints, we only describe the ordering of
blocks and defer the details of the repair scheme to Appendix B.

Construction E ($(3v-2)$-Construction). Let $(V,{\mathcal{B}})$ be an ${\rm
SQS}(v)$ with $V=\\{\infty\\}\cup[N]$. We construct a ${\rm SQS}(3v-2)$-design
on the point set $\\{\infty\\}\cup[N]\times\\{0,1,2\\}$.

The collection of blocks comprises six groups:

  * •

${\mathcal{B}}_{1}$ is the collection
$\\{((i_{1},v_{1}),(i_{2},v_{2}),(i_{3},v_{3}),(i_{4},v_{4})):\\{v_{1},v_{2},v_{3},v_{4}\\}\in{\mathcal{B}},~{}\sum_{j=1}^{4}i_{j}=0\pmod{3}\\}$.
In other words, ${\mathcal{B}}_{1}$ contains $27|{\mathcal{B}}|$ blocks.

  * •

${\mathcal{B}}^{1}_{2}$ is the collection
$\\{((i_{1},v_{1}),\infty,(i_{3},v_{3}),(i_{2},v_{2})):\\{\infty,v_{1},v_{2},v_{3}\\}\in{\mathcal{B}},~{}v_{1}<v_{2}<v_{3},~{}\sum_{j=1}^{3}i_{j}=0\pmod{3},i_{1}=i_{2}\\}$
and

  * •

${\mathcal{B}}^{2}_{2}=\\{((i_{1}.v_{1}),\infty,(i_{2},v_{2}),(i_{3}.v_{3})):\\{\infty,v_{1},v_{2},v_{3}\\}\in{\mathcal{B}},~{}v_{1}<v_{2}<v_{3},\sum_{j=1}^{3}i_{j}=0\pmod{3}\\}$.
In other words, ${\mathcal{B}}^{1}_{1}\cup{\mathcal{B}}^{2}_{2}$ contains
$9|{\mathcal{B}}|$ blocks.

  * •

${\mathcal{B}}_{3}$ is the collection
$\\{((i,v_{1}),(i+1,v_{2}),(i,v_{3}),(i+2,v_{2})):\\{\infty,v_{1},v_{2},v_{3}\\}\in{\mathcal{B}},i\in\\{0,1,2\\}\\}$.
In other words, ${\mathcal{B}}_{3}$ contains $9|{\mathcal{B}}|$ blocks.

  * •

${\mathcal{B}}_{4}$ is the collection
$\\{((i,v_{1}),(i+1,v_{1}),(i+1,v_{2}),(i,v_{2})):\\{v_{1},v_{2}\\}\text{ is a
two-subset of }[0,N-1],i\in\\{0,1,2\\}\\}$, $v_{1}<v_{2}$. In other words,
${\mathcal{B}}_{4}$ contains $3\binom{N}{2}$ blocks.

  * •

${\mathcal{B}}_{5}$ is the collection
$\\{\infty,((0,v),(1,v),(2,v)):v\in[N]\\}$. In other words,
${\mathcal{B}}_{4}$ contains $N$ blocks.

######  Theorem 8.

The repair scheme for Construction E is correct. That is, for
${\boldsymbol{b}}\in{\mathcal{B}}$, we are able to determine
${\boldsymbol{b}}$ from all reads. Moreover, the repair scheme has locality
two and skip cost zero.

###  IV-B Method of Differences

Besides the quadruple systems described by Hanani, many other classes of SQS
were studied (see survey by Lindner and Rosa [16]). Of interest, we look at
SQS with large automorphism groups. For such systems of order $v$, the vertex
set is defined over the cyclic group $\mathbb{Z}_{v}$ or $\mathbb{Z}_{v-1}$
with a fixed point $\infty$. In other words, $V=\mathbb{Z}_{v}$ or
$V=\mathbb{Z}_{v-1}\cup\\{\infty\\}$. Then we have a set of base blocks
${\mathcal{S}}$ and all blocks are obtained via cyclic shifts of blocks in
${\mathcal{S}}$. In other words,
${\mathcal{B}}=\\{{\boldsymbol{b}}+i\,:\,{\boldsymbol{b}}\in{\mathcal{S}},i\in\mathbb{Z}_{v}\\}$
or
${\mathcal{B}}=\\{{\boldsymbol{b}}+i\,:\,{\boldsymbol{b}}\in{\mathcal{S}},i\in\mathbb{Z}_{v-1}\\}$.

Now, in this section, we provide quadruple systems with a stronger property.

######  Definition 3.

An ${\rm SQS}(v)$ $(V,{\mathcal{B}})$ has repeated adjacent pairs if for all
$2$-subsets $P$ of $V$, the pair $P$ appears as an adjacent pair in at least
two different blocks in ${\mathcal{B}}$.

Observe that if an ${\rm SQS}(v)$ has repeated adjacent pairs, then the ${\rm
SQS}(v)$ has locality two and skip cost zero. Next, we employ the method of
differences to construct such quadruple systems.

######  Definition 4.

Let $(a,b,c,d)$ be an ordered block defined over a cyclic group
$\mathbb{Z}_{g}$. Its difference list ${\rm diff}(a,b,c,d)$ is given by
$\langle|b-a|,|c-b|,|d-c|\rangle$. Here,
$|b-a|=\min\\{b-a\pmod{g},a-b\pmod{g}\\}$ and we use $\langle\cdot\rangle$ to
denote a multi-set.

Given a collection of blocks ${\mathcal{S}}$, we use ${\rm
diff}({\mathcal{S}})$ to denote
$\bigcup_{{\boldsymbol{b}}\in{\mathcal{S}}}{\rm diff}({\boldsymbol{b}})$ . As
with difference lists, we are taking a multi-union of multi-sets.

######  Proposition 2.

Consider a ${\rm SQS}(v)$ with base blocks ${\mathcal{S}}$.

  1. (i)

Suppose that $V=\mathbb{Z}_{v}$. If the difference $i$ appears at least twice
in ${\rm diff}({\mathcal{S}})$ for all $0<i<v/2$ and the difference $i$
appears at least once in ${\rm diff}({\mathcal{S}})$, then the ${\rm SQS}(v)$
has repeated adjacent pairs.

  2. (ii)

Suppose that $V=\mathbb{Z}_{v-1}\cup\\{\infty\\}$. If the difference $i$
appears at least twice in ${\rm diff}({\mathcal{S}})$ for all $0<i\leq(v-1)/2$
and $\infty$ appears at least two different blocks in ${\mathcal{S}}$, then
the ${\rm SQS}(v)$ has repeated adjacent pairs.

Due to space constraints, we defer the proof to Appendix C. Instead, we
provide an example for the case $v=26$.

######  Example 5.

We consider an ${\rm SQS}(26)$ defined over $\mathbb{Z}_{25}\cup\\{\infty\\}$.
Specifically, [17] provided the following 26 base blocks. Here, we reorder the
points in some blocks in order to fulfill the conditions of Proposition 2.

$\small\begin{array}[]{llllll}(0,1,3,\infty),&(0,4,11,\infty),&(0,5,13,\infty),&(0,6,15,\infty),&(0,1,2,5),\\\
(0,1,6,7),&(0,1,8,9),&(0,1,10,11),&(0,1,12,22),&(0,1,13,21),\\\
(0,1,14,23),&(0,2,4,12),&(0,2,6,9),&(0,2,7,17),&(0,2,8,22),\\\
(0,2,11,18),&(0,2,13,19)&(0,2,14,21),&(0,2,15,20),&(0,3,6,10),\\\
(0,3,8,17),&(0,3,9,14),&(0,3,12,18),&(0,3,13,20),&(0,14,8,4),\\\
(0,4,9,13).\end{array}$

For example, we observe that $\infty$ is in both the first two blocks. The
difference one appears twice in the block $(0,1,2,5)$, while the difference
five appears once in the block $(0,2,8,17)$ and once in the block
$(0,4,9,13)$.

###  IV-C Proof for Theorem 3

Recall that [15] yields that an ${\rm SQS}(v)$ whenever $v\equiv 2$ or
$4\pmod{6}$ (see Theorem 2). Applying Construction B, we then obtain an ${\rm
SQS}(V)$ with locality two and skip cost zero whenever $V\equiv 4$ or
$8\pmod{12}$. Similarly, Construction C yields an ${\rm SQS}(V)$ with locality
two and skip cost zero whenever $V\equiv 4$ or $10\pmod{18}$. These two
constructions yield the infinite set of parameters in Theorem 3.

Next, for $v\in\\{26,34,38\\}$, we use Proposition 2. Example 5 provides the
base blocks for ${\rm SQS}(26)$, while Appendix C provides the base blocks for
${\rm SQS}(34)$ and ${\rm SQS}(38)$.

Finally, we provide an explicit construction of a ${\rm SQS}(14)$ with zero
skip cost in Appendix D. This completes the proof for Theorem 3.

## References

  * [1] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” _IEEE transactions on information theory_ , vol. 56, no. 9, pp. 4539–4551, 2010.
  * [2] A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Suh, “A survey on network codes for distributed storage,” _Proceedings of the IEEE_ , vol. 99, no. 3, pp. 476–489, 2011.
  * [3] S. Liu and F. Oggier, “An overview of coding for distributed storage systems,” _Network Coding and Subspace Designs_ , pp. 363–383, 2018.
  * [4] V. Ramkumar, M. Vajha, S. B. Balaji, M. N. Krishnan, B. Sasidharan, and P. V. Kumar, “Codes for distributed storage,” in _Concise Encyclopedia of Coding Theory_. Chapman and Hall/CRC, 2021, pp. 735–762.
  * [5] M. Ye and A. Barg, “Explicit constructions of high-rate mds array codes with optimal repair bandwidth,” _IEEE Transactions on Information Theory_ , vol. 63, no. 4, pp. 2001–2014, 2017.
  * [6] M. Vajha, V. Ramkumar, B. Puranik, G. Kini, E. Lobo, B. Sasidharan, P. V. Kumar, A. Barg, M. Ye, S. Narayanamurthy _et al._ , “Clay codes: Moulding $\\{$MDS$\\}$ codes to yield an $\\{$MSR$\\}$ code,” in _16th USENIX Conference on File and Storage Technologies (FAST 18)_ , 2018, pp. 139–154.
  * [7] T.-Y. Wu, Y. S. Han, Z. Li, B. Bai, G. Zhang, X. Zhang, and X. Wu, “Achievable lower bound on the optimal access bandwidth of $(k+2,k,2)$-mds array code with degraded read friendly,” in _2021 IEEE Information Theory Workshop (ITW)_ , 2021, pp. 1–5.
  * [8] N. B. Shah, K. V. Rashmi, P. V. Kumar, and K. Ramchandran, “Distributed storage codes with repair-by-transfer and nonachievability of interior points on the storage-bandwidth tradeoff,” _IEEE Transactions on Information Theory_ , vol. 58, no. 3, pp. 1837–1852, 2012.
  * [9] I. Tamo, Z. Wang, and J. Bruck, “Zigzag codes: Mds array codes with optimal rebuilding,” _IEEE Transactions on Information Theory_ , vol. 59, no. 3, pp. 1597–1616, 2013.
  * [10] S. El Rouayheb and K. Ramchandran, “Fractional repetition codes for repair in distributed storage systems,” in _2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , 2010, pp. 1510–1517.
  * [11] T. Ernvall, “The existence of fractional repetition codes,” _arXiv e-prints_ , pp. arXiv–1201, 2012.
  * [12] O. Olmez and A. Ramamoorthy, “Fractional repetition codes with flexible repair from combinatorial designs,” _IEEE Transactions on Information Theory_ , vol. 62, no. 4, pp. 1565–1591, 2016.
  * [13] B. Zhu, K. W. Shum, H. Li, and H. Hou, “General fractional repetition codes for distributed storage systems,” _IEEE Communications Letters_ , vol. 18, no. 4, pp. 660–663, 2014.
  * [14] N. Silberstein and T. Etzion, “Optimal fractional repetition codes and fractional repetition batch codes,” in _2015 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2015, pp. 2046–2050.
  * [15] H. Hanani, “On quadruple systems,” _Canadian Journal of Mathematics_ , vol. 12, pp. 145–157, 1960.
  * [16] C. C. Lindner and A. Rosa, “Steiner quadruple systems-a survey,” _Discrete Mathematics_ , vol. 22, no. 2, pp. 147–181, 1978.
  * [17] L. Ji and L. Zhu, “An improved product construction of rotational steiner quadruple systems,” _Journal of Combinatorial Designs_ , vol. 10, no. 6, pp. 433–443, 2002.
  * [18] N. Alon, “Combinatorial nullstellensatz,” _Combinatorics, Probability and Computing_ , vol. 8, no. 1-2, pp. 7–29, 1999.

SPACE TO FORCE NEW PAGE

##  Appendix A Proof of MDS Property of Construction A

Let us recall Construction A. For $m\geq 2$, set $k=m+1$, $M=2^{m}$ and
$N=2k=2(m+1)$. Then any codeword has $k=m+1$ information columns
${\boldsymbol{a}}^{(0)},{\boldsymbol{a}}^{(1)}\ldots,{\boldsymbol{a}}^{(m)}$,
while the remaining $k=m+1$ are parity nodes
${\boldsymbol{p}}^{(0)},{\boldsymbol{p}}^{(1)},\ldots,{\boldsymbol{p}}^{(m)}$.

Here, we use ${\boldsymbol{A}}$ to represent the $2^{m}\times k$ array
$\left(a^{(i)}_{\bf x}\right)$. Also, we use a column vector
${\boldsymbol{B}}$ of length $Mk$, where the column $i\in[0,k-1]$ of
${\boldsymbol{A}}$ is in the row set $[iM,(i+1)M-1]$ of ${\boldsymbol{B}}$.
Each systematic node $i$, or ${\boldsymbol{a}}^{(i)}$, can be represented as
${\boldsymbol{V}}_{i}{\boldsymbol{B}}$, where
${\boldsymbol{V}}_{i}=[{\boldsymbol{0}}_{p\times pi},{\boldsymbol{I}}_{p\times
p},\ldots,{\boldsymbol{0}}_{p\times p(k-i-1)}]$.

For a fixed $i,j$ and any ${\boldsymbol{x}}\in\mathbb{F}^{m}_{2}$, we set
$\alpha^{(i,j)}_{\boldsymbol{x}}=x_{j,i}$. Similarly, each parity node
$p^{(i)}$ can be obtained by ${\boldsymbol{W}}_{i}{\boldsymbol{B}}$, where
${\boldsymbol{W}}_{i}=[x_{i,0}{\boldsymbol{P}}_{i,0},x_{i,1}{\boldsymbol{P}}_{i,1},\ldots,x_{i,k-1}{\boldsymbol{P}}_{i,k-1}]$,
${\boldsymbol{P}}_{0,j}={\boldsymbol{I}}_{p\times p}$ and
${\boldsymbol{P}}_{i\neq 0,j}$ are permutation matrices (not necessarily
distinct) of size $p\times p$ for $i,j\in[0,k-1]$. The permutation matrix
${\boldsymbol{P}}_{i,j}=(p^{(i,j)}_{{{\boldsymbol{x}}},{{\boldsymbol{y}}}})$
is defined as $p^{(i,j)}_{{{\boldsymbol{x}}},{{\boldsymbol{y}}}}=1$ if and
only if $a^{(j)}_{{\boldsymbol{y}}}=a^{(0)}_{{\boldsymbol{x}}}+v_{i,j}$, where
$v_{i,j}$ is the $(j+1)$-th element of set $\boldsymbol{S}_{i}$.

Now, to demonstrate the MDS property, it suffices to show that there is an
assignment for the indeterminates $\\{x_{i,j}\\}$ in the field
$\mathbb{F}_{q}$, such that for any subset
$\\{s_{1},s_{2},\ldots,s_{k}\\}\subset[0,k-1]$, the matrix
${\boldsymbol{W}}=[{\boldsymbol{W}}^{T}_{s_{1}},{\boldsymbol{W}}^{T}_{s_{2}},\ldots,{\boldsymbol{W}}^{T}_{s_{k}}]$
is of full rank.

It is clear that
${\boldsymbol{W}}=[{\boldsymbol{V}}^{T}_{0},\cdots,{\boldsymbol{V}}^{T}_{k-1}]$
is of full rank. Let $t\in[1,k]$ be an integer. Assume that
$[{\boldsymbol{W}}^{T}_{i_{1}},{\boldsymbol{W}}^{T}_{i_{2}},\ldots,{\boldsymbol{W}}^{T}_{i_{t}}]$
is a submatrix of ${\boldsymbol{W}}$, i.e.,
$\\{i_{1},i_{2},\ldots,i_{t}\\}\subset\\{s_{1},s_{2},\ldots,s_{k}\\}$. This
means that there exists $0\leq
j_{1}<j_{2}<\ldots<j_{t}\notin\\{s_{1},s_{2},\ldots,s_{k}\\}$ such that
$V^{T}_{j_{1}},V^{T}_{j_{2}},\ldots V^{T}_{j_{t}}$ is not a submatrix of $W$.
In this case, ${\boldsymbol{W}}$ is of full rank if and only if the submatrix

${\boldsymbol{D}}_{T^{1},T^{2}}=\left(\begin{array}[]{ccccccccc}x_{i_{1}j_{1}}{\boldsymbol{P}}_{i_{1}j_{1}}&x_{i_{1}j_{2}}{\boldsymbol{P}}_{i_{1}j_{2}}&\ldots&x_{i_{1}j_{t}}{\boldsymbol{P}}_{i_{1}j_{t}}\\\
x_{i_{2}j_{1}}{\boldsymbol{P}}_{i_{2}j_{1}}&x_{i_{2}j_{2}}{\boldsymbol{P}}_{i_{2}j_{2}}&\cdots&x_{i_{2}j_{t}}{\boldsymbol{P}}_{i_{2}j_{t}}\\\
\vdots&\vdots&\ddots&\vdots\\\
x_{i_{t}j_{1}}{\boldsymbol{P}}_{i_{t}j_{1}}&x_{i_{t}j_{1}}{\boldsymbol{P}}_{i_{t}j_{1}}&\ldots&x_{i_{t}j_{t}}{\boldsymbol{P}}_{i_{t}j_{t}}\end{array}\right),$
(3)

is of full rank, where $T^{1}=\\{i_{1},i_{2},\ldots,i_{t}\\}$,
$T^{2}=\\{j_{1},j_{2},\ldots,j_{t}\\}$. This is equivalent to
$\det({\boldsymbol{D}}_{T^{1},T^{2}})\neq 0$. Note that
$\deg(\det({\boldsymbol{B}}_{T^{1},T^{2}}))=pt$ and the coefficient of
$\prod^{t}_{z=1}x_{i_{z}j_{z}}^{p}$ is
$\det(\prod^{t}_{z=1}{\boldsymbol{P}}_{i_{z}j_{z}})\in\\{1,-1\\}$.

Let $\mathcal{T}=\\{\\{i_{1},i_{2},\ldots,i_{t}\\}\mid 0\leq
i_{1}<i_{2}<\ldots<i_{t}\leq k-1\\}$. Obviously, $|\mathcal{T}|=\binom{k}{t}$.
Let $T^{1}$ and $T^{2}$ be a subset of set $\mathcal{T}$ with size $t$, and
define the polynomial

$Y(x_{0,0},x_{0,1},\ldots,x_{k-1,k-1})=\prod_{T^{1}\in\mathcal{T}}\prod_{T^{2}\in\mathcal{T}}\det({\boldsymbol{D}}_{T^{1},T^{2}})\,.$
(4)

The result follows if there are elements
$\lambda_{0,0},\ldots,\lambda_{k-1,k-1}$ in $\mathbb{F}$ such that
$Y(x_{0,0},x_{0,1},\ldots,x_{k-1,k-1})\neq~{}0$. Assume that there exists a
largest nonzero term $\prod^{k-1}_{i=0,j=0}x_{i,j}^{y_{i,j}}$ in the
polynomial $Y(x_{0,0},x_{0,1},\ldots,x_{k-1,k-1})$, where
$\deg(x_{i,j})=y_{i,j}$. We apply the Combinatorial Nullstellensatz [18], If
$q\geq\max\\{y_{i,j}\\}+1$, then there exists elements
$\lambda_{0,0}$,$\ldots$, $\lambda_{k-1,k-1}\in\mathbb{F}$ such that
$Y(x_{0,0},x_{0,1},\ldots,x_{k-1,k-1})\neq 0$.

First, we consider the selection of columns of the given parity matrices. For
a given subset $T^{1}=\\{i_{1},i_{2},\ldots,i_{t}\\}$ and any subset $T^{2}$,
we have $\deg(x_{i_{1},0})=\binom{k-1}{t-1}$,
$\deg(x_{i_{1},1})=\binom{k-2}{t-1}$, $\cdots$,
$\deg(x_{i_{1},k-t})=\binom{t-1}{t-1}$, $\deg(x_{i_{2},1})=\binom{k-2}{t-2}$,
$\deg(x_{i_{2},2})=\binom{2}{1}\binom{k-3}{t-2}$,
$\deg(x_{i_{1},3})=\binom{3}{1}\binom{k-4}{t-2}$, $\cdots$,
$\deg(x_{i_{1},k-t+1})=\binom{t-2}{t-2}\binom{k-t+1}{1}$,
$\deg(x_{i_{3},2})=\binom{k-3}{t-3}$,
$\deg(x_{i_{3},3})=\binom{3}{2}\binom{k-4}{t-3}$,
$\deg(x_{i_{3},4})=\binom{4}{2}\binom{k-5}{t-3}$, $\cdots$,
$\deg(x_{i_{3},k-t+2})=\binom{t-3}{t-3}\binom{k-t+2}{2}$, $\cdots$,
$\deg(x_{i_{t},t-1})=\binom{k-t}{0}$,
$\deg(x_{i_{t},t})=\binom{t}{t-1}\binom{k-t-1}{0}$,
$\deg(x_{i_{t},t+1})=\binom{t+1}{t-1}\binom{k-t-2}{0}$, $\cdots$,
$\deg(x_{i_{t},k-1})=\binom{k-1}{t-1}\binom{0}{0}$. Note that for the
$i_{\ell}$ parity matrix, when $j\leq\ell-2$, the term $x_{i_{\ell},j}$ does
not exist; when $\ell-1\leq j\leq k-t+\ell-1$, the term $x_{i_{\ell},j}$
exists. Therefore, there exists a term
$\prod^{t}_{\ell=1}\prod^{k-t+\ell-1}_{j=\ell-1}x_{i_{\ell},j}^{\binom{j}{\ell-1}\binom{k-(j+1)}{t-\ell}p}$
with the largest degree being $\det({\boldsymbol{D}}_{T^{1},T^{2}})$.

Next, we consider the case of any subset $T^{1}$. For a given $0\leq\beta\leq
k-1$, we need to calculate the number $Q_{\beta,\ell}$ of the subset
$T^{1}=\\{i_{1},i_{2},\cdots,i_{t}\\}$ that satisfies $i_{\ell}=\beta$ for
$\ell\in[t]$. According to the sorting order, $\beta$ appears in a position
whose index is less than $\beta+1$ of subset $T^{1}$, i.e., $\ell\leq\beta+1$.
Hence, we obtain
$Q_{\beta,\ell}=\binom{\beta}{\ell-1}\binom{k-(\beta+1)}{t-\ell}$. For
example, if $\beta=0$, $\beta$ occurs only in the first position of each
subset $T^{1}$, i.e., $i_{1}=0$. Therefore, we have
$Q_{\beta=0,\ell=1}=\binom{k-1}{t-1}$. It is clear that
$\deg(x_{0,j})=p\binom{k-1}{t-1}\binom{k-(j+1)}{t-1}$ for $j\in[0,k-1]$.

For fixed $\beta\in[0,k-1]$ and $j\in[0,k-1]$, we find that the largest degree
of $x_{\beta,j}$ in a term $\prod^{k-1}_{i,j=0}x_{i,j}^{y_{i,j}}$ is
$\sum^{t}_{\ell=1}pQ_{\beta,\ell}\binom{j}{\ell-1}\binom{k-(j+1)}{t-\ell}=\sum^{t}_{\ell=1}p\binom{\beta}{\ell-1}\binom{k-(\beta+1)}{t-\ell}\binom{j}{\ell-1}\binom{k-(j+1)}{t-\ell}$
. By the following inequality

$\displaystyle\sum^{t}_{\ell=1}\binom{\beta}{\ell-1}\binom{k-(\beta+1)}{t-\ell}\binom{j}{\ell-1}\binom{k-(j+1)}{t-\ell}$
$\displaystyle\leq$
$\displaystyle\left(\sum^{t}_{\ell=1}\binom{\beta}{\ell-1}\binom{k-(\beta+1)}{t-\ell}\right)\left(\sum^{t}_{\ell=1}\binom{j}{\ell-1}\binom{k-(j+1)}{t-\ell}\right)$
$\displaystyle\leq$
$\displaystyle\binom{k-(\beta+1)+\beta}{t-1}\binom{k-(j+1)+j}{t-1}=\binom{k-1}{t-1}^{2},$

we have that $\max\\{y_{i,j}\\}=p\binom{k-1}{t-1}^{2}$. The equation holds due
to the identity $\sum^{k}_{i=0}\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}$. In
fact, we can find a largest term
$x_{0,0}^{p\binom{k-1}{t-1}^{2}}\prod^{k-1}_{i,j=1}y_{i,j}$ of the polynomial
$Y(\lambda_{0,0},\lambda_{0,1},\ldots,\lambda_{k-1,k-1})$ and its coefficient
is nonzero as the result of the product of the permutation matrix. When
$t=\lfloor\frac{k-1}{2}\rfloor+1=\lceil\frac{k}{2}\rceil$, we have the maximum
value $p\binom{k-1}{t-1}^{2}$ such that the function
$Y(\lambda_{0,0},\lambda_{0,1},\ldots,\lambda_{k-1,k-1})\neq 0$.

##  Appendix B Repair Scheme for Construction C

Repair of Block ${\boldsymbol{b}}\in{\mathcal{B}}_{1}$: Then
${\boldsymbol{b}}$ is of the form
$((v_{1},i_{1}),(v_{2},i_{2}),(v_{3},i_{3}),(v_{4},i_{4}))$. Then we pick the
following reads and blocks.

  * •

${\sf R}_{1}=\\{(i_{1},v_{1}),(i_{2},v_{2})\\}$ in the block
${\boldsymbol{b}}_{1}=((i_{1},v_{1}),(i_{2},v_{2}),(i_{3}+1,v_{3}),(i_{4}+2,v_{4}))$;

  * •

${\sf R}_{2}=\\{(i_{3},v_{3}),(i_{4},v_{4})\\}$ in the block
${\boldsymbol{b}}_{2}=((i_{1}+1,v_{1}),(i_{2}+2,v_{2}),(i_{3},v_{3}),(i_{4},v_{4}))$.

Repair of Block ${\boldsymbol{b}}\in{\mathcal{B}}^{1}_{2}$: Then
${\boldsymbol{b}}$ is of the form
$((i_{1},v_{1}),\infty,(i_{3}.v_{3}),(i_{2},v_{2}))$ with $i_{1}=i_{2}$. Then
$i_{1}+i_{2}+i_{3}=0\pmod{3}$ implies that $i_{1}=i_{2}=i_{3}$.

  * •

${\sf R}_{1}=\\{(i_{1},v_{1}),\infty\\}$ in the block
${\boldsymbol{b}}_{1}=((i_{1},v_{1}),\infty,(i_{2}+1,v_{2}),(i_{3}+2,v_{3}))\in{\mathcal{B}}_{2}^{2}$;

  * •

${\sf R}_{2}=\\{(i_{2},v_{3}),(i_{2},v_{2})\\}$ in the block
${\boldsymbol{b}}_{2}=(i_{2}-1,v_{2}),(i_{2},v_{2}),(i_{2},v_{3}),(i_{2}-1,v_{3}))\in{\mathcal{B}}_{4}$.

Repair of Block ${\boldsymbol{b}}\in{\mathcal{B}}^{2}_{2}$: Then
${\boldsymbol{b}}$ is of the form
$((i_{1},v_{1}),\infty,(i_{2},v_{2}),(i_{3},v_{3}))$ with $i_{1}\neq i_{2}$.
Then $i_{1}+i_{2}+i_{3}=0\pmod{3}$ implies that
$\\{i_{1},i_{2},i_{3}\\}=\\{0,1,2\\}$.

  * •

${\sf R}_{1}=\\{(i_{1},v_{1}),\infty\\}$ in the block
${\boldsymbol{b}}_{1}=((i_{1},v_{1}),\infty,(i_{1},v_{2}),(i_{1},v_{3}))\in{\mathcal{B}}_{2}^{1}$;

  * •

If $i_{3}=i_{2}+1$, then ${\sf R}_{2}=\\{(i_{3},v_{3}),(i_{2},v_{2})\\}$ in
the block
${\boldsymbol{b}}_{2}=((i_{2}+1,v_{1}),(i_{2}+2,v_{2}),(i_{2}+1,v_{3}),(i_{2},v_{2}))\in{\mathcal{B}}_{3}$.

  * •

If $i_{3}=i_{2}+2$, then ${\sf R}_{2}=\\{(i_{3},v_{3}),(i_{2},v_{2})\\}$ in
the block
${\boldsymbol{b}}_{2}=((i_{2}+2,v_{1}),(i_{2},v_{2}),(i_{2}+2,v_{3}),(i_{2}+1,v_{2}))\in{\mathcal{B}}_{3}$.

Repair of Block ${\boldsymbol{b}}\in{\mathcal{B}}_{3}$: Then
${\boldsymbol{b}}$ is of the form
$((i,v_{1}),(i+1,v_{2}),(i,v_{3}),(i+2,v_{2}))$. Then we pick the following
reads and blocks.

  * •

${\sf R}_{1}=\\{(i,v_{1}),(i+1,v_{2})\\}$ in the block
${\boldsymbol{b}}_{1}=((i+1,v_{3}),(i+2,v_{1}),(i+1,v_{2}),(i,v_{1}))\in{\mathcal{B}}_{3}$;

  * •

${\sf R}_{2}=\\{(i,v_{3}),(i+2,v_{2})\\}$ in the block
${\boldsymbol{b}}_{2}=((i+2,v_{2}),(i,v_{3}),(i+2,v_{1}),(i+1,v_{3}))\in{\mathcal{B}}_{3}$.

Repair of Block ${\boldsymbol{b}}\in{\mathcal{B}}_{4}$: Then
${\boldsymbol{b}}$ is of the form
${\boldsymbol{b}}=((i,v_{1}),(i+1,v_{1}),(i+1,v_{2}),(i,v_{2}))$. Then we have
the following three sub-cases.

If $v_{1}=0,v_{2}=1$, then ${\boldsymbol{b}}=((i,0),(i+1,0),(i+1,1),(i,1))$.
Let $v\in[0,N]$. Then we pick the following reads and blocks.

  * •

${\sf R}_{1}=\\{(i,0),(i+1,0)\\}$ in the block
${\boldsymbol{b}}_{1}=((i,0),(i+1,0),(i+1,v),(i,v))\in{\mathcal{B}}_{4}$,
where $v>1$.

  * •

${\sf R}_{2}=\\{(i+1,1),(i,1)\\}$ in the block
${\boldsymbol{b}}_{1}=((i,1),(i+1,1),(i+1,v),(i,v)\in{\mathcal{B}}_{4}$, where
$v>1$.

If $v_{1}=N-2$, then $v_{2}=N-1$ and
${\boldsymbol{b}}=((i,N-2),(i+1,N-2),(i+1,N-1),(i,N-1))$.

  * •

${\sf R}_{1}=\\{(i,N-2),(i+1,N-2)\\}$ in the block
${\boldsymbol{b}}_{1}=((i,v),(i+1,v),(i+1,N-2),(i,N-2))\in{\mathcal{B}}_{4}$,
where $v<N-2$.

  * •

${\sf R}_{2}=\\{(i+1,N-1),(i,N-1)\\}$ in the block
${\boldsymbol{b}}_{1}=((i,v),(i+1,v),(i+1,N-1),(i,N-1)\in{\mathcal{B}}_{4}$,
where $v<N-1$.

If $(v_{1},v_{2})\neq(0,1)$ and $v_{1}\neq N-2$, then
${\boldsymbol{b}}=((i,v_{1}),(i+1,v_{1}),(i+1,v_{2}),(i,v_{2}))$.

  * •

${\sf R}_{1}=\\{(i,v_{1}),(i+1,v_{1})\\}$ in the block
${\boldsymbol{b}}_{1}=((i,v_{1}),(i+1,v_{1}),(i+1,v),(i,v))\in{\mathcal{B}}_{4}$,
where $v\neq v_{2}$.

  * •

${\sf R}_{2}=\\{(i+1,v_{2}),(i,v_{2})\\}$ in the block
${\boldsymbol{b}}_{1}=((i,v),(i+1,v),(i+1,v_{2}),(i,v_{2}))\in{\mathcal{B}}_{4}$,
where $v\neq v_{1}$.

Repair of Block ${\boldsymbol{b}}\in{\mathcal{B}}_{5}$: Then
${\boldsymbol{b}}$ is of the form $(\infty,(0,v),(1,v),(2,v))$. Let ${\sf
R}_{1}=\\{\infty,(0,v)\\}$ and ${\sf R}_{2}=\\{(1,v),(2,v)\\}$. Then we pick
the following reads and blocks.

  * •

For the second read ${\sf R}_{2}=\\{(1,v),(2,v)\\}$ of ${\boldsymbol{b}}$ can
be obviously repaired from ${\mathcal{B}}_{4}$. The specific repair process is
as follows:

    * –

If $v=0$, then ${\sf R}_{2}=\\{(1,0),(2,0)\\}$ in the block
${\boldsymbol{b}}_{2}=((1,0),(2,0),(2,v_{1}),(1,v_{1}))\in{\mathcal{B}}_{4}$,
where $v_{1}>0$.

    * –

If $v<N-1$, then ${\sf R}_{2}=\\{(1,v),(2,v)\\}$ in the block
${\boldsymbol{b}}_{2}=((1,v),(2,v),(2,v_{1}),(1,v_{1}))\in{\mathcal{B}}_{4}$,
where $v_{1}>v$.

    * –

If $v=N-1$, then ${\sf R}_{2}=\\{(1,N-1),(2,N-1)\\}$ in the block
${\boldsymbol{b}}_{2}=((1,v_{1}),(2,v_{1}+1),(2,N-1),(1,N-1))\in{\mathcal{B}}_{4}$,
where $v_{1}<N-1$.

  * •

For the first read ${\sf R}_{1}$, for a given $v\in[0,N-1]$, there exists a
subset of $v\in\\{\infty,v,v_{1},v_{2}\\}\in{\mathcal{B}}$,

    * –

If $v<v_{1}<v_{2}$, then ${\sf R}_{1}=\\{\infty,(0,v)\\}$ in the block
${\boldsymbol{b}}_{1}=((0,v),\infty,(0,v_{2}),(0,v_{1}))\in{\mathcal{B}}_{2}^{1}$;

    * –

If $v_{1}<v<v_{2}$, then ${\sf R}_{1}=\\{\infty,(0,v)\\}$ in the block
${\boldsymbol{b}}_{1}=((1,v_{1}),\infty,(0,v),(2,v_{2}))\in{\mathcal{B}}_{2}^{2}$;

    * –

If $v_{1}<v_{2}<v$, then ${\sf R}_{1}=\\{\infty,(0,v)\\}$ in the block
${\boldsymbol{b}}_{1}=((0,v_{1}),\infty,(0,v),(2,v_{2}))\in{\mathcal{B}}_{2}^{1}$.

##  Appendix C SQS from Method of Differences

Here, we prove Proposition 2(i) and then list down the base blocks for ${\rm
SQS}(34)$ and ${\rm SQS}(38)$.

###### Proof of Proposition 2(i).

We remark that the proof of Proposition 2(ii) is similar and hence, omitted.
Consider any pair $(x,y)$ and let $z=|x-y|$. From the conditions of the
proposition, suppose that $z$ appears as a difference in blocks
${\boldsymbol{b}}_{1}$ and ${\boldsymbol{b}}_{2}$ (with possibly
${\boldsymbol{b}}_{1}={\boldsymbol{b}}_{2}$).

Suppose that ${\boldsymbol{b}}_{1}=(a,b,c,d)$ with $b=a+z$ and $y=x+z$. Then
we choose $i=x-a$ and the block
${\boldsymbol{b}}+i=(x,b+x-a,c+x-a,d+x-a)=(x,y,c+x-a,d+x-a)$. Therefore,
$(x,y)$ belongs to the block ${\boldsymbol{b}}_{1}+i$. Similarly, we can find
another shift $j$ such that ${\boldsymbol{b}}_{2}+j$ contains $(x,y)$. In
other words, $(x,y)$ belongs to different blocks and this concludes the proof.
∎

Finally, we provide the base blocks for ${\rm SQS}(34)$ and ${\rm SQS}(38)$
that have repeated adjacent pairs. As before, the base blocks given here are
obtained from [17].

Base blocks for ${\rm SQS}(34)$:

$\small\begin{array}[]{llllll}(0,11,22,\infty),^{*}&(0,1,5,\infty),&(0,2,10,\infty),&(0,3,15,\infty),&(0,6,19,\infty),\\\
(0,7,16,\infty),&(0,1,2,4),&(0,1,6,7),&(0,1,8,9),&(0,1,10,11),\\\
(0,1,12,13),&(0,1,14,15),&(0,1,16,29),&(0,1,17,31),&(0,1,18,30),\\\
(0,2,5,7),&(0,2,6,8),&(0,2,9,11),&(0,2,12,14),&(0,2,13,16),\\\
(0,2,15,17),&(0,2,22,25),&(0,3,6,26),&(0,3,7,25),&(0,3,8,28),\\\
(0,3,9,17),&(0,18,10,3),&(0,3,12,27),&(0,3,14,29),&(0,3,16,24),\\\
(0,4,8,16),&(0,4,9,28),&(0,4,10,24),&(0,4,11,25),&(0,4,13,26),\\\
(0,19,14,4),&(0,4,15,23),&(0,4,17,27),&(0,5,10,17),&(0,5,11,21),\\\
(0,5,15,26),&(0,16,5,22),&(0,5,18,27),&(0,6,12,21),&(0,6,13,25),\\\
(0,7,14,24).\end{array}$

Here, the points are defined over $\mathbb{Z}_{33}\cup\\{\infty\\}$. The block
marked with $*$ is a special base block that generates $33/3=11$ blocks. All
other base blocks generates $33$ blocks.

Base blocks for ${\rm SQS}(38)$:

$\footnotesize\begin{array}[]{llllll}(0,1,27,\infty),&(0,2,22,\infty),&(0,3,33,\infty),&(0,5,24,\infty),&(0,6,29,\infty),\\\
(0,9,25,\infty),&(0,1,4,11),&(0,2,17,31),&(0,3,7,28),&(0,5,18,20),\\\
(0,6,14,19),&(0,9,10,21),&(0,1,2,6),&(0,1,3,14),&(0,1,7,19),\\\
(0,1,9,35),&(0,1,10,24),&(0,30,13,1),&(0,1,15,16),&(0,1,17,33),\\\
(0,1,20,34),&(0,1,25,29),&(0,2,4,16),&(0,2,5,8),&(0,2,7,21),\\\
(0,2,15,18),&(0,2,25,30),&(0,10,20,23),&(0,10,30,29),&(0,10,33,5),\\\
(0,10,16,17),&(0,10,26,18),&(0,10,19,4),&(0,10,2,12),&(0,10,22,34),\\\
(0,10,15,7),&(0,10,28,31),&(0,20,3,12),&(0,20,13,6),&(0,20,33,25),\\\
(0,20,2,32),&(0,20,28,4),&(0,26,15,8),&(4,0,26,31),&(0,26,34,13),\\\
(0,26,12,22),&(1,0,26,32),&(0,26,5,3),&(0,26,20,9),&(0,26,35,7),\\\
(2,0,26,33),&(0,26,21,14),&(0,15,30,9),&(0,15,19,23),&(0,15,34,28),\\\
(0,15,20,24),&(0,15,21,3).\end{array}$

Here, the points are defined over $\mathbb{Z}_{37}\cup\\{\infty\\}$.

##  Appendix D ${\rm SQS}(14)$ with Locality Two and Zero Skip Cost

Here, we simply list down the blocks for ${\rm SQS}(14)$ with 14 symbols
$\\{0,1,\ldots,9,A,B,C,D\\}$. We remark that these blocks were first given in
Hanani [15] and we adjusted the arrangement to obtain the desired skip cost.

$\footnotesize\begin{array}[]{llllll}(0,1,2,5),&(0,3,8,D),&(1,2,3,6),&(1,5,7,C),&(2,4,A,C),&(3,5,7,9),\\\
(4,7,9,C),&(0,1,3,B),&(0,3,9,A),&(1,2,4,7),&(1,5,8,9),&(2,4,B,D),\\\
(3,5,8,B),&(5,6,7,8),&(0,1,4,6),&(0,4,5,9),&(1,2,8,B),&(1,5,B,D),\\\
(2,5,7,B),&(3,5,A,C),&(5,6,9,B),&(0,8,1,7),&(0,4,7,B),&(1,2,9,A),\\\
(1,6,7,9),&(2,5,8,A),&(3,6,7,B),&(5,D,6,C),&(0,1,9,D),&(0,4,8,A),\\\
(1,2,C,D),&(1,6,8,D),&(2,5,9,C),&(3,6,8,9),&(5,9,A,D),&(0,1,A,C),\\\
(0,4,C,D),&(1,3,4,5),&(1,6,B,C),&(2,6,7,C),&(3,6,A,D),&(6,8,A,C),\\\
(0,2,3,4),&(0,5,7,D),&(1,3,7,D),&(1,7,A,B),&(2,6,9,D),&(3,B,C,D),\\\
(7,8,9,A),&(0,2,6,8),&(0,5,8,C),&(1,3,8,A),&(2,3,5,D),&(2,6,A,B),\\\
(4,5,7,A),&(7,8,B,C),&(0,2,7,9),&(0,5,A,B),&(1,3,9,C),&(2,3,7,A),\\\
(2,7,8,D),&(4,5,8,D),&(7,9,B,D),&(0,2,A,D),&(0,6,7,A),&(1,4,8,C),\\\
(2,3,8,C),&(3,4,6,C),&(4,5,B,C),&(7,A,C,D),&(0,2,B,C),&(0,6,9,C),\\\
(1,4,9,B),&(2,3,9,B),&(3,4,7,8),&(4,6,7,D),&(8,9,C,D),&(0,3,5,6),\\\
(0,6,B,D),&(1,4,A,D),&(2,4,5,6),&(3,4,9,D),&(4,6,8,B),&(8,A,B,D),\\\
(0,3,7,C),&(0,8,9,B),&(1,5,6,A),&(2,4,8,9),&(3,4,A,B),&(4,6,9,A),\\\
(9,A,B,C).\end{array}$