1

Code Constructions for Distributed Storage With
Low Repair Bandwidth and Low Repair Complexity

arXiv:1801.05989v1 [] 18 Jan 2018

Siddhartha Kumar, Student Member, IEEE, Alexandre Graell i Amat, Senior Member, IEEE,
Iryna Andriyanova, Member, IEEE, Fredrik Brännström, Member, IEEE, and Eirik Rosnes, Senior Member, IEEE

Abstract—We present the construction of a family of erasure
correcting codes for distributed storage systems that achieve low
repair bandwidth and low repair complexity. The construction is
based on two classes of codes, where the primary goal of the first
class of codes is to achieve a good fault tolerance, while the second
class of codes aims at reducing the repair bandwidth and the
repair complexity. The repair procedure is a two-step procedure
where parts of the failed node are repaired in the first step using
the first code. The downloaded symbols during the first step are
cached in the memory and used to repair the remaining erased
data symbols at no additional read cost during the second step of
the repair process. The first class of codes is based on maximum
distance separable (MDS) codes modified using piggybacks, while
the second class of codes is designed to reduce the number of
additional symbols that need to be downloaded to repair the
remaining erased symbols. We show that the proposed codes
achieve better repair bandwidth compared to MDS, Piggyback,
and local reconstruction codes, while a better repair complexity is
achieved when compared to MDS, Zigzag, and Piggyback codes.

I. I NTRODUCTION

I

N recent years, there has been a widespread adoption of
distributed storage systems (DSSs) as a viable storage
technology for Big Data. Distributed storage provides an
inexpensive storage solution for storing large amounts of data.
Formally, a DSS is a network of numerous inexpensive disks
(or nodes) where data is stored in a distributed fashion. Storage
nodes are prone to failures, and thus to losing the stored data.
Reliability against node failures (commonly referred to as fault
tolerance) is achieved by means of erasure correcting codes
(ECCs). ECCs are a way of introducing structured redundancy,
and for a DSS, it means addition of redundant nodes. In case of
a node failure, these redundant nodes allow complete recovery
of the data stored. Since ECCs have a limited fault tolerance,
to maintain the initial state of reliability, when a node fails a
new node needs to be added to the DSS network and populated
Parts of this paper were presented at the IEEE Global Communications
Conference (GLOBECOM), San Diego, CA, December 2015. This work was
partially funded by the Research Council of Norway (grant 240985/F20),
Simula@UiB, and the Swedish Research Council (grant #2016-04253).
S. Kumar was with the Department of Electrical Engineering, Chalmers
University of Technology, SE-41296 Gothenburg, Sweden. He is now with
Simula@UiB, N-5020 Bergen, Norway (e-mail: kumarsi@simula.no).
A. Graell i Amat and F. Brännström are with the Department of Electrical
Engineering, Chalmers University of Technology, SE-41296 Gothenburg,
Sweden (e-mail: {alexandre.graell, fredrik.brannstrom}@chalmers.se).
I. Andriyanova is with the ETIS-UMR8051 group, ENSEA/University of Cergy-Pontoise/CNRS, 95015 Cergy, France (e-mail:
iryna.andriyanova@ensea.fr).
E. Rosnes is with Simula@UiB, N-5020 Bergen, Norway (e-mail:
eirikrosnes@simula.no).

with data. The problem of repairing a failed node is known as
the repair problem.
Current DSSs like Google File System II and Quick File
System use a family of Reed-Solomon (RS) ECCs [1]. Such
codes come under a broader family of maximum distance
separable (MDS) codes. MDS codes are optimal in terms
of the fault tolerance/storage overhead tradeoff. However, the
repair of a failed node requires the retrieval of large amounts
of data from a large subset of nodes. Therefore, in the recent
years, the design of ECCs that reduce the cost of repair has
attracted significant attention. Pyramid codes [2] were one of
the first code constructions that addressed this problem. In
particular, they aim at reducing the number of nodes that need
to be contacted to repair a single failed node, known as the
repair locality. Other codes that reduce the repair locality are
local reconstruction codes (LRCs) [3] and locally repairable
codes [4], [5].
Another important parameter related to the repair is the repair bandwidth, defined as the number of symbols downloaded
to repair a single failed node. Dimakis et al. [6] derived an
optimal repair bandwidth-storage per node tradeoff curve and
defined two new classes of codes for DSSs known as minimum
storage regenerating (MSR) codes and minimum bandwidth
regenerating (MBR) codes. MSR codes are MDS codes that
have the lowest possible repair bandwidth while storing the
minimum amount of data per node (referred to as the subpacketization level). On the other hand, MBR codes are MDS
codes achieving the lowest repair bandwidth while having the
maximum sub-packetization level. Product-Matrix MBR (PMMBR) codes and Fraction Repetition (FR) codes in [7] and [8],
respectively, are examples of MBR codes. In particular, FR
codes achieve low repair complexity at the cost of high storage
overheads. Codes such as minimum disk input/output (I/O)
repairable (MDR) codes [9] and Zigzag codes [10] strictly fall
under the class of MSR codes. These codes have a high subpacketization level. Alternatively, the MSR codes presented
in [11], [12] achieve the minimum possible sub-packetization
level.
Piggyback codes presented in [13] are another class of
codes that achieve a sub-optimal reduction in repair bandwidth
with a much lower sub-packetization level in comparison to
MSR codes, using the concept of piggybacking. Piggybacking
consists of adding carefully chosen linear combinations of data
symbols (called piggybacks) to the parity symbols of a given
ECC. This results in a lower repair bandwidth at the expense of
a higher complexity in encoding and repair operations. More
recently, the authors in [14] presented a family of codes that

2

II. S YSTEM M ODEL AND C ODE C ONSTRUCTION
We consider the DSS depicted in Fig. 1, consisting of
storage nodes, of which k are data nodes and n − k are parity
nodes. Consider a file that needs to be stored on the DSS. We
represent a file as a k × k matrix D = [di,j ], called the data
array, over GF(q), where GF(q) denotes the Galois field of size
q, with q being a prime number or a power of a prime number.
In order to achieve reliability against node failures, the matrix
D is encoded using an (n, k) vector code [16] to obtain a
code matrix C = [ci,j ], referred to as the code array, of size
k × n, ci,j ∈ GF(q). The symbol ci,j in C is then stored at the
i-th row of the j-th node in the DSS. Thus, each node stores k
symbols. Each row in C is referred to as a stripe so that each
file in the DSS is stored over k stripes in n storage nodes.
We consider the (n, k) code to be systematic, which means
that ci,j = di,j for i, j = 0, . . . , k − 1. Correspondingly, we
refer to the k nodes storing systematic symbols as data nodes
and the remaining n − k nodes containing parity symbols only
as parity nodes. The efficiency of the code is determined by
the code rate, given by R = k 2 /kn = k/n. Alternatively, the
inverse of the code rate is referred to as the storage overhead.
For later use, we denote the set of message symbols in the
k data nodes as D = {di,j } and by Pt , t = k, . . . , n − 1, the

Class A parities

k data nodes

k data symbols

reduce the encoding and repair complexity of PM-MBR codes
while maintaining the same level of fault tolerance and repair
bandwidth. However, this comes at the cost of large alphabet
size. In [15], binary MDS codes that achieve optimal repair
bandwidth and low repair complexity were introduced, with
the caveat that the file size is asymptotic and that the fault
tolerance is limited to 3.
In this paper, we propose a family of ECCs that achieve low
repair bandwidth and low repair complexity while keeping the
field size relatively small and having variable fault tolerance.
In particular, we propose a systematic code construction based
on two classes of parity symbols. Correspondingly, there
are two classes of parity nodes. The first class of parity
nodes, whose primary goal is to provide erasure correcting
capability, is constructed using an MDS code modified by
applying specially designed piggybacks to some of its code
symbols. The second class of parity nodes is constructed
using a block code whose parity symbols are obtained through
simple additions. The purpose of this class of parity nodes is
not to enhance the erasure correcting capability, but rather to
facilitate node repair at low repair bandwidth and low repair
complexity. We provide two constructions for the second class
of parity nodes. The first one is given by a simple equation.
The second one is a heuristic construction which is more
involved but further improves the repair bandwidth in some
cases. The proposed codes achieve better repair bandwidth
compared to Piggyback codes, MDS codes, and LRCs, and a
repair bandwidth close to that of Zigzag codes. Furthermore,
they achieve a better repair complexity than Zigzag codes,
MDS codes, Piggyback codes, and binary addition and shift
implementable cyclic-convolutional (BASIC) PM-MBR codes
[14].

...
...

...

Class B parities

...
...

...

...
...

...

...

nA + nB − 2k parity nodes

Fig. 1. System model of the DSS.

set of parity symbols in the t-th node. Subsequently, we define
the set DI ⊆ D as
DI = {di,j ∈ D | (i, j) ∈ I},
where I is an arbitrary index set. We also define the operator
(a + b)k , (a + b) mod k for integers a and b.
Our main goal is to construct codes that yield low repair
bandwidth and low repair complexity of a single failed data
node. We focus on the repair of data nodes since the raw
data is stored on these nodes and the users can readily access
the data through these nodes. Thus, their survival is a crucial
aspect of a DSS. To this purpose, we construct a family of
systematic (n, k) codes consisting of two different classes
of parity symbols. Correspondingly, there are two classes of
parity nodes, referred to as Class A and Class B parity nodes,
as shown in Fig. 1. Class A and Class B parity nodes are
built using an (nA , k) code and an (nB , k) code, respectively,
such that n = nA + nB − k. In other words, the parity nodes
from the (n, k) code correspond to the parity nodes of Class A
and Class B codes. The primary goal of Class A parity nodes
is to achieve a good erasure correcting capability, while the
purpose of Class B nodes is to yield low repair bandwidth and
low repair complexity. In particular, we focus on the repair of
data nodes. The repair bandwidth (in bits) per node, denoted
by γ, is proportional to the average number of symbols (data
and parity) that need to be downloaded to repair a data symbol,
denoted by λ. More precisely, let β be the sub-packetization
level of the DSS, which is the number of symbols per node.1
Then,
γ
,
(1)
λ=
νβ
where ν = ⌈log2 q⌉ is the size (in bits) of a symbol. λ can
be interpreted as the repair bandwidth normalized by the size
(in bits) of a node, and will be referred to as the normalized
repair bandwidth.
The main principle behind our code construction is the
following. The repair is performed one symbol at a time. After
the repair of a data symbol is accomplished, the symbols read
to repair that symbol are cached in the memory. Therefore,
they can be used to repair the remaining data symbols at no
additional read cost. The proposed codes are constructed in
such a way that the repair of a new data symbol requires a
low additional read cost (defined as the number of additional
1 For

our code construction, β = k, but this is not the case in general.

3

symbols that need to be read to repair the data symbol), so
that λ (and hence γ) is kept low.
Definition 1: The read cost of a symbol is the number
of symbols that need to be read to repair the symbol. The
additional read cost of a symbol is the number of additional
symbols that need to be read to repair the symbol, considering
that other symbols are already cached in the memory (i.e.,
previously been read to recover some other data symbols).

DX0

DQ0

pAi,j =

k−1
X

αl,j di,l , j = k, . . . , nA − 1,

(2)

l=0

where αl,j denotes a coefficient in GF(q) and i =
0, . . . , k−1. Store the parity symbol in the corresponding
row of the code array. Overall, k(nA −k) parity symbols
are generated.
2) Modify some of the parity symbols by adding piggybacks. Let τ , 1 ≤ τ ≤ nA − k − 1, be the number of
piggybacks introduced per row. The parity symbol pAi,u
is updated as
A,p
pi,u
= pAi,u + d(i+u−nA +τ +1)k ,i ,

