Improved Upper Bounds on Systematic-Length for Linear
Minimum Storage Regenerating Codes ⋆

arXiv:1610.08026v2 [] 5 Sep 2017

Kun Huang1 , Udaya Parampalli2 and Ming Xian1

Abstract. In this paper, we revisit the problem of finding the longest systematic-length k for a
linear minimum storage regenerating (MSR) code with optimal repair of only systematic part, for a
given per-node storage capacity l and an arbitrary number of parity nodes r. We study the problem
by following the geometric analysis of linear subspaces and operators. First, a simple quadratic
bound is given, which implies that k = r + 2 is the largest number of systematic nodes in the scalar
scenario. Second, an r-based-log bound is derived, which is superior to the upper bound on log-base
2
2 in the prior work. Finally, an explicit upper bound depending on the value of rl is introduced,
which further extends the corresponding result in the literature.
Key Words: MSR Codes, Systematic-Length, Linear Subspaces, Upper Bounds.

1

INTRODUCTION

Distributed storage systems (DSSs) are efficient storage systems designed for coping with the tremendously growing data. They have become an indispensable component of many distributed applications
such as cloud storage, social networking and peer to peer networking. Through introducing redundancy
in the form of replication or erasure coding, DSSs provide data storage services with high reliability [1].
Compared with the systems that employ replication, erasure codes achieve higher reliability for the same
level of redundancy [3]. In regard to repair bandwidth as a classical measurement of reliable DSSs, Dimakis et al. [4] propose a novel class of codes termed regenerating codes that are particularly advantageous
in repair efficiency.
1.1

Regenerating Codes

Regenerating codes [4] are a family of maximal distance separable (MDS) codes. In the framework, a
B-sized original data file over a finite field F is encoded into nα symbols that are distributed across n
nodes with each node storing α symbols. Data symbols stored in any k out of n nodes are sufficient to
recover the original data file, and meanwhile, any single node failure can be repaired by downloading β
symbols from each of d helper nodes out of the remaining n − 1 nodes. It is shown in [4] that regenerating
codes with parameter set {n, k, d, α, β, B} have to comply with the following constraint (tradeoff curve):
B≤

k
X

min{α, (d − i + 1)β},

(1)

i=1

where codes that achieve the above curve are called optimal regenerating codes. This tradeoff curve is
equipped with two extreme points, namely, minimum bandwidth regenerating (MBR) point and minimum
storage regenerating (MSR) point, respectively representing optimal regenerating codes with the least
⋆ 1

Kun Huang and Ming Xian are with State Key Laboratory of Complex Electromagnetic Environment Effects
on Electronics and Information System, National University of Defense Technology, Changsha, 410073, China
(khuangresearch923@gmail.com; qwertmingx@tom.com).
2
Udaya Parampalli is with Department of Computing and Information Systems, University of Melbourne, VIC
3010, Australia (udaya@unimelb.edu.au).

repair bandwidth and ones with the least per node storage. The corresponding parameters of the two
points are determined by

B
B


 (αMSR , βMSR ) = ( k , k(d − k + 1) )
(2)
2dB
2B


 (αMBR , βMBR ) = (
,
).
k(2d − k + 1) k(2d − k + 1)

There are three repair models considered in literature: functional repair, exact repair and exact repair
of systematic nodes [1]. Compared to functional repair, exact repair is highly favorable, since exact
repair can restore the exact replicas of the lost data [5]. In the exact repair scenario, Shah et al. in [6]
demonstrate that it is not achievable for most interior points on the tradeoff curve. For those possibly
achievable interior points, there are few constructions of codes [7,8]. Hereinafter, we restrict our focus to
exact repair of linear MSR codes.
1.2

Minimum Storage Regenerating Codes

Apart from the concept of regenerating codes, array codes [2] are extensively studied over several years
and have been widely deployed in DSSs [9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30].
An {n, k, l}-array code is built from an (l × n) matrix, where each column is the codeword stored in the
i-th node. The notation l known as sub-packetization size [32] basically represents the same meaning with
the parameter α of regenerating codes in the linear scenario. In this sense, as for optimal-repair MDS
array codes with {d = n − 1} that reside in the MSR scenario, the corresponding parameter notations can
be rewritten as {n, k, α = l, β = rl , B = kl} where r = n − k. Additionally, any optimal-repair systematic
MDS array code obviously belongs to the scenario of MSR codes, since the systematic structure of a code
signifies its property of minimum storage.
From the perspective of coding theory and technique for MSR codes, a lot of progresses have been
made. Collectively, MSR codes are categorized into scalar MSR codes with {β = 1} [9,10,11,12,13,14]
and vector MSR codes with {β > 1} [15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]. When d = n − 1,
scalar MSR codes are formed by {l = r} and the majority of these vector MSR codes are provided
with {β = (n − k)x ↔ l = rx+1 , x ≥ 1}. Most of current constructions are established on interference
alignment that is necessary for constructing linear MSR codes as shown in [14]. Moreover, it is verified
in [14] that there only exist scalar linear MSR codes within the low rate regime { nk ≤ 12 }. The known
product-matrix-based MSR code [9] is scalar for {2k − 2 ≤ d ≤ n − 1}. Another design for scalar
MSR codes with {d = n − 1 ≥ 2k − 1} is given in [10] that entirely stems from the technique of
interference alignment. In the high rate regime { nk > 21 }, vector MSR codes can be leveraged to allow
arbitrarily high rates to be attained. However, many of them allow optimal repair of only systematic
part [17,18,19,20,21,22,23,24,25,26,27,28] that are also referred to as systematic-repair1 MSR codes for
brevity, such as Permutation codes [17] and Zigzag codes [18]. Vector MSR codes permitting optimal
repair of parity nodes as well are proposed in [15,16,29], where the code given in [15] is a variant of
Zigzag code. On the other hand, Cadambe et al. in [32] prove that with l (or α) scaling to infinity, there
exist high-rate MSR codes with parameter set {n, k, d} of any value. Goparaju et al. in [31] provide an
non-explicit construction of systematic-repair MSR codes for all {k ≤ d ≤ n − 1} that can be used to
n
meet the high-rate requirement. For d < n − 1, authors in [30] present a special {l = 21 · r r } vector MSR
code with an explicit coupled-layer construction that optimally repairs all nodes, which in fact is built
on the design of [24] and also can be adjusted to have nk as close to 1 as desirable high rate.
1

The two concepts of systematic MSR codes and systematic-repair MSR codes have generated differences in
the definition of MSR codes. As described in [4], the formal description of an MSR code requires all nodes
be optimally repairable. But, many references in the literature also term a code as an MSR code even if it
allows optimal repair of systematic nodes only. In this case, we will distinguish between two types of MSR
codes by calling them as systematic-repair MSR codes and systematic MSR codes with optimal repair of all
nodes (or just systematic MSR codes for simplicity) respectively. When the context is clear or the distinction
is unnecessary, they both are named by MSR codes.

