1

Linear Programming Bounds for Distributed
Storage Codes
Ali Tebbi† , Terence H. Chan‡ , Chi Wan Sung†

arXiv:1710.04361v1 [cs.IT] 12 Oct 2017

†

Department of Electronic Engineering, City University of Hong Kong
Email: {ali.tebbi,albert.sung@cityu.edu.hk}

‡

Institute for Telecommunications Research, University of South Australia
Email: terence.chan@unisa.edu.au

Abstract
A major issue of locally repairable codes is their robustness. If a local repair group is not able to
perform the repair process, this will result in increasing the repair cost. Therefore, it is critical for a
locally repairable code to have multiple repair groups. In this paper we consider robust locally repairable
coding schemes which guarantee that there exist multiple alternative local repair groups for any single
failure such that the failed node can still be repaired locally even if some of the repair groups are not
available. We use linear programming techniques to establish upper bounds on the code size of these
codes. Furthermore, we address the update efficiency problem of the distributed data storage networks.
Any modification on the stored data will result in updating the content of the storage nodes. Therefore,
it is essential to minimise the number of nodes which need to be updated by any change in the stored
data. We characterise the update-efficient storage code properties and establish the necessary conditions
that the weight enumerator of these codes need to satisfy.
Index Terms
Robust locally repairable codes, update-efficient codes, linear programming

I. I NTRODUCTION
Significant increase in the internet applications such as social networks, file, and video sharing
applications, results in an enormous user data production which needs to be stored reliably. In a
An earlier conference versions of the paper appeared at ICICS 2013 [1] and ITW 2014 [2]. In this journal version, we present
more details on deriving linear programming bounds and update cost of storage codes.

2

data storage network, data is usually stored in several data centres, which can be geographically
separated. Each data centre can store a massive amount of data, by using hundreds of storage
disks (or nodes). The most common issue with all storage networks is failure. The failure in
storage networks is the result of the failed components which are varied from corrupted disk
sectors to one or a group of failed disks or even the entire data centre due to the physical
damages or natural disasters. The immediate consequence of failure in a storage network is
data loss. Therefore, a recovery mechanism must be in place to handle these failures. Protection
against failures is usually achieved by adding redundancies [3]. The simplest way to introduce
redundancy is replication. In this method multiple copies of each data block are stored in the
network. In the case of any failure in the network, the content of the failed node can be recovered
by its replica. Because of its simplicity in storage and data retrieval, this method is used widely
in conventional storage systems (e.g., RAID-1 where each data block is duplicated and stored
in two storage nodes) [4], [5]. However, replication is not an efficient method in term of the
storage requirement [6], [7].
Another method for data storage is erasure coding which has gained a wide attention in
distributed storage [8]–[12]. In this method as a generalisation of replication, a data block is
divided into K fragments and then encoded to N (N > K) fragments via a group of mapping
functions to store in the network [13]. Erasure coding is capable of providing more reliable
storage networks compared to replication with the same storage overhead [14]. It is noteworthy
to mention that replication can also be considered as an erasure code (i.e., repetition code [3]).
One of the challenges in storage networks using erasure codes is the repair bandwidth. When
a storage node fails, the replaced node (i.e., newcomer) has to download the information content
of the survived nodes to repair the lost data. In other word, the repair bandwidth of a distributed
storage network is the total amount of the information which is needed to be retrieved to recover
the lost data. Compared to the replication, It has been shown in [14] that for the same system
parameters such as mean time to failure (MTTF), erasure coding reduces the storage overhead
and the repair bandwidth significantly.
From coding theory, it is well known that in a storage network employing an erasure code
for data storage the minimum amount of information which has to be downloaded to repair a
single failure is at least the same size of the original data [13]. In other words, the amount of
data transmitted in the network to repair a failed node is much more than the storage capacity
of the node. Regenerating codes which have been introduced in [15] provide coding techniques

3

to reduce the repair bandwidth by increasing the number of nodes which the failed node has to
be connected during the repair procedure. It has been shown that there exists a tradeoff between
the storage and repair bandwidth in distributed storage networks [15]. Many storage codes in
literature assume that lost data in a failed data centre can be regenerated from any subset (of
size greater than a certain threshold) of surviving data centres. This requirement can be too
restrictive and sometimes not necessary. Although these methods reduce the repair bandwidth,
it seems that high I/O traffic is the bottleneck of these networks. The number of nodes which
involve in repairing a failed node is defined as the code locality [16]. The concept of code
locality relaxes the repairing requirement so that any failed node can be repaired by at least one
set (of size smaller than the threshold) of surviving nodes. We refer to these sets as the ”local
repair groups”. Moreover, any erasure code which satisfies this property is referred as ”locally
repairable code”.
One significant issue of locally repairable codes is their robustness. Consider a distributed
storage network with N storage nodes such that there exists only one local repair group for
each node in the network. Therefore, if any node fails, the survived nodes in its repair group can
locally repair the failure. However, if any other node in the repair group is also not available (for
example, due to the heavy loading), then the repair group cannot be able to repair the failed node
anymore which will result in increase of repair cost. To avoid this problem, it is essential to have
multiple local repair groups which can be used for repairing the failure if additional nodes fail or
become unavailable in the repair groups. The concept of locally repairable codes with multiple
repair groups (or alternatives) was studied in [17] where codes with multiple alternatives were
also constructed. Locally repairable code construction with multiple disjoint repairing groups
was investigated in [18]. In [19], locally repairable codes with multiple erasure tolerance have
been constructed using combinatorial methods. A lower bound on the code size was derived
and some code examples provided which are optimal with respect to this bound. A class of
locally repairable codes with capability of repairing a set of failed nodes by connecting to a set
of survived nodes are studied in [20]. Bounds on code dimension and also families of explicit
codes were provided.
The main contributions of this paper are as follows:
•

We investigate the linear (r, Γ, ζ, β) robust locally repairable codes where any failed node
can be repaired by ζ different repair groups at the presence of any Γ extra failures in the
network. Moreover, these codes can tolerate any β simultaneous failures.

4

•

By employing the criteria from the definition of our robust locally repairable codes, we
establish a linear programming bound to upper bound the code size.

•

We investigate the update efficiency of storage codes. In an erasure code, each encoded
symbol is a function of the data symbols. Therefore, the update complexity of an erasure
code is proportional to the number of encoded symbols that have to be changed in regard
of any change in the original data symbols. In other words, in a storage network the content
of the storage nodes must be updated by any change in the stored data. We characterise the
properties of update-efficient storage codes and establish the necessary conditions that the
code need to satisfy.

This work is partially presented in 2013 9th International Conference on Information, Communications & Signal Processing (ICICS) [1] and 2014 IEEE Information Theory Workshop (ITW)
[2]. This work presents more detailed discussions on characterising robust locally repairable and
update-efficient storage codes.
The remaining of the paper is organised as follows. In Section II, we review the related works
on the locally repairable codes. In Section III, we introduce our robust locally repairable codes
and propose their criteria. In Section IV, we establish a linear programming problem to upper
bound the code size. We also exploit symmetry on the linear programming bound to reduce its
complexity. Section V studies the update efficiency of the locally repairable codes. We establish
the necessary conditions for distributed storage codes in order to satisfy the locality and update
efficiency at the same time. Examples and numerical results are provided in Section VI. The
paper then concludes in Section VII.
II. BACKGROUND

AND

R ELATED WORKS

The high I/O overhead in regenerating codes due to use N − 1 storage nodes to minimise the
repair bandwidth, seems to be the bottleneck of the storage networks. Therefore, the number
of nodes which help to repair a failed node is a major metric to measure the repair cost in
storage networks. Locally repairable codes aim to optimise this metric (i.e., the number of
helper nodes needed to repair a failed node). The locality of a code is defined as the number of
code coordinates r such that any code coordinate is a function of them [16]. Consequently, in a
storage network employing a locally repairable code, any failed node can be repaired using only
r survived nodes. In the case of the linear locally repairable storage codes which are the topic
of this paper, the content of any storage node is a linear combination of the contents of a group

5