(3)

where u = nA − τ, . . . , nA − 1, the second term in
the summation is the piggyback, and the superscript
A,p
p in pi,u
indicates that the parity symbol contains
piggybacks.
The fault tolerance (i.e., the number of node failures that
can be tolerated) of Class A codes is given in the following
theorem.
Theorem 1: An (nA , k) Class A code with τ piggybacks per
row can correct a minimum of nA − k − τ + 1 node failures.
Proof: See Appendix A.
When a failure of a data node occurs, Class A parity nodes
are used to repair τ + 1 of the k failed symbols. Class A parity
symbols are constructed in such a way that, when node j is
erased, τ +1 data symbols in this node can be repaired reading
the (non-failed) k − 1 data symbols in the j-th row of the data
array and τ + 1 parity symbols in the j-th row of Class A
parity nodes (see also Section IV-C). For later use, we define
the set Rj as follows.
Definition 2: For j = 0, . . . , k − 1, the index set Rj is
defined as
Rj = {(j, (j + 1)k ), (j, (j + 2)k ), . . . , (j, (j + k − 1)k )}.
2 We use the superscript A to indicate that the parity symbol is stored in a
Class A parity node.

P6A

d0,0

d0,1

d0,2

d0,3

d0,4

pA0,5

pA0,6 + d1,0

d1,0

d1,1

d1,2

d1,3

d1,4

pA1,5

pA1,6 + d2,1

d2,0

d2,1

d2,2

d2,3

d2,4

pA2,5

pA2,6 + d3,2

d3,0

d3,1

d3,2

d3,3

d3,4

pA3,5

pA3,6 + d4,3

d4,0

d4,1

d4,2

d4,3

d4,4

pA4,5

pA4,6 + d0,4

III. C LASS A PARITY N ODES
Class A parity nodes are constructed using a modified
(nA , k) MDS code, with k + 2 ≤ nA < 2k, over GF(q). In
particular, we start from an (nA , k) MDS code and apply piggybacks [13] to some of the parity symbols. The construction
of Class A parity nodes is performed in two steps as follows.
1) Encode each row of the data array using an (nA , k) MDS
code (same code for each row). The parity symbol pAi,j
is obtained as2

P5A

Fig. 2. A (7, 5) Class A code with τ = 1 constructed from a (7, 5) MDS
code. P5A and P6A are the parity nodes. For each row j, colored symbols
belong to DRj .

Then, the set DRj is the set of k − 1 data symbols that are
read from row j to recover τ + 1 data symbols of node j using
Class A parity nodes.
Example 1: An example of a Class A code is shown in
Fig. 2. One can verify that the code can correct any 2 node
failures. For each row j, the set DRj is indicated in red color.
For instance, DR0 = {d0,1 , d0,2 , d0,3 , d0,4 }.
The main purpose of Class A parity nodes is to provide good
erasure correcting capability. However, the use of piggybacks
helps also in reducing the number of symbols that need to
be read to repair the τ + 1 symbols of a failed node that are
repaired using the Class A code, as compared to MDS codes.
The remaining k − τ − 1 data symbols of the failed node can
also be recovered from Class A parity nodes, but at a high
symbol read cost of k. Hence, the idea is to add another class
of parity nodes, namely Class B parity nodes, in such a way
that these symbols can be recovered with lower read cost.
IV. C LASS B PARITY N ODES
Class B parity nodes are obtained using an (nB , k) linear
block code with nB < 2k − τ − 1 over GF(q) to encode the
k×k data symbols of the data array. This generates k×(nB −k)
Class B parity symbols, pBi,l , i = 0, . . . , k − 1, l = nA , . . . , n−
1. In [17], we presented an algorithm to construct Class B
codes. In this section, we present a similar construction in a
much more compact, mathematical manner.
A. Definitions and Preliminaries
Definition 3: For j = 0, . . . , k − 1, the index set Qj is
defined as
Qj =
{((j + τ + 1)k , j), ((j + τ + 2)k , j), . . . , ((j + k − 1)k , j)}.
Assume that data node j fails. It is easy to see that the set
DQj is the set of k − τ − 1 data symbols that are not recovered
using Class A parity nodes.
Example 2: For the example in Fig. 2, the set DQj is indicated by hatched symbols for each column j, j = 0, . . . , k −1.
For instance, DQ0 = {d2,0 , d3,0 , d4,0 }.
For later use, we also define the following set.

4

Definition 4: For j = 0, . . . , k − 1, the index set Xj is
defined as

P7B

P8B

P9B

d2,0 + d0,1 + d0,2

d3,0 + d0,1

d4,0

d3,1 + d1,2 + d1,3

d4,1 + d1,2

