1

Increasing Availability in Distributed Storage
Systems via Clustering
Saeid Sahraei, Student Member, IEEE, and Michael Gastpar, Fellow, IEEE

arXiv:1710.02653v2 [] 22 Jan 2018

Abstract
We introduce the Fixed Cluster Repair System (FCRS) as a novel architecture for Distributed Storage Systems
(DSS) that achieves a small repair bandwidth while guaranteeing a high availability. Specifically we partition the
set of servers in a DSS into s clusters and allow a failed server to choose any cluster other than its own as its repair
group. Thereby, we guarantee an availability of s − 1. We characterize the repair bandwidth vs. storage trade-off for
the FCRS under functional repair and show that the minimum repair bandwidth can be improved by an asymptotic
multiplicative factor of 2/3 compared to the state of the art coding techniques that guarantee the same availability.
We further introduce cubic codes designed to minimize the repair bandwidth of the FCRS under the exact repair
model. We prove an asymptotic multiplicative improvement of 0.79 in the minimum repair bandwidth compared
to the existing exact repair coding techniques that achieve the same availability. In addition, we show that cubic
codes are information-theoretically optimal for the FCRS with 2 and 3 complete clusters.

I. I NTRODUCTION
A Distributed Storage System (DSS) is a network consisting of several servers that collectively store
a large content. A DSS is designed with two main criteria in mind. Firstly, as individual servers can fail
at any given time, the data must be stored in a redundant manner. The objective is to avoid a permanent
loss of the data even in the event of multiple simultaneous failures. Secondly, these failed servers must be
replaced with new ones efficiently, that is, without generating too much traffic. The abstract model that
is commonly used to capture these two aspects is as follows. Suppose we have a file M of size M and
n servers each with a storage of size α. We require that any set of k servers can collectively recover the
file M. This is referred to as the data recovery criterion. Put differently, the network must be resilient to
failure of any set of n − k servers. As a server fails, a newcomer must replace it, by connecting to d other
servers and downloading β units of data from each, thus occupying a repair bandwidth of γ = dβ. This is
called the repair process and the set of d servers are called the repair group. The definition of repair can
be rather ambiguous as there are several different repair models studied in the literature. We are interested
in two of them here. “Exact repair”, where the newcomer must be identical to the failed server; and
“functional repair” where the newcomer has the same functionality as the failed server, meaning that it
must be able to participate in future data recovery and repair processes of other servers. These definitions
will be made more precise in the following sections.
Assuming that a failed server must be able to choose any set of d servers as its repair group, the
trade-off between α and γ has been completely characterized in [1] under functional repair via a network
information flow analysis. Two points on this trade-off are of particular interest: the Minimum Bandwidth
Regenerating (MBR) point and the Minimum Storage Regenerating (MSR) point where γ and α are
minimized, respectively. As for the exact repair model, explicit codes [2]–[5] and converse bounds [6],
[7] have been studied in depth. It is known [8] that a non-vanishing gap exists between the overall
achievable (α, γ) region for the two repair models.
It was observed in [1] that as the size of the repair group, the parameter d, grows large the required
repair bandwidth γ can be made smaller for a fixed storage size α. Setting d = n − 1, we achieve the best
tradeoff between α and γ. However there are important downfalls to setting d very large. A coding scheme
This work was supported in part by the Swiss National Science Foundation under Grant 169294.
S. Sahraei and M. Gastpar are with the school of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne,
Lausanne 1015, Switzerland (email: saeid.sahraei@epfl.ch; michael.gastpar@epfl.ch).

2