of r other nodes. Usually two types of code locality are defined in the literature as information
symbol locality and all symbol locality which means that just the information symbols in a
systematic code have locality r and all symbols have locality r, respectively. In this paper, the
code locality is referred to all symbol locality since we do not impose any systematic code
constraint on the locally repairable storage codes.
The problem of storage codes with small locality has been initially proposed in [21]–[23],
independently. The pyramid codes introduced in [21] are an example of initial works on practical
locally repairable storage codes. A basic pyramid code is constructed using an existing erasure
code. An MDS erasure code will be an excellent choice in this case, since they are more tolerable
against simultaneous failures. To construct a pyramid code using an MDS code, it is sufficient
to split K data blocks into

K
r

disjoint groups. Then, a parity symbol is calculated for each group

as a local parity. In other words, one of the parity symbols from the original code is split into
K
r

blocks and the other parity symbols are kept as global parities. Therefore, any single failure

in data nodes can be repaired by r survived nodes in the same group instead of retrieving data
from K nodes. Generally, for a pyramid code with data locality r constructed from an (N, K, d)
MDS code, the code length (i.e., number of storage nodes) is


1
+ d − 2.
N =K 1+
r

(1)

Obviously, low locality is gained in the cost of ( Kr − 1) extra storage. To obtain all symbol

locality for the code, it is sufficient to add a local parity to each group of the global parities of
size r where will result in a code length of


1
N = (K + d − 2) 1 +
.
r
Both of the code lengths in (1) and (2) show a linear increase in storage overhead.

(2)

The pioneer work of Gopalan et al. in [16] is an in-depth study of codes locality which results
in presenting a trade-off between the code length N, data block size K, minimum distance of
code d, and code locality r. It has been shown that for any [N, K, d]q linear code with information
locality r,



K
N −K ≥
+ d − 2.
(3)
r
In other words, to have a linear storage code with locality r, we need a linear overhead of at
 
least Kr + d − 2. As a special case of locality r = K, the bound in (3) is reduced to
N −K ≥d−1

(4)

6

which is the singleton bound and is achievable by MDS codes such as Reed-Solomon codes.
According to (1) and (2), pyramid codes can achieve the bound in (3) which shows their
optimality.
Due to their importance in minimising the number of helper nodes to repair a single failure,
locally repairable codes have received a fair amount of attention in literature. Different coding
schemes to design explicit optimum locally repairable codes has been proposed in [24]–[26].
For the bound in (3), the assumption is that any storage node has entropy equal to α =
is also mentioned that low locality r << K affects the distance d indicated by term

K
.
r

M
.
K

It

It has

been shown in [27] that there exist erasure codes which have high distance and low locality if
storage nodes store an additional information of factor 1r , such that
 


K
K
−
+ 2,
d≤N−
1+ǫ
r (1 + ǫ)

(5)

where ǫ > 0.
The main issue with locally repairable codes is that they mostly tend to repair a single node
failure. This means that if any of the helper nodes in the repairing group of a failed node is
not available, the locally repair process will be failed. Therefore, it is critical to have multiple
repairing groups for each node in the storage network. The concept of locally repairable codes
with multiple repair alternatives has been studied initially in [17]. The main idea in [17] is to
obtain the parity check matrix of the code from a partial geometries. However, there are only a
few such explicit codes due to the limited number of known constructions of partial geometries
with desirable parameters. A lower and upper bound is also obtained for the rate of these
codes with different locality and repair alternativity. Rawat et al. investigated the availability in
storage networks employing locally repairable codes [18]. The notion of availability is useful
for applications involving hot data since it gives the ability of accessing to a certain information
by different users simultaneously. Therefore, each information node must have t disjoint repair
groups of size at most r (i.e., (r, t)-Information local code). An upper bound for the code
minimum distance has been obtained in [18] as
dmin ≤ N − K + 1 −





Kt
−t ,
r

(6)

which is a generalised version of the bound in (3). However, this bound only stands for information symbols availability with the assumption of only one parity symbol for each repair

7

group. Different bounds on the rate and minimum distance of storage codes with locality r and
availability t have been obtained independently in [28] as
1

j=1 1 +

K
≤Q
t
N

and

1
jr




t 
X
K −1
.
d≤N−
i
r
i=0

(7)

(8)

The minimum distance upper bound in (8) reduces to (3) for t = 1. However, the bounds in (6)
and (8) seem to be incomparable since the bound in (8) is tighter than (6) in some cases and
vice versa.
An upper bound on the codebook size of locally repairable codes which is dependent on the
alphabet size has been obtained in [29] as
i
h
(q)
K ≤ min tr + Kopt (n − t(r + 1), d)
t∈Z+

(9)

(q)

where, Kopt is the maximum dimension of a linear or non-linear code of length N and minimum

distance d with alphabet size of q. This bound is tighter than the bound in (3).
Locally repairable codes with small availability t = 2, 3 are investigated in [30]. The smallest
the availability the highest the code rate would be since the dependency among the code symbols
is less while the code is still comparable to the practical replication codes. The rate optimal
binary (r, t)-availability codes are designed and it has been shown that for (r, 2)-availability
codes which their rate is upper bounded by

K
N

≤

r
r+2

for N ≥ r + 1 and r + 1 | 2N in [31],