d0,1

d4,2 + d2,3 + d2,4

d0,2 + d2,3

d1,2

d0,3 + d3,4 + d3,0

d1,3 + d3,4

d2,3

d1,4 + d4,0 + d4,1

d2,4 + d4,0

d3,4

Xj = {(j, (j + 1)k ), (j, (j + 2)k ), . . . , (j, (j + k − τ − 1)k )}.
k−1
Note that Xj = Rj ∩ {∪l=0
Ql }.
Example 3: For the example in Fig. 2, the set DXj is
indicated by hatched symbols for each row j. For instance,
X0 = R0 ∩{Q0 ∪Q1 ∪Q2 ∪Q3 ∪Q4 } = {(0, 1), (0, 2), (0, 3)},
thus we have DX0 = {d0,1 , d0,2 , d0,3 }.
The purpose of Class B parity nodes is to allow the recovery
of the data symbols in DQj , j = 0, . . . , k − 1, at a low
additional read cost. Note that after recovering τ + 1 symbols
using Class A parity nodes, the data symbols in the sets DRj
are already stored in the decoder memory. Therefore, they
are accessible for the recovery of the remaining k − τ − 1
data symbols using Class B parity nodes without the need of
reading them again. The main idea is based on the following
proposition.
Proposition 1: If a Class B parity symbol pB is the sum of
one data symbol d ∈ DQj and a number of data symbols in
DXj , then the recovery of d comes at the cost of one additional
read (one should read parity symbol pB ).
This observation is used in the construction of Class B parity
nodes in Section IV-B below to reduce the normalized repair
bandwidth λ. In particular, we add up to k − τ − 1 Class B
parity nodes which allow to reduce the additional read cost of
all k(k − τ − 1) data symbols in all DQj ’s to 1. (The addition
of a single Class B parity node allows to recover one new
data symbol in each DQj , j = 0, . . . , k − 1, at the cost of one
additional read.)

Fig. 3. Class B parity nodes for the data nodes in Fig. 2.

t = 0, . . . , k − 1, the parity symbols in the first Class B parity
node (the 7-th node) are
pBt,7 = d(2+t)5 ,t
+

1
X

dt,(1+j+t)5 = d(2+t)5 ,t + dt,(1+t)5 + dt,(2+t)5 .

j=0

The constructed parity symbols are as seen in Fig. 3, where the
t-th row in node P7B contains the parity symbol pBt,7 . Notice
that d(2+t)5 ,t ∈ DQt and {dt,(1+t)5 , dt,(2+t)5 } ⊂ DXt . In a
similar way, the parity symbols in nodes P8B and P9B are
pBt,8 = d(3+t)5 ,t +

0
X

dt,(1+j+t)5 = d(3+t)5 ,t + dt,(1+t)5

j=0

and
pBt,9 = d(4+t)5 ,t +

−1
X

dt,(1+j+t)5 = d(4+t)5 ,t ,

j=0

B. Construction of Class B Nodes
For t = 0, . . . , k − 1, each parity symbol in the l-th Class
B parity node, l = nA , . . . , n − 1, is sequentially constructed
as
pBt,l = d(τ +1−nA +l+t)k ,t +

k−τ −3+n
X A −l

dt,(1+j+t)k .

(4)

j=0

The construction above follows Proposition 1 wherein
k−τ −3+nA −l
⊆
d(τ +1−nA +l+t)k ,t ∈ DQt and {dt,(1+j+t)k }j=0
DXt . This ensures that the read cost of each of the k symbols
d(τ +1−nA +l+t)k ,t is 1. Thus, the addition of each parity symbol
leads to k data symbols to have a read cost of 1. The same
principle was used in [17]. It should be noted that the set of
data symbols used in the construction of the parity symbols
in (4) may be different compared to the construction in [17].
However, the overall average repair bandwidth remains the
same. In the sequel, we will refer to the construction of Class
B parity nodes according to (4) as Construction 1.
Example 4: With the aim to construct a (10, 5) code,
consider the construction of an (8, 5) Class B code where the
(7, 5) Class A code, with τ = 1, is as shown in Fig. 2. For

respectively.
Consider the repair of the first data node in Fig. 2. The
symbol d0,0 is reconstructed using pA0,5 . This requires reading
the symbols d0,1 , d0,2 , d0,3 , and d0,4 . Since pA0,6 is a function
of all data symbols in the first row, reading pA0,6 + d1,0 is
sufficient for the recovery of d1,0 . From Fig. 3, the symbols
d2,0 , d3,0 , and d4,0 can be recovered by reading just the parities
d2,0 + d0,1 + d0,2 , d3,0 + d0,1 , and d4,0 , respectively. Thus,
reading 5 + 4 = 9 symbols is sufficient to recover all the
symbols in the node, and the normalized repair bandwidth is
9/5 = 1.8 per failed symbol. A more formal repair procedure
is presented in Section IV-C.
Adding nB − k Class B parity nodes allows to reduce the
additional read cost of nB − k data symbols from each DQj ,
j = 0, . . . , k − 1, to 1. However, this comes at the cost
of a reduction in the code rate, i.e., the storage overhead is
increased. In the above example, adding nB − k = 3 Class B
parity nodes leads to the reduction in code rate from R = 5/7
to R = 5/10 = 1/2. If a lower storage overhead is required,
Class B parity nodes can be punctured, starting from the last
parity node (for the code in Example 4, nodes P9B , P8B , and
P7B can be punctured in this order), at the expense of an
increased repair bandwidth. If all Class B parity nodes are
punctured, only Class A parity nodes would remain, and the

5

repair bandwidth is equal to the one of the Class A code.
Thus, our code construction gives a family of rate-compatible
codes which provides a tradeoff between repair bandwidth and
storage overhead: adding more Class B parity nodes reduces
the repair bandwidth, but also increases the storage overhead.

d0,0

d0,1

d0,2

P4A

P5A

P6B

P6B,h

d0,3

pA0,4

pA0,5 + d1,0

d2,0 + d0,1

d2,0 + d0,2

pA1,5

+ d2,1

d3,1 + d1,2

d3,1 + d1,3

d1,0

d1,1

d1,2

d1,3

pA1,4

d2,0

d2,1

d2,2

d2,3

pA2,4

pA2,5 + d3,2

d0,2 + d2,3

d1,2 + d2,3

d3,0

d3,1

d3,2

d3,3

pA3,4

pA3,5 + d0,3

d1,3 + d3,0

d3,0 + d0,1

(a)

(b)

C. Repair of a Single Node Failure: Decoding Schedule
The repair of a failed data node proceeds as follows. First,
τ + 1 symbols are repaired using Class A parity nodes. Then,
the remaining symbols are repaired using Class B parity nodes.
With a slight abuse of language, we will refer to the repair
of symbols using Class A and Class B parity nodes as the
decoding of Class A and Class B codes, respectively.
We will need the following definition.
Definition 5: Consider a Class B parity node and let P B
denote the set of parity symbols in this node. Also, let d ∈
for some j and pB ∈ P B be the parity symbol pB =
DQj P
d + d′ ∈D′ d′ , where D′ ⊂ D, i.e., the parity symbol pB is
the sum of d and a subset of other data symbols. We define
D̆ = D′ ∪ {d}.
Suppose that node j fails. Decoding is as follows.
• Decoding the Class A code. To reconstruct the failed data
symbol in the j-th row of the code array, k symbols (k−1
data symbols and pAj,k ) in the j-th row are read. These
symbols are now cached in the memory. We then read the
τ piggybacked symbols in the j-th row. By construction
(see (3)), this allows to repair τ failed symbols, at the
cost of an additional read each.
• Decoding the Class B code. Each remaining failed data
symbol di,j ∈ DQj is obtained by reading a Class B
parity symbol whose corresponding set D̆ (see Definition 5) contains di,j . In particular, if several Class B parity
symbols pBi′ ,j ′ contain di,j , we read the parity symbol
with largest index j ′ . This yields the lowest additional
read cost.
V. A H EURISTIC C ONSTRUCTION OF C LASS B N ODES
W ITH I MPROVED R EPAIR BANDWIDTH
In this section, we provide a way to improve the repair
bandwidth of the family of codes constructed so far. More
specifically, we achieve this by providing a heuristic algorithm
for the construction of the Class B code, which improves
Construction 1 in Section IV for some values of n and k.
The algorithm is based on a simple observation. Let pB1 and
B
p2 be two parity symbols constructed from ρ data symbols in
D in two different ways as follows:
pB1 = di,j + dj,i + dj,i2 + · · · + dj,iρ−1 ,