that is designed based on say, d = n−1 is not optimal for repairing multiple parallel failures. Furthermore,
the servers involved in the repair process of one failed server may not be available to perform other tasks.
More specifically, an architecture with large d is not suitable for applications that involve reading hot
data [9], [10] where multiple parallel reads of the same block might become necessary. Mainly in light of
this latter issue, the parameter availability is defined in the literature. A server in a DSS is said to have
(all-symbol) availability s − 1 if there are s − 1 disjoint sets of servers that can serve as its repair group.
A DSS has availability s − 1 if all the servers in the DSS have availability s − 1.
This parameter has been largely investigated in the context of locally repairable codes [11], [12], i.e.
codes for which the size of the repair group can be made much smaller than k. The tradeoff between locality
(size of the repair group) and availability has been extensively studied [9], [10], [13]–[15]. Nevertheless, in
the context of locally repairable codes the parameter repair bandwidth is typically ignored (and sacrificed).
In this work we introduce the Fixed Cluster Repair System (FCRS) model as a novel architecture
which aims at achieving a high availability while maintaining a low repair bandwidth. The main idea is
to partition the servers into s clusters of equal size, and a final cluster of size s0 = mod (n, s). As a
server in a cluster fails, we allow it to choose any of the remaining clusters as its repair group (the last
cluster is an exception: as it does not contain as many servers as the remaining clusters, we exempt it
from serving as a repair group.) This way, we achieve an availability of s − 1. It is noteworthy that this
clustering is not relevant for the data recovery process, meaning that any set of k servers must be able to
recover the file, regardless of which cluster they belong to.
The term Fixed Cluster Repair System has been specifically chosen to contrast with Adjustable Cluster
Repair System (ACRS), a general model where the repair groups of two different servers do not necessarily
coincide with each other. Studying an ACRS should lead us to answering a general question. Suppose we
are given a DSS consisting of n servers that follow the data recovery and repair requirements discussed
above, while guaranteeing an availability s − 1. What is the trade-off between storage α and repair
bandwidth γ under these constraints? To the best of our knowledge there has not been any literature so
far that specifically addresses this question. However, the random linear codes as well as the explicit
codes for the seminal work in [1] serve as achievability results for ACRS. In fact, since a server can
choose any subset of d servers as its repair group in [1] where d ∈ [k : n], it is possible to achieve an
c]. The random linear codes and the cubic codes designed
availability of s − 1 for any s − 1 ∈ [1 : b n−1
k
for FCRS (Sections III and IV) can be viewed as achievability schemes for ACRS too for any availability
s − 1 ∈ [1 : b nk c − 1]. While we emphasize that a comparison with the work in [1] is not in its entirety fair
as the parameter availability has not been a driving motive there, we do find it instructive to demonstrate,
through a comparative study, how clustering can help with achieving a low repair bandwidth and a high
availability.
Our main objective in this paper is to thoroughly analyze the FCRS under both functional and exact
repair models. We will follow a network information flow analysis to completely characterize the α vs γ
trade-off for the FCRS with arbitrary parameters. An interesting observation is made here. We show that
the only adverse affect of increasing the number of clusters in the FCRS is the inevitable decrease in the
size of the repair groups. In other words, two FCRSs with n = ds and n0 = ds0 with respectively s and
s0 clusters have exactly the same performance in terms of the achievable (α, γ) region. By characterizing
the entire (α, γ) region, we show that for small values of γ FCRS performs better than [1]. Whereas, on
the other end of the spectrum, when α is small, [1] is superior. The improvements offered by the FCRS
are most visible at the MBR point itself (the point where the repair bandwidth is minimized), at which
we prove an asymptotic multiplicative improvement of 23 over the repair bandwidth compared to [1], as
s, k and n grow large.
Our second contribution is to propose cubic codes for the FCRS which are designed to minimize the
repair bandwidth under exact repair. Cubic codes are examples of Fractional Repetition codes [16], codes
that do not require any computation to perform the repair process. More specifically, they are subclasses
of Affine Resolvable Designs and generalisations of Grid Codes both discussed in [17]. When the number
of clusters is small (two or three complete clusters with no residual servers), we prove that cubic codes

3

do minimize the repair bandwidth for the FCRS. While we do not generalize this proof of optimality of
cubic codes to an arbitrary number of clusters, we prove that they achieve an asymptotic (again, as s, k
and n grow large) multiplicative improvement of 0.79 over the repair bandwidth compared to the MBR
codes for [1].
Before we move on, it is worth noting that clustering is not a new term or technique in the analysis
of Distributed Storage Systems. “Clustered Storage Systems” have been studied in a series of works
[18], [19] where different repair bandwidths are associated to inter-cluster and intra-cluster repair. These
models have close connections with the “rack model” [20]–[22] and are generally motivated by the physical
architecture of the network and the fact that the cables/channels which connect the servers within one
cluster or rack have higher capacities than the inter-cluster counterparts, which creates the motivation
to mostly confine the repair process to within the same cluster as the failed server. They also have
slightly different data recovery requirements in [18] than [1] and the model studied here. These physical
considerations do not play any role in our analysis. We simply assume a completely symmetric structure
where the communication bandwidth between any pair of servers is identical.
The rest of the paper is organized as follows. In Section II we provide a precise description of FCRS.
In Section III we analyze the FCRS with arbitrary parameters under the functional repair model and make
a numerical as well as analytical comparison with the results in [1]. In section IV we introduce cubic
codes as explicit constructions targeted to minimize the repair bandwidth for the FCRS under exact repair.
Comparisons with MBR codes for [1] will follow. Finally in Section V, we provide a converse bound for
the exact repair problem with s ≤ 3 complete clusters (no residual servers) which indicates that cubic
codes indeed minimize the repair bandwidth when the number of clusters is small.
II. M ODEL D ESCRIPTION
The FCRS is defined by three parameters n, k and s. Suppose the network consists of n = ds + s0
servers where d = b ns c and s0 = mod (n, s) and 2 ≤ s ≤ b nk c. We partition these servers into s + 1
clusters, s of which are of size d and the last of size s0 . We have a file M of size H(M) = M . Each
server i ∈ [1 : n] is equipped with a memory. We model each memory with a random variable where
(i)
the server can store a function of M. Specifically the random variable Xj,t represents the content of the
j’th server in the i’th cluster at time slot t where (i, j) ∈ {[1 : s] × [1 : d]} ∪ {{s + 1} × [1 : s0 ]} and
(i)
t ∈ Z+ ∪ {0}. We restrict the size of each memory to be bounded by α, that is, H(Xj,t ) ≤ α ∀ i, j, t.
(i)
(i)
For a set E ⊆ [1 : d] we define XE,t = {Xe,t s.t. e ∈ E}. The initial contents of the servers at t = 0
must be chosen in such a way that any set of k servers can collectively decode the file M, irrespective
of their clusters. In P
other words, for any (E1 , . . . , Es , Es+1 ) that satisfy Ei ⊆ [1 : d] for i ∈ [1 : s] and
Es+1 ∈ [1 : s0 ], and s+1
i=1 |Ei | = k, we must have
(1)

(s+1)

H(M|XE1 ,0 , . . . , XEs+1 ,0 ) = 0.
The servers in the network are subject to failure. We assume that at the end of each time slot exactly one
server fails. Suppose at the end of time slot t, the `’th server in the r’th cluster fails. At the beginning of the
next time slot this server is replaced by a newcomer. A second cluster i will be chosen arbitrarily such that
(r,i)
i 6= r. We refer to this as the repair group. The j’th server in the repair group transmits Y`,j,t , a function
(i)
(r,i)
of Xj,t to the newcomer. We limit the size of this message to satisfy H(Y`,j,t ) ≤ β. Upon receiving these
(r)
(r,i)
(r)
(r,i)
d messages the newcomer stores X`,t+1 a function of Y`,[1:d],t . Therefore, H(X`,t+1 |Y`,[1:d],t ) = 0. We refer
to this process as one round of failure and repair. Due to this requirement, we can assume without loss
(i)
(i)
of generality that α ≤ dβ. Note that if (i, j) 6= (`, r) then Xj,t+1 = Xj,t . In other words, apart from the
failed server, the remaining servers remain unchanged at time slot t. We will study two different repair
models, both of which have been widely studied in the literature.

4

repair

X

X

rep
air

air
rep

DC

Fig. 1. The FCRS with three complete clusters. Two nodes in the blue cluster fail which are repaired by the red and green clusters respectively.
A data collector (DC) is connected to k = k1 + k2 + k3 servers, one of which is newcomers.

•

Exact repair: Under the exact repair model the content of the newcomer must be identical to the
failed server. Therefore, we must have
(i)

(i)

Xj,t = Xj,t+1 ∀ t, i, j.
(i)

•

(i)

while studying this model we may omit the subscript t for simplicity and write Xj,t = Xj .
Functional repair: Under the functional repair model the newcomer may not be identical to the failed
server but it must satisfy the data recovery requirement.
That is, for any (E1 , . . . , Es+1 ) that satisfy
P
|E
Ei ⊆ [1 : d] for i ∈ [1 : s] and Es+1 ⊆ [1 : s0 ] and s+1
i | = k, we must have
i=1
(1)

(s)

H(M|XE1 ,t , . . . , XEs+1 ,t ) = 0, ∀ t ≥ 0.
The model described above is what we refer to as Fixed Cluster Repair System (FCRS). See Figure 1 for
an illustration of an FCRS with three complete clusters and no residual servers (s0 = 0). By contrast, a
general DSS (what we referred to as ACRS in the introduction) lacks many of these constraints. A DSS
with parameters (n, k) consists of n servers {X1 , . . . , Xn } such that any k servers can recover the file
M. A DSS is said to have availability s − 1 if for each server Xi there are s − 1 disjoint sets of servers
(i)
(i)
of respective sizes d1 , . . . , ds−1 that can serve as its repair group while generating repair bandwidths
(i) (i)
(i)
(i)
d1 β1 , . . . , ds−1 βs−1 , respectively. The repair process can be defined either as functional or exact repair.
The repair bandwidth is defined as
γ=

max
i∈[1:n],j∈[1:s−1]

(i) (i)

dj βj .

(1)

III. T HE F UNCTIONAL R EPAIR M ODEL
(i)
In this section, we present a network information flow analysis for the FCRS. Each server Xj,t is
(i)
(i)
modelled by a pair of nodes Xj,t,in and Xj,t,out that are connected with an edge. The source is directly
(i)
(i)
connected to the nodes Xj,0,in with edges of infinite capacity. The nodes Xj,0,in are in turn connected to
(i)
Xj,0,out with edges of capacity α. Suppose at the end of time slot t − 1 (where t ≥ 1) the j’th server
from the i’th cluster fails. Assume the newcomer replacing this server is repaired by connecting to the

5

(r)

(i)

r’th cluster. We represent this by d edges which connect X[1:d],t−1,out to Xj,t,in . Each of these edges has
(i)
(i)
a capacity of β. Furthermore, there will be an edge of capacity α from Xj,t,in to Xj,t,out . Since we have
only one failure per time slot, for all other (i0 , j 0 ) 6= (i, j) there will be edges of infinite capacity from
(i0 )
(i0 )
(i0 )
(i0 )
Xj 0 ,t−1,out to Xj 0 ,t,in and from Xj 0 ,t,in to Xj 0 ,t,out . At any given time a data collector can be connected
to the out nodes of any set of servers of size k with edges of infinite capacity. An illustration has been
provided in Figure 2 which involves three clusters.

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞
∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞
∞

∞
∞

∞
∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

(r)

(q)

(p)

Fig. 2. The network information flow model for the FCRS. At the end of t = 0, 1, 2 the servers Xj,0 , X`,1 and Xi,2 fail respectively.
These servers are repaired by connecting to clusters p, r and q, in that order. Finally a data collector connects to k servers at time slot t = 3
for recovering the file M. Note that some of these k servers are newcomers.

Our goal in this section is to find the minimum cut that separates any data collector from the source
in this graph under all possible failure and repair patterns. As we shall see this minimum cut helps us to
characterize the smallest possible value of α for any choice of γ = dβ, such that any data collector can
recover the file. Furthermore, the tradeoff (α, γ) characterized by this min-cut is achievable, for instance
if we resort to random linear codes [23].
Consider a sequence of failures and repairs as depicted in Figure 3. Note that only two clusters participate
in this sequence. First, k1 ≥ d k2 e servers from the first cluster fail. All of these servers are repaired by
connecting the second cluster. Next, k2 = k − k1 servers from the second cluster fail. These servers are
repaired by the first cluster. Assume a data collector connects to these k newcomers in order to recover
the file M. As we shall see soon, a simple cut-set argument shows that we must have
M ≤ k1 α + (d − k1 )(k − k1 )β.

Our first objective is to prove that for any choice of the parameters α and dβ, there exists a k1 ∈ [d k2 e : k]
such that this is the smallest cut which separates any data collector from the source. Let us assume that at
some arbitrary point in time, t0 , a data collector is connected to k servers which we call Z1,t0 , . . . , Zk,t0 .
For any i ∈ [1 : k] let ti ≤ t0 be the smallest integer such that an edge of infinite capacity exists from
Zi,t0 ,out to Zi,t0 +1,in for all t0 ∈ [ti : t0 ]. If no such ti exists, set ti = t0 . We say that there is a path from
Zi,ti to Zj,tj if there exists a t0 ∈ [ti : tj − 1] such that there is an edge of capacity β connecting Zi,t0 ,out
to Zj,t0 +1,in . We can order these k servers such that i < j implies ti ≤ tj . As a result, i < j implies there

6

is no path from Zj,tj to Zi,ti . Let us assume that such an ordering is in place. Define ei ∈ [1 : s + 1] as
the cluster to which Zi,t0 belongs and let
c(i, j) = |{` s.t. ` ≤ j and e` = i}| for j ∈ [1 : k]