2

1.3

Existing Upper Bounds on Systematic-Length

In this paper, we center on {n = k + r, k, l} systematic-repair MSR codes for d = n − 1. We continue
investigating the question considered in [33,34] “the relationship between the node storage capacity l and
the number of systematic nodes k for some constant r”. In other words, our focus is on the question:
what is the longest systematic-length k for which there exists a linear systematic-repair MSR code, for a
given sub-packetization size l and a given number of parity nodes r?
Tamo et al. in [33] put forward this question. They first consider systematic-repair MSR codes with
two properties of particular interest, i.e., optimal access and optimal update, where an optimal-access
code transmits only the symbols it accesses and an optimal-update code updates exactly once in each
parity node. When restricted to optimal update, they demonstrate that the code with optimal access
has the same longest systematic-length k as the one with optimal bandwidth only, where kmax = logr l.
For example, Zigzag codes [18] are optimal-update that can attain this value. Without this restriction,
they further show that k = r logr l is the longest systematic-length for a systematic-repair MSR code
with optimal access. In [22], authors propose a first optimal-access and systematic-repair MSR code
that achieves this optimal value of systematic-length. Recently, authors in [28] also present an explicit
k
construction for systematic-repair MSR codes with optimal access, where l = r r reaches the optimal
value. Another construction of systematic-repair MSR codes with optimal access given in [29] requires
k
k
n
that l = r⌈ r ⌉ = r⌈ r ⌉+1 , which differs from lmin = r r by r2 approximately. However, for the general case
(i.e., non-optimal update and non-optimal access), Tamo et al. obtain a loose upper bound
 
l
(3)
k≤l l ,
r

and conjecture that k is of the order of logr l. In [19] and its extended version [20], authors design a
k
systematic-repair MSR code, where l = r r+1 or k = (r + 1) logr l that accords with the conjecture.
Towards the general case, Goparaju et al. in [34] transform it into a linear algebra problem involving a
set of linear subspaces and operators. Incorporating the idea of interference alignment and translation of
certain subspaces, they geometrically analyze the linear dependency of the relevant matrices and proceed
to derive three new upper bounds on k based on different number of parity nodes. For an arbitrary
number of parity nodes r, they first obtain a simple systematic-length bound
k ≤ l2 .

(4)

For the special case of 2 parity nodes, they prove that k ≤ 4l + 1. Then, based on the method of partition
for systematic part [1, k] where repair subspaces within each partition span the entire space Fl , they
k
design 2 λ linearly independent matrices and further derive
k ≤ 2λ log2 l,

(5)

where λ isjthe size kof each partition. Applying the geometric analysis ofj invariant
they prove
k subspaces,

r
r
that λ ≤ log r−1
log r−1
l + 1, which means that if the partition contains
l + 1 number of repair
subspaces, they necessarily span the whole space Fl . As a result, the second case in fact is included herein,
since it can be verified that 2 log2 l ⌊log2 l⌋ + 1 < 4l + 1.

Example 1 Consider a tiny storage disk of size that equals with 28 bits, i.e., l = 28 . As for the
 case of
8
16 2 + 1 ⋍ 1391.
r = 16 parity nodes, from the latest upper bound on k, we have that k ≤ 2 log2 28 log 15
With our new upper bound present in this paper, we will prove that k cannot exceed 348.

1.4

Our Contribution

In this work, we keep studying this general question by further exploiting the geometric analysis of linear
subspaces and operators raised in [34]. We consider the case of arbitrary number of parity nodes r.
3