(5)

pB2

(6)

= di,j + dj,i1 + dj,i2 + · · · + dj,iρ−1 ,

where di,j ∈ DQj (see Definition 3), i1 , . . . , iρ−1 6= i, and
dj,i1 , dj,i2 , . . . , dj,iρ−1 ∈ DXj (see Definition 4). Note that
the only difference between the two parity symbols above is
that pB2 does not involve dj,i (and that pB1 does not involve
dj,i1 ). This has a major consequence in the repair of the
data symbols di,j , dj,i , . . . , dj,iρ −1 and di,j , dj,i1 , . . . , dj,iρ −1
using pB1 and pB2 , respectively. Consider the repair using parity

Fig. 4. A (7, 4) code constructed from a (6, 4) Class A code with τ = 1 and
a (5, 4) Class B code. (a) Class B node constructed according to Construction
1 in Section IV. (b) A different configuration of the Class B node that reduces
the repair bandwidth.

symbol pB1 . From Proposition 1, it is clear that the repair of
symbol di,j will have an additional read cost of 1, since the
remaining ρ − 1 data symbols are in DXj . As the symbol
dj,i ∈ DQi and di,j ∈ DXi , from Proposition 1 and the
fact that dj,i2 , . . . , dj,iρ−1 6∈ DXi , we can repair dj,i with an
additional read cost of ρ − 1. The remaining ρ − 2 symbols
each have an additional read cost of ρ, whereas the symbols
repaired using pB2 incur an additional read cost of 1 for the
symbol di,j and ρ for the remaining symbols. Clearly, we see
that the combined additional read cost, i.e., the sum of the
individual additional read costs for each data symbol using pB1
is lower (by 1) than that using pB2 .
In the way Class A parity nodes are constructed and due to
the structure of the sets DQj and DXj , it can be seen that di,j ∈
DQj and dj,i ∈ DXj when k ≥ 2(τ + 1). From Construction
1 of the Class B code in Section IV we observe that for odd
k and k > 2(τ + 1), the parity symbols in node PlB are as
in (5) for nA ≤ l ≤ nA + ⌊k/2⌋ − τ − 1. Furthermore, for
nA + ⌊k/2⌋ − τ ≤ l ≤ n − 1, the parity symbols in node PlB
have the structure in (6). On the other hand, for k even and
k ≥ 2(τ + 1), the parity symbols in the node PlB are as in (5)
for nA ≤ l ≤ nA + k/2 − τ − 2. However, contrary to case of k
odd, the parity symbols in the node PnBA +k/2−τ −1 follow (6).
But since k ≥ 2(τ + 1), we know that di,j ∈ DQj and dj,i ∈
DXj . Thus, it is possible to construct some parity symbols in
this node as in (5), and Construction 1 of Class B nodes in the
previous section can be improved. However, the improvement
comes at the expense of the loss of the mathematical structure
of Class B nodes given in (4).
Example 5: Consider the (7, 4) code as shown in Fig. 4.
Fig. 4(a) shows the node P6B using Construction 1 in Section IV, while Fig. 4(b) shows a different configuration of
the node P6B . Note that k = 2(τ + 1) = 4. Thus, each pair
(DQj , DXj ) contains one symbol di,j and dj,i . The node P6B
has parity symbols according to (6), while P6B,h has two parity
symbols as in (5) and two parity symbols according to (6). The
configuration of the (7, 4) code arising from Construction 1
has a normalized repair bandwidth of 2, while the (7, 4) code
with node P6B,h in Fig. 4(b) has a repair bandwidth of 1.825,
i.e., an improvement is achieved.
In order to describe the modified code construction, we
define the function read(d, pB ) as follows.
Definition 6: Consider the construction of the parity symbol

6

pB as pB = d +

P

d′ ∈D ′

d′ (see Definition 5). Then,
B

read(d, p ) = |D̆\DXj |.

For a given data symbol d, the function read(d, pB ) gives
the additional number of symbols that need to be read to
recover d (considering the fact that some symbols are already
cached in the memory). The set D̆ represents the set of data
symbols that the parity symbol pB is a function of. We use the
index set U to represent the indices of such data symbols. We
denote by Ut , t = 0, . . . , k − 1, the index set corresponding to
the t-th parity symbol in the node (there are k parity symbols
in a parity node).
In the following, denote by A = [ai,j ] a temporary matrix
of read costs for the respective data symbols in D = [di,j ].
After Class A decoding,

k−1

∞ if di,j ∈ ∪t=0 DQt
ai,j = k if i = j
.
(7)


1 otherwise
In Section V-A below, we will show that the construction of
parities depends upon the entries of A. To this extent, for some
real matrix M = [mi,j ] and index set I, we define Ψ(MI )
as the set of indices of matrix elements of M from I whose
values are equal to the maximum of all entries in M . More
formally, Ψ(MI ) is defined as


′
′
Ψ(MI ) = (i, j) ∈ I | mi,j = ′max
mi ,j . (8)
′
(i ,j )∈I

The heuristic algorithm to construct the Class B code is
given in Appendix B and we will refer to the construction of
the Class B code according to this algorithm as Construction 2.
In the following subsection, we clarify the heuristic algorithm
to construct the Class B code with the help of a simple
example.
A. Construction Example
Let us consider the construction of a (7, 4) code using a
(6, 4) Class A code and a (5, 4) Class B code. In total, there
are three parity nodes; two Class A parity nodes, denoted by
P4A and P5A , respectively, and one Class B parity node, denoted
by P6B,h , where the upper index h is used to denote that the
parity node is constructed using the heuristic algorithm. The
parity symbols of the nodes are depicted in Fig. 4. Each parity
symbol of the Class B parity node is the sum of k − τ − 1
data symbols di,j ∈ ∪j ′ DQj′ , constructed such that the read
cost of each symbol di,j is lower than ai,j as shown below.
1. Construction of P6B,h
Each parity symbol in this node is constructed using ρ6 =
k − τ − 1 = 2 unique symbols as follows.
1.a Since no symbols have been constructed yet, we
have Ut1 = ∅, t1 = 0, . . . , 3. (This corresponds to
the execution of Line 1 to Line 19 of Algorithm 2
in Appendix B.)
1.b Select di,0 ∈ DQ0 such that its read cost is maximum, i.e., di,0 ∈ DΨ(AQ0 ) . Choose di,0 = d2,0 ,
as a2,0 = ∞. Note that we choose d2,0 since
d0,2 ∈ DX0 .