such a construction is unique. The equality on the boubd holds if and only if the code is a direct
, r + 1] codes, each generated by the complete graph on r + 2 points.
sum of [ (r+1)(r+2)
2
The locally repairable codes with multiple (ri , δi )-localities are presented in [32]. The locally
repairable codes with (r, δ)-locality are first introduced in [33] where any systematic code symbol
can be recovered by at most r other code symbols even if there exists δ − 2 other failures. The
minimum distance of these codes is upper bounded as
 

K
d ≤N −K +1−
− 1 (δ − 1).
r

(10)

Note that (10) is reduced to (3) for δ = 2. Locally repairable codes with multiple localities are
introduced in [34] and [35] such that coded symbols have different localities. An upper bound

8

on the minimum distance of these codes with multiple locality of the information symbols is
derived as
d≤N −K−


r 
X
Kj
j=1

j

+ 2,

where, Kj is the number of the information symbols with locality j. The work in [32] is a
generalisation of [33] and [34]. Locally repairable codes with multiple (ri , δi )-localities ensures
different locality for coded symbols at the presence of extra failures. A Singleton-like bound on
the minimum distance has been derived and explicit codes have been proposed.
Notation: Let N = {1, 2, 3, . . . , N} and 2N be the set of all possible subsets of N . In this
paper we represent a subset ν of N as a binary vector w = [w1 , . . . , wn ] such that wi = 1 if
and only if i ∈ N . In our convention, ν and w can be used interchangeably. Similarly, we use
zero vector 0 to present an empty set ∅. Also, we will make no distinction between an index i
and {i} for a single element set.
III. L INEAR L OCALLY R EPAIRABLE C ODES
A. Linear Storage Codes
Let FN
q = {[z1 , . . . , zN ] : zi ∈ Fq for all i ∈ N } be the vector space of all N-tuples over the
field Fq . A linear storage code C generated by a K × N full rank (i.e. rank K) generator matrix
G is a subspace of FN
q over the field Fq . Here, K is the dimension of the subspace. The linear

is defined as the set of all linear combinations (i.e. spans) of the row
code C = uG : u ∈ FK
q
vectors of the generator matrix G.

To store a data block of size M in a storage network using a linear code C, the original data
is first divided into k data blocks of size M/K. We may assume without loss of generality that
the original data is a matrix with M/K rows and k columns. Then each block (or row) will
be encoded using the same code. In this paper, we may assume without loss of generality that
there is only one row (and thus M = K). Let u = M be the information to be stored. Then the
storage node i will store the symbol ugi where gi is the ith column of the generator matrix G.
Notice that if Xi is the content that the storage node i stores, then (X1 , . . . , XN ) is a codeword
in C. To retrieve the stored information, it is sufficient to retrieve the information content of
K nodes (which are indexed by I) such that the columns gi for i ∈ I are all independent.
Specifically,
u = cI G−1
I

(11)

9

where cI is the row vector whose ith entry equals to ugi and GI is a submatrix of the generator
matrix G formed by the columns gi for i ∈ I.
Definition 1 (Support). For any vector c = [c1 , . . . , cN ] ∈ FN
q , its support λ(c) is defined as a
subset of N = {1, . . . , N} such that i ∈ λ(c) if and only if ci 6= 0.
For a linear storage code C over Fq , any codeword c is a vector of n symbols [c1 , . . . , cN ]
where ci ∈ Fq for all i = 1, . . . , N. Since we assume that code C is linear, for any codeword
c ∈ C the vector ac for all a ∈ Fq and a 6= 0 is also a codeword in C. Therefore, there exists at
least q − 1 codewords in C with the same support (excluding the zero codeword).
Definition 2 (Support Enumerator). The support enumerator ΛC (w) of the code C is the number
of codewords in C with the same support w, i.e.,
ΛC (w) , |{c ∈ C : λ(c) = w}| ,

∀w ⊆ N .

The support enumerator of a code is very useful to characterise the relation between a code
C and its dual code C ⊥ via MacWilliam theorem, hence we aim to bound the size of the
locally repairable codes using the dual code properties. Any linear code C can be specified
by a (N − K) × N parity check matrix H which is orthogonal to the generator matrix G such
that
GH ⊤ = 0,
where 0 is a K × (N − K) zero matrix. Then, this parity check matrix H can generate another
linear code C ⊥ called dual code. It is well known that

⊤
C ⊥ = h ∈ FN
q : hc = 0 for all c ∈ C .

In other words, a linear code C can be uniquely determined by its dual code C ⊥ . The number of the
codewords in C ⊥ for any support w (i.e., support enumerator ΛC ⊥ (w)) can also be determined
uniquely by the support enumerator ΛC (w) of the code C via the well-known MacWilliams
identities.
There are various variation or extensions of MacWilliams identity, all based on association
scheme. In the following, we will restate the MacWilliam identity.

10

Proposition 1 (MacWilliams identity [3]). Let C be an (N, K) linear code and C ⊥ be its dual.
Then for any codeword support w = [w1 , . . . , wN ] ⊆ N ,
1
ΛC ⊥ (w) =
|C|

X

s=[s1 ,...,sN

ΛC (s)
]∈2N

N
Y

κq (sj , wj ) ≥ 0

(12)

j=1

where



1



κq (s, w) = q − 1




−1

if w = 0
if s = 0 and w = 1

(13)

otherwise.

Remark 1. Here, subsets w and s of N are considered as binary vectors with nonzero coordinates corresponding to the indices indexed in them.
In the next subsection we will show the significance of dual code support enumerator in our
definition of robust locally repairable codes.
B. Locality of Linear Storage Codes
A linear storage code has locality r, if for any failed node i, there exists a group of survived
nodes of size at most r (i.e., repair group) such that the failed node can be repaired by this group
of nodes [16]. To be precise, consider a linear code C and its dual code C ⊥ . Let h = [h1 , . . . , hN ]
and c = [c1 , . . . , cN ] be the codewords in C ⊥ and C, respectively. Then, from the definition of
the dual code
hc⊤ = 0,

∀h ∈ C ⊥ , c ∈ C.

(14)

hj Xj = 0,

(15)

Consequently,
X

j∈λ(h)

where λ(h) is the support of the dual codeword h. Now, if the node i fails and i ∈ λ(h), the
content of the failed node can be recovered from the set of surviving nodes indexed by λ(h) \ i.
P
In particular, Xi = −h−1
i
j∈λ(h)\i Xj hj . As such, the set λ(h) \ i can be seen as a repair group
for node i.

Definition 3 (Locally repairable code [27]). An (r, β) locally repairable code C is a linear code
which satisfies

11

1) Local Recovery (LR). for any i ∈ N , there exists h ∈ C ⊥ such that i ∈ λ(h) and
|λ(h)| − 1 ≤ r.
2) Global Recovery (GR). ΛC (w) = 0, for all w ⊆ N such that 1 ≤ |w| ≤ β.
For a (r, β) locally repairable code, the local recovery criterion implies that any failed node i,
can always be repaired by retrieving the contents stored in at most r nodes. On the other hand,
the global recovery criterion guarantees that the storage network can be regenerated as long as
there are at most β simultaneous node failures.
Remark 2. The LR criterion requires the existence of a set of r surviving nodes which can be
used to repair a failed node. However, under the criteria, there is no guarantee that a failed
node can still be efficiently repaired1 if a few additional nodes also fail (or become unavailable).
Therefore, it is essential to have alternative repair groups in case of multiple node failures.
Definition 4 (Robust locally repairable code). An (r, β, Γ, ζ) robust locally repairable code is a
linear code satisfying the following criteria:
1) Robust Local Recovery (RLR). for any i ∈ N and γ ⊂ N \ i such that |γ| = Γ, there
exists h1 , . . . , hζ ∈ C ⊥ such that for all j = 1, . . . , ζ,
a) i ∈ λ(hj ), γ ∩ λ(hj ) = ∅, and |λ(hj )| − 1 ≤ r.
b) λ(hj ) 6= λ(hℓ ) for ℓ 6= j.
2) Global Recovery (GR). ΛC (w) = 0, for all w ⊆ N such that 1 ≤ |w| ≤ β.
The RLR criterion guarantees that a failed node can be repaired locally from any one of the
ζ groups of surviving nodes of size r even if Γ extra nodes fail. In the special case when Γ = 0,
then the robust locally repairable codes are reduced to locally repairable codes with multiple
repair alternatives as in [17]. When ζ = 1, then it further reduces to the traditional locally
repairable codes. The GR criterion is the same as that for locally repairable codes.
IV. L INEAR P ROGRAMMING B OUNDS
One of the most fundamental problems in storage network design is to optimise the tradeoff
between the costs for storage and repair. For a storage network using an (N, K) linear code
1

Strictly speaking, by the GR criterion, the failed node can still be repaired if there are no more than β node failures.

However, the global recovery cannot guarantee that each failed node can be repaired efficiently. In other words, one may need
a much larger set of surviving nodes to repair one failed node.

12

the capacity of each node is

M
K

where M is the information size. In other words, the storage

cost (per information per node) is given by

M
.
logq |C|

Since our coding scheme is linear locally

repairable, a group of r nodes participate in repairing a failed node. Thus, the repair cost of a
single failure is given by

rM
.
logq |C|

Consequently, by maximising the codebook size |C| the cost

will be minimised.
In this section, we will obtain an upper bound for the maximal codebook size, subject to
robust local recovery and global recovery criteria in Definition 4.
Theorem 1. Consider any (r, β, Γ, ζ) robust locally repairable code C. Then, |C| is upper
bounded by the optimal value of the following optimisation problem.
P
maximize
w⊆N Aw
subject to

Aw ≥ 0
Bw =

P

s⊆N

Q
κq (sj ,wj )
As n
P j=1
s⊆N As

∀w ⊆ N
∀w ⊆ N

Bw ≥ 0

∀w ⊆ N

Aw = 0

1 ≤ |w| ≤ β

A∅ = 1
X

Bs ≥ ζ(q − 1)

(16)

∀i ∈ N , γ ∈ ∆i

s∈Ωi :γ∩s=∅

where Ωi is the collection of all subsets of N that contains i and of size at most r + 1 and ∆i
is the collection of all subsets of N \ i of size at most Γ.
Proof. Let C be a (r, β, Γ, ζ) robust locally repairable code. Then, we define
Aw , ΛC (w),
Bw , ΛC ⊥ (w),

w⊆N
w ⊆ N.

The objective function of the optimisation problem in (16) is the sum of the number of all
codewords with support w, which is clearly equal to the size of the code C. Since Aw and Bw
are enumerator functions of the code C and C ⊥ respectively, Aw , Bw ≥ 0 for all w ⊆ N . The
constraint A∅ = 1 follows from the fact that the zero codeword is contained in any linear code.
P
The second constraint follows from (12) by substituting |C| and ΛC (s) with s⊆N As and As ,
respectively. The fourth constraint follows directly from GR criterion which says that there are