(2)

be the number of servers in Z[1:j],t0 which belong to the i’th cluster. Let F (Z[1:k],t0 ) be the value of the
minimum cut that separates a data collector connecting to Z[1:k],t0 ,out from the source. In order to find
this cut, we must decide for any j ∈ [1 : k] whether to include both Zj,tj ,in and Zj,tj ,out on the sink (data
collector) side, or to include Zj,tj ,in on the source side and Zj,tj ,out on the sink side (if we include both
Zj,tj ,in and Zj,tj ,out on the source side, the value of the cut will be infinite). In the latter case the value
of the cut is increased by α, whereas in the former scenario, the value of the cut is increased by at least
(d − maxi∈[1:s+1]\{ej } c(i, j))β. This is because any newcomer must be repaired by a cluster differently
from his own. As a result, the value of this cut must satisfy
F (Z[1:k],t0 ) ≥

k
X
j=1

min{(d −

max

i∈[1:s+1]\{ej }

c(i, j))β, α}.

Let us represent this lower bound by
4

∗

F (e[1:k] ) =

k
X
j=1

min{(d −

max

i∈[1:s+1]\{ej }

c(i, j))β, α}.

(3)

Note that for fixed parameters α, d and β, the expression in (3) is uniquely determined by the sequence
e[1:k] , hence the change of the argument in F ∗ (·) from Z[1:k],t0 to merely e[1:k] . The first lemma tells us
that among all different sequences e[1:k] the value of F ∗ (e[1:k] ) is minimized when this sequence has a
very specific structure.
Lemma 1: For any sequence e[1:k] ∈ [1 : s + 1]k , there exists a sequence e0[1:k] ∈ [1 : 2]k such that
∗ 0
F (e[1:k] ) ≤ F ∗ (e[1:k] ).
Proof:
Let c(i, j) be as defined in (2) and
4
e0j =