1.c Construct p0,6 = d2,0 + d0,2 (see Line 4 of
Algorithm 2). Correspondingly, we have U0 =
{(2, 0), (0, 2)}.
1.d Recursively construct the next parity symbol in the
node as follows. Similar to Item 1.b, choose d3,1 ∈
DΨ(AQ1 ) . Construct p1,6 = d3,1 + d1,3 . Likewise,
we have U1 = {(1, 3), (3, 1)}
1.e For the next parity symbol, note that d0,2 is already
used in the construction of p0,6 . The only possible
choice of symbol in DQ2 is d1,2 , but d2,1 6∈ DX2 .
Therefore, we choose di1 ,2 ∈ DΨ(AQ2 \∪j′ Uj′ ) (see
Line 7 of Algorithm 2). In particular, since a1,2 =
∞, we choose di1 ,2 = d1,2 . Then, Lines 8 to 11 of
Algorithm 2 are executed.
1.f Choose an element d2,i2 ∈ DX2 \∪j′ Uj′ . In other
words choose a symbol in DX2 which has not been
used in p0,6 and p1,6 . We have d2,i2 = d2,3 . Construct p2,6 = d1,2 +d2,3 . Thus, U2 = {(1, 2), (2, 3)}.
1.g To construct the last parity symbol, we look for data
symbols from the sets DQ3 and DX3 . However, all
symbols in DQ3 have been used in the construction
of previous parity symbols. Therefore, we cyclically
shift to the next pair of sets (DQ0 , DX0 ). Following
Items 1.e and 1.f, we have p3,6 = d3,0 + d0,1 and
U3 = {(3, 0), (0, 1)}.
Note that |Ut | = 2 for all t, thus this completes the construction of the (7, 4) code. The Class B parity node constructed
above is depicted in Fig. 4(b).
B. Discussion
In general, the algorithm constructs nB − k parity nodes,
B
, recursively. In the l-th Class B node, l =
PnBA , . . . , Pn−1
nA , . . . , n − 1, each parity symbol is a sum of at most
ρl = k − τ − 1 − l + nA symbols di,j ∈ ∪j ′ DQj′ . Each parity
symbol pt,l , t = 0, . . . , k − 1, in the l-th Class B parity node
with ρl > 1 is constructed recursively with ρl − 1 recursion
steps. In the first recursion step, each parity symbol pt,l is
either equal to a single data symbol or a sum of 2 data symbols.
In the latter case, the first symbol di,j ∈ DQt is chosen
as the symbol with the largest read cost ai,j . The second
symbol is dj,i ∈ DXt if such a symbol exists. Otherwise
(i.e., if dj,i 6∈ DXt ), symbol dj,i′′ ∈ DXt is chosen. In the
remaining ρl − 2 recursion steps a subsequent data symbol
dj,i′ ∈ DXt (if it exists) is added to pt,l . Doing so ensures
that k symbols have a new read cost that is reduced to 1 when
parity symbols pt,l are used to recover them. Having obtained
these parity symbols, the read costs of all data symbols in
∪j ′ DQj′ are updated and stored in A. This process is repeated
for successive parity nodes. If ρl = 1 for the l-th parity node,
its parity symbols pt,l are equal to the data symbols di,j ∈ DQt
whose read costs ai,j are the maximum possible.
In the above example, only a single recursion for the
construction of P6B,h is needed, where each parity symbol is
a sum of two data symbols.
VI. C ODE C HARACTERISTICS AND C OMPARISON
In this section, we characterize different properties of the
codes presented in Sections III-V. In particular, we focus

7

TABLE I
C OMPARISON OF (n, k) CODES THAT AIM AT REDUCING THE REPAIR BANDWIDTH . T HE REPAIR BANDWIDTH AND THE REPAIR COMPLEXITY ARE
NORMALIZED PER SYMBOL , WHILE THE ENCODING COMPLEXITY IS GIVEN PER ROW OF THE CODE ARRAY. N OTE THAT FOR MDR CODES , n = k + 2.
β
Fault Tolerance
Norm. Repair Band.
Norm. Repair Compl.
Enc. Complexity
1

MDS

n−k

k

n−k

2

n−k

(k−tr )(k+t)+tr (k+tr +ℓ−2)
2k

1

r+1

MDR [9]

2k

2

(n −

Piggyback [13]

k

Proposed codes

k
O((⌈ n−k−r
⌉

k)k−1

LRC [3]

Zigzag [10]

O((k − 1)ν + kν 2 )

k
n−k−r
k+1
2
n−1
n−k

≥ nA −k −τ +1

≤

O((k − 1)ν +

O((k − 1)ν)

kν 2 )

O((n − k)(k − 1)ν + kν 2 )

–

–

CR /k

CE

For Construction 1, the remaining k − τ − 1 failed data
symbols in the failed node are corrected using k − τ − 1 parity
symbols from nB − k Class B nodes. To this extent, let fl ,
l = nA , . . . , n − 1, denote the number of parity symbols
Pn−1 that
are used from the l-th Class B node. Note that l=nA fl =
k − τ − 1. The repair complexity for repairing the remaining
k − τ − 1 symbols is

A. Fault Tolerance
The fault tolerance of the Class A code depends on the
MDS code used in its construction and τ , as stated in Theorem
1. Hence, the proposed code family has fault tolerance f ≥
nA − k − τ + 1. Since 1 ≤ τ ≤ nA − k − 1, the proposed codes
have a fault tolerance of at least 2.

k
⌉ − 1)ν)
rO((k − 1)ν + kν 2 ) + (n − k − r)O((⌈ n−k−r

O((k − 1)ν)

k+τ +(k−τ −1)2
k

on the fault tolerance, repair bandwidth, repair complexity,
and encoding complexity. We consider the complexity of
elementary arithmetic operations on field elements of size
ν = ⌈log2 q⌉ in GF(q). The complexity of addition is O(ν),
while that of multiplication is O(ν 2 ), where the argument of
O(·) denotes the number of elementary binary additions.3

− 1)ν)

O((n − k)(k − 1)ν + kν 2 )

CBr =

n−1
X

O(fl (k − τ − 2 − l + nA )ν).

According to Construction 1 in Section IV, we have
fnA = fnA +1 = · · · = fn−2 = 1,
fn−1 = k − τ − 1 −

λ ≤ (k + τ + (k − τ − 1)2 )/k.
It is observed that when τ increases, the fault tolerance reduces
while λ improves.

n−2
X

fl .

l=nA

B. Normalized Repair Bandwidth
According to Section IV-C, to repair the first τ + 1 symbols
in a failed node, k − 1 data symbols and τ + 1 Class A parity
symbols are read. The remaining k − τ − 1 data symbols in the
failed node are repaired by reading Class B parity symbols.
As seen in Section IV, the parity symbols in the first Class
B parity node are constructed from sets of data symbols of
cardinality |DQj | = k − τ − 1. Therefore, to repair each of
the k − τ − 1 data symbols in this set it is sufficient to read at
most k − τ − 1 symbols. The remaining Class B parity nodes
are constructed from fewer symbols than k − τ − 1. An upper
bound on the normalized repair bandwidth is therefore

(9)

l=nA

Thus, (9) simplifies to
CBr =

n−2
X

O((k − τ − 2 − l + nA )ν)

l=nA

+ O((k − τ − n + nA )(k − τ − 1 − n + nA )ν).
For Construction 2, the final k − τ − 1 failed data symbols
require at most k−τ −2 additions, since Class B parity symbols
are constructed as sums of at most k − τ − 1 data symbols.
The corresponding repair complexity is therefore
CBr ≤ O((k − τ − 2)(k − τ − 1)ν).
Finally, the total repair complexity is CR = CAr + CBr .
D. Encoding Complexity

To repair the first symbol requires k multiplications and
k − 1 additions. To repair the following τ symbols require an
additional τ k multiplications and additions. Thus, the repair
complexity of repairing τ + 1 failed symbols is

The encoding complexity, denoted by CE , is the sum of
the encoding complexities of Class A and Class B codes. The
generation of each of the nA −k Class A parity symbols in one
row of the code array, pAi,j in (2), requires k multiplications
and k − 1 additions. Adding data symbols to τ of these parity
symbols according to (3) requires an additional τ additions.
The encoding complexity of the Class A code is therefore

CAr = O((k − 1)ν + kν 2 ) + O(τ k(ν + ν 2 )).

CAe = O((nA − k)(kν 2 + (k − 1)ν)) + O(τ ν).

C. Repair Complexity of a Failed Node

3 It should be noted that the complexity of multiplication is quite pessimistic.
However, for the sake of simplicity we assume it to be O(ν 2 ). When the field
is GF(2ν ) there exist algorithms such as the Karatsuba-Ofman algorithm [18],
[19] and the Fast Fourier Transform [20]–[22] that lower the complexity to
O(ν log2 3 ) and O(ν log2 ν), respectively.

According to Sections IV and V, the parity symbols in the
first Class B parity node are constructed as sums of at most k−
τ − 1 data symbols, and each parity symbol in the subsequent
parity nodes is constructed as a sum of data symbols from a

8

TABLE II
C OMPARISON OF NORMALIZED REPAIR COMPLEXITY OF (n, k, f ) BASIC PM-MBR CODES [14] AND THE PROPOSED CODES WITH τ = 1.
Proposed

nA

R

GF(q)

BASIC PM-MBR

Rb

δb

Rm

Crb

Cr

(9, 5, 3)
(11, 7, 3)
(14, 9, 3)

8
10
12

0.5556
0.6364
0.6428

GF(11)
GF(11)
GF(13)