no codewords with support of size ≤ β (i.e., the minimum distance of code is d = β + 1).

13

Finally, the last constraint follows from the RLR criterion. Since the repair groups are specified
by dual code C ⊥ , this constraint bounds the number of codewords in the dual code with support
of size at most r + 1. The support of the corresponding codewords must contain the index of
the failed node i chosen from set Ωi . However, none of the extra failed nodes indexed in γ can
be included in these supports. As mentioned earlier, due to the fact that C is a linear code, for
any nonzero h ∈ C ⊥ , then ah ∈ C ⊥ for all nonzero a ∈ Fq . Let w = λ(h). Then, Bw ≥ (q − 1)
(i.e., there exist at least q − 1 codewords in dual code with support w). Consequently,
X
Bw ≥ ζ(q − 1).
s∈Ωi :γ∩s=∅

In other words, this constraint guarantees that there exist at least ζ repair groups to locally repair
a failed node at the presence of |γ| = Γ extra failures. Therefore, (Aw , Bw : w ⊆ N ) satisfies
the constraints in the maximisation problem in (16) and the theorem follows.
The optimisation problem in Theorem 1 derives an upper bound on the codebook size |C|
(i.e., Code dimension k) of a robust linear locally repairable code with minimum distance of
d = β + 1 over Fq such that any failed node can be repaired with a repair group of size r at
the presence of any Γ extra failure. Although the maximisation problem in (16) is not a linear
programming problem, it can be converted to one easily with a slight manipulation as follows:
P
maximize
w⊆N Aw
subject to

Aw ≥ 0
P
Qn
j=1 κq (sj , wj ) ≥ 0
s⊆N As

∀w ⊆ N
∀w ⊆ N
1 ≤ |w| ≤ β

Aw = 0
A∅ = 1
X

w∈Ωi :γ∩w=∅

X

As

s⊆N

≥ ζ(q − 1)

n
Y

κq (sj , wj )

j=1

P

w⊆N

(17)

!

Aw

∀i ∈ N , γ ∈ ∆i .

The complexity of the linear programming problem in (17) will increase exponentially with
the number of storage nodes N. In the following, we will reduce the complexity of the Linear
Programming problem in (17) by exploiting the symmetries.
To this end, suppose a (r, β, Γ, ζ) linear storage code C is generated by the matrix G with
columns gi , i = 1, 2, . . . , N. Let SN be the symmetric group on N whose elements are all

14

the permutations of the elements in N which are treated as bijective functions from the set of
symbols to itself. Clearly, |SN | = N!. Let σ be a permutation on N (i.e., σ ∈ SN ). Together
with the code C, each permutation σ defines a new code C σ specified with the generator matrix
columns fi , i = 1, 2, . . . , N, such that for all i ∈ N , fi = gσ(i) . Since all the codewords are
the linear combinations of the generator matrix rows and the permutation σ just changes the
generator matrix columns position, the permutation cannot affect the minimum distance of the
code (i.e., every codeword cσ ∈ C σ is just a permuted version of the corresponding codeword
c ∈ C). Therefore, the code C σ is still a (r, β, Γ, ζ) linear storage code and we have the following
proposition.
Proposition 2. Suppose (aw : w ⊆ N ) satisfies the constraint in the optimisation problem (17).
For any σ ∈ SN , let
(aσw : w ⊆ N ) = aσw = aσ(w) ,
where σ(w) , {σ(i) : i ∈ w}. Then (aσw : w ⊆ N ) also satisfies the constraint in (17).
Corollary 1. Let
a∗w =

1 X σ
a .
|SN | σ∈S w
N

Then (a∗w : w ⊆ N ) satisfies the constraint in (17) and
X
X
a∗w =
aw .
w⊆N

w⊆N

Proof. From Proposition 2, for any feasible solution (aw : w ⊆ N ) in (17), there exists |SN |
σ(i)

feasible solutions (aw : w ⊆ N , and σ (i) ∈ SN ). Since (17) is a linear programming problem,
a∗w (the average of all feasible solutions) is also a feasible solution. The result then follows.
Proposition 2 can be used to reduce the complexity in solving the optimisation problem (17).
Proposition 3. If |w| = |s|, then a∗w = a∗s .
Proof. Direct verification due to symmetry.
By Proposition 2, it is sufficient to consider only “symmetric” feasible solution (a∗w : w ⊆ N ).
Therefore, we can impose additional constraint
Aw = As ,

∀|w| = |s|.

(18)

15

to (17) without affecting the bound. These equality constraint will significantly reduce the number
of variables in the optimisation problem. Specifically, we have the following theorem.
Theorem 2. Consider a (r, β, Γ, ζ) robust locally repairable code C. Then, |C| is upper bounded
by the optimal value in the following maximisation problem

Maximize

N  
X
N

t

t=0

at

Subject to



at ≥ 0,




P PN −t t N −t



ai+j (−1)i (q − 1)t−i
bt = ti=0 j=0

i
j





bt ≥ 0,

Pβ

a =0

 t=1 t





a0 = 1





N  
r 
X
X

N
N −1−Γ


at .
bt+1 ≥ ζ(q − 1)

t
t
t=0
t=1

∀t = 0, . . . , N
∀t = 0, . . . , N
∀t = 0, . . . , N
(19)

Proof. Due to Proposition 3, we can simplify the LP in (17) by rewriting the variables as follows:
at = Aw
bt = Bw

for t = |w|
!
X
As
for t = |w|.

s⊆N

Using the new variables, the objective function (i.e., the number of codewords in code C) is
reduced to sum of the number of codewords with a support of size t (i.e., at ) multiplied by the

number of subsets with size t (i.e., Nt ) on all t = 0, . . . , N.
The first constraint follows by the fact that the number of codewords with support of size t

is not negative. For any w ⊆ N with the size of t, the second constraint corresponds to that the
number of codewords in dual code C ⊥ is nonnegative.
To rewrite the second constraint, notice that
N
Y
j=1

κ(sj , wj ) = (−1)|s∩w| (q − 1)|w−s|

(20)

16

for any pair (s, w) such that |s ∩ w| = i and |w − s| = t − i. In addition, the number of s such
that |s ∩ w| = i and |w − s| = t − i is equal to

 
t N −t
.
j
i

The third constraint follows by the fact that the number of codewords in dual code C ⊥ with
support of size t is not negative. The forth constraint follows from the GR criterion and is

equivalent to the third constraint in (17). According to the GR criterion, there exist no codewords
with the support size ≤ β (i.e., at = 0, 1 ≤ t ≤ β). Since (at ≥ 0, ∀t = 0, . . . , N), then
Pβ
t=1 at = 0. The constraint a0 = 1 is equivalent to the fourth constraint in (17) which states

that there exists only one codeword in code C with a support of size t = 0 (i.e., zero codeword).
The last constraint is equivalent to the last constraint in (17) which follows from the RLR

criterion where there are N −1−Γ
subsets (i.e., supports) of size t chosen from (N − 1 − Γ)
t
survived nodes.

Remark 3. The number of variables and constraint now scales only linearly with N (the number
of nodes in the network).
V. C OST

FOR

U PDATE

In previous sections, criteria evaluating performance of storage codes include 1) storage
efficiency, 2) local recovery capability and 3) global recovery capability. However, data are
rarely static but will be updated from time to time. The fundamental question is how efficient
an scheme can be?
A. Update Model and Code Definition
To answer this question, we assume that the data M consists of multiple files of identical
size. In our previous model, we assume that each file will be encoded using the same storage
code. Therefore, to update each file, one needs make request to each individual storage node to
update the content (regarding that updated file) stored there, leading to excessive overheads.
In this section, we consider a variation of our scheme in the sense that we treat each systematic
codeword symbol as a single file (which can be updated individually). The whole collection of
files will still be robust and efficient as in the original model. However, one can now consider the
problem of update as a single systematic codeword symbol and evaluate how many parity-check
codeword symbols are required to be updated.

17