(
1
2

if c(ej , j − 1) = maxi∈[1:s+1] c(i, j − 1)
Otherwise.

4

for j ∈ [2 : k] and e01 = 1. Define two variables as follows.
(
0
v2 (j) =
v2 (j − 1) + e0j − 1
4

if j = 0
if 0 < j ≤ k

(4)

and
4

v1 (j) = j − v2 (j).

(5)

(2)

For any finite discrete set D, let maxi∈D f (i) return the second largest value of f (·) over D (if the
(2)
maximizer of f (·) over D is not unique, then maxi∈D f (i) = maxi∈D f (i)). We proceed by proving the
(2)
following two claims: v1 (j) = maxi∈[1:s+1] c(i, j) and v2 (j) ≥ maxi∈[1:s+1] c(i, j). The first claim can be
proven by induction. Trivially, v1 (1) = 1 = maxi c(i, 1). Assume the hypothesis is true for j − 1. Then
v1 (j) = 1{e0j = 1}(v1 (j − 1) + 1) + 1{e0j = 2}v1 (j − 1)
= 1{c(ej , j − 1) = max c(i, j − 1)}(max c(i, j − 1) + 1)
i

i

+ 1{c(ej , j − 1) < max c(i, j − 1)} max c(i, j − 1)
i

= max c(i, j).
i

i

7

P
The second claim follows because v2 (j) = j − v1 (j) = j − maxi c(i, j) = i6=i∗ c(i, j) ≥ max(2) c(i, j)
where i∗ = arg maxi c(i, j).
As a result, we have maxi∈[1:s+1]\{ej } c(i, j) ≤ (e0j −1)v1 (j)+(2−e0j )v2 (j) for any j ∈ [1 : k]. Therefore,
F ∗ (e[1:k] ) ≥

k
X
j=1

min{(d − (e0j − 1)v1 (j) − (2 − e0j )v2 (j))β, α}.

Now consider a sequence of failures and repairs occurring at t = j ∈ [1 : k] such that if e0j = 1 a
server from the first cluster fails and is repaired by the second cluster, and if e0j = 2 then a server from
the second cluster fails and is repair by the first cluster. At each time-slot the parameters v1 (j) and v2 (j)
represent the number of failed servers from the first and the second cluster respectively. Therefore we can
write
k
X
F ∗ (e0[1:k] ) =
min{(d − (e0j − 1)v1 (j) − (2 − e0j )v2 (j))β, α},
(6)
j=1

thus, F

∗

(e0[1:k] )

∗

≤ F (e[1:k] ).

Suppose now that we are given an arbitrary sequence e0[1:k] such that e0i ∈ {1, 2}. The next question is
then how to sort the elements of e0[1:k] such that the expression in Equation (6) is minimized. It turns out
there is a simple and global answer to this equation. Assume without loss of generality that v1 (k) ≥ v2 (k).
The next lemma tells us that the the failures from each cluster must occur consecutively, without being
interrupted. Specifically, v1 (k) servers must fail from the first cluster, and only then, v2 (k) servers fail
from the second. Such a pattern always minimizes (6) regardless of the value of α and dβ.
Lemma 2: Let e0[1:k] ∈ [1 : 2]k be an arbitrary binary sequence of length k and let v1 (j) and v2 (j) be as
defined in equations (5) and (4). Assume without loss of generality that v1 (k) ≥ v2 (k). We have
F ∗ (e0[1:k] ) ≥ v1 (k)α + v2 (k) min{(d − v1 (k))β, α}.

(7)

e0[1:v1 (k)]

e0[1:k]

are all ones.
is sorted, i.e. if
This is achieved with equality if
Pk
Proof: Let us for simplicity define f (α) = j=1 min{(d − (e0j − 1)v1 (j) − (2 − e0j )v2 (j))β, α} and
g(α) = v1 (k)α + v2 (k) min{(d − v1 (k))β, α}. The proof follows from three simple observations.
• As long as α ≤ (d − v1 (k))β we have f (α) = g(α) = kα.
• The curve f (α) is concave within (d − v1 (k))β ≤ α ≤ dβ whereas the curve g(α) is linear within
the same interval.
• f (dβ) = g(dβ).
To see why the last claim holds, note that
k
X
f (dβ) =
(d − (e0j − 1)v1 (j) − (2 − e0j )v2 (j))β
j=1

k
X
= kdβ − β( (e0j − 1)v1 (j) + (2 − e0j )v2 (j)).
j=1

P
Since g(dβ) = kdβ − v1 (k)v2 (k)β, it is left to show that kj=1 (e0j − 1)v1 (j) + (2 − e0j )v2 (j) = v1 (k)v2 (k).
This can be proved by induction over k. For k = 1, the result trivially holds. Let us assume it is true for
k − 1. Then:
k
X
(e0j − 1)v1 (j) + (2 − e0j )v2 (j) = v1 (k − 1)v2 (k − 1) + (e0k − 1)v1 (k) + (2 − e0k )v2 (k)
j=1

= (v1 (k) + e0k − 2)(v2 (k) − e0k + 1) + (e0k − 1)v1 (k) + (2 − e0k )v2 (k)
= v1 (k)v2 (k).

8

Fig. 3. Network information flow graph corresponding to a sequence of failures and repairs where k1 ≥ d k2 e servers from the first cluster
fail, followed by k2 = k − k1 failures from the second cluster. Each failure in cluster 1 is repaired by cluster 2 and vice versa. A data
collector is connected to the k newcomers.

Remember that F ∗ (e0[1:k] ) is merely a lower bound on value of the min-cut separating any data collector
from the source. But it is easy to find a cut the value of which is given by Equation (7). The sequence
of failures and repairs leading to this cut is what is depicted in Figure 3: at the end of each time slot
(1)
t ∈ [0 : k1 − 1] the server Xt+1,t fails and is repaired by the second cluster. Next, at the end of each time
(2)
slot t ∈ [k1 : k − 1] the server Xt−k1 +1,t fails and is repaired by the first cluster. Then a data collector
(1)
(2)
(1)
connects to the k servers X[1:k1 ],k and X[1:k−k1 ],k . For every t ∈ [1 : k1 ] we include Xt,t,in on the source
(1)
side of the cut and Xt,t,out on the sink side. If (d − k1 )β > α, we do exactly the same thing for the servers
(2)
in {Xt−k1 ,t |t ∈ [k1 + 1 : k]}. Otherwise, if (d − k1 )β ≤ α then for all t ∈ [k1 + 1 : k] we include both
(2)
(2)
Xt−k1 ,t,in and Xt−k1 ,t,out on the sink side. Since v1 (k) = k1 and v2 (k) = k − k1 , the value of this cut is
precisely what is given by Equation (7).
We have therefore proved the claim which we made at the beginning of this section. The last question
to answer is what is the optimal choice of k1 for a specific value of α and dβ. With a slight abuse of
notation, let us denote by F ∗ (α, dβ) the value of the min-cut for the FCRS with a storage of size α and
a repair bandwidth of γ = dβ.
Lemma 3: Suppose we have an FCRS with parameters n, k, s and d = b ns c. The value of the min-cut
separating any data collector from the source is given by

kdβ − b k2 cd k2 eβ
if d ≤ αβ ,



k α + (d − k )(k − k )β
if d + k − 2k1 − 1 ≤ αβ < min{d + k − 2k1 + 1, d}
1
1
1
F ∗ (α, dβ) =
(8)
k

for
k
1 ∈ [d 2 e : k],



kα
if αβ < d − k − 1.
Proof: Let us define g(k1 ) = k1 α + (k − k1 ) min{(d − k1 )β, α}. We want to minimize g(k1 ) over k1 ∈
: k] for a specific choice of α and dβ. Without loss of generality we can assume (d−k−1)β ≤ α ≤ dβ.
If α > dβ then g(k1 ) is clearly minimized for k1 = d k2 e which matches with the first line of Equation (8).
On the other hand, if α < (d−k−1)β then g(k1 ) is minimized at k1 = k which yields the last line in (8). Let
us now minimize a simpler function h(k1 ) = k1 α + (d − k1 )(k − k1 )β. This is a second degree polynomial
in k1 and evidently its minimizer over k1 ∈ [d k2 e : k] is k1∗ = min{b 12 (d + k − α/β)e, k} where b·e returns
[d k2 e

9

the closest integer to its argument. Note that g(k1 ) = min{k1 α + (k − k1 )(d − k1 )β, k1 α + (k − k1 )α} =
min{h(k1 ), kα}, so the same k1∗ minimizes g(·) too. Finally, k1∗ = min{b 21 (d + k − α/β)e, k} implies
d + k − 2k1∗ − 1 ≤ αβ ≤ d + k − 2k1∗ + 1 which is the same as the second line in Equation (8).
For any FCRS with parameters n, k, s and file size M we must have M ≤ F ∗ (α, dβ) given by Equation
(8), otherwise there exists a sequence of failures and repairs after which a data collector (connecting to
the newcomers) is incapable of recovering the file. Furthermore, satisfying M ≤ F ∗ (α, dβ) is sufficient
for successfully repairing any sequence of failures, and for any data collector to recover the file, if we
resort to random linear codes [23]. The function F ∗ (α, dβ) can be inverted in order to find the minimum
value of α for a specific choice of dβ and M , in much the same way as illustrated in [1]. We will sketch
this - mostly replicated - proof for the sake of completeness. Let us summarize the result in the next
theorem.
Theorem 1: The tradeoff between α and γ = dβ in an FCRS with parameters n, k, s and d = b ns c can
be characterized as
(
M
if γ ∈ [f (0), ∞)
k
α∗ =
(9)
M − di (d−k+i)γ
if
γ
∈
[f
(i),
f
(i
−
1))
k−i
where
(
4

f (i) =

if 0 ≤ i < b k2 c
if i = b k2 c.

Md
(2k−i−1)i+k(d−k+1)
Md
kd−b k2 cd k2 e

Proof: The function M = F ∗ (α, dβ) can be inverted in terms of α.

M


 Mk −(d−k )(k−k )β if 0 ≤ M < k(d − k − 1)β
1
1
if (dk − k12 − k1 )β ≤ M < (dk − k12 + k1 )β for k1 ∈ [d k2 e + 1 : k]
α∗ = F −1 (m, dβ) =
k1
k
k


 M −(d−dk2 e)b 2 cβ
if (dk − d k2 e2 − d k2 e)β ≤ M ≤ (dk − b k2 cd k2 e)β
d2e

If we write the conditions in terms of dβ we find

M
dM

if dβ ≥ k(d−k−1)

 Mk −(d−k )(k−k )β
dM
1
1
if dβ ∈ [ dk−k
, dM2 ] for k1 ∈ [d k2 e + 1 : k)
2
α∗ =
k1
1 +k1 dk−k1 −k1

k
k

dM
 M −(d−dk2 e)b 2 cβ
if dβ ∈ [ dk−bdM
,
)
k
d e
cd k e dk−d k e2 −d k e
2

2

2

2

2

which is essentially the same as Equation (9). We intentionally substitute i = k − k1 to find an expression
similar to Equation (1) in [1].
Let us denote by (αM BR,c , γM BR,c ) the operating point at which the repair bandwidth of the FCRS is
minimized. At this point we have
k
Md
γM BR,c = f (b c) =
.
2
kd − b k2 cd k2 e
By plugging in this value in Equation (9) we find
αM BR,c =

Md
= γM BR,c .
kd − b k2 cd k2 e

Therefore,
(αM BR,c , γM BR,c ) = (

dM
dM
,
).
k
k
kd − b 2 cd 2 e kd − b k2 cd k2 e

(10)

10

0.17
FCRS
DSS model in [1]

0.16

Storage size

0.15
0.14
0.13
0.12
0.11
0.1

0.2

0.3

0.4

0.5

0.6

Repair bandwidth
Fig. 4. Comparison of the achievable region (α, γ) for FCRS and [1]. We have n = 100, k = 10 and both schemes are required to achieve
an availability of s − 1 = 9.

A. Comparison with [1]
As discussed in the introduction, random linear codes for FCRS can be viewed as an achievability
scheme for a more general problem, ACRS, where we are given a DSS and we are required to characterize
the region (α, γ) for any fixed availability, where α is the storage size and γ is the repair bandwidth
as defined in Equation (1). Interestingly, although the parameter availability has not been a motivation
behind the work in [1], their scheme serves as an achievability result for this general problem too, for
any availability s − 1 ∈ [1 : b n−1
c]. In particular, the random linear codes proposed in [1] can achieve an
k
availability of s − 1 if we set d = do = b n−1
c whereas the random linear codes for FCRS with s complete
s−1
and one incomplete clusters (n = ds + s0 ) achieve an availability of s − 1 with d = dc = b ns c. In this
section, we want to illustrate how FCRS can improve the tradeoff (α, γ) compared to [1] for the same
availability and for certain range of parameters. To begin with, we find this comparison most interesting
if neither system has any “residual servers”, namely if s − 1|n − 1 and s|n. For instance let us select
n = k 2 and s = k. For FCRS we will have k clusters each of size k and therefore dc = k. For [1]
we have do = n−1
= k + 1. By plugging in these values of d in Equations (9) and Equation (1) from
s−1
[1] respectively, we can find the smallest value of α for any repair bandwidth γ. This is precisely what
we have plotted in Figure 4 for a choice of n = 100 and k = 10 (both repair bandwidth and storage
size are normalized by M ). The figure suggests that at small values of repair bandwidth FCRS has a
superior performance, and that there is a threshold value of γ beyond which it is outperformed by [1].
The improvements offered by FCRS are most visible at the MBR point for which we are going to provide
4
oM
an analytical comparison. Let us define γM BR,o = 2kd2d
which is the value of the repair bandwidth at
2
o −k +k
MBR point in [1]. The two conditions s|n and s − 1|n − 1 imply that n = (`s − ` + 1)s for some positive
integer `. Under this constraint we have do = `s + 1 and dc = `s − ` + 1 and we can write
γM BR,c
=
γM BR,o

dc M
kdc −b k2 cd k2 e
2do M
2kdo −k2 +k

≤

dc M
2
kdc − k4

2do M
2kdo −k2 +k

=

`s + 1 − (k − 1)/2 `s − ` + 1
·
.
`s − ` + 1 − k/4
`s + 1

This ratio is upper-bounded by 1 for almost the entire range of parameters (except when s = 2 or k = 1
or when (s, k) ∈ {(3, 2), (3, 3), (4, 2)}) as can be easily verified. The ratio is smallest when s is maximal,

11

that is, s = b nk c. This implies k = `s − ` + 1, which results in
γM BR,c
2 `s + ` + 2
≤ ·
.
γM BR,o
3
`s + 1
This can be upper-bound by
γM BR,c
2 s+3
≤ ·
γM BR,o
3 s+1
which is achieved when ` = 1. This indicates an asymptotic multiplicative improvement of 2/3 over the
repair bandwidth at MBR point in comparison to [1].
It is worth noting that the assumption of “no residual server” becomes irrelevant as the parameters k and
s grow large and as long as we choose s = b nk c.
Proposition 1: Let s , k and s0 be three positive integers such that 0 ≤ s0 < min{k, s}. Let n = sk +s0 ,
c, and define
dc = b ns c = k and do = b n−1
s−1
γM BR,c
=
f (s, k, s0 ) =
γM BR,o
4

dc
kdc −b k2 cd k2 e
2do
2kdo −k2 +k

.

We have
f (s, k, s0 ) ≤
Proof:
dc
2
kdc − k4

2 (s + 3)k + s − 3
·
.
3
(s + 1)k − 1

2 2do − k + 1
dc
2do − k + 1
≤ ·
·
k
2do
3
do
dc − 4
2
(k − 1)(s − 1)
2
(k − 1)(s − 1)
2 (s + 3)k + s − 3
≤
(2 −
) ≤ (2 −
)= ·
.
3
sk + s0 − 1
3
(s + 1)k − 1
3
(s + 1)k − 1

f (s, k, s0 ) ≤

2do
2kdo −k2 +k

=

. If we further let s → ∞,
As a result of this proposition we see that limk→∞ f (s, k, s0 ) ≤ ( 23 + ) · s+3
s+1
2
the ratio of 3 will be established.
This result may appear puzzling at first. Suppose the file M consists of m independent symbols over a
sufficiently large field Fq so that M = m log(q). The random linear codes for FCRS require each server
α
to store log(q)
random linear combinations of the m symbols of the file. If this server ever takes part in
α
symbols to a newcomer.
a repair process, he transmits logβ q random linear combinations of these log(q)
dβ
α
symbols. But this
Eventually, the newcomer stores log(q) random linear combinations of the received log
q
is precisely the mechanism behind the random linear codes for [1] (or in essence, any other network
flow problem). How is it possible that one code outperforms the other? The truth is that the two codes
are different in that they choose different parameters α and dβ. By excluding the possibility of certain
repair patterns, we are able to achieve a larger min-cut on the network. Thereby, we can choose α and
dβ smaller (at MBR point) without eventually running into trouble. This “exclusion” may come at a price
depending on what the designer aims at optimizing. However, this cost is not reflected in the (s − 1, α, γ)
tradeoff for an ACRS at small repair bandwidth and large availability.

12

IV. T HE EXACT REPAIR MODEL : ACHIEVABILITY RESULTS FOR MBR POINT
In this section we introduce cubic code as a coding scheme designed to minimize the repair bandwidth
for the FCRS with s + 1 clusters where 2 ≤ s ≤ b nk c. Cubic Codes are examples of Affine Resolvable
Designs [17] which themselves are subclasses of Fractional Repetition codes [16]. They can also be
viewed as generalizations of grid codes discussed in [17]. As we shall prove in the next section via a
converse bound, cubic codes are information-theoretically optimal, in the sense that they minimize the
repair bandwidth of FCRS with 2 and 3 clusters and no residual server. On the other hand, they have a
strictly worse performance compared to random linear codes that can achieve the cutset bound analyzed
in Section III. This implies an inherent gap between the functional repair and exact repair models at the
MBR point for the FCRS with 2 and 3 complete clusters. This is by contrast to the DSS model studied in
[1] where the MBR point for functional and exact repair coincide. Despite this, we will show that cubic
codes still achieve an asymptotic multiplicative improvement of 0.79 on the repair bandwidth compared
to the MBR codes [2], [3] that guarantee the same availability.
Suppose as stated in Section II the network consists of n = ds + s0 servers divided into s clusters
of size d and one cluster of size s0 < s. In this section we further assume that s0 < d. If this is not
true, we can increase s to s0 such that n = ds0 + s00 where s00 < min{d, s0 } and s0 ≤ b nk c. Also note
that this condition is automatically satisfied if k 2 ≥ n. Assuming the file is large enough, we break it
into m independent chunks M = {M1 , . . . , Mm } so that H(Mi ) = M/m. The value of m will be
determined shortly. We start by constructing a (ds+1 , m) MDS code over these m symbols and indexing
the codewords by strings of s + 1 digits. Let Cb represent a codeword of the MDS code where b is a
string of s + 1 digits, b = bs+1 . . . b1 , and bi ∈ [1 : d].
Server j in Cluster i stores all the codewords of the form Cb where bi = j and the other indices vary.
That is,
(i)

Xj = {Cb |bi = j} for all (i, j) ∈ {[1 : s] × [1 : d]} ∪ {{s + 1} × [1 : s0 ]}.
This is akin to arranging the codewords of an MDS code in an s + 1-dimensional hyper-cube and

Fig. 5. Cubic Codes for the FCRS with 3 clusters and with n = 15, d = 5. The codewords of an MDS code (the small blocks) are arranged
in a three dimensional cube. The j’th node in the i’th cluster stores the codewords that form that j’th plane parallel to the i’th axis.

13

requiring the servers within the i’th cluster to store hyperplanes parallel to the i’th axis. See Figure 5 for
an illustration. One can also express this code in terms of its generator matrix. Let B be the generator matrix
of any (ds+1 , m) MDS code. For any integer ` let φs+1 (`) . . . φ1 (`) be the s+1-digit expansion of ` in base
d, where φs+1 (·) represents the most significant digit. For any (i, j) ∈ {[1 : s]×[1 : d]}∪{{s+1}×[1 : s0 ]}
let Q(i,j) be the ds by ds+1 matrix where



for e ∈ [1 : i − 1] and

φe (r) = φe (`)


1 if φ (r) = φ (`) for e ∈ [i + 1 : s + 1] and
e
e−1
(i,j)

Q`,r =


φi (r) = j − 1



0 otherwise.
Then we can write
(i)

Xj = Q(i,j) B[M1 , . . . , Mm ]T .
(r)

(r,i)

If a server X` fails and chooses cluster i for repair, then the j’th server in cluster i transmits Y`,j =
(r,i)
{Cb |bi = j, br = `} to the newcomer. Upon receiving all such codewords Y`,[1:d] , the newcomer is capable
of reconstructing the failed server. Furthermore, the newcomer receives a total of ds codewords which
shows that for cubic codes dβ = α.
Let us now analyze the performance of this code. Based on the data recovery requirement, we know
that every k servers in the network, regardless of their cluster must be able to recover
the file. Consider
Ps+1
a set of k servers chosen in such a way that ki servers belong to cluster i where i=1 ki = k. These
servers together provide a total of R codewords of the MDS code where
R =

s+1
X
i=1

+

s

d ki −

s+1 X
s+1
X
i=1 j=i+1

s+1 X
s+1 X
s+1
X
i=1 j=i+1 `=j+1

= d

s+1

ds−1 ki kj

ds−2 ki kj k` − . . .

s+1
Y
− (d − ki ).
i=1

Thus, in order for the file M to be recoverable from these k servers, we must have
ds+1 −

s+1
Y
(d − ki ) ≥ m.

(11)

i=1

Note that this inequality must be true for any choiceP
of the parameters ki . Let us therefore minimize the
left hand side of this inequality over the constraints s+1
i=1 ki = k, ki ≥ 0 and ks+1 ≤ s0 .
∗
k[1:s+1]
=

arg min
Ps+1
k[1:s+1] : i=1 ki =k and

ks+1 ≤s0

ds+1 −

s+1
Y
(d − ki ).
i=1

To solve this optimization problem, it is necessary to distinguish between two regimes.
k
• Regime 1: s0 ≥ b
c.
s+1
Define s1 = mod (k, s + 1). The solution to (12) can be expressed as
(
k
e if i ≤ s1
d s+1
ki∗ =
k
b s+1 c if s1 < i ≤ s + 1.

(12)

14

k
k
e)s1 (d − b s+1
c)(s+1−s1 ) . Since each
Returning to Inequality (11) we can write m = ds+1 − (d − d s+1
s
server stores d codewords, the storage size is

M ds
M ds
= s+1
.
k
k
m
d − (d − d s+1
e)s1 (d − b s+1
c)(s+1−s1 )

α=

We saw that for cubic codes γ = α. Therefore,
γ=
•

M ds
.
k
k
ds+1 − (d − d s+1
e)s1 (d − b s+1
c)(s+1−s1 )

k
c.
Regime 2: s0 < b s+1
This time define s1 = mod (k − s0 , s). The solution to (12) is

k−s0

d s e if i ≤ s1
0
ki∗ = b k−s
c if s1 < i ≤ s
s

s
if i = s + 1.
0

Again, plugging this into (11) we have
k − s0 s1
k − s0 s+1−s1
e) (d − b
c)
s
s
k − s0 s1
k − s0 s−s1
k − s0
c − s0 )(d − d
e) (d − b
c)
− (b
s
s
s
k − s0 s1
k − s0 s−s1
= ds+1 − (d − s0 )(d − d
e) (d − b
c)
.
s
s

m = ds+1 − (d − d

Consequently,
γ=α=

M ds
.
0
0
ds+1 − (d − s0 )(d − d k−s
e)s1 (d − b k−s
c)s−s1
s
s

Let us summarize this in the following thereom.
Theorem 2: Suppose we have an FCRS with parameters n, k, s where n = ds + s0 and s0 < min{d, s}.
The cubic codes achieve a repair bandwidth of

γcc (n, k, s) =




M ds
k
k
ds+1 −(d−d s+1
e)s1 (d−b s+1
c)(s+1−s1 )
s
M
d
 s+1
k−s
k−s
d
−(d−s0 )(d−d s 0 e)s2 (d−b s 0 c)s−s2

k
if s0 ≥ b s+1
c
k
if s0 < b s+1
c

(13)

where s1 = mod (k, s + 1) and s2 = mod (k − s0 , s).
An interesting regime is when there are no residual servers, that is when n = sd. In this case we have
γcc (sd, k, s) =

M/d
1 − (1 −

d ks e/d)s2 (1

− b ks c/d)s−s2

.

(14)

This can be further simplified if we assume s|k.
γcc (sd, `s, s) =

M/d
.
1 − (1 − d` )s

In fact, it follows from a simple argument that
γcc (sd, k, s) ≤

M/d
.
k s
1 − (1 − sd
)

(15)

15

To see why, note that
1 − dk/se
d
k
1 − sd

!s2

1 − bk/sc
d
k
1 − sd

!s−s2
≤1

which is true since the geometric mean of s numbers is upperbounded by their arithmatic mean.
It is not difficult to see that if we fix s and k, γcc (n, k, s) is monotonically decreasing in n. This
Q is because
adding one more server to the last cluster cannot increase the expression mink[1:s+1] ds+1 − s+1
i=1 (d − ki ).
Based on this property and Equation (15) we can establish the following bound.
Corollary 1: Let γcc (n, k, s) be the repair bandwidth of cubic codes for an FCRS with parameters n, k, s
where n = ds + s0 and s0 ≤ min{s, d}. Then
γcc (n, k, s) ≤

M/d
.
k
1 − (1 − (s+1)d
)s+1

This bound is sufficiently tight for our purpose and we will resort to it for our analytical comparison in
the next section.
A. Comparison with Functional Repair and [3]
Let us start with a numerical comparison. Here we fix the number of servers n and let the availability
grow gradually. For every fixed availability we compare the repair bandwidth for the three schemes: the
MBR point for functional repair of FCRS in Section III, that is expression (10), the MBR codes proposed
in [3] (which corresponds to the functional repair MBR point in [1]) and finally the cubic codes, that
is expression (13). For this numerical analysis we set n = 400, k = 20, and we let s − 1 grow from
1 to 19. We normalize the repair bandwidth by the size of the file. As can be seen in Figure 6, as s
grows large cubic codes perform somewhere in between the functional repair points of FCRS and [1].
The multiplicative improvement over [1] can be measured around 0.79 at its peak, i.e. when s − 1 = 19.
This will be theoretically justified next.

0.095

functional MBR point for FCRS
cubic codes
MBR point for [1]

0.09

0.085

Repair Bandwidth

0.08

0.075

0.07

0.065

0.06

0.055

0.05

0

2

4

6

8

10

12

14

16

18

20

Availability

Fig. 6. Comparison of cubic codes with the functional repair MBR point of FCRS and the MBR point of [1] for n = 400, k = 20.

16

Let us first bound the ratio of repair bandwidth for cubic codes and functional repair bandwidth for the
FCRS. Assuming k even we have
γcc
γM BR,c

≤

M/dc
k
1−(1− (s+1)d
)s+1
c

M
k2
k− 4d

=

c

≤

k(1 −

dc − dc (1 −

k
)
4dc
k
)s+1
(s+1)dc

k
k
1
3
(1 −
)
≤
.
−k/d
c
dc
4dc 1 − e
4(1 − e−1 )

In conjunction with the results of Section III-A, if we further assume that s is chosen as large as possible,
i.e. s = b nk c, we can write
γcc
γM BR,o

≤

3
2 (s + 3)k + s − 3
· ·
.
−1
4(1 − e ) 3
(s + 1)k − 1

cc
Since the expression for the ratio γMγBR,o
does not depend on whether k is odd or even, the same bound
holds for general k. We have therefore established the following proposition.
Proposition 2: Let s , k and s0 be three positive integers such that s0 < min{k, s}. Let n = sk + s0 ,
c, and define
dc = b ns c = k and do = b n−1
s−1

4

g(s, k, s0 ) =

γcc
γM BR,o

≤

1
k
1−(1− (s+1)d
)s+1
c

2do
2kdo −k2 +k

.

We have
g(s, k, s0 ) ≤

(s + 3)k + s − 3
1
·
.
−1
2(1 − e )
(s + 1)k − 1

Based on this proposition, if we let k → ∞, we find
γcc
2
s+3
s+3
3
· ( + ) ·
≈ 0.79 ·
.
≤
−1
γM BR,o
4(1 − e ) 3
s+1
s+1

This proves that for the same availability of s − 1 = b nk c − 1, cubic codes achieve an asymptotic (as
k, s, n → ∞) multiplicative improvement of 0.79 over the minimum repair bandwidth in comparison to
MBR point in [1].
V. CONVERSE BOUND FOR EXACT REPAIR
In this section we provide an exact repair converse bound for the FCRS. The main purpose of this
converse bound is to prove that the cubic codes introduced in Section IV minimize the repair bandwidth
for the FCRS with two or three complete clusters and no residual servers. Unfortunately a straightforward
generalization of the bound to more than three clusters is loose and is omitted for this reason. As we are
(i)
(j)
dealing with exact repair we can drop the time index from X and Y variables, since Xj,t = Xj,t0 for all
(i)
t and t0 . Therefore, we simply represent this by Xj . The same slight change of notation applies for the
helper variables Y .
Theorem 3: Cubic codes achieve the minimum repair bandwidth under exact repair for the FCRS with
2 or 3 complete clusters, i.e. when s ∈ {2, 3} and s0 = 0.
Proof: We will present the proof for s = 3. The proof for s = 2 is omitted to avoid redundancy.
Therefore, we have n = 3d. Assume ki servers from the i’th cluster take part in the data recovery.
Specifically, let τi ⊆ [1 : d] for i ∈ [1 : 3] represent the set P
of indices of the servers from i’th cluster
that are connected to a data collector, such that |τi | = ki and 3i=1 ki = k. By taking an average over all
possible such choices of τ1 , τ2 , τ3 we can write

17

1

M ≤

X


d


d


d

k1

k2

k3

1

=

τ1 ,τ2 ,τ3

τi ⊆[1:d], |τi |=ki

X


d


d


d

k1

k2

k3

H(Xτ(1)
, Xτ(2)
, Xτ(3)
)
1
2
3

τ1 ,τ2 ,τ3

k1

k2

k3



d
k2

τ1 ,τ2

(16)

τ1 ,τ2 ,τ3

1
d
k1

k2

τ1

Let us start by upper-bounding the first term.
X
(∗)
1
4
(1)
(2)
(3)



)
≤
,
X
Q3 =
|X
H(X
τ1
τ2
τ3
d
d
d
=

k1

1 X

).
H(Xτ(1)
1
d

+

k1

X
1


)
|Xτ(1)
H(Xτ(2)
1
2
d
d

)+
, Xτ(1)
|Xτ(2)
H(Xτ(3)
1
2
3

X


d
k3

τ1 ,τ2 ,τ3

X


d


d

k1

k2

k3

(#)

(3,2)



1

d

) ≤
, Xτ(1)
H(Yτ3 ,[1:d]\τ2 |Yτ(3,2)
1
3 ,τ2
(3)

d
k1

(3,2)

τ1 ,τ2 ,τ3

)
, Xτ(1)
H(Yτ3 ,[1:d] |Yτ(3,2)
1
3 ,τ2

X d − k2
1
(3,2)
 d
).
H(Yτ3 ,[1:d] |Xτ(1)
1
d
k
τ ,τ
3

1

3

(3,2)

(3,2)

(2)

Inequality (∗) follows from the fact that H(Xτ3 |Yτ3 ,[1:d] ) = 0 and H(Yτ3 ,τ2 |Xτ2 ) = 0. Inequality (#)
follows from (conditional) Han’s inequality. Let us continue by bounding the right hand side of this
inequality.
X d − k2
1
(3,2)


Q3 ≤
H(Yτ3 ,[1:d] |Xτ(1)
)
1
d
d
d
k1 k3 τ1 ,τ3
X d − k2
X d − k2
1
1
(3,2)
 d
=
H(Xτ(3)
H(Yτ3 ,[1:d] |Xτ(1)
, Xτ(3)
|Xτ(1)
)
)+ d d
1
3
3
1
d
d
d
k1 k3 τ1 ,τ3
k1 k3 τ1 ,τ3
X d − k2
X d − k2
1
1
(3,1)
(3,2)
(3,1)




≤
H(Y
|Y
H(Yτ3 ,[1:d] |Xτ(3)
)
+
)
τ
,τ
τ
,[1:d]
3
1
3
d
d
d
d
3
d
d
k
k
k
k
τ ,τ
τ ,τ
1

3

1

1

3

3

1

3

d − k2 X
1 (d − k2 )(d − k1 ) X
(3,1)


H(Y
)
+
k
(d
−
k
)β
−
≤
H(Xτ(3)
)
3
2
τ3 ,[1:d]
3
d
d
2
d
d
k3
k3
τ3
τ3
d − k2 X
(d − k2 )(d − k1 )

β + k3 (d − k2 )β −
H(Xτ(3)
≤ k3
).
3
d
d
d k3 τ3

(∗)

Inequality (∗) follows from the fact that H(Y |X) = H(Y ) − H(X) if X is a function of Y and from
applying Han’s inequality for a second time. We go back to Equation (16) and bound the second term.
X
X
1
1
4
(2,1)
(2)
(1)




H(X
|X
)
≤
H(Yτ2 ,[1:d] |Yτ(2,1)
)
Q2 =
τ
τ
2
1
2 ,τ1
d
d
d
d
k1

=

k1

≤

k2

k1

τ1 ,τ2

k2

τ1 ,τ2

X
1
(2,1)
 d
H(Yτ2 ,[1:d]\τ1 |Yτ(2,1)
)
2 ,τ1
d
k2

τ1 ,τ2

1 d − k1 X
(2,1)

H(Yτ2 ,[1:d] ) ≤ k2 (d − k1 )β.
d
d
k
τ
2

2

18

Therefore, we proved
M ≤ Q3 + Q2 +

1 X

H(Xτ(1)
)
1
d
k1

τ1

d − k2 X
(d − k2 )(d − k1 )

β + k3 (d − k2 )β −
H(Xτ(3)
)
3
d
d
d k3 τ3
1 X
+ k2 (d − k1 )β + d 
).
H(Xτ(1)
1

≤ k3

k1

τ1

Via an identical procedure we can more generally prove that if π : {1, 2, 3} → {1, 2, 3} is a bijection,
then
(d − kπ2 )(d − kπ1 )
d − kπ2 X

M ≤ kπ3
β + kπ3 (d − kπ2 )β −
H(Xτ(ππ33 ) )
d
d
d kπ
τ π3
3
X
1
+ kπ2 (d − kπ1 )β + d 
H(Xτ(ππ11 ) ).
k π1

τπ1

By averaging this inequality over all possible bijections π we find
M ≤ k3

(d − k3 )(d − k1 )
(d − k3 )(d − k1 )
(d − k2 )(d − k1 )
β + k2 β
+ k1 β
3d
3d
3d

1
((d − k1 )k2 + (d − k1 )k3 + (d − k2 )k1 + (d − k2 )k3 + (d − k3 )k1 + (d − k3 )k2 ) β
3
1
+
(k1 k2 + k1 k3 + k2 k3 )β
3
β
(d − k2 )(d − k1 )
(d − k3 )(d − k1 )
(d − k2 )(d − k3 )
=
(2dk + k3
+ k2
+ k1
− k1 k2 − k1 k3 − k2 k3 )
3
d
d
d
β
=
(2d2 k + 3k1 k2 k3 − 3d(k1 k2 + k1 k3 + k2 k3 ) + d2 k)
3d
β 3
(d − (d − k1 )(d − k2 )(d − k3 )),
=
d
P
where we have used the fact that α ≤ dβ (due to the repair requirement)
and
ki = k. Note that the
P
inequality above must hold for any choice of k1 , k2 , k3 that satisfy
ki = k. In particular we must be
able to choose ki = d k3 e for i ∈ [1 : s2 ] and ki = b k3 c for i ∈ [s2 + 1 : 3] where s2 = mod (k, 3). For
this choice of k[1:3] we have
+

γ = dβ ≥

M d2
M/d
=
.
k s2
k 3−s2
k
3
d − (d − d 3 e) (d − b 3 c)
1 − (1 − d 3 e/d)s2 (1 − b k3 c/d)3−s2

This is the same expression as the achievable repair bandwidth of cubic codes specified by Equation (14)
if we set s = 3.
R EFERENCES
[1] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” IEEE
Transactions on Information Theory, vol. 56, no. 9, pp. 4539–4551, 2010.
[2] K. Rashmi, N. B. Shah, P. V. Kumar, and K. Ramchandran, “Explicit construction of optimal exact regenerating codes for distributed
storage,” in 47th Annual Allerton Conference on Communication, Control, and Computing. IEEE, 2009, pp. 1243–1249.
[3] 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 Transactions on Information Theory, vol. 57, no. 8, pp. 5227–5239, 2011.
[4] N. B. Shah, K. Rashmi, P. V. Kumar, and K. Ramchandran, “Interference alignment in regenerating codes for distributed storage:
Necessity and code constructions,” IEEE Transactions on Information Theory, vol. 58, no. 4, pp. 2134–2158, 2012.

19

[5] V. R. Cadambe, S. A. Jafar, H. Maleki, K. Ramchandran, and C. Suh, “Asymptotic interference alignment for optimal repair of mds
codes in distributed storage,” IEEE Transactions on Information Theory, vol. 59, no. 5, pp. 2974–2987, 2013.
[6] B. Sasidharan, K. Senthoor, and P. V. Kumar, “An improved outer bound on the storage-repair-bandwidth tradeoff of exact-repair
regenerating codes,” arXiv preprint arXiv:1312.6079, 2013.
[7] N. Prakash and M. N. Krishnan, “The storage-repair-bandwidth trade-off of exact repair linear regenerating codes for the case d= k=
n- 1,” in IEEE International Symposium on Information Theory (ISIT). IEEE, 2015, pp. 859–863.
[8] C. Tian, “Rate region of the (4, 3, 3) exact-repair regenerating codes,” in IEEE International Symposium on Information Theory (ISIT).
IEEE, 2013, pp. 1426–1430.
[9] A. S. Rawat, D. S. Papailiopoulos, A. G. Dimakis, and S. Vishwanath, “Locality and availability in distributed storage,” IEEE
Transactions on Information Theory, vol. 62, no. 8, pp. 4481–4493, 2016.
[10] I. Tamo and A. Barg, “Bounds on locally recoverable codes with multiple recovering sets,” in IEEE International Symposium on
Information Theory (ISIT). IEEE, 2014, pp. 691–695.
[11] D. S. Papailiopoulos and A. G. Dimakis, “Locally repairable codes,” IEEE Transactions on Information Theory, vol. 60, no. 10, pp.
5843–5855, 2014.
[12] I. Tamo, D. S. Papailiopoulos, and A. G. Dimakis, “Optimal locally repairable codes and connections to matroid theory,” IEEE
Transactions on Information Theory, vol. 62, no. 12, pp. 6661–6671, 2016.
[13] L. Pamies-Juarez, H. D. Hollmann, and F. Oggier, “Locally repairable codes with multiple repair alternatives,” in IEEE International
Symposium on Information Theory (ISIT). IEEE, 2013, pp. 892–896.
[14] A. Wang, Z. Zhang, and M. Liu, “Achieving arbitrary locality and availability in binary codes,” in IEEE International Symposium on
Information Theory (ISIT). IEEE, 2015, pp. 1866–1870.
[15] P. Huang, E. Yaakobi, H. Uchikawa, and P. H. Siegel, “Linear locally repairable codes with availability,” in IEEE International
Symposium on Information Theory (ISIT). IEEE, 2015, pp. 1871–1875.
[16] S. El Rouayheb and K. Ramchandran, “Fractional repetition codes for repair in distributed storage systems,” in 48th Annual Allerton
Conference on Communication, Control, and Computing. IEEE, 2010, pp. 1510–1517.
[17] O. Olmez and A. Ramamoorthy, “Fractional repetition codes with flexible repair from combinatorial designs,” IEEE Transactions on
Information Theory, vol. 62, no. 4, pp. 1565–1591, 2016.
[18] N. Prakash, V. Abdrashitov, and M. Médard, “A generalization of regenerating codes for clustered storage systems,” in 54th Annual
Allerton Conference on Communication, Control, and Computing, 2018.
[19] ——, “The storage vs repair-bandwidth trade-off for clustered storage systems,” arXiv preprint arXiv:1701.04909, 2017.
[20] B. Gastón, J. Pujol, and M. Villanueva, “A realistic distributed storage system: the rack model,” arXiv preprint arXiv:1302.5657, 2013.
[21] J. Pernas, C. Yuen, B. Gastón, and J. Pujol, “Non-homogeneous two-rack model for distributed storage systems,” in Information Theory
Proceedings (ISIT), 2013 IEEE International Symposium on. IEEE, 2013, pp. 1237–1241.
[22] M. A. Tebbi, T. H. Chan, and C. W. Sung, “A code design framework for multi-rack distributed storage,” in IEEE Information Theory
Workshop (ITW). IEEE, 2014, pp. 55–59.
[23] T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong, “A random linear network coding approach to multicast,”
IEEE Transactions on Information Theory, vol. 52, no. 10, pp. 4413–4430, 2006.