(8, 5, 3)
(11, 7, 4)
(14, 9, 5)

0.4464
0.4454
0.4450

7
10
13

R11
R11
R17

135
187.5
384

44
50.857
55.556

550
(8, 5, 3)

normalized repair complexity

500
450
(8, 4, 4)

400
350

(9, 5, 4)(8, 5, 3)
(10, 5, 5)

300 (8, 4, 4)
250

(10, 5, 5), (9, 5, 4), (8, 5, 3)

(7, 4, 3)

(8, 4, 4), (7, 4, 3)

(7, 4, 3)

(10, 5, 2) (9, 5, 2)

MDS code
LRC [3]
Zigzag [10]
Piggyback [13]
Our code, τ = 1, nA = k + 2
Our code, τ = 1, nA = k + 3
Our code, τ = 2, nA = k + 3

200 (8, 4, 2)(7, 4, 2)
(8, 5, 2)
(10, 5, 2)
(9, 5, 2)
150
(8, 4, 2) (10, 5, 3)(9, 5, 3)
(8, 4, 3)
100
50

(10, 5, 4), (9, 5, 3), (8, 5, 2)

(8, 4, 3), (7, 4, 2)
0
1.5

2

2.5

3

3.5

4

4.5

5

normalized repair bandwidth (λ)
Fig. 5. Comparisons of different codes (n, k, f ) with ν = 8.

set of size one less. Therefore, the encoding complexity of the
Class B code is
CBe ≤

n−n
XA

O((k − τ − 1 − i)ν).

(10)

i=1

Note that for Construction 1 the upper bound on CBe in (10)
is tight. Finally, CE = CAe + CBe .
E. Code Comparison
Table I provides a summary of the characteristics of the
proposed codes as well as different codes proposed in the
literature.4 In the table, column 2 reports the value of β (see
(1)) for each code construction. For our code, β = k, unlike
for MDR and Zigzag codes, for which β grows exponentially
with k. This implies that our codes require less memory
to cache data symbols during repair. The piggyback codes
presented in the table and throughout this section are from the
piggybacking design 1 in [13], which provides efficient repair
for only data nodes. The fault tolerance f , the normalized
repair bandwidth λ, the normalized repair complexity, and the
encoding complexity, discussed in the previous subsections,
are reported in columns 3, 4, 5, and 6, respectively.
In Fig. 5, we compare our codes with Construction 1 for
the Class B codes (i.e., the codes are constructed as shown
in Sections III and IV) with other codes in the literature. In
particular, the figure plots the normalized repair complexity of
(n, k, f ) codes over GF(28 ) (ν = 8) versus their normalized
4 The variables (t, t ) and r in Table I are defined in [13] and [3],
r
respectively. The definition of ℓ comes directly from r that is defined in
[13].

repair bandwidth λ. In the figure, we show the exact repair
bandwidth for our proposed codes, while the reported repair
complexities and the repair bandwidths of the other codes are
from Table I.
The best codes for a DSS should be the ones that achieve the
lowest repair bandwidth and have the lowest repair complexity.
As seen in Fig. 5, MDS codes have both high repair complexity
and repair bandwidth, but they are optimal in terms of fault
tolerance for a given n and k. Zigzag codes achieve the same
fault tolerance and high repair complexity as MDS codes, but
at the lowest repair bandwidth. At the other end, LRCs yield
the lowest repair complexity, but a higher repair bandwidth
and worse fault tolerance than Zigzag codes. Piggyback codes
have a repair bandwidth between those of Zigzag and MDS
codes, but with a higher repair complexity. For a given storage
overhead, our proposed codes have better repair bandwidth
than MDS codes, Piggyback codes, and LRCs, and equal
or similar repair bandwidth as Zigzag codes. Furthermore,
they yield lower repair complexity as compared to MDS,
Piggyback, and Zigzag codes. However, the benefits in terms
of repair bandwidth and/or repair complexity with respect to
MDS and Zigzag codes come at a price of a lower fault
tolerance.
In Table II, we compare the normalized repair complexity
of the proposed codes with Construction 1 for the Class B
code and BASIC PM-MBR codes presented in [14]. BASIC
PM-MBR codes are constructed from an algebraic ring Rm ,
where each symbol in the ring is a binary vector of length
m. In order to have a fair comparison with our codes, we
take the smallest possible field size for our codes and the
smallest possible ring size for the codes in [14]. Furthermore,
to compare codes with similar storage overhead, we consider
BASIC PM-MBR codes with repair locality, denoted by δ b ,
that leads to the same file size as for our proposed codes
(which is equal to k 2 ) and code length n such that the code
rate (which is the inverse of the storage overhead) is as close
as possible to that of our proposed codes. The Class A codes
of the proposed codes in the table are (nA , nA − f ) RS codes.
The codes are over GF(nA + 1) if nA + 1 is a prime (or a
power of a prime). If nA + 1 is not a prime (or a power of
prime), we construct an (n′ , n′ − f ) RS code over GF(n′ + 1),
where n′ + 1 is the smallest prime (or the smallest power of
a prime) with n′ + 1 ≥ nA + 1, and then we shorten the RS
code to obtain an (nA , nA − f ) Class A code. In the table, the
parameters for the proposed codes are given in columns 1 to 4
and those of the codes in [14] in columns 5 to 8. The code rates
R and Rb of the proposed codes and the BASIC PM-MBR
codes5 are given in columns 3 and 6, respectively. The smallest
5 BASIC PM-MBR codes have
k+1
+ k(δb − k) is the file size
2

code rate Rb = B/nδb , where B =
and δb ∈ {k, k + 1, . . . , n − 1}.

9

TABLE III
I MPROVEMENT IN NORMALIZED REPAIR BANDWIDTH OF THE PROPOSED
(n, k) CODES WHEN THE C LASS B NODES ARE HEURISTICALLY
CONSTRUCTED .
Code

nA

τ

λC1

λC2

Improvement

(7, 4)
(10, 6)
(13, 8)
(14, 8)
(16, 10)

6
9
12
12
15

1
2
3
3
4

2
2.5
3
2.375
3.5

1.875
2.4167
2.9375
2.3125
3.45

6.25%
3.33%
2.08%
2.63%
1.43%

possible field size for our codes and the smallest possible ring
size for the BASIC PM-MBR codes are given in columns
4 and 8, respectively. The normalized repair complexity6 for
BASIC PM-MBR codes, Crb , is given in column 9, while the
normalized repair complexity of the proposed codes, Cr , is
given in the last column. It can be seen that the proposed
codes achieve significantly better repair complexity. However,
this comes at the cost of a lower fault-tolerance for the codes in
rows 2 and 3 (but our codes have significantly higher code rate)
and higher repair bandwidth (since BASIC PM-MBR codes are
MBR codes, their normalized repair bandwidth is equal to 1).
For the (9, 5, 3) code, the same fault tolerance of the (8, 5, 3)
code in [14] is achieved, despite the fact that the proposed
code has a higher code rate.
In Table III, we compare the normalized repair bandwidth
of the proposed codes using Construction 1 and Construction
2 for Class B nodes. In the table, with λC1 and λC2 , we
refer to the normalized repair bandwidth for Construction 1
and Construction 2, respectively. For the codes presented, it
is seen that the heuristic construction yields an improvement
in repair bandwidth in the range of 1% − 7% with respect to
Construction 1.
VII. C ONCLUSION
In this paper, we constructed a new class of codes that
achieve low repair bandwidth and low repair complexity for
a single node failure. The codes are constructed from two
smaller codes, Class A and B, where the former focuses on
the fault tolerance of the code, and the latter focuses on
reducing the repair bandwidth and complexity. Our proposed
codes achieve better repair complexity than Zigzag codes,
Piggyback codes, and BASIC PM-MBR codes and better
repair bandwidth than LRCs, at the cost of slightly lower
fault tolerance. A side effect of such a construction is that the
number of symbols per node that needs to be encoded grows
only linearly with the code dimension. This implies that our
codes are suitable for memory constrained DSSs as compared
to Zigzag and MDR codes, for which the number of symbols
per node increases exponentially with the code dimension.
A PPENDIX A
P ROOF OF T HEOREM 1
Without loss of generality, consider the (nA − τ )-th piggybacked node whose parity symbols include piggybacks. By
6 The normalized repair complexity of BASIC PM-MBR codes is C b =
r
(3.5δb +2.5)(m−1)/2 [14]. Such codes have β = δb , λ = 1, and f = n−k.
The value of m is conditioned on the code length n (see [14, Th. 14]).