With the basic principle of interference alignment and some equivalent transformations, we formalize two
derivative properties of subspaces and operators: (i) it is closed for operations by repair subspaces on
the addition and multiplication of encoding matrices, and (ii) any vectors coming from different linear
subspaces that mutually intersect trivially are linearly independent. Using the two properties, we find
new linearly independent matrices, which naturally bounds the systematic-length k.
First, we prove that all the encoding matrices are linearly independent, with which we give a simple
quadratic bound
l2 − 1
k≤
.
(6)
r−1
This simple bound implies that k = r + 2 is the longest systematic-length in the scalar scenario.
Then, we follow the idea of partition employed in [34], where we instead construct new matrix by
“adding” matrices of the same row within each partition. The reason for adding matrices instead of
multiplying them as in [34] is that matrix’s addition possesses the commutative law while multiplication
of matrix is non-commutative. Afterwards, through multiplying these constructed matrices from different
k
partitions in sequence, we further strike out r λ new matrices, where λ is the size of a partition. We
k
demonstrate that these r λ new matrices are all non-zero matrices and linearly independent, from which
we derive an r-based-log upper bound
k ≤ 2λ logr l.
(7)
k we consider estimating the partition size λ, where Goparaju et al. in [34] show that λ ≤
j Finally,
r
l + 1. Leveraging our previous work in [36], we introduce an explicit result as follows
log r−1
(
= r,
k when t = r;
j
(8)
λ:
(r−t)l
r
, when 1 ≤ t < r,
≤ t + 1 + log r−1
r
2

2

2

r
where t = ⌈ rl ⌉, i.e., t is an integer such that rt ≤ rl < t−1
or rl ≤ t < rl + 1. This result indicates that
j
k
r
λ = r if t = r and λ ≤ log r−1
l + 1 for t = 1, which extend the result in [34]. Furthermore, it is easy to
k
j
2
r
l + 1. In Example 1, for l = 28 and r = 16, we have that t = ⌈ 16
verify that r ≤ λ ≤ log r−1
28 ⌉ = 1 and


28 + 1 ⋍ 348.
therewith our r-based-log upper bound leads to that k ≤ 2 log16 28 log 16
15

Table 1 illustrates the research progresses on systematic-length k for linear systematic-repair MSR
codes2 including upper bounds and the scheme with the longest known systematic-length.
Table 1. Progresses on Systematic-Length k for Linear Systematic-Repair MSR Codes.
Citation
Tamo et al. [33]

Corresponding Results

k ≤ l ll
r
j
k ≤ l2 & k ≤ 2λ log2 l, where λ ≤ log

Goparaju et al. [34]
Wang et al. [20]
This Paper

r
r−1

k
l +1

the longest known scheme with
( systematic-length k = (r + 1) log r l
= r,
k when t = r;
j
−1
& k ≤ 2λ logr l, where λ :
k ≤ lr−1
, when 1 ≤ t < r.
≤ t + 1 + log r (r−t)l
r
2

r−1

2

In subsequent description, construction of linear systematic-repair MSR codes have to satisfy the condition
required for interference alignment, which however aims at designing MSR codes with only optimally repairing systematic nodes. Since interference alignment does not apply to systematic MSR codes (with optimally
repairing all nodes), it is evident that upper bounds on k for systematic MSR codes should be tighter than the
one for systematic-repair MSR codes. For the sake of clarity, we stress again that linear systematic-repair MSR
codes are our research object in this paper.

4

1.5

Organization

Section 2 gives preliminaries including the basic system setting, the technique of interference alignment
and two useful properties related to subspaces. Section 3 presents the detailed proof of our new results
for upper bounds on systematic-length. Section 4 concludes this paper.

2

PRELIMINARIES

In this section, we first describe the system setting about the basic construction of linear systematicrepair MSR codes. Then, the technique of interference alignment is introduced, where some equivalent
transformations are applied. Last, we formalize two properties of subspaces and operators, which will be
used to find new linearly independent matrices.
2.1

System Setting

Consider a linear systematic-repair MSR code with {n = k + r, k, l}, where each of n nodes stores l
data symbols over a finite field F such that any k nodes are sufficient to recover the k · l original data
symbols. With its systematic feature, we let (W1 , · · · , Wk ) denote these original data symbols stored in
the k systematic nodes. Each of the remaining r nodes, as a parity node, stores a linear combination of
(W1 , · · · , Wk ). Formally, the l encoded symbols of Wk+u stored in parity node u for each u ∈ [1, r], can
be expressed as
k
X
Cu,j Wj ,
(9)
Wk+u =
j=1

where Cu,j is a square encoding matrix of order l corresponding to the parity node u and the systematic
node j ∈ [1, k]. Hence, any linear systematic-repair MSR code can be uniquely represented as follows


C1,1 · · · C1,k


C = (Cu,j ){u∈[1,r],j∈[1,k]} =  ... . . . ...  .
(10)
Cr,1 · · · Cr,k

The MDS property of systematic-repair MSR codes requires that any r node failures can be recovered,
which is equivalent to that any block submatrix of (10) has to be invertible. Consequently, each encoding
matrix Cu,j also must be invertible.
In order to optimally repair any systematic node i ∈ [1, k], the remaining n − 1 nodes are supposed
to send a fraction rl of their data stored, i.e., each helper node {ν 6= i|ν ∈ [1, n]} sends rl repair data
l
symbols represented by Si,ν Wν , where Si,ν is a matrix over F r ×l . To this end, each repair data made of
l
r data symbols sent from helper node ν to systematic node i can be regarded as the projection of Wν
onto a subspace of dimension rl , which corresponds to the subspace spanned by the rows of Si,ν .
P
Note
U 1 To avoid confusion of the subsequent discussion, we let “ ” denote the normal sum
Lof matrices,
“ ” be the sum of subspaces (spanned by the rows of the corresponding matrices) and “ ” represent
the direct sum of certain subspaces that mutually intersect trivially. Besides, Si and Si Cu,j can represent
either a ( rl × l) matrix or a subspace of dimension rl . Furthermore, we let “0” denote the scalar zero,
zero-matrix or zero-subspace, which will be clear from the context.
2.2

Interference Alignment

As shown in [19], a linear systematic-repair MSR code has to meet the requirement
of interference

alignment. Optimal repair of a systematic node i is possible if and only if there exist Si,ν |ν 6= i, ν ∈ [1, n]
5

satisfying, for any u ∈ [1, r] and j ∈ [1, k] with j 6= i,

S ≃ Si,k+u Cu,j

 i,j
r
]

Si,k+u Cu,i ≃ Fl ,


(11)

u=1

where “ ≃ ” means that the subspaces
the corresponding matrices are identical.
U spanned by the rows ofL
Besides, the sum of the subspaces “ ” must be a direct sum “ ”, since the dimension of each subspace
{Si,ν |ν 6= i, ν ∈ [1, n]} is rl and each matrix Cu,i is invertible.
As explained in [33], each encoding matrix for one of the parity nodes in a linear systematic-repair
MSR code can be assumed to be the identity matrix I, i.e., C1,i = I for any i ∈ [1, k]. Thereafter, the
authors prove that if there exists a {k + r + 1, k + 1, l} linear systematic-repair MSR code, then there
also exists a {k + r, k, l} linear systematic-repair MSR code where the repair subspaces are independent
of the helper nodes. It indicates that, for a given i ∈ [1, k], Si,ν stays unchanged for any ν ∈ [1, n] and
ν 6= i, which can be replaced by Si accordingly.
Henceforth, the subspace conditions (11) almost can be equivalently transformed into:

S ≃ Si Cu,j

 i
r
M

Si Cu,i ⊕ Si ≃ Fl ,


(12)

u=2

where i, j ∈ [1, k] with j 6= i and Si is the repair matrix (or viewed as the independent repair subspace)
for systematic node i.
2.3

Properties of Subspaces

From the subspace conditions (12), two derivative properties are formally presented as follows, which can
be counted as a generalization of some results derived in [34].
Lemma 1. Given an {n = k + r, k, l} linear systematic-repair MSR code with independent repair subspaces, for any u1 , u2 ∈ [1, r] and any i, j1 , j2 ∈ [1, k] such that j1 6= i and j2 6= i, it must be that
(
Si (Cu1 ,j1 + Cu2 ,j2 )  Si ;
(13)
Si Cu1 ,j1 Cu2 ,j2  Si ,
where “  ” represents that the left subspace lies in the right one.
Proof. According to the first item in (12), “Si ≃ Si Cu,j ” signifies that the subspace spanned by the rl
row vectors of Si is same as the one spanned by the rl row vectors of Si Cu,j . Equivalently speaking, there
exists an invertible ( rl × rl ) matrix Pu,i,j such that Si Cu,j = Pu,i,j Si .
Thereby, we have
(

Si (Cu1 ,j1 + Cu2 ,j2 ) = (Pu1 ,i,j1 + Pu2 ,i,j2 )Si ;
Si Cu1 ,j1 Cu2 ,j2 = Pu1 ,i,j1 Pu2 ,i,j2 Si .

(14)

From the above equation, it is clear that Si Cu1 ,j1 Cu2 ,j2 ≃ Si , since Pu1 ,i,j1 Pu2 ,i,j2 still is an invertible
matrix. Moreover, because Pu1 ,i,j1 +Pu2 ,i,j2 also is a ( rl × rl ) matrix, it apparently leads to that (Pu1 ,i,j1 +

Pu2 ,i,j2 )Si  Si .
Remark 1 Lemma 1 indicates that it is closed for operations by Si on the addition and multiplication
of Cu,j for any j 6= i and u ∈ [2, r]. Consequently, any subspace generated from operating Si on a matrix
formed by arbitrary times of addition and multiplication of matrices Cu,j still lies in Si .
6

Lemma 2. Given an {n = k + r, k, l} linear systematic-repair MSR code with independent repair subl
spaces, for any i ∈ [1, k],
Pr if there exist r matrices {Θ1 , · · · , Θr } of size ( r × l) such that Θu  Si Cu,i
for each u ∈ [1, r] and u=1 Θu = 0, then it must be that
Θu = 0.

Lr
Proof. According to the second item in (12), “ u=2 Si Cu,i ⊕ Si ≃ Fl ” indicates that all the r subspaces
{Si Cu,i |u ∈ [1, r]} where C1,i = I, exactly span the entire space Fl . That is to say, the total l row vectors
of {Si Cu,i |u ∈ [1, r]} are linearly independent. Thus, it leads to that any r non-zero vectors coming from
r different subspaces Si Cu,i for u ∈ [1, r] are also linearly independent.
Pr Hereby, we assume there are non-zero matrices Θu for some u ∈ [1, r]. However, the condition
u=1 Θu = 0 implies that all non-zero vectors of the same row within these non-zero matrices Θu
are not linearly independent. Since these non-zero vectors lie in the corresponding subspaces Si Cu,i ,
contradiction arises.

Remark 2 Lemma 2 in fact is a derivative property of direct sum of linear subspaces, which means that
those vectors from different linear subspaces that mutually intersect trivially are linearly independent.
Subsequently, we use Lemma 1 and Lemma 2 to find new linearly independent matrices, which will
naturally offer the upper bounds on the systematic-length k.

3

IMPROVED SYSTEMATIC-LENGTH UPPER BOUNDS

In this section, we will present two new upper bounds on systematic-length. The first one is a simple
quadratic bound, which stems from the linear independence of encoding matrices. The second one is an rbased-log upper bound, which is based on the partition of systematic nodes [1, k], where repair subspaces
within each standard partition span the entire space Fl . Furthermore, we estimate the size of the standard
2
partition and introduce an explicit result depending on the value of rl , which can be integrated into the
r-based-log bound.
3.1

A Simple Quadratic Bound

Theorem 1. For any {n = k + r, k, l} linear systematic-repair MSR code with independent repair subspaces, the following upper bound holds
l2 − 1
k≤
.
(15)
r−1
n
o
Proof. We proceed to show that the k(r − 1) + 1 number of matrices I, Cu,i |u ∈ [2, r], i ∈ [1, k] are
linearly independent.
Assume there exist k(r − 1) + 1 coefficients au,i and b in F such that
k X
r
X

au,i Cu,i + bI = 0,

(16)

i=1 u=2

where “0” represents the zero-matrix.
Then, operating the above equation on Si for each i ∈ [1, k], we have
r
X

u=2

r
XX
au,i Si Cu,i + (
au,j Si Cu,j + bSi ) = 0,
j6=i u=2

7

(17)

P Pr
where Lemma 1 leads to that ( j6=i u=2 au,j Si Cu,j + bSi )  Si . With Lemma 2, we know that, for any
u ∈ [2, r] and i ∈ [1, k],
au,i = 0.
Combining with equation (16), we further derive
b = 0,
n
o
which exactly means that the k(r − 1) + 1 matrices I, Cu,i |u ∈ [2, r], i ∈ [1, k] are linearly independent.
Since they all lie in the l2 -dimensional space of matrices Fl×l , we have
k(r − 1) + 1 ≤ l2 ⇔ k ≤

l2 − 1
.
r−1

(18)


Remark 3 In [34], Goparaju et al. obtain that k ≤ l2 under the case of two parity nodes. Here, we look
2
−1
.
into the case of arbitrary number of parity nodes r and derive that k ≤ lr−1
In addition, we find that when l = r, it has to be that k ≤ r + 1. Without the premise that the repair
subspaces are independent of the helper nodes, we further have k ≤ r + 2 that is exactly consistent with the
corresponding result in [14], i.e., scalar linear systematic-repair MSR codes only exist when d ≥ 2k − 3
for d = n − 1. That is to say, in the scalar linear systematic-repair MSR scenario, k = r + 2 is the longest
systematic-length.
3.2

An r-Based-Log Bound

Theorem 2. For any {n = k + r, k, l} linear systematic-repair MSR code with independent repair subspaces, the following upper bound holds
k ≤ 2λ logr l,
(19)

Uλ
Uλ
l
where λ is the smallest integer value such that ν=1 Siν ≃ F or dim( ν=1 Siν ) = l for iν ∈ [1, k].
Proof. We follow the idea of partition considered in [34], while we employ the addition of matrices within
each partition instead of matrices’ multiplication therein. The basic difference is that matrix’s addition
has the commutative law while multiplication of matrix is non-commutative. We analyze two situations
as follows.
1. The situation when λ divides k.
Divide the indices of systematic nodes [1, k] into

k
λ

disjoint partitions {X1 , X2 , · · · , X k }, where Xi =
λo
n
[1 + (i − 1)λ, · · · , iλ]. Accordingly, partition {S1 , · · · , Sk } and I, Cu,i |u ∈ [2, r], i ∈ [1, k] as follows








S1
I
C2,1
..
.
Cr,1

· · · Sλ
··· I
· · · C2,λ
.
· · · ..
· · · Cr,λ

Sλ+1
I
C2,λ+1
..
.
Cr,λ+1

· · · S2λ
··· I
· · · C2,2λ
..
···
.
· · · Cr,2λ

···
···
···
···
···

Sk−λ+1
I
C2,k−λ+1
..
.
Cr,k−λ+1

where all entries of the second row are set to be the identity matrix I.
Setting: For each u ∈ [1, r] and i ∈ [1, λk ], define


 I, if u = 1;
X
Γi,u =
Cu,j , if u ∈ [2, r].


j∈Xi

8

· · · Sk
··· I
· · · C2,k
.
· · · ..
· · · Cr,k






,



(20)

(21)

Then, for any ui ∈ [1, r] and i ∈ [1, λk ], we define
k

∆u1 u2 ···u k =
λ

λ
Y

Γi,ui .

i=1

k

Thus, we totally obtain r λ square matrices formed as ∆u1 u2 ···u k for ui ∈ [1, r], which in fact all are
λ

k

non-zero matrices (It is proved in Appendix). In the following, we further show that these r λ square
matrices are also linearly independent.
Induction claim: Assume for some s ∈ [1, λk ], the following rs number of square matrices
(

∆u1 u2 ···us =

s
Y

Γi,ui | ui ∈ [1, r], i ∈ [1, s]

i=1

)

are linearly independent.
Base case: For s = 1, we have


λ
λ

o  X
o n
n
X
Cr,j .
C2,j , · · · ,
∆u1 | u1 ∈ [1, r] = Γ1,u1 | u1 ∈ [1, r] = I,


j=1

(22)

j=1

Assume there exist r coefficients (a1 , · · · , ar ) in F such that
a1 I + a2

λ
X

C2,j + · · · + ar

λ
X

Cr,j = 0.

(23)

j=1

j=1

Operating equation (23) by Si for any i ∈ [1, λ], we have
r
X

u=2

where
derive

P

j6=i

Pr

u=2

r
XX
au Si Cu,i + (
au Si Cu,j + a1 Si ) = 0,

(24)

j6=i u=2

au Si Cu,j +a1 Si  Si following from Lemma 1. According to Lemma 2, we can similarly
a1 = a2 = · · · = ar = 0,

(25)

which means the r matrices in (22) are linearly independent.
Inductive step: Let the inductive claim hold for some s, then it is true for s + 1. Otherwise, we have
(s)

(s)

Ψ1 + Ψ2 Γs+1,2 + · · · + Ψ(s)
r Γs+1,r = 0,
(s)

(26)

where Ψu for each u ∈ [1, r] are linear combinations of elements formed as ∆u1 u2 ···us . Operating the
above equation on Si for each i in Xs+1 = [sλ + 1, (s + 1)λ], we have
X
X
(s)
(s)
Cr,j ) = 0,
(27)
C2,j ) + · · · + Si Ψ(s)
Si Ψ1 + Si Ψ2 (
r (
j∈Xs+1

j∈Xs+1

which can be rearranged to
n
o
X
X
(s)
(s)
(s)
C2,j ) + · · · + Ψ(s)
Cr,j ) + Si Ψ2 C2,i + · · · + Si Ψ(s)
Si Ψ1 + Ψ2 (
r (
r Cr,i = 0.
j6=i

j6=i

9

Similarly, Lemma 1 leads to that
o
 n
X
X
(s)
(s)

C2,j ) + · · · + Ψ(s)
Cr,j )  Si ;
 Si Ψ1 + Ψ2 (
r (
j6=i




Si Ψ(s)
u Cu,i

j6=i

(28)

 Si Cu,i , f or u ∈ [2, r].

By Lemma 2, we know for each u ∈ [2, r] and i ∈ Xs+1 ,
Si Ψ(s)
u Cu,i = 0,

(29)

(s)

from which we derive Si Ψu = 0 for Cu,i is invertible. Combining with equation (27), we further know
(s)
(s)
Si Ψ1 = 0. Thus, for each u ∈ [1, r] and i ∈ Xs+1 , we have Si Ψu = 0.
U
(s)
Due to the condition that i∈Xs+1 Si ≃ Fl , it has to be that Ψu = 0 for each u ∈ [1, r], which
contradicts the induction assumption.
k

Conclusion: That is to say, the r λ square matrices formed by ∆u1 u2 ···u k are linearly independent.
Because they all lie in the l2 -dimensional space of matrices Fl×l , we have

λ

k

r λ ≤ l2 ⇔ k ≤ 2λ logr l.

(30)

2. The situation when λ does not divide k.
 
 
Assume pλ < k < (p + 1)λ, i,e., p = λk and p + 1 = λk . Then, divide [1, k] into p + 1 disjoint sets
as X1 = [1, · · · , k − pλ] and Xi = [k − (p + 2 − i)λ + 1, · · · , k − (p + 1 − i)λ], where |X1 | = k − pλ and
|Xi | = λ for each i ∈ [2, p + 1]. It should be noted here that X1 is not a standard partition and repair
subspaces within it cannot span the whole space Fl , because |X1 | < λ.
As in the first situation, we only need to consider the base case, since we apply the same method of
induction. In this case, by operating on Si for any i ∈ [1, k − pλ], it is trivial to verify that


k−pλ

o  k−pλ
n
X
X
Cr,j
(31)
C2,j , · · · ,
Γ1,u1 | u1 ∈ [1, r] = I,


j=1

j=1

are also linearly independent. Thus, we totally obtain rp+1 linearly independent square matrices
)
(
p+1
Y
Γi,ui | ui ∈ [1, r], i ∈ [1, p + 1] .
∆u1 u2 ···up+1 =
i=1

Therefore, we derive
r⌈ λ ⌉ ≤ l2 ⇒ k < 2λ logr l.
k

(32)

j

k

r
Remark 4 In [34], Goparaju et al. derive that k ≤ 2λ log2 l, where λ ≤ log r−1
l + 1. Here, we improve
the upper bound from log-base 2 to log-base r and obtain that k ≤ 2λ logr l.

In subsequent, we estimate the size of each standard partition λ, with which we will further give an
explicit upper bound.
3.3

An Explicit

r2
-Dependent
l

Bound

In the following, we use our previous work [36] to estimate the size of standard partition λ, combining
2
which with Theorem 2 we will further present an explicit bound depending on the value of rl .
10

3.3.1 Estimation of λ. In [34], Goparaju et al. apply the geometric analysis of the invariant subspace
and derive that for any m ∈ [1, k],
dim(

m
]

Si ) = dim(S1 ⊎ S2 ⊎ · · · ⊎ Sm ) ≥ 1 − (

i=1

r − 1 m
) l,
r

(33)

j
k
r
from which they obtain that λ ≤ log r−1
l + 1, i.e., if the size of a standard partition equals with
j
k
r
log r−1
l + 1, the repair subspaces within it necessarily span the entire space Fl . In addition, they find

that formula (33) is useful for studying the secrecy capacity of linear MSR codes in [35]. We also focus on
this secrecy issue in [36] and ultimately present an explicit result on secrecy capacity in the linear MSR
scenario that extends the result given in [35]. As shown in Theorem 6 of [36], it closely depends on the
value of β that is equal to rl herein. The following theorem can be looked upon as a direct corollary of
formula (72) of Theorem 6 given in [36].
Theorem 3. Given an {n = k + r, k, l} linear systematic-repair MSR code with independent repair
subspaces, for any set F ( [1, k] with |F | = m, we have
dim(

]

i∈F

Si ) :



= m rl ,
if
l
r−1 e
e
)
]
=
l
−
(r
−
t)(
)
,
if
≥ t rl + rl (r − t)[1 − ( r−1
r
r
r

m ≤ t;
m = t + e,

(34)

2

where t = ⌈ rl ⌉ and e ≥ 1.
Proof. As stated in Remark 11 of [36], all results therein in fact also apply to MSR codes with optimal
repair of systematic nodes only, although the general case for MSR codes with optimal repair of all
nodes is the study object in [36]. In this paper, we let a linear systematic-repair MSR code represented
by {n = k + r, k, l}, where n = d + 1, l = α and rl = β. Through changing the expression of related
parameters, formula (72) of Theorem 6 in [36] can be equivalently transformed into as follows
dim(

]

i∈F

Si ) :



= m rl ,
if
l
r−1 e
e
)
]
=
l
−
(r
−
t)(
)
,
if
≥ t rl + rl (r − t)[1 − ( r−1
r
r
r

r
m ≤ t, rl < t−1
;
r
m = t + e, t ≤ rl <

where 1 ≤ t ≤ r and e ≥ 1. Since t is an integer satisfying the condition that
o
r2
r2
l + 1 , we can rewrite it as t = ⌈ l ⌉, where it is trivial that 1 ≤ t ≤ r.

n

r
t

≤

l
r

<

r
t−1

r
t−1 ,

⇔

r2
l

(35)

≤t<


Remark 5 It has been verified in [36] that,

l
l
r−1 e
l
l
r−1
l
l
t
l
l

 t + (r − t)[1 − (
) ] < t + (r − t)[e(1 −
)] = t + e (1 − ) < (t + e) = m ;
r r
r
r r
r
r
r
r
r
r

 t l + l (r − t)[1 − ( r − 1 )e ] = l[1 − ( r − t )( r − 1 )e ] ≥ l[1 − ( r − 1 )t ( r − 1 )e ] = [1 − ( r − 1 )m ]l,
r r
r
r
r
r
r
r
(36)
U
which implies that when dim( i∈F Si ) ≤ l,
[1 − (

]
r−1 m
l
) ]l ≤ dim(
Si ) ≤ m .
r
r

(37)

i∈F

As assumed in [34], we also make hypothesis that λ < k, i.e., there exists at least one standard
partition properly included in [1, k]. Otherwise,
we have k ≤ λ. Next, we apply Theorem 3 to estimate λ,
U
the smallest value of m satisfying dim( i∈F Si ) = l.
11

Theorem 4. Given an {n = k + r, k, l} linear systematic-repair MSR code with independent repair
subspaces, we have
(
= r,
k if t = r;
j
λ:
(38)
(r−t)l
r
, if 1 ≤ t < r.
≤ t + 1 + log r−1
r
2

where t = ⌈ rl ⌉.

Proof. There are two cases analyzed as follows.
1. The case when t = r.
U
According to the first item of Theorem 3, we know when m = r, it is clear that dim( i∈F Si ) = l.
Thus, we have λ = r.
2. The case when 1 ≤ t < r.
U
According to the second item of Theorem 3, we know when m = t + e, then dim( i∈F Si ) ≥ l − rl (r −
U
(r−t)l
l
r−1 e
e
r
t)( r−1
r ) . Hence, when r (r − t)( r ) < 1 or e > log r−1
r , it has to be that dim( i∈F Si ) = l. Thus,
k
j
(r−t)l
r
.

we obtain that λ ≤ t + e = t + 1 + log r−1
r

k
j
(r−1)l
r
= 2+
Remark 6 From Theorem 4, we know when t = 1, it is clear that λ ≤ 2 + log r−1
r
k
j
k
j
r
r
l − 1 = 1 + log r−1
l , which is consistent with the corresponding result in [34]. Besides, one
log r−1
can check that, for 1 < t < r,


k
j
(r − t)l
r
r
l ,
(39)
< 1 + log r−1
r < t + 1 + log r−1
r
which basically corresponds to the inequality (37).

3.3.2 Final Explicit Result. Eventually, combining Theorem 2 and Theorem 4, we derive the final
explicit bound as follows.
Theorem 5. For any {n = k + r, k, l} linear systematic-repair MSR code with independent repair subspaces, the following upper bound holds
k ≤ 2λ logr l,
(40)
wherein
λ:
2

where t = ⌈ rl ⌉.

(

= r,
j
r
≤ t + 1 + log r−1

(r−t)l
r

k when
, when

t = r;
1 ≤ t < r,

(41)

Remark 7 Through literature survey, MSR codes for {d = n − 1} known so far are generally divided
into scalar MSR codes with {l = r} and vector MSR codes with {l = rx+1 , x ≥ 1}, which correspond to
t = r and t = 1 respectively. As stated in [36], it remains open for constructing vector MSR codes with
{r < l < r2 }.
When l = r, Theorem 1 implies that k = r + 1 is the longest systematic-length for the scalar linear
systematic-repair MSR codes with independent repair subspaces. According to Theorem 5, we know that
when l = r, it has to be that λ = t = r, following which we have k ≤ 2r. Essentially, when k = r + 1, it
is evident that λ = r does not divide k and thus it should be that k < 2r following from Theorem 2. The
reason is that, for k = r + 1, k systematic nodes can only be split into one standard partition as well as
an nonstandard partition, where the size of the nonstandard partition equals with 1 that is smaller than r.
In some sense, the r-based-log upper bound basically coincides with the real largest number of systematic
12

nodes in the scalar scenario. In other words, the longest systematic-length k = r + 1 is indeed included in
the actual case of k < 2r derived from the r-based-log upper bound for l = r.
When l ≥ r2 , it is clear that t = 1. For example in Table
 1, the systematic-repair MSR code with the
longest systematic-length
known
so
far
given
in
[20]
is
with
k = (r+1) logr l . However, Theorem
5 leads
j
k
k
j
r
r
to that k ≤ 2 logr l 1+ log r−1
l . By comparison, we find that r+1 is strictly less than 2 1+ log r−1
l

even for l = r2 and r = 2, which means that the code in [20] cannot reach the derived upper bound. That
is to say, although we do improve the upper bound from previous log-base 2 to current log-base r, it is
still unknown yet whether the upper bound in Theorem 5 can be achieved for some unexplored vector
linear systematic-repair MSR code. Nevertheless, our r-based-log upper bound is nearly in line with the
conjecture that k is of the order of logr l proposed by Tamo et al. in [33].
3.4

Further Discussions

As stated in Remark 5, our Theorem 3, Theorem 4 and Theorem 5 all are based on the assumption λ < k,
i.e., systematic part at least properly includes one standard partition, while Theorem 2 also applies to the
case of k = λ as the systematic part [1, k] exactly constitutes a standard partition. Thereby, the situation
k ≤ λ is left open.
When k = λ, it is clear that k ≤ 2λ logr l from Theorem 2, since it is trivial that r ≤ l for r divides l.
When k < λ, the systematic part cannot satisfy the condition for the formation of a standard partition,
which implies the notation λ is meaningless at present. In this case, we cannot obtain the log-based upper
bound similarly. Hence, we put forward two questions as follows.
Question 1. What value of l and r taken can we make the largest number of systematic node k equal with
λ in the linear systematic-repair MSR scenario? What is the exact value of k for this case?
Technically, under the condition (12), we assume k{l,r} is the longest systematic-length for given l and
r. Then, what values of l and r taken will make k{l,r} satisfy

k{l,r}

]



Si ) = l;
dim(



i=1
(42)
k{l,r} −1

]




Sij ) < l, f or any distinct ij ∈ [1, k{l,r} ],
dim(


j=1

where dim(Si ) =

l
r

for each i ∈ [1, k{l,r} ].

Question 2. What value of l and r taken will make the systematic part cannot form a standard partition
in the linear systematic-repair MSR scenario? What is the largest number of systematic nodes k now?
With the same definition of k{l,r} as above, what range of values for l and r will make k{l,r} satisfy
k{l,r}

dim(

]

Si ) < l,