Definition 5 (Update-efficient storage code). A K-symbol update-efficient storage code is specified by a K × (N + K) generator matrix G with columns (g1 , . . . , gN +K ) which satisfy the
following criteria:
1) Pseudo-Systematic – The submatrix formed by the columns (gN +1 , . . . , gN +K ) is an identity
matrix.
2) Full Rank: The matrix formed by (g1 , . . . , gN ) is full rank (i.e., of rank equal to K).
The first N columns correspond to the ”coded symbols” stored in the N storage nodes, while
the last K columns correspond to the K source symbols. Let [u1 , . . . , uK ] be the K source
symbols. In our context, each source symbol may correspond on a file which can be separately
updated. Then, any codeword c = [c1 , . . . , cN , cN +1 , . . . , cN +K ] in the update efficient storage
code C is generated by
ci =

K
X

uj gj,i ,

∀i = 1, . . . , N + K,

j=1

where gi = [g1,i , . . . , gK,i]⊤ . However, only the first N coordinates of the codeword c will be
stored in the network. Therefore, for any i ∈ N the content of the storage node Xi , is the coded
symbol ci . In particular,
Xi =

K
X

uj gj,i ,

∀i = 1, . . . , N.

(21)

j=1

For any vector v = [v1 , . . . , vN +K ], we will often rewrite it as v = [v1 , v2 ] where
v1 = [v1 , . . . , vN ] and v2 = [vN +1 , . . . , vN +K ].
Definition 6 (support). For any vector v = [v1 , v2 ] where
v1 = [v1 , . . . , vN ] and v2 = [vN +1 , . . . , vN +K ],
its support λ(v) is defined as two subsets (w1 ⊆ N , w2 ⊆ K) where
i ∈ w1 if vi 6= 0
i ∈ w2 if vi+N 6= 0,
and K = {1, . . . , K}. As before, it is also instrumental to view w1 and w2 as binary vectors
w1 = [w1,1 , . . . , w1,N ] and w2 = [w2,1 , . . . , w2,K ] such that w1,i = 1 if vi 6= 0 and w2,i = 1 if
vi+N 6= 0.

18

K

N



...
...
..
.

g1,N
g2,N
..
.

gK,1 . . .

gK,N

g1,1
 g2,1

G= .
 ..


0 ... 0
1 . . . 0

.. . . ..  K
. .
.
0 0 ... 1
1
0
..
.

Fig. 1. Generator matrix of an update efficient storage code.

K

N


p1,1
..
.




 pN −K,1
H=
pN −K+1,1


..

.
pN,1

...
..
.
...
...
..
.

p1,K
..
.
pN −K+1,K
..
.

1 ...
.. . .
.
.
0 ...
0 ...
.. . .
.
.

...

pN,K

0 ...

pN −K,K

0 0 ...
.. .. . .
.
. .
1 0 ...
0 1 ...
.. .. . .
.
. .
0 0 ...


0
.. 
N −K
.

0

0

.. 
. K
1

Fig. 2. Parity check matrix of an update efficient storage code.

Lemma 1. Let G be the generator matrix of an update efficient storage code, as depicted in
Figure 1. Then
1) For any i = 1, . . . , K, there exists a dual codeword h = (h1 , h2 ) such that all entries of
h2,j is non-zero if and only if j 6= i.
2) The rank of the last K column of the parity check matrix must be K.
3) If h = (h1 , h2 ) is a dual codeword, and h2 is non-zero, then h1 must be non-zero as well.
4) If c = (c1 , c2 ) is a codeword, and c2 is non-zero, then c1 must be non-zero as well.
Proof. Rank of G is clearly K and hence rank of H must be N. By construction, the first N
columns of G has rank K. This implies 1), which in turns also implies 2). Next, 3) follows from
that the last K columns of G has rank K. Finally, 4) follows from that the matrix formed by
(g1 , . . . , gN ) is of rank K.
Remark 4. Assume without loss of generality that the last N columns of the generator matrix
G has rank N. We can assume that the parity check matrix H of the update-efficient storage
code can be taken the form in Figure 2 such that for any 1 ≤ ℓ ≤ K, the N − K + ℓth row of

19

H has at least two non-zero entries. In other words, entries pN −K+ℓ,1, . . . , pN −K+ℓ,K cannot be
all zero.
Proposition 4 (Code Properties). Let C be a K-symbol update efficient locally repairable code.
Then



(22.a)







(22.b)




P

w2 ⊆K:|w2 |≥1 ΛC (0, w2 )

P

=0

w2 ⊆K:|w2 |≥1 ΛC ⊥ (0, w2 )

=0

P
|w2 | N −K
(22.c)
q
,
∀w2 ⊆ K, |w2 | ≥ 0
w1 ⊆N ΛC ⊥ (w1 , w2 ) = (q − 1)



P


|w2 |

(22.d)
,
∀w2 ⊆ K, |w2 | ≥ 0

w1 ⊆N ΛC (w1 , w2 ) = (q − 1)




(22.e) Λ (0, 0) = Λ ⊥ (0, 0) = 1
C
C

(22)

Proof. Direct verification from the generator matrix and the parity check matrix in Figures 1
and 2, respectively.
Definition 7 (Update efficient locally repairable storage code). A K − symbol update efficient
locally repairable code C is a (r, β, δ) storage code if satisfies the following criteria:
1) Local Recovery (LR): for any i ∈ {1, . . . , N}, there exists h = [h1 , h2 ] ∈ C ⊥ where
h1 = [h1 , . . . , hN ] and h2 = [hN +1 , . . . , hN +K ] such that i ∈ λ(h1 ), λ(h2 ) = ∅, and
|λ(h1 )| − 1 ≤ r.
2) Global Recovery (GR): ΛC (w1 , w2 ) = 0, for all w1 ⊆ N such that 1 ≤ |w1 | ≤ β and
w2 ⊆ K.
3) Efficient Update (EU): For any w2 ⊆ K and |w2 | = 1,
∀w1 ⊆ N and |w1 | > δ.

ΛC (w1 , w2 ) = 0,

The LR criterion guarantees that for any failed node Xi there exists a local repair group
specified by the support of the first N symbols of the corresponding dual codeword. In other
words, while
hc⊤ =

N
+K
X

hi ci = 0,

i=1

only (h1 , . . . , hN ) and (c1 , . . . , cN ) are participating in the repair process such that
N
X
i=1

hi Xi = 0.

20

Therefore, the support of h1 = [h1 , . . . , hN ] specifies the repair groups while h2 must be a zero
vector. The GR criterion guarantees that the stored data is recoverable at the presence of severe
failure pattern. More specifically, in the worst case of β simultaneous node failures, data stored
in the network can still be repaired from the survived nodes. Finally, the EU criterion ensures
that if any of the source symbols is modified, then no more than δ storage nodes need to be
updated. In particular, for any singleton w2 , there exists a unique w1 such that
X
ΛC (w1′ , w2 ) = q − 1.
ΛC (w1 , w2 ) =
w1′

The w1 corresponds to codewords where only the single data file (indexed by the support of
w2 ) is non-zero. In that case, if the data file has been changed, only the codeword symbols
corresponding to the support of w1 need to be updated. In order to maintain the update cost
efficiency (i.e., equal or less than δ nodes per any source symbol change), the code C must not
include any codeword with support |w1 | > δ for any |w2 | = 1.
Proposition 5. For a (r, β, δ) update efficient locally repairable code C, we have

P


(23.a)

w1 ⊆N :ℓ∈w1 and |w1 |≤r+1 ΛC ⊥ (w1 , ∅) ≥ (q − 1), ∀ℓ ∈ N


(23.b) ΛC (w1 , w2 ) = 0,
∀w1 ⊆ N , w2 ⊆ K, 1 ≤ |w1 | ≤ β





(23.c) ΛC (w1 , w2 ) = 0,
∀w1 ⊆ N and |w1 | > δ and |w2 | = 1
(23)

Remark 5. It is worth to notice that these parameters may depend on each other. For example,
it can be directly verified that there is no (r, β, δ) storage code where β ≥ δ.
Remark 6. For notation convenience, we will first consider only the case of local recovery.
However, the extension to include robust local recovery is straightforward. We will present the
results afterwards.
The following theorem characterises an update efficient locally repairable code based on its
generator matrix specifications in Definition 7.
Theorem 3 (Necessary condition). Let C be a (N, K, r, β, δ) update-efficient locally repairable