construction of the Class A code, these piggybacks are from
k distinct rows and k distinct columns of the data array D.
We will use this observations in the proof. We first proceed
to prove that θ + 1 ≤ nA − k − τ + 1 data nodes can be
corrected using θ non-modified parity nodes and the (nA − τ )th piggybacked node. Using this, we will complete the proof
of Theorem 1.
Lemma 1: Consider an (nA , k) Class A code with k + 2 ≤
nA < 2k. The code consists of τ piggybacked nodes and
nA − k − τ non-modified MDS parity nodes. Then, the code
can correct θ + 1 data node failures using θ ≤ nA − k − τ nonmodified parity nodes and a single piggybacked parity node.
Proof: Assume that θ+1 data nodes fail. By construction,
A,p
the parity symbol p(i−1)
is (see (3))
k ,nA −τ
A,p
p(i−1)
= pA(i−1)k ,(nA −τ ) + di,(i−1)k ,
k ,(nA −τ )

(11)

where i = 0, . . . , k − 1. Let i be the largest row index such
that the symbol di,(i−1)k is not erased (such a non-erased data
symbol always exists since not all data nodes fail). To recover
all data symbols, set i′ = i and repeat the following steps k
times.
1) Obtain the MDS parity symbol pA(i′ −1)k ,(nA −τ ) (see (11))
in the (i′ − 1)k -th row.
2) Using the θ + 1 MDS parity symbols in the (i′ − 1)k -th
row, recover the θ + 1 symbols in the (i′ − 1)k -th row of
the failed data nodes, from which the piggyback symbol
d(i′ −1)k ,(i′ −2)k is obtained.
3) i′ ← i′ − 1.
With this recursion, one recovers the θ + 1 failed data nodes.
To prove that the code can correct any nA − k − τ + 1
failed nodes (both data and parity nodes) assume that the
code consists of nA − k − τ non-modified parity nodes and
a single piggybacked node (in other words, τ − 1 of the
piggybacked nodes are punctured). We consider two cases.
In the first case, assume that the piggybacked node is one of
the nA − k − τ + 1 failures. One can view the resulting code
as a punctured MDS code consisting of nA − k − τ MDS
parity nodes. Since the punctured code is an MDS code, one
can correct nA − k − τ failures and recover all data nodes,
from which the failed piggybacked node can be recovered.
Thus, the code can recover nA − k − τ + 1 node failures.
In the second case, we assume that the piggybacked node is
not one of the failed nodes. Now consider the following node
failure pattern. Let ξ ≤ nA − k − τ + 1 data nodes fail and
nA − k − τ + 1 − ξ parity nodes fail. Then, by Lemma 1
the available ξ parity nodes (consisting of ξ − 1 non-modified
parity and a single piggybacked node) can correct all ξ failed
data nodes, and from the data nodes all failed parity nodes can
be corrected. Thus, nA −k −τ +1 nodes can be corrected. The
fault tolerance for the code with nA −k−τ non-modified nodes
and τ piggybacked nodes is at least the same, and therefore
nA − k − τ + 1 is a lower bound on the fault tolerance of the
Class A code.

10

Algorithm 1: Class B node construction
Initialization:
A = [ai,j ] as defined in (7)
n = nA + nB − k with nB < 2k − τ − 1 and nA < 2k
1 for l ∈ {nA , . . . , n − 1} do
2
ρl ← k − τ − 1 − l + n A
3
if l ≤ nA + k/2 − τ − 2 then
4
PlB,h ← PlB
5
else if l > nA + k/2 − τ − 2 and ρl > 1 then
6
PlB,h ← ConstructNode(A, ρl)
7
else if l > nA + k/2 − τ − 2 and ρl = 1 then
8
PlB,h ← ConstructLastNode()
9
end
10
A ← UpdateReadCost()
11 end

di,j . A symbol di,j such that there is a valid dj,i ∈ DXj
is preferred, since it allows a larger reduction of the repair
bandwidth.
The second part of the algorithm chooses recursively at most
ρl − 2 data symbols that should participate in the construction
of the k parity symbols. The algorithm chooses a symbol
dj,i3 ∈ DXj \∪j′ Uj′ 6= ∅ such that read(dj,i3 , pBj,t + dj,i3 ) <
aj,i3 (see Line 23). In other words, choose data symbols
such that their read cost do not increase. It may happen that
DXj \∪j′ Uj′ = ∅. If so, select dj2 ,i ∈ ∪j1 DXj1 \∪j′ Uj′ such
1
1
that a symbol di′ ,j2 ∈ DUt , for some i′ 6= i, exists, and then
add dj2 ,i to the parity symbol pBt,l (see Line 33). If dj2 ,i does
not exist, then an arbitrary symbol dj3 ,i ∈ ∪j1 DXj1 \∪j′ Uj′ is
1
1
added (see Line 37). This process is then repeated ρl −2 times.
B. ConstructLastNode ( )

A PPENDIX B
C LASS B PARITY N ODE C ONSTRUCTION
In this appendix, we give an algorithm that constructs nB −k
B,h
Class B parity nodes PnB,h
, PnB,h
, . . . , Pn−1
. The algorithm
A
A +1
is a heuristic for the construction of Class B parity nodes such
that the repair bandwidth of failed nodes is further reduced in
comparison with Construction 1 in Section IV.
The nodes PlB,h , l = nA , . . . , n − 1, are constructed
recursively as shown in Algorithm 1. The k parity symbols in the l-th node are sums of at most ρl data symbols
di,j ∈ ∪j ′ DQj′ . The construction of the l-th node for
l ≤ nA + k/2 − τ − 2 (see Line 4) is identical to that
resulting from Construction 1 in Section IV. The remaining parity nodes PlB,h , l > nA + k/2 − τ − 2, are constructed using the sub-procedures ConstructNode(A, ρl)
and ConstructLastNode( ). After the construction of
each parity node, the read costs of the data symbols di,j
are updated by the sub-procedure UpdateReadCost( ). In
the following, we describe each of the above-mentioned subprocedures.
A. ConstructNode (A, ρl )
This sub-procedure allows the construction of the l-th Class
B parity node, where each parity symbol in the node is a
sum of at most ρl data symbols. The algorithm for the subprocedure is shown in Algorithm 2. Here, the algorithm is
divided into two parts. The first part (Line 1 to Line 19) adds
at most two data symbols to each of the k parity symbols,
while the second part (Line 21 to Line 43) adds at most ρl − 2
data symbols.
In the first part, each parity symbol pBt,l , t = 0, . . . , k − 1, is
recursively constructed by adding a symbol di,j ∈ DQj \∪j′ Uj′
which has a corresponding read cost ai,j that is the largest
among all symbols in the index set Qj \ ∪j ′ Uj ′ (see Line 2
and Line 7). The next symbol added to pBt,l is dj,i ∈ DXj if
such a symbol exists (Line 4). Otherwise, the symbol added is
dj,i2 ∈ DXj \∪j′ Uj′ if such a symbol exists (Line 10). The set
Ut denotes the index set of data symbols from D that are added
to pBt,l . Note that there exist multiple choices for the symbol