(43)

i=1

where dim(Si ) =

l
r

for each i ∈ [1, k{l,r} ].

Remark 8 Question 1 and Question 2 are our next direction of study. It may help further improve
the upper bound on systematic-length, since our r-based-log upper bound are built on the assumption
Uk{l,r}
Si ) > l. The intuition establishes on the fact that the length k{l,r} of the systematic part
dim( i=1
herein is not larger than λ the least number of systematic nodes for supporting a standard partition.
13

4

CONCLUSION

Finding the exact systematic-length upper bound for a systematic-repair MSR code with r parity nodes
and storage capacity l is an open problem. Following the method of geometric analysis on a set of
subspaces and operators, we formalize two helpful derivative properties of subspaces under the case of
arbitrary number of parity nodes. With them, we first demonstrate the linear independence among all
encoding matrices and then design new linearly independent matrices based on the idea of partition,
which naturally bound the systematic-length k. Finally, we derive a simple quadratic bound and an rbased-log bound, which both are superior to the previous results. Moreover, leveraging our prior work
[36], we estimate the size of a standard partition and further present an explicit bound depending on the
2
value of rl .

5

APPENDIX

Corollary 1. In Theorem 2, we define
k

∆u1 u2 ···u k =
λ

where
Γi,u

λ
Y

Γi,ui ,

i=1



 I, if u = 1;
X
=
Cu,j , if u ∈ [2, r],



(44)

j∈Xi

k

for ui ∈ [1, r] and i ∈ [1, λk ]. In fact, all of these r λ matrices are non-zero.
Proof. We still employ the proof of contradiction.
Induction claim: Assume for some s ∈ [1, λk ], the following square matrix
∆u1 u2 ···us =

s
Y

Γi,ui 6= 0,

i=1

where ui ∈ [1, r].
Base case: For s = 1, we have
∆u1 = Γ1,u1 ,
where it is clear from the definition that Γ1,u1 = I 6= 0 if u1 = 1.
P
If u1 ∈ [2, r], Γ1,u1 = j∈X1 Cu1 ,j . According to Theorem 1, we know
P that the matrices {Cu1 ,j | j ∈
X1 } are linearly independent, from which it is apparent that Γ1,u1 = j∈X1 Cu1 ,j 6= 0 for any u1 ∈ [2, r].

Inductive step: Let the inductive claim hold for some s, then it is true for s + 1. Otherwise, we have
∆u1 u2 ···us+1 =

s+1
Y

Γi,ui = 0.

(45)

i=1

1. When us+1 = 1, we have Γs+1,1 = I. Thus, it has to be that ∆u1 u2 ···us+1 = ∆u1 u2 ···us = 0, which
contradicts the induction assumption.
P
2. When us+1 ∈ [2, r], Γs+1,us+1 = j∈Xs+1 Cus+1 ,j , with which we have
∆u1 u2 ···us+1 = ∆u1 u2 ···us (

X

j∈Xs+1

14

Cus+1 ,j ) = 0.

(46)

Operating the above equation on Si for each i in Xs+1 = [sλ + 1, (s + 1)λ], we obtain
X
Si ∆u1 u2 ···us Cus+1 ,i + Si ∆u1 u2 ···us (
Cus+1 ,j ) = 0,

(47)

j6=i

P
where Si ∆u1 u2 ···us Cus+1 ,i  Si Cus+1 ,i and Si ∆u1 u2 ···us ( j6=i Cus+1 ,j )  Si from Lemma 1.
Further by Lemma 2, we derive, for each i ∈ Xs+1 ,

Si ∆u1 u2 ···us Cus+1 ,i = 0,

(48)

from which we have Si ∆u1 u2 ···us = 0, since Cus+1 ,i is invertible. Under the condition
must be that ∆u1 u2 ···us = 0, which also contradicts the induction assumption.
Conclusion: That is to say, any square matrix formed as ∆u1 u2 ···u k is non-zero.

U

i∈Xs+1

Si ≃ Fl , it



λ

References
1. A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Suh, “A survey on network codes for distributed storage,”
Proc. IEEE, vol. 99, no. 3, pp. 476–489, Mar. 2011.
2. M. Blaum, P. G. Farell, and H. van Tilborg, “Array codes,” in Handbook of Coding Theory, V. Pless and W.
C. Huffman, Eds. Elsevier Science, 1998, vol. II, ch. 22, pp. 1855-1909.
3. H. Weatherspoon and J. D. Kubiatowicz, “Erasure coding vs. replication: A quantitiative comparison,” in
Proc. Int. Workshop. Peer–Peer Syst., 2002, pp. 328–338.
4. 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.
5. C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, and S. Yekhanin, “Erasure coding in
windows azure storage,” presented at the USENIX Annu. Tech. Conf., Boston, MA, USA, Jun. 2012.
6. N. B. Shah, K. V. Rashmi, and P. V. Kumar, and K. Ramachandran, “Distributed storage codes with repairby-transfer and nonachievability of interior points on the storage-bandwidth tradeoff,” IEEE Trans. Inf.
Theory, vol. 58, no. 3, pp. 1837–1852, Mar. 2012.
7. C. Tian, B. Sasidharan, V. Aggarwal, V. A. Vaishampayan, and P. V. Kumar, “Layered exact-repair regenerating codes via embedded error correction and block designs,” IEEE Trans. Inf. Theory, vol. 61, no. 4, pp.
1933–1947, Apr. 2015.
8. T. Ernvall, “Codes between MBR and MSR points with exact repair property,” IEEE Trans. Inf. Theory,
vol. 60, no. 11, pp. 6993–7005, Nov. 2014.
9. K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Optimal exact-regenerating codes for distributed storage at
the MSR and MBR points via a product-matrix construction,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp.
5227–5239, Aug. 2011.
10. C. Suh and K. Ramchandran, “Exact-repair MDS code construction using interference alignment,” IEEE
Trans. Inf. Theory, vol. 57, no. 3, pp. 1425–1442, Mar. 2011.
11. Y. Wu and A. G. Dimakis, “Reducing repair traffic for erasure coding-based storage via interference alignment,” in Proc. Int. Symp. Inf. Theory. (ISIT), Jul. 2009, pp. 2276–2280.
12. K. V. Rashmi, N. B. Shah, P. V. Kumar, and K. Ramchandran, “Explicit construction of optimal exact
regenerating codes for distributed storage,” in Proc. 47th Annu. Allerton Conf. Commun., Control, Comput.,
Urbana-Champaign, Sep. 2009, pp. 1243–1249.
13. K. V. Rashmi, N. B. Shah, K. Ramchandran, and P. V. Kumar, “Regenerating codes for errors and erasures
in distributed storage,” in Proc. Int. Symp. Inf. Theory. (ISIT), Jul. 2012, pp. 1202–1206.
14. N. B. Shah, K. V. Rashmi, P. V. Kumar, and K. Ramchandran, “Interference alignment in regenerating
codes for distributed storage: Necessity and code constructions,” IEEE Trans. Inf. Theory, vol. 58, no. 4, pp.
2134–2158, Apr. 2012.
15. Z. Wang, I. Tamo, and J. Bruck, “On codes for optimal rebuilding access,” in Proc. 49th Annu. Allerton
Conf. Commun., Control, Comput., Monticello, IL, USA, Sep. 2011, pp. 1374–1381.
16. D. S. Papailiopoulos, A. G. Dimakis, and V. R. Cadambe, “Repair optimal erasure codes through hadamard
designs,” IEEE Trans. Inf. Theory, vol. 59, no. 5, pp. 3021–3037, May. 2013.

15

17. V. R. Cadambe, C. Huang, and J. Li, “Permutation code: Optimal exact-repair of a single failed node in MDS
code based distributed storage systems,” in Proc. Int. Symp. Inf. Theory (ISIT), Jul. 2011, pp. 1225-1229.
18. 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.
19. Z. Wang, I. Tamo, and J. Bruck, “Long MDS codes for optimal repair bandwidth,” in Distrib. Inf. Syst.
Group, Dept. Elect. Eng., California Inst. Technol, Pasadena, CA, USA, Tech. Rep. ETR116, Jul. 2012, pp.
1182–1186.
20. Z. Wang, I. Tamo, and J. Bruck, “Explicit minimum storage regenerating codes,” IEEE Trans. Inf. Theory,
vol. 62, no. 8, pp. 4466–4480, Aug. 2016.
21. V. R. Cadambe, C. Huang, S. A. Jafar, and J. Li. (Jun. 2011). “Optimal repair of MDS codes in distributed
storage via subspace interference alignment.” [Online]. Available: http://arxiv.org/abs/1106.1250
22. V. R. Cadambe, C. Huang, J. Li, and S. Mehrotra, “Polynomial length MDS codes with optimal repair in
distributed storage,” in Proc. Conf. Rec. Signals, Syst. Comput. 45th Asilomar Conf., Nov. 2011, pp. 1850–
1854.
23. G. K. Agarwal, B. Sasidharan, and P. V. Kumar, “An alternate construction of an access-optimal regenerating
code with optimal subpacketization level,” in Proc. Nat. Conf. Commun. (NCC), Feb. 2015, pp. 1–6.
24. B. Sasidharan, G. K. Agarwal, and P. V. Kumar, “A high-rate MSR code with polynomial sub-packetization
level,” in Proc. Int. Symp. Inf. Theory (ISIT), Jul. 2015, pp. 2051–2055.
25. Y. S. Han, H. T. Pai, R. Zheng, and P. K. Varshney, “Update-efficient regenerating codes with minimum
per-node storage,” in Proc. Int. Symp. Inf. Theory (ISIT), Jul. 2013, pp. 1436–1440.
26. J. Li, X. Tang, and U. Parampalli, “A framework of constructions of minimal storage regenerating codes with
the optimal access/update property,” IEEE Trans. Inf. Theory, vol. 61, no. 4, pp. 1920-1932, Apr. 2015.
27. A. S. Rawat, O. O. Koyluoglu, and S. Vishwanath, “Progress on high-rate MSR codes: Enabling arbitrary
number of helper nodes.” [Online]. Available: http://arxiv.org/abs/1601.06362
28. N. Raviv, N. Silberstein, and T. Etzion, “Access-optimal MSR codes with optimal sub-packetization over
small fields.” [online]. Available: http://arxiv.org/abs/1505.00919
29. M. Ye and A. Barg, “Explicit constructions of optimal-access MDS codes with nearly optimal subpacketization.” [online]. Available: http://arxiv.org/abs/1605.08630
30. B. Sasidharan, M. Vajha, and P. V. Kumar, “An explicit, coupled-layer construction of a high-rate
MSR code with low sub-packetization level, small field size and all-node repair.” [online]. Available:
http://arxiv.org/abs/1607.07335
31. S. Goparaju, A. Fazeli, and A. Vardy, “Minimum storage regenerating codes for all parameters,” in Proc. Int.
Symp. Inf. Theory (ISIT), Jul. 2016, pp. 76–80.
32. V. R. Cadambe, S. Jafar, H. Maleki, K. Ramchandran, and C. Suh, “Asymptotic Interference Alignment
for Optimal Repair of MDS Codes in Distributed Storage,” IEEE Trans. Inf. Theory, vol. 59, no. 5, pp.
2974–2987, May. 2013.
33. I. Tamo, Z. Wang, and J. Bruck, “Access vs. bandwidth in codes for storage,” IEEE Trans. Inf. Theory, vol.
60, no. 4, pp. 2028–2037, Apr. 2014.
34. S. Goparaju, I. Tamo, and R. Calderbank, “An improved sub-packetization bound for minimum storage
regenerating codes,” IEEE Trans. Inf. Theory, vol. 60, no. 5, pp. 2770–2779, May. 2014.
35. S. Goparaju, S. El Rouayheb, R. Calderbank, and H. V. Poor, “Data secrecy in distributed storage systems
under exact repair,” in Proc. IEEE Int. Symp. Netw. Coding. (NETCOD), Calgary, AB, Canada, Jun. 2013,
pp. 1–6.
36. K. Huang, U. Parampalli, and M. Xian, “On secrecy capacity of minimum storage regenerating codes,” IEEE
Trans. Inf. Theory, vol. 63, no. 3, pp. 1510–1524, Mar. 2017.

16