21

storage code.




(C1)







(C2)







(C3)






(C4)







(C5)






(C6)

Then there exists (Aw1 ,w2 , Cw1 ,w2 : w1 ⊆ N , w2 ⊆ K) such that
P
QN +K
κq (sj , wj ),
∀w1 ⊆ N , w2 ⊆ K
Cw1 ,w2 = s1 ⊆N ,s2⊆K As1 ,s2 j=1
Aw1 ,w2 ≥ 0,

∀w1 ⊆ N , w2 ⊆ K

Cw1 ,w2 ≥ 0,

∀w1 ⊆ N , w2 ⊆ K

A∅,w2 = 0

∀w2 ⊆ K, |w2 | ≥ 1

C∅,w2 = 0
P
|w2 | N
q ,
w1 ⊆N Cw1 ,w2 = (q − 1)
P

|w2 |

(C7)
,

w1 ⊆N Aw1 ,w2 = (q − 1)






(C8) A∅,∅ = 1,







(C9) C∅,∅ = q K ,





P

K

(C10)

w1 ⊆N :ℓ∈w1 and |w1 |≤r+1 Cw1 ,∅ ≥ (q − 1)q ,






(C11) Aw1 ,w2 = 0,






(C12) Aw1 ,w2 = 0,

∀w2 ⊆ K, |w2 | ≥ 1
∀w2 ⊆ K, |w2 | ≥ 0

(24)

∀w2 ⊆ K, |w2 | ≥ 0

∀ℓ ∈ N
∀1 ≤ |w1 | ≤ β
∀|w1 | > δ, |w2 | = 1

Proof. Let C be a (r, β, δ) update efficient linear storage code. We define
Aw1 ,w2 , ΛC (w1 , w2 )

(25)

Cw1 ,w2 , q K ΛC ⊥ (w1 , w2 ).

(26)

Constraint (C1) follows directly from the MacWilliams identity in Proposition 1. Constraint (C2)
and (C3) follow from (25) and (26) and that enumerating functions are non-negative. Constraints
(C4) - (C9) are consequences of Proposition 4 and Constraints (C10)-(C12) are due to Proposition
5.
As before, the constraints in (24) are overly complex. Invoking symmetry, we will to simplify
the above set of constraints.
Proposition 6. Suppose the generator matrix specified with the column vectors (g1 , . . . , gN +K )
defines a (r, β, δ) code C. For any σ1 ∈ SN (i.e., symmetric group of N ) and σ2 ∈ SK (i.e.,
symmetric group of K), let C σ1 ,σ2 be another code specified by (fi , i = 1, . . . , N + K) such that
fi = gσ1 (i)
fN +j = gN +σ2 (j)

for i ∈ N
for j ∈ K.

22

Then C σ1 ,σ2 is still a (r, β, δ) code.
Proof. Let c = [c1 , c2 ] be a codeword in C where c1 = [c1 , . . . , cN ] and c2 = [cN +1 , . . . , cN +K ].
Then, the vector cσ1 ,σ2 = [cσ1 1 , cσ2 2 ] is a codeword in C σ1 ,σ2 where cσ1 1 = [σ1 (c1 ), . . . , σ1 (cN )] and
cσ2 2 = [cN +σ2 (1) , . . . , cN +σ2 (K) ]. In other words, any codeword cσ1 ,σ2 ∈ C σ1 ,σ2 is a permutation of
a codeword c ∈ C for all σ1 ∈ SN and σ2 ∈ SK . Equivalently, the new code C σ1 ,σ2 is obtained
from C by relabelling or reordering the codeword indices. The proposition thus follows.
Corollary 2. Suppose (aw1 ,w2 , cw1 ,w2 : w1 ⊆ N , w2 ⊆ K) satisfies (24). Let
X X
1
a∗w1 ,w2 =
aσ1 (w1 ),σ2 (w2 )
|SN ||SK | σ ∈S σ ∈S
1

c∗w1 ,w2 =

1
|SN ||SK | σ

N

2

K

X X

1 ∈SN

(27)

cσ1 (w1 ),σ2 (w2 ) .

(28)

σ2 ∈SK

Then (a∗w1 ,w2 , c∗w1 ,w2 : w1 ⊆ N , w2 ⊆ K) also satisfies (24). Furthermore, for any w1 , s1 ⊆ N
and w2 , s2 ⊆ K such that |w1 | = |s1 | and |w2 | = |s2 |. Then
a∗w1 ,w2 = a∗s1 ,s2

(29)

c∗w1 ,w2 = c∗s1 ,s2 .

(30)

Proof. From Proposition 6, if (aw1 ,w2 , cw1 ,w2 : w1 ⊆ N , w2 ⊆ K) satisfy constraints (24),
then (aσ1 (w1 ),σ2 (w2 ) , cσ1 (w1 ),σ2 (w2 ) : w1 ⊆ N , w2 ⊆ K) will satisfy them for all σ1 ∈ SN and
σ2 ∈ K. Since all the constraints in (24) are convex, any convex combination of all these feasible
solutions is still feasible. Hence, (a∗w1 ,w2 , c∗w1 ,w2 : w1 ⊆ N , w2 ⊆ K) is still feasible. Also,
{(σ1 (w1 ), σ2 (w2 )) : ∀σ1 ∈ SN , σ2 ∈ SK } = {(σ1 (s1 ), σ2 (s2 )) : ∀σ1 ∈ SN , σ2 ∈ SK }
if |w1 | = |s1 | and |w2 | = |s2 | for any w1 , s1 ⊆ N and w2 , s2 ⊆ K.
Theorem 4 (Necessary condition). Let C be a (N, K, r, β, δ) update-efficient storage code. Then
there exists real numbers (at1 ,t2 , ct1 ,t2 : t1 = 0, . . . , N, t2 = 0, . . . , K) satisfying (31).

23




(D1)







(D2)







(D3)






(D4)







(D5)






(D6)

ct1 ,t2 =

Pt1

u1 =0

at1 ,t2 ≥ 0,

u2 =0

v1 =0

PK−t2
v2 =0

Ξ(u1 , v1 , u2 , v2 )au1 +v1 ,u2 +v2
∀0 ≤ t1 ≤ N, 0 ≤ t2 ≤ K

ct1 ,t2 ≥ 0,

∀0 ≤ t1 ≤ N, 0 ≤ t2 ≤ K

a0,t2 = 0,

∀t2 ≥ 1

c0,t2 = 0

PN
N

∀t2 ≥ 1

t1 =0



(D7)







(D8)







(D9)







(D10)







(D11)






(D12)

PN −t1 Pt2

PN

t1 =0

t1

N
t1

a0,0 = 1,



ct1 ,t2 = (q − 1)t2 q N ,

∀t2

at1 ,t2 = (q − 1)t2 ,

∀t2

c0,0 = q K
Pr+1 N −1
t1 =2

t1 −1

ct1 ,0 ≥ (q − 1)q K

at1 ,t2 = 0,

∀1 ≤ t1 ≤ β

at1 ,1 = 0,

∀t1 > δ
(31)

where
Ξ(u1 , v1 , u2 , v2 ) = (−1)

u1 +u2

(q − 1)

t1 +t2 −u1 −u2


 
 
k − t2
t2
N − t1
t1
.
v2
u2
v1
u1

Proof. The theorem is essentially a direct consequence of Theorem 3 and Corollary 2, which
guarantees that there exists a “symmetric” feasible solution (a∗w1 ,w2 , c∗w1 ,w2 : w1 ⊆ N , w2 ⊆ K)
satisfying (24). Due to symmetry, we can rewrite a∗w1 ,w2 as at1 ,t2 and c∗w1 ,w2 as ct1 ,t2 where
t1 = |w1 | and t2 = |w2 |. The set of constraints in (31) is basically obtained by rewriting (24)
and grouping like terms. Most rephrasing is straightforward. The more complicated one is (D1),
where we will show how to rewrite it.
Recall the constraint (C1) in (24)
Cw1 ,w2 =