This procedure constructs the l-th Class B parity node that
has ρl = 1. In other words, each parity symbol pBt,l is a data
symbol di,j ∈ ∪j ′ DQj′ . The procedure works as follows. First,
initialize Ut to be the empty set for t = 0, . . . , k − 1. Then,
for t = 0, . . . , k − 1, assign first the data symbol di,j to the
parity symbol pBt,l , where di,j ∈ DΨ(A∪ ′ Q ′ \∪ ′ U ′ ) , and then
j
j
t t
subsequently add (i, j) to Ut . Note that for each iteration there
may exist several choices for di,j , in which case we can pick
one of these randomly.
C. UpdateReadCost ( )
After the construction of the l-th node, we update the read
costs of all data symbols di,j ∈ ∪j ′ DQj′ . These updated values
are used during the construction of the (l + 1)-th node. The
read cost updates for the parity symbol pBt,l , t = 0, . . . , k − 1,
are
ai,j = read(di,j , pBt,l ), ∀di,j ∈ DUt .
R EFERENCES
[1] J. Huang, X. Liang, X. Qin, P. Xie, and C. Xie, “Scale-RS: An efficient
scaling scheme for RS-coded storage clusters,” IEEE Trans. Parallel and
Distributed Systems, vol. 26, no. 6, pp. 1704–1717, Jun. 2015.
[2] C. Huang, M. Chen, and J. Li, “Pyramid codes: Flexible schemes to
trade space for access efficiency in reliable data storage systems,” in
Proc. IEEE Int. Symp. Network Comput. and Appl. (NCA), Cambridge,
MA, Jul. 2007.
[3] C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li,
and S. Yekhanin, “Erasure coding in Windows Azure storage,” in Proc.
USENIX Annual Technical Conf., Boston, MA, Jun. 2012.
[4] M. Sathiamoorthy, M. Asteris, D. Papailiopoulos, A. G. Dimakis,
R. Vadali, S. Chen, and D. Borthakur, “XORing elephants: Novel erasure
codes for big data,” in Proc. 39th Very Large Data Bases Endowment
(VLDB), Trento, Italy, Aug. 2013.
[5] D. Papailiopoulos and A. Dimakis, “Locally repairable codes,” IEEE
Trans. Inf. Theory, vol. 60, no. 10, pp. 5843–5855, Oct. 2014.
[6] A. Dimakis, P. Godfrey, Y. Wu, M. Wainwright, and K. Ramchandran,
“Network coding for distributed storage systems,” IEEE Trans. Inf.
Theory, vol. 56, no. 9, pp. 4539–4551, Sep. 2010.
[7] K. Rashmi, N. Shah, and P. V. Kumar, “Optimal exact-regenerating codes
for distributed storage at the MSR and MBR points via a product-matrix
construction,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5227–5239,
Aug. 2011.
[8] S. El Rouayheb and K. Ramchandran, “Fractional repetition codes for
repair in distributed storage systems,” in Proc. 48th Annual Allerton
Conf. Commun., Control, and Comput., Monticello, IL, Sep./Oct. 2010.

11

[9] Y. Wang, X. Yin, and X. Wang, “MDR codes: A new class of RAID6 codes with optimal rebuilding and encoding,” IEEE J. Sel. Areas
Commun., vol. 32, no. 5, pp. 1008–1018, May 2014.
[10] I. Tamo, Z. Wang, and J. Bruck, “Zigzag codes: MDS array codes with
optimal rebuilding,” IEEE Trans. Inf. Theory, vol. 59, no. 3, pp. 1597–
1616, Mar. 2013.
[11] G. K. Agarwal, B. Sasidharan, and P. V. Kumar, “An alternate construction of an access-optimal regenerating code with optimal subpacketization level,” in Proc. 21st Nat. Conf. Commun. (NCC), Mumbai,
India, Feb. 2015.
[12] V. R. Cadambe, C. Huang, J. Li, and S. Mehrotra, “Polynomial length
MDS codes with optimal repair in distributed storage,” in Proc. 45th
Asilomar Conf. Signals, Syst. and Comput. (ASILOMAR), Pacific Grove,
CA, Nov. 2011.
[13] K. Rashmi, N. Shah, and K. Ramchandran, “A piggybacking design
framework for read-and download-efficient distributed storage codes,”
IEEE Trans. Inf. Theory, vol. 63, no. 9, pp. 5802–5820, Sep. 2017.
[14] H. Hou, K. W. Shum, M. Chen, and H. Li, “BASIC codes: Lowcomplexity regenerating codes for distributed storage systems,” IEEE
Trans. Inf. Theory, vol. 62, no. 6, pp. 3053–3069, Jun. 2016.
[15] H. Hou, P. P. C. Lee, Y. S. Han, and Y. Hu, “Triple-fault-tolerant binary
MDS array codes with asymptotically optimal repair,” in Proc. IEEE
Int. Symp. Inf. Theory (ISIT), Aachen, Germany, Jun. 2017.
[16] M. Blaum, J. Brady, J. Bruck, and J. Menon, “EVENODD: An efficient
scheme for tolerating double disk failures in RAID architectures,” IEEE
Trans. Comput., vol. 44, no. 2, pp. 192–202, Feb. 1995.
[17] S. Kumar, A. Graell i Amat, I. Andriyanova, and F. Brännström, “A family of erasure correcting codes with low repair bandwidth and low repair
complexity,” in Proc. IEEE Global Commun. Conf. (GLOBECOM), San
Diego, CA, Dec. 2015.
[18] A. Karatsuba and Y. Ofman, “Multiplication of multidigit numbers on
automata,” Sov. Phys. Doklady, vol. 7, no. 7, pp. 595–596, Jan. 1963.
[19] A. Weimerskirch and C. Paar, “Generalizations of the Karatsuba
algorithm for efficient implementations,” Jul. 2006. [Online]. Available:
https://eprint.iacr.org/2006/224.pdf
[20] J. M. Pollard, “The fast Fourier transform in a finite field,” Math.
Comput., vol. 25, no. 114, pp. 365–374, 1971.
[21] R. E. Crandall and C. Pomerance, Prime Numbers: A Computational
Perspective. Springer, 2001.
[22] S. Gao and T. Mateer, “Additive fast Fourier transforms over finite
fields,” IEEE Trans. Inf. Theory, vol. 56, no. 12, pp. 6265–6272, Dec.
2010.

Algorithm 2: ConstructNode (A, ρl )
Initialization:
t, j ← 0
Ut1 ← ∅, t1 = 0, . . . , k − 1
1 while arg min∀t1 |Ut1 | < 2 do
2
Select di,j ∈ DΨ(AQj \∪ ′ U ′ ) s.t.
j
j
∃ dj,i ∈ DXj , aj,i > 1
3
if di,j exists then
4
pBt,l ← di,j + dj,i ; t ← t + 1;
5
Ut ← Ut ∪ {(i, j), (j, i)}
6
else
7
Select di1 ,j ∈ DΨ(AQj \∪ ′ U ′ )
j

8
9

10
11
12
13
14
15
16
17
18
19
20
21
22
23

24
25
26
27
28
29
30
31

32
33
34
35
36
37
38
39
40
41
42
43
44

j

if di1 ,j exists then
if ∃ dj,i2 ∈ DXj \∪j′ Uj′ s.t.
read(dj,i2 , pBt,l + dj,i2 ) < aj,i2 and aj,i2 > 1
then
pBt,l ← di1 ,j + dj,i2 ;
t ← t + 1; Ut ← Ut ∪ {(i1 , j), (j, i2 )}
else
pBt,l ← di1 ,j ; t ← t + 1;
Ut ← Ut ∪ {(i1 , j), (−1, −1)}
end
end
end
j ← (j + 1)k
end
t, j ← 0
while arg min∀t1 |Ut1 | ≤ ρl do
if DXj \∪j1 Uj1 6= ∅ then
if ∃ dj,i3 ∈ DXj \∪j′ Uj′ s.t.
read(dj,i3 , pBt,l + dj,i3 ) < aj,i3 and aj,i3 > 1
then
pBt,l ← pBt,l + dj,i3 ; t ← t + 1;
Ut ← Ut ∪ {(j, i3 )}
else if l > nA then
Ut ← Ut ∪ (−1, −1)}; t ← t + 1
end
else
if |Ut | ≤ ρl − 1 then
Select dj2 ,i ∈ ∪j1 DXj1 \∪j′ Uj′ s.t.
1
1
di′ ,j2 ∈ DUt for some i′ 6= i
if dj2 ,i exists then
pBt,l ← pBt,l + dj2 ,i ; t ← t + 1;
Ut ← Ut ∪ {(j2 , i)}
else
Select dj3 ,i ∈ ∪j1 DXj1 \∪j′ Uj′
1
1
pBt,l ← pBt,l + dj3 ,i ; t ← t + 1;
Ut ← Ut ∪ {(j3 , i)}
end
end
end
j ← (j + 1)k
end
return {pB0,l , . . . , pBk−1,l }