X

s1 ⊆N ,s2 ⊆K

Let |w1 | = t1 , |w2 | = t2 . For any

As1 ,s2

NY
+K

κq (sj , wj ),

∀w1 ⊆ N , w2 ⊆ K.

(32)

j=1

0 ≤ u1 ≤ t1 , and 0 ≤ v1 ≤ N − t1

(33)

0 ≤ u2 ≤ t2 , and 0 ≤ v2 ≤ K − t2 ,

(34)

24

the number of pairs of (s1 , s2 ) such that
u1 = |w1 ∩ s1 | and v1 = |s1 \ w1 |
u2 = |w2 ∩ s2 | and v2 = |s2 \ w2 |
is equal to

 
 
K − t2
t2
N − t1
t1
.
v2
u2
v1
u1
Also, for each such pair, by (20),
NY
+K

κq (sj , wj ) = (−1)u1 +u2 (q − 1)t1 +t2 −u1 −u2 .

j=1

Grouping all like terms together, (32) can be written as in (D1) in (31).
Notice that the complexity of the constraints in Theorem 3 is increased exponentially by the
number of the storage nodes N and the number of the information symbols K. However, the
symmetrisation technique which is applied to the constraints significantly reduces the number
of the variables to 2(N + 1)(K + 1).
Remark 7. Theorem 4 can be used to prove the existence of an updated efficient code, which
in turn can be used to search and determine performance bounds for the codes.
Remark 8. In the previous linear programming bound, we consider only the local recovery
criteria. Extension to robust local recovery criteria is similar.
For the robust local recovery criteria, recall from Definition 4, it requires that for any failed
node i ∈ N and additional Γ failed nodes γ, there exists at least ζ dual codewords (with different
supports).
In other words, for any i ∈ N and γ ⊂ N \ i such that |γ| = Γ,
X
ΛC ⊥ (w1 , ∅) ≥ ζ(q − 1).

(35)

w1 ⊆N ,i∈w1 ,γ∩w1 =∅

As before, the constraint can be rewritten as follows, after symmetrisation

r+1 
X
N −Γ−1
ct1 ,0 ≥ ζ(q − 1)q K .
t
−
1
1
t =2
1

(36)

25

VI. N UMERICAL R ESULTS A ND D ISCUSSION
In this section, we present two examples of robust locally repairable codes. We will show that
these codes can repair a failed node locally when some of the survived nodes are not available.
Using our bound, we prove that these codes are optimal.
Example 1: Consider a binary linear storage code of length n = 16 with k = 9 as defined by
the following parity check equations
0 = P1 + C 1 + C 2 + C 3

(37)

0 = P2 + C 4 + C 5 + C 6

(38)

0 = P3 + C 7 + C 8 + C 9

(39)

0 = P4 + C 1 + C 4 + C 7

(40)

0 = P5 + C 2 + C 5 + C 8

(41)

0 = P6 + C 3 + C 6 + C 9

(42)

0 = P7 + C 1 + C 2 + C 3
+ C4 + C5 + C6
+ C7 + C8 + C9 .

(43)

Here, (C1 , . . . , C9 , P1 , . . . , P7 ) correspond to the content stored at the 16 nodes. In particular,
we might interpret that C1 , . . . , C9 are the systematic bits while P1 , . . . , P7 are the parity check
bits. The code can also be represented by Figure 3. In this case, the parity check equations are
equivalent to that the sum of rows and the sum of columns are all zero.
According to (37)-(43), every failed node (either systematic or parity) can be recovered by
two different repair groups of size r = 3. For instance, if C1 is failed, it can be repaired by
repair group RC1 1 = {C2 , C3 , P1 } or repair group RC2 1 = {C4 , C7 , P4 }. Notice that the two repair
groups are disjoint. Therefore, even if one of the repair groups is not available, there exists an
alternative repair group to locally repair the failed node.
It can be verified easily that our code has a minimum distance of 4 and it is a (3, 3, 1, 1)
robust locally repairable code. Therefore, any failed node can be repaired by at least ζ = 1
repairing group of size r = 3 in the presence of any Γ = 1 extra failure. Also, the original data
can be recovered even if there are β = 3 simultaneous failure. In fact, it is also a (3, 3, 0, 2)
robust locally repairable code.

26

Group 1

C1

C2

C3

P1

C4

C5

C6

P2

C7

C8

C9

P3

P4

P5

P6

P7

Group 2

Fig. 3. A (3,3,1,1) robust locally repairable code of length N = 16 and dimension K = 9.

Now, we will use the bound obtained earlier to show that our code is optimal. We have plotted
our bound in Figure 4 when n = 16 and β = 3. The horizontal axis is the code locality (i.e.,
r) and the vertical axis is the dimension of the code (or log |C|). From the figure, when r = 3,
the dimension of a (3, 3, 1, 1) robust locally repairable code is at most 9. And our constructed
code has exactly 9 dimensions. Therefore, our code meets the bound and is optimal. In fact,
our bound also indicates that the dimension of a (3, 3, 0, 2) robust locally repairable code is
also at most 9. Therefore, our code is in fact an optimal (3, 3, 1, 1) and (3, 3, 0, 2) robust locally
repairable code.

Maximum numb er of data blocks

11

Γ =0 and ζ=2
Γ =1 and ζ=1
10

r =3
k=9

9

8

7

0

1

2

3

4

5

6

7

8

9

10

11

12

Repairing group size r

Fig. 4. Upper bounds for (3, 3, Γ, ζ) binary robust locally repairable code of length n = 16.

27

Example 2: Consider a binary linear code of length n = 8 and dimension k = 4 defined by the
following parity check equations:
P1 = C 1 + C 2 + C 3

(44)

P2 = C 1 + C 2 + C 4

(45)

P3 = C 2 + C 3 + C 4

(46)

P4 = C 1 + C 3 + C 4

(47)

Again, C1 , . . . , C4 are the information bits while P1 , . . . , P4 are the parity check bits. The code
can be represented by Figure 5. The above parity check equations imply that the sum of any
node and its three adjacent nodes in Figure 5 is always equal to zero.
This code has a minimum distance of 4. According to the Equations (44)-(47), for every single
node failure, there exists 7 repair groups with size r = 3. For example, suppose C1 fails. Then,
the repair groups are
R1C1 = {3, 4, 8}, R2C1 = {2, 4, 6}, R3C1 = {2, 3, 5}
R4C1 = {2, 7, 8}, R5C1 = {3, 6, 7}, R6C1 = {4, 5, 7}
R7C1 = {5, 6, 8}
Hence, our code is a (3, 3, 0, 7) robust locally repairable code. Furthermore, it can be directly
verified that for any distinct i, j 6= 1,

ℓ : i 6∈ RℓC1

and


=4

ℓ : {i, j} ∩ RℓC1 = ∅

(48)

= 2.

(49)

Therefore, if any one of the surviving nodes is not available, (48) implies that there are still 4
alternative repair groups. This means that our code is also a (3, 3, 1, 4) robust locally repairable
code. Similarly, by (49), our code is also a (3, 3, 2, 2) robust locally repairable code.
As shown in our bound (see Figure 6), our code has the highest codebook size for the given
parameters among all binary (3, 3, 0, 7), (3, 3, 1, 4) and (3, 3, 2, 2) robust locally repairable codes.

28

1

6

C1
5

2

P1

C2
8

3

C3

P2

4

P4

C4
7

P3

Fig. 5. A robust locally repairable code of length n = 8 and dimension k = 4 with ζ = 7 repair group for any failure.

Maximum numb er of data blocks k

4

r =3
k =4

Γ=0 and ζ=7
Γ=1 and ζ=4
Γ=2 and ζ=2

3

2

1

1

2

3

4

Repairing Group Size r

Fig. 6. Upper bounds for (3, 3, Γ, ζ) binary robust locally repairable code of length n = 8.

VII. C ONCLUSION
In this paper, we characterised the coding scheme for robust locally repairable storage codes.
This coding scheme overcomes a significant issue of the locally repairable codes which is their
repair inefficiency under the circumstances when there exist extra failures or unavailability in the
network. This coding scheme guarantees the local repairability of any failure at the presence of
extra failures by constructing multiple local repair groups for each node in the network. In this

29

case, if any of the repair groups is not available during the repair process, there exist alternative
groups to locally repair the failed node. We also established a linear programming problem to
upper bound the size of these codes. This practical bound can optimise the trade-off between
different parameters of the code such as minimum distance, code length, locality, the number of
alternative repair groups, and the number of the extra failures.
The update efficiency of the storage networks was addressed. We characterised an update
efficient storage code such that any changes in the stored data will result in a small number of
node updates. The necessary conditions was established which can be used to prove the existence
of an updated efficient code.
We also showed how the symmetries in the codes can be exploit to significantly reduce the
complexity of the constraints in the linear programming problem and in the necessary conditions.
R EFERENCES
[1] T. H. Chan, M. A. Tebbi, and C. W. Sung, “Linear programming bounds for storage codes,” in 9th International Conference
on Information, Communication, and Signal Processing (ICICS 2013), Dec. 2013.
[2] M. A. Tebbi, T. H. Chan, and C. Sung, “Linear programming bounds for robust locally repairable storage codes,” in proc.
Information Theory Workshop (ITW), 2014 IEEE, Nov. 2014, pp. 50–54.
[3] F. J. Macwilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, North Holland, Amsterdam, 1977.
[4] W. J. Bolosky, J. R. Douceur, D. ELY, and M. Theimer, “Feasibility of a serverless distributed file system deployed on an
existing set of desktop pcs,” in Proc. of Sigmetrics, June 2000.
[5] P. Druschel and A. Rowstron, “Storage management and caching in past, a large-scale, persistent peer-to-peer storage
utility,” in Proc. of ACM SOSP, 2001.
[6] Y. Chen, J. Edler, A. Goldberg, S. S. A. Gottlieb, and P. Yianilos, “Prototype implementation of archival intermemory,”
in Proc. of IEEE ICDE, Feb. 1996, pp. 485–495.
[7] S. Rhea, C. Wells, P. Eaton, D. Geels, B. Zhao, H. Weatherspoon, and J. Kubiatowicz, “Maintenance free global storage
in oceanstore,” in Poc. of IEEE Internet Computing, 2001, pp. 40–49.
[8] D. A. Patterson, G. Gibson, and R. Katz, “A case for redundant arrays of inexpensive disks (raid),” Computer Science
Division, Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA 94720,
Tech. Rep. CSD-87-391, Dec. 1987.
[9] J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer,
C. Wells, and B. Zhao, “Oceanstore: An architecture for global-scale persistent storage,” in Proc. 9th Int. Conf. Architectural
Support Programm. Lang. Oper. Syst., Boston, MA, Nov. 2000, pp. 190–201.
[10] R. Bhagwan, K. Tati, S. S. Y. Cheng, and G. Voelker, “Total recall: System support for automated availability management,”
in Proc. NSDI ’04.
[11] M. Blaum, J. Brady, J. Bruck, and J. Menon, “Evenodd: An efficient scheme for tolerating double disk failures in raid
architectures,” IEEE Trans. Inf. Theory, vol. 44, pp. 192–202, 1995.
[12] M. Blaum, J. Bruck, and A. Vardy, “Mds array codes with independent parity symbols,” IEEE Trans. Inf. Theory, vol. 42,
pp. 529–542, 1996.

30

[13] S. B. Wicker, Error Control Systems for Digital Communication and Storage. Englewood Cliffs, NJ: Prentice Hall, 1995.
[14] H. Weatherspoon and J. D. Kubiatowicz, “Erasure coding vs. replication: A quantitative comparison,” in Proc. Int. Workshop
Peer-to-Peer Syst., 2002.
[15] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage
systems,” IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4539–4551, Sep 2010.
[16] P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the locality of codeword symbols,” IEEE Trans. Inf. Theory,
vol. 58, no. 11, pp. 6925–6934, Nov. 2012.
[17] L. Pamies-Juarez, H. D. Hollmann, and F. Oggier, “Locally repairable codes with multiple repair alternatives,” in proc.
IEEE Int. Symp. Information Theory, 2013, pp. 892–896.
[18] A. S. Rawat, D. S. Papailiopoulos, A. G. Dimakis, and S. Vishwanath, “Locality and availability in distributed storage,”
in proc. IEEE Int. Symp. Information Theory, 2014, pp. 681–685.
[19] A. Wang and Z. Zhang, “Repair locality from a combinatorial perspective,” in proc. IEEE Int. Symp. Information Theory,
July 2014, pp. 1972–1976.
[20] A. S. Rawat, A. Mazumdar, and S. Vishwanath, “On cooperative local repair in distributed storage,” in 48th Annual
Conference on Information Sciences and Systems (CISS), March 2014, pp. 1–5.
[21] C. Huang, M. Chen, and J. Li, “Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data
storage systems,” Microsoft Research, Tech. Rep. MSR-TR-2007-25, March 2007.
[22] F. Oggier and A. Datta, “Self-repairing homomorphic codes for distributed storage systems,” in proc. IEEE INFOCOM,
2011, pp. 1251–1223.
[23] D. Papailiopoulos, J. Luo, A. Dimakis, C. Huang, and J. Li, “Simple regenerating codes: Network coding for cloud storage,”
in proc. IEEE INFOCOM, March 2012, pp. 2801–2805.
[24] I. Tamo, D. Papailiopoulos, and A. Dimakis, “Optimal locally repairable codes and connections to matroid theory,” in
proc. IEEE Int. Symp. Information Theory, Istanbul, July 2013, pp. 1814–1818.
[25] N. Silberstein, A. Rawat, O. Koyluoglu, and S. Vishwanath, “Optimal locally repairable codes via rank-metric codes,” in
proc. IEEE Int. Symp. Information Theory, Istanbul, July 2013, pp. 1819–1823.
[26] I. Tamo and A. Barg, “A family of optimal locally recoverable codes,” IEEE Trans. Inf. Theory, vol. 60, no. 8, pp.
4661–4676, July 2014.
[27] D. S. Papailiopoulos and A. G. Dimakis, “Locally repairable codes,” in proc. IEEE Int. Symp. Information Theory,
Cambridge, MA, July 2012, pp. 2771–2775.
[28] I. Tamo and A. Barg, “Bounds on locally recoverable codes with multiple recovering sets,” in proc. IEEE Int. Symp.
Information Theory, Honolulu, HI, July 2014, pp. 691–695.
[29] V. Cadambe and A. Mazumdar, “An upper bound on the size of locally recoverable codes,” in proc. Int. Symp. Network
Coding (NetCod), Calgary, AB, June 2013, pp. 1–5.
[30] S. Kadhe and R. Calderbank, “Rate optimal binary linear locally repairable codes with small availability,” in Proc. IEEE
Int. Symp. Information Theory, Aachen, Germany, June 2017, pp. 166–170.
[31] N. Prakash, V. Lalitha, and P. Kumar, “Codes with locality for two erasures,” in Proc. IEEE Int. Symp. Information Theory
(ISIT), June 2014, pp. 1962–1966.
[32] B. Chen, S.-T. Xia, and J. Hao, “Locally repairable codes with multiple (ri , δi )-localities,” in Proc. IEEE Int. Symp.
Information Theory (ISIT), Aachen, Germany, June 2017, pp. 2038–2042.
[33] N. Prakash, G. M. Kamath, V. Lalitha, and P. V. Kumar, “Optimal linear codes with a local-error-correction property,” in
Proc. IEEE Int. Symp. Information Theory (ISIT), Cambridge, MA, U.S.A., Jul. 2012, pp. 2776–2780.

31

[34] A. Zeh and E. Yaakobi, “Bounds and constructions of codes with multiple localities,” in Proc. IEEE Int. Symp. Information
Theory (ISIT), Barcelona, Spain, Jul. 2016, pp. 640–644.
[35] S. Kadhe and A. Sprintson, “Codes with unequal locality,” in Proc. IEEE Int. Symp. Information Theory (ISIT), Barcelona,
Spain, Jul. 2016, pp. 435–439.

