The Storage vs Repair Bandwidth Trade-off for
Multiple Failures in Clustered Storage Networks

Abstract—We study the trade-off between storage overhead
and inter-cluster repair bandwidth in clustered storage systems,
while recovering from multiple node failures within a cluster.
A cluster is a collection of m nodes, and there are n clusters.
For data collection, we download the entire content from any
k clusters. For repair of t ≥ 2 nodes within a cluster, we
take help from ` local nodes, as well as d helper clusters. We
characterize the optimal trade-off under functional repair, and
also under exact repair for the minimum storage and minimum
inter-cluster bandwidth (MBR) operating points. Our bounds
show the following interesting facts: 1) When t|(m−`) the tradeoff is the same as that under t = 1, and thus there is no advantage
in jointly repairing multiple nodes, 2) When t - (m − `), the
optimal file-size at the MBR point under exact repair can be
strictly less than that under functional repair. 3) Unlike the case
of t = 1, increasing the number of local helper nodes does not
necessarily increase the system capacity under functional repair.

Cluster (d+1)

Cluster 1

𝑡+ℓ

Node 1

1

𝛽
𝑚𝛼

Data
Collection

arXiv:1708.05474v1 [] 18 Aug 2017

Vitaly Abdrashitov, N. Prakash and Muriel Médard
Research Laboratory of Electronics, MIT, USA. Email: {vit, prakashn, medard}@mit.edu.

ℓ𝛼
t

𝑑𝛽

Node m

𝑡+ℓ+1

𝑘𝑚𝛼
𝛽
𝑚𝛼

𝑡+ℓ

𝑚

𝛽

Cluster k
Cluster d

Fig. 1. System model for clustered data storage, illustrating data collection
and repair from multiple failures. The model is suitable for storing coded data
across multiple data centers (clusters) as in cloud-of-cloud applications.

I. I NTRODUCTION
We study the storage-overhead vs repair-bandwidth trade-off
for multiple node failures under the setting of clustered storage
networks. Our model is motivated by applications to cloud
storage settings, where user data is spread across distinct datacenters, even possibly belonging to different service providers
(as in a cloud-of-cloud setting). Practical implementation
studies that show the benefits of Reed-Solomon codes for data
storage in cloud-of-cloud settings appear in [1]–[3]. In our
model, a cluster represents a data center. In such networks,
it is common to differentiate between intra- and inter-cluster
bandwidth costs; typically, intra-cluster bandwidth cost is
much less than inter-cluster bandwidth cost. To keep the
model simple, we ignore any hierarchical topology that may
be present within a data-center (cluster), and simply assume
equal cost connectivity between any two nodes inside a cluster.
We also assume direct connectivity between any two clusters
in the network.
In our model, a cluster is a collection of m physical nodes
(see Fig. 1), each of size α symbols from the finite field Fq ,
for some q. There are n clusters in total in the system. A file
of size B symbols is encoded into nmα symbols and stored
across the nm storage nodes. We follow a clustering approach
for both data collection and repairs. For data collection,
we demand that the entire content of an arbitrary set of k
clusters is sufficient to decode the original file. Thus, during
data collection, we assume a cluster to be either completely
This work is in part supported by the Air Force Office of Scientific Research
(AFOSR) under award No FA9550-14-1-043, and in part supported by the
National Science Foundation (NSF) under Grant No. CCF-1527270.

Special Case of Our Model
No clustering, single-node
repair: m = 1, t = 1, ` = 0
With clustering, single-node
repair: t = 1

Prior Work
Classical RC, [5]

Generalized RC, [6],
Studies impact of ` on
1) storage vs Inter-cluster BW trade-off
2) Intra-cluster BW
With clustering, multiple-node
Two Layer coding scheme [7]
repairs: t ≥ 1
Study limited to ` = m − t
TABLE I
S PECIAL C ASES OF S YSTEM M ODEL A PPEARING IN L ITERATURE .

available (if we connect to it) or completely unavailable (if
we do not connect to it). Such an assumption is realistic in a
multi-data-center cloud setting [4].
Nodes within a cluster represent failure domains; in this
work, we deal with the problem of recovery from t nodefailures that occur in one of the n clusters. While singlenode failure is the most common failure event, correlated
failures of nodes within a data center is an important issue
reported in practice [8] and this motivates our failure model.
The t newcomer nodes are added to the same cluster as
replacement to those failed. For restoring the content of the
t new nodes, we download local as well as external content.
External help is taken from any set of d other clusters, each
of which contributes β inter-cluster symbols. The β symbols
from any cluster is possibly a function of all the mα symbols
in the cluster. For completeness of the model, we assume the
presence of a compute unit in the cluster that can combine
these mα symbols to generate the β helper symbols. We
also download entire content from any set of ` ≤ m − t
surviving nodes in the failure cluster. Once again, we assume

Probability of Decoding

4
3
2
1
0

1

1.5

2

2.5

(a) Trade-off for an (n = 5, k = 4, d =
4)(m = 3, ` = 0, t = 2) system.

1.0
0.8
0.6
0.4
0.2
0.0

65
60

B = 10
B = 11

55
50

0

10

20
30
# of repairs

40

50

45

(b) RLNC simulation for an (n = 3, k =
2, d = 2)(α = 2, β = 2)(m = 3, ` = 0, t =
2) system.

0

2

4

6

8

10

12

(c) Impact of number of local helper nodes,
`, on file-size for an (n = 7, k = 4, d =
5, m = 17, t = 5) clustered storage system
at MBR point (α = 1, β = 1). Local help
does not provide any advantage unless ` > 2.

Fig. 2. Illustration of the implications of the exact and functional repair file-size bounds.

the presence of a compute unit in the failure cluster that
combines all the local and external helper data, and generates
the content of the replacement nodes. We assume that the
encoding function does not introduce any local dependence
among the nodes of a cluster; for e.g., the model excludes the
possibility of a local parity node within a cluster. An analysis
of the impact of such local parity nodes is left for future work.
We also restrict ourselves to the case d ≥ k, even though
analysis for the case 0 ≤ d ≤ k − 1 is perfectly feasible.
A code satisfying the above model requirements for repair and data collection shall be called multi-node repair
generalized regenerating code (MRGRC) C with parameters
{(n, k, d), (α, β), (m, `, t)}. In this paper, we study the tradeand inter-cluster
off between storage-overhead (S.O.) mnα
B
(IC) repair-bandwidth-overhead dβ
for
the
above
setting, under
tα
both functional and exact repair. Under exact repair, the
content of any of the t new nodes is exactly the same as
what was stored before failure, while in functional repair, the
restored content allows data-collection and further repairs.
Special cases of the model have been studied in the past (see
Table I). The setting of regenerating codes (RC) introduced in
[5] corresponds to the case with t = 1, m = 1, ` = 0 - we
refer to these as classical RCs. The case of single node failure
(t = 1) in clustered systems was previously studied in [6],
where the authors first identify the storage-vs-inter-cluster-BW
trade-off (ignoring intra-cluster BW), and then find bounds
on the minimum intra-cluster BW that is needed to achieve
this trade-off. The authors, show the surprising fact that while
increasing the number of local helper nodes ` improves the
storage-vs-inter-cluster-repair-BW trade-off; increasing ` not
only increases intra-cluster BW in the host-cluster (this is
obvious since one downloads `α symbols), but also increases
the intra-cluster BW in the d remote helper clusters. In other
words, in situations when intra-cluster BW cannot be entirely
ignored, the choice of the number of local nodes becomes an
important one.
Motivated by the above result of [6], for the case of multiple
failures that we consider here, even though we do not explore
bounds on intra-cluster BW in this paper, we still parametrize
the number of local helper nodes ` in the range 0 ≤ ` ≤ m−t,
so that our results remain relevant for a future study on intra-

cluster BW for t ≥ 1. The case of ` = m − t, t ≥ 1 has been
previously studied in [7]. However, as we show in this paper,
even when restricted to storage-vs-inter-cluster-BW trade-off
(ignoring intra-cluster BW), the case 0 ≤ ` < m − t, t > 1
offers several surprising results which cannot be inferred from
an analysis of the case ` = m − t, t > 1. Following is a
summary of our results in this paper:
A. Our Results
(a)File-Size bound under functional repair: Let (m − `) =
at+b, a ≥ 1, 0 ≤ b ≤ t−1. Then, the file-size under functional
repair of an MRGRC is upper bounded by B ≤ BF∗ , where
BF∗ = `kα+a

k−1
X

min(tα, (d−i)β)+

i=0

k−1
X

min(bα, (d−i)β). (1)

i=0

The bound is shown by considering the information-flow
graph (IFG) under functional-repair, and calculating the minimum cut. The bound is indeed tight, if there is a known
upper bound on the number of repairs in the system - the
achievability follows from results in network coding [9].
(b)File-Size bound under exact repair: For exact repair, we
prove a tighter bound, given by
B

≤

∗
BE
= `kα + (m − `)

k−1
X



(d − i)β
.
min α,
t
i=0

(2)

∗
We note that BE
≤ BF∗ . The bound is optimal at the
minimum storage-overhead (MSR) and the minimum intercluster repair-bandwidth-overhead (MBR) points characterized
by B = mkα and tα = dβ, respectively. We show how
optimal constructions for the case t > 1 can be directly
obtained from optimal constructions for the case t = 1 [6].

Implications of the Bounds: Case a) t|(m − `): In this case,
the bounds in (1) and (2) coincide. Further, (1) gives the same
S.O. vs IC-repair-bandwidth-overhead trade-off for any value
of t ≥ 1. i.e., under functional repair, there is no advantage to
jointly repairing multiple nodes (instead of repairing one ). For
exact repair, at the MSR and MBR points, there is no benefit
to jointly repairing multiple nodes for any t > 1, irrespective
of if t|(m − `) or not.

Case b) t - (m − `): In this case, it is possible that
∗
BF∗ > BE
. Specifically, at the MBR point with tα = dβ,
∗
we have BF∗ > BE
, whenever k > 1. This also means
that the S.O. vs IC-repair-bandwidth-overhead trade-off under
functional repair for the case t > 1 (with k > 1) is strictly
better than that for the case t = 1. A comparison of tradeoffs between exact and functional repair for the case of
{(n = 5, k = 4, d = 4)(m = 3, ` = 0, t = 2)} is shown
in Fig. 2a. In Fig. 2b, we present a simulation result that
shows probability of successful decoding while using random
linear network codes (RLNCs) [10] with sufficiently large field
size in an {(n = 3, k = 2, d = 2)(m = 3, ` = 0, t = 2)}
storage system operating at the MBR point with β = 2. In
this case, optimal file-sizes under exact and functional repair
∗
are BE
= 9 and BF∗ = 10. RLNCs enable functional repair,
and our simulation result indeed confirms the achievability of
file-size BF∗ = 10.
Another implication of the bounds relates to the usefulness
of the number of local helper nodes ` used in the repair
process. Under functional repair, for the case of t = 1 [6], if
we fix n, k, d, m, t, α, β, the optimal file-size increases strictly
monotonically with `, whenever α > (d − k + 1)β (i.e., if we
exclude the MSR point) . However, strict monotonicity is not
necessarily true when t > 1. Specifically, at the MBR point, it
can be shown that whenever (m mod t) ≤ b(d − k + 1)t/dc,
for any ` in the range 0 ≤ ` ≤ (m mod t), the capacity is as
good as with no local help at all (see Fig. 2c).

B. Other Related Work
The problem of multiple-node repair for classical RCs have
been studied under the frameworks of cooperative repair [11],
[12] and centralized repair [13], [14]. In cooperative repair,
each of the t replacement nodes first individually contacts respective sets of d helper nodes, and then communicates among
themselves before restoring the new content. In centralized
repair, a centralized compute node downloads data from some
subset of d nodes, and generates the data for all t replacement
nodes. Our repair model can be considered as a centralized
repair model for clustered storage systems.
Regenerating code variations for data-center-like topologies
consisting of racks and nodes are considered in [15]–[19]. All
these works focus on single-node repair, whereas we focus on
multiple-node repairs. Further, the models in [15], [16] and
[17] use clustering approach only for repair (by distinguishing
inter and intra rack repair costs), and not for data-collection.
File retrievability is demanded from any set of k nodes in the
whole system, irrespective of which clusters they belong to.
The difference in data collection model is the main difference
between our model and the models in [15], [16] and [17].
We next describe how exact repair codes for t > 1 can be
directly obtained from exact repair codes for t = 1. In Sections
III and IV we discuss the exact-repair and functional-repair
bounds, respectively. For functional repair, our IFG model is
substantially different, and more elaborate than the one used
in [7] for the case of ` = m − t. The complexity of our model
comes from the need to handle the case ` < m − t.

II. E XACT R EPAIR C ODES
Optimal constructions of exact repair MRGRCs for any
t > 1 can be directly obtained from constructions for the
case t = 1, whenever t|β. In order to construct an exact
repair MRGRC C with parameters (n, k, d)(α, β)(m, `, t), t|β,
we start with an exact repair code [6] C 0 with parameters
{(n, k, d)(α, β 0 = β/t)(m, `, t0 = 1)}. The code C 0 was shown
to exist at the MSR and MBR points; in fact it was shown
in [6] that an optimal (n, k, d)(α, β 0 )(m, `, t = 1) C 0 can be
constructed whenever a classical
k, d)(α, β 0 )
Pk−1 exact repair (n,
0
RC exists, with file-size i=0 min(α, (d − i)β ).
The code C 0 can be viewed as the code C as it is, if we
assume that repair of any group of t nodes in C happens one
node at a time via the repair procedure in C 0 . Also, we use
the same set of local and external helpers for the repair of any
of the t failed nodes. Inter-cluster bandwidth, for the repair of
the entire group, per external helper amounts to β = tβ 0 . The
file-size B that we obtain is given by
B = B 0 = `kα + (m − `)

k−1
X

min(α, (d − i)β 0 )

i=0
k−1
X



(d − i)β
. (3)
= `kα + (m − `)
min α,
t
i=0
III. F ILE S IZE BOUND , EXACT REPAIR
In this section, we present the proof of the file-size upper
bound in (2) for exact repair codes. We assume the code to be
deterministic; by this we mean that the helper data is uniquely
determined given the indices of the t failed nodes, local helper
nodes and helper clusters. We begin with useful notation. Let
F denote the random variable corresponding to the data file
that gets stored. We assume F to be uniformly distributed over
α
FB
q . Let Yi,j ∈ Fq , 1 ≤ i ≤ n, 1 ≤ j ≤ m denote the content
stored in node j of cluster i. For j ≤ j 0 , we write Yi,[j,j 0 ] to
denote {Yi,j , Yi,j+1 , . . . , Yi,j 0 }. We also write Yi to denote
Yi,[1,m] . Further, for i ≤ i0 , Y[i,i0 ] will denote {Yi , . . . , Yi0 }.
The property of data collection demands that
H (F|{Yi , i ∈ S})

=

0 ∀S ⊂ [n], |S| = k,

(4)

where H(.) denotes the entropy function computed with
respect to log q. Next, consider the repair of t nodes indexed by Ri in cluster i. Let H ⊂ [n]\{i}, |H| = d, and
L ⊂ [m]\Ri , |L| = ` respectively denote the indices of helper
clusters and local nodes that aid in the repair process. Let
ZiH,L
denote helper data passed by cluster i0 . The property
0 ,R
i
of exact repair is
 jointly characterized

by thefollowing set of
inequalities: H ZiH,L
=
0,
H
ZiH,L
≤ β, and
0 ,R |Yi0
0 ,R
i
i


0
0
H {Yi,j , j ∈ Ri }|{ZiH,L
= 0,
0 ,R , Yi,j 0 , i ∈ H, j ∈ L}
i
∀H ⊂ [n]\{i}, |H| = d, ∀L ⊂ [m]\Ri , |H| = `. (5)
Our proof technique of the file-size bound presented here,
though has some similarity with the information theoretic
techniques in works like [14], [20], it differs in an important
way. The proofs in these other works rely on the chain rule of
entropy, and so does our proof; however in here we demand

that the chain be expanded in a specific order. The following
lemma is used to determine this order. The lemma is valid only
when b > 0, where (m − `) = at + b, a ≥ 1, 0 ≤ b ≤ t − 1.
When b = 0, the bound-proof does not need this lemma.

𝑖𝑛
𝑋1,1
0

e 0 , Si , j 0 ) = Yi0 ,[1,`] ∪{Yi0 ,σ 0
Y(i
i ,S

i

(j) , j

∈ [`+1, j 0 −1]}. (7)

Proof. In here, we only present the candidate for the permutation σi0 ,Si . The proof that this satisfies the lemma can
be found in Appendix A. Consider the content, of the cluster i0 , given by {Yi0 ,1 , Yi0 ,2 , . . . , Yi0 ,m }. Define the quantities (jm , Vm ), (jm−1 , Vm−1 ), . . . , (jm−b+1 , Vm−b+1 ) in this
respective order as below:
Step 1. Let U = {Yi0 ,`+1 , Yi0 ,`+2 , . . . , Yi0 ,m }, and x = 0
Step 2. Define (jm−x , Vm−x ) as
(jm−x , Vm−x )

=

arg

min
(j,V) :
Yi0 ,j ∈U
V⊂U \{Yi0 ,j },|V|=t−1

where Θ = H Yi0 ,j |V, Y(Si ), Yi0 ,[1:`] .
Step 3. If x < b − 1, update U as U = U\{Yi0 ,jm−x }.
Increment x by 1 and return to Step 2.
Additionally, let us also define {j`+1 , j`+2 , . . . , jm−b } ,
{` + 1, . . . , m} \ {jm , jm−1 , . . . , jm−b+1 }. In the preceding definition, we only need equality as sets. We do not
care about any particular ordering of the elements in {` +
1, . . . , m} \ {jm , jm−1 , . . . , jm−b+1 }, while associating these
with {j`+1 , j`+2 , . . . , jm−b }. The candidate for the permutation σi0 ,Si on the set {`+1, . . . , m} is now defined as follows:
(8)

Proof of Exact Repair Upper Bound: We have
B

=

H(F) ≤ H(Y[1,k] ) =

k
X

H(Yi0 |Y[1,i0 −1] )

i0 =1
k
X

=
H(Yi0 ,[1,`] |Y[1,i0 −1] ) + H(Yi0 ,[`+1,m] |Yi0 ,[1,`] , Y[1,i0 −1] )
i0 =1

≤

`kα +

k
X

H(Yi0 ,[`+1,m] |Yi0 ,[1,`] , Y[1,i0 −1] ).

𝑖𝑛
𝑜𝑢𝑡
𝑋1,1
2 𝑋1,1
2

𝑋1𝑒𝑥𝑡 2

𝑖𝑛
𝑜𝑢𝑡
𝑋3,1
2 𝑋3,1
2

Cluster
𝑟𝑒𝑝

𝑋3

1

Edge Capacities

𝛼

𝛽

∞

Fig. 3. An illustration of the information flow graph used in cut-set based
upper bound for the file-size under functional repair. We assume (n = 3, k =
2, d = 2)(m = 3, ` = 0, t = 2). Only a subset of nodes are named so as
to avoid clutter. Two batches, each of t = 2 nodes, fail and get repaired first
in cluster 1 and then in cluster 3. We also indicate a possible choice of the
S − T cut that results in the desired upper bound. We fail nodes in cluster 3
instead of cluster 2 only to make the figure compact.

H(Yi0 ,[`+1,m] |Yi0 ,[1,`] , Y[1,i0 −1] ) in (9) using the order determined by the permutation σ, as follows:
H(Yi0 ,[`+1,m] |Yi0 ,[1,`] , Y[1,i0 −1] )
= H({Yi0 ,σ(j 0 ) , j 0 ∈ [` + 1, m]}|Yi0 ,[1,`] , Y[1,i0 −1] )
≤

a−1
X

H({Yi0 ,σ(`+ut+v) , v ∈ [1, t]}|Yi0 ,[1,`] , Y[1,i0 −1] )

u=0
m
X

e 0 , [1, i0 − 1], j 0 )), (10)
H(Yi0 ,σ(j 0 ) , |Y[1,i0 −1] , Y(i

j 0 =m−b+1



σi0 ,Si (p) = jp , ` + 1 ≤ p ≤ m.

2

S

+

Θ,

𝑟𝑒𝑝

𝑋1

T

Lemma III.1. Let (m − `) = at + b, a ≥ 1, 1 ≤ b ≤ t − 1.
Consider any Si ⊂ [n], |Si | = i, 1 ≤ i ≤ k − 1, and let
Y(Si ) = {Yi , i ∈ Si }. Then, for any i0 ∈ [n]\Si , there exists
a permutation σi0 ,Si of {` + 1, ` + 2, . . . , m} such that




e 0 , Si , j 0 ) ≤ min α, (d − i)β ,
H Yi0 ,σi0 ,S (j 0 ) |Y(Si ), Y(i
i
t
(6)
for all j 0 ∈ {m − b + 1, m − b + 2, . . . , m}, where

𝑜𝑢𝑡
𝑋1,1
0

(9)

i0 =1

Now, if we let σ = σi0 ,[1,i0 −1] to be the permutation
as obtained from Lemma III.1, then we expand the term

e 0 , [1, i0 − 1], j 0 ) is defined using (7). Using (5), each
where Y(i
term under the first summation in (10) is upper bounded by
min(tα, (d − i0 + 1)β), while each term under the second
summation in (10) is upper bounded using Lemma III.1. Thus,
we get that
H(Yi0 ,[`+1,m] |Yi0 ,[1,`] , Y[1,i0 −1] )


(d − i0 + 1)β
≤ a min(tα, (d − i + 1)β) + b min α,
t


0
(d − i + 1)β
= (m − `) min α,
.
(11)
t
0

The desired bound now follows by combining (9) with (11).
IV. G ENERAL F ILE S IZE BOUND , FUNCTIONAL REPAIR
In this section, we present the file-size upper bound under
functional repair via IFG analysis. Under functional repair,
ability to recover a file after a sequence of node failures
and repairs is equivalent to multicasting the source file to an
arbitrary number of data collectors over the IFG [5]. The IFG
characterizes the data flows from the source to a data collector,
and reflects the sequence of failures and repairs in the storage
network. The IFG used here (see Fig. 3) is a generalization of
the one presented in [6] for the case of t = 1.
A. Information Flow Graph Model
Let Xi denote the physical cluster i, and let Xi,j denote the
physical node j in cluster i, 1 ≤ i ≤ n, 1 ≤ j ≤ m. In the
in
out
IFG, Xi,j is mapped to the pair of nodes (Xi,j
, Xi,j
) such

in
out
that the edge Xi,j
→ Xi,j
has capacity α. The external node
ext
Xi of cluster i serves to transfer data outside the cluster.
The m out-nodes connect to Xiext via edges of capacity α.
When a cluster, say i, experiences a batch of t failures, the
whole cluster becomes inactive and is replaced with a new
active cluster. In the new cluster, a special repair node Xirep is
used to combine local and external helper data, and generate
the content of the replacement nodes. The out nodes of the
` local helper nodes connect to Xirep via links of capacity
α, and the external nodes of the d helper clusters connect
to Xirep via links of capacity β. Also, Xirep connects to the
in-nodes of the replacement nodes via links of capacity α.
Further, the m − t nodes, which did not experience failure
in the inactive cluster are copied as such in the new active
cluster. At any point in time, physical cluster i contains one
active and fi inactive clusters in the IFG where fi ≥ 0 denotes
the total number of batch failures and repairs in the cluster.
We write Xi (τ ), 0 ≤ τ ≤ fi to denote the cluster in the IFG
after the τ th (batch) repair associated with cluster i, and use
Ri (τ ), 0 ≤ τ ≤ fi − 1 to denote the indices of nodes that fail
in Xi (τ ). The clusters Xi (0), . . . , Xi (fi −1) are inactive, while
Xi (fi ) is active, after fi repairs. The nodes of Xi (τ ) will be
in
out
denoted by Xi,j
(τ ), Xi,j
(τ ), Xiext (τ ), Xirep (τ ) (there is no
repair node if τ = 0).
Finally, the source node S connects to all the mn inin
nodes Xi,j
(0), 1 ≤ i ≤ m, 1 ≤ j ≤ n via links of infinite
capacity. The data collector T connects to k external nodes,
say Xiext (fi ), 1 ≤ i ≤ k also via links of infinite capacity.

B. File-Size Upper Bound
We explain the proof of the bound in (1) by considering
the special case (n = 3, k = 2, d = 2)(α, β)(m = 3, ` =
0, t = 2). A full proof appears in Appendix B. Note that for
this special case, t - (m − `) and this will help us illustrate
the difference between functional and exact repair. Consider
the following sequence of 4 batches of failures and repairs
(see Fig. 3). Batches 1 and 2 are associated with cluster 1
with R1 (0) = {2, 3} and R1 (1) = {1, 2}. Batches 3 and
4 are associated with cluster 3 with R3 (0) = {2, 3} and
R3 (1) = {1, 2}. There is no local help in this example,
cluster 1 receives external help from X2ext (0) and X3ext (0)
for both batches of repairs, while cluster 3 receives external
help from X2ext (0) and X1ext (2) for its repairs. Consider
data collection by connecting to X1ext (2) and X3ext (2), and
consider the S-T cut whose edges are found as follows:
out
out
For disconnecting X1,1
(2) and X1,2
(2), we either remove
(based on whichever has smaller capacity) the two edges
in
out
in
out
X1,1
(2) → X1,1
(2) and X1,2
(2) → X1,2
(2) or the set of
rep
ext
helper edges X2 (0) → X1 (2) and X3ext (0) → X1rep (2).
out
For disconnecting X1,3
(2), we either remove the single
in
out
edge X1,3 (1) → X1,3 (1) or the set of two helper edges
X2ext (0) → X1rep (1) and X3ext (0) → X1rep (1). The set of
edges that disconnects cluster 3 is similarly found, except that
if we choose to disconnect links from external helpers, we
only disconnect those from X2ext (0) and not X1ext (2). The
value of the cut forms an upper bound for B, and is given
by B ≤ min(2α, dβ) + min(α, dβ) + min(2α, (d − 1)β) +
min(α, (d − 1)β), which is the same as the one give by (1).

Converse: We note that it can also be shown that any
valid IFG, regardless of the specific sequence of failures and
repairs, BF∗ (see (1)) is indeed a lower bound on the minimum
possible value of any S-T cut. Please see Appendix C for a
proof of this fact, which establishes the system capacity under
functional repair. Note that the RLNC simulation in Fig. 2b is
an experimental verification for the validity of this converse
statement.
R EFERENCES
[1] H. Abu-Libdeh, L. Princehouse, and H. Weatherspoon, “Racs: a case
for cloud storage diversity,” in Proceedings of the 1st ACM symposium
on Cloud computing. ACM, 2010, pp. 229–240.
[2] A. Bessani, M. Correia, B. Quaresma, F. André, and P. Sousa, “Depsky:
dependable and secure storage in a cloud-of-clouds,” ACM Transactions
on Storage (TOS), vol. 9, no. 4, p. 12, 2013.
[3] J. Y. Chung, C. Joe-Wong, S. Ha, J. W.-K. Hong, and M. Chiang,
“Cyrus: Towards client-defined cloud storage,” in Proceedings of the
Tenth European Conference on Computer Systems. ACM, 2015, p. 17.
[4] J. D. Cook, R. Primmer, and A. de Kwant, “Compare cost and performance of replication and erasure coding,” Hitachi Review, vol. 63, p.
304, 2014.
[5] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” Information
Theory, IEEE Transactions on, vol. 56, no. 9, pp. 4539–4551, 2010.
[6] N. Prakash, V. Abdrashitov, and M. Médard, “The Storage vs RepairBandwidth Trade-off for Clustered Storage Systems,” ArXiv e-prints,
vol. abs/1701.04909, Jan. 2017.
[7] M. Gerami, M. Xiao, and M. Skoglund, “Two-layer coding in distributed
storage systems with partial node failure/repair,” IEEE Communications
Letters, vol. PP, no. 99, 2017.
[8] D. Ford, F. Labelle, F. I. Popovici, M. Stokely, V.-A. Truong, L. Barroso,
C. Grimes, and S. Quinlan, “Availability in globally distributed storage
systems.” in OSDI, vol. 10, 2010, pp. 1–7.
[9] R. Koetter and M. Médard, “An algebraic approach to network coding,”
IEEE/ACM Transactions on Networking, vol. 11, no. 5, pp. 782–795,
Oct 2003.
[10] T. Ho, M. Mé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, Oct 2006.
[11] K. W. Shum and Y. Hu, “Cooperative regenerating codes,” IEEE
Transactions on Information Theory, vol. 59, no. 11, 2013.
[12] A.-M. Kermarrec, N. Le Scouarnec, and G. Straub, “Repairing multiple
failures with coordinated and adaptive regenerating codes,” in Network
Coding (NetCod), 2011 International Symposium on. IEEE, 2011.
[13] 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.
[14] A. S. Rawat, O. O. Koyluoglu, and S. Vishwanath, “Centralized repair
of multiple node failures with applications to communication efficient
secret sharing,” CoRR, vol. abs/1603.04822, 2016.
[15] Y. Hu, P. P.-C. Lee, and X. Zhang, “Double regenerating codes for
hierarchical data centers,” in Information Theory (ISIT), 2015 IEEE
International Symposium on. IEEE, 2016.
[16] J. Sohn, B. Choi, S. W. Yoon, and J. Moon, “Capacity of clustered
distributed storage,” CoRR, vol. abs/1610.04498, 2016.
[17] B. Gastón, J. Pujol, and M. Villanueva, “A realistic distributed storage
system: the rack model,” arXiv preprint arXiv:1302.5657, 2013.
[18] J. Pernas, C. Yuen, B. Gastón, and J. Pujol, “Non-homogeneous tworack model for distributed storage systems,” in Information Theory
Proceedings (ISIT), 2013 IEEE International Symposium on, July 2013.
[19] G. Calis and O. O. Koyluoglu, “Architecture-aware coding for distributed storage: Repairable block failure resilient codes,” CoRR, vol.
abs/1605.04989, 2016.
[20] N. B. Shah, K. V. Rashmi, P. V. Kumar, and K. Ramchandran, “Distributed storage codes with repair-by-transfer and nonachievability of
interior points on the storage-bandwidth tradeoff,” IEEE Transactions
on Information Theory, vol. 58, no. 3, pp. 1837–1852, March 2012.

A PPENDIX A
P ROOF OF L EMMA III.1

A PPENDIX B
P ROOF OF UPPER - BOUND 1

We will show that the permutation σi0 ,Si is such that




e 0 , Si , j 0 ) ≤ min α, (d − i)β ,
H Yi0 ,σi0 ,S (j 0 ) |Y(Si ), Y(i
i
t
(12)

We prove that under functional repair the file-size is upperbounded by

B≤

BF∗

= `kα + a

k
X

min(tα, (d − i + 1)β)

i=1

for all j 0 ∈ {m − b + 1, m − b + 2, . . . , m}, where
e 0 , Si , j 0 ) = Yi0 ,[1,`] ∪{Yi0 ,σ 0
Y(i
i ,S

(j) , j
i

∈ [`+1, j 0 −1]}. (13)

+

k
X

min(bα, (d − i + 1)β).

i=1

Let [A, B] = {integer x : A ≤ x ≤ B}, and [B] = [1, B].
To show the bound, it is enough to demonstrate a sequence
of batch failures and a set of k clusters used by a datacollector, such that there exists a cut between the source
and the data-collector with capacity no more than BF∗ . In
the example sequence, that we consider, the clusters 1 to k
are used for data-collection and experience node failures. At
each of these clusters a + 1 batch failures occur. They jointly
for all V ⊂ {Yi0 ,j`+1 , Yi0 ,j`+2 , . . . , Yi0 ,jm−x }\{Yi0 ,jp } such that cover the first m − ` nodes of a cluster. Specifically, at cluster
|V| = t − 1, and for all p, ` + 1 ≤ p ≤ m − x − 1. Towards i ∈ [k], the first batch failure affects the last t of these nodes:
proving (12), first of all, observe that
Ri (0) = {m − ` − t + 1, . . . , m − `}. The remaining batch


failures affect disjoint sets of t nodes starting from the first
e 0 , Si , j 0 )
H Yi0 ,σi0 ,S (j 0 ) |Y(Si ), Y(i
≤
node Xi,1 : Ri (1) = {1, . . . , t}, Ri (2) = {t + 1, . . . , 2t}, until
i


Ri (a) = {(a − 1)t, . . . , at}.
H Yi0 ,σi0 ,S (j 0 ) |Y(Si ), Vm−x , Yi0 ,[1:`] .(15)
In all cases, the last ` nodes in a cluster provide the local
i
helper
data. For repairs in cluster i, clusters 1, . . . , i − 1 and
This follows from (13) and because of the fact that Vm−x ⊂
n
−
(d
−
i), . . . , n serve as helper clusters. Failures first occur
{Yi0 ,j`+1 , Yi0 ,j`+2 , . . . , Yi0 ,jm−x−1 }. Without loss of generality,
in
cluster
1, then in clusters 2, 3, etc. until cluster k.
assume that Vm−x = {Yi0 ,j`+1 , Yi0 ,j`+2 , . . . , Yi0 ,j`+t−1 }. Next,
In
the
IFG,
corresponding to the described failure sequence,
from the exact repair condition given in (5), we know that
cluster
X
(a
+
1) is active for each i ∈ k. Let τj be the such
i


that
the
cluster
Xi (τj ) appears in the IFG right after the last
min(tα, (d − i)β) ≥ H Yi0 ,σi0 ,S (j 0 ) , Vm−x |Y(Si ), Yi0 ,[1:`]
i
repair of node Xi,j (we say “last repair" since nodes whose
`+t−1
X

indices belong to Ri (0) ∩ Ri (a) fail twice in our sequence of
H Yi0 ,jp |Yi0 ,j`+1 , . . . , Yi0 ,jp−1 , Y(Si ), Yi0 ,[1:`] +
=
failures; other nodes in cluster i fail only once). Consider a
p=`+1
cut-set (IF GS , IF GT ) consisting of the following edges:


α
in
out
H Yi0 ,σi0 ,S (j 0 ) |Vm−x , Y(Si ), Yi0 ,[1:`]
• Xi,j (a + 1) → Xi,j (a + 1), ∀i ∈ [k], j ∈ [m − ` + 1, m].
i
Total capacity of these edges is `kα.
`+t−1
X

• For all i ∈ [k]:
≥
H Yi0 ,jp |Vjp , Y(Si ), Yi0 ,[1:`] +
α
in
p=`+1
– Edge set Xirep (τj ) → Xi,j
(τj ), j ∈ [at], or edge


β
rep
ext
0
set Xi0 (0) → Xi (τj )∀i ∈ [n − (d − i), n], j ∈
H Yi0 ,σi0 ,S (j 0 ) |Vm−x , Y(Si ), Yi0 ,[1:`] ,
(16)
i
{t, 2t, . . . , at}, whichever set capacity is smaller. Towhere Vjp = Vm−x \{Yi0 ,jp } ∪ {Yi0 ,σi0 ,S (j 0 ) }. Noting that
tal capacity of these edges is a min(tα, (d−i+1)β).
i
α
in
|Vjp | = t − 1, we see that each term under the first summation
– If b > 0: edge set Xirep (τj ) → Xi,j
(τj ), j ∈ [at +
β
in (16) can be lower bounded using (14), i.e.,
ext
1, m − `], or edge set Xi0 (0) → Xirep (τj )∀i0 ∈

[n − (d − i), n], j = m − `, whichever set capacity is
H Yi0 ,jp |Vjp , Y(Si ), Yi0 ,[1:`]

smaller. Total capacity of these edges is min(bα, (d−
≥ H Yi0 ,jm−x |Vm−x , Y(Si ), Yi0 ,[1:`]
i + 1)β).


Pk
= H Yi0 ,σi0 ,S (j 0 ) |Vm−x , Y(Si ), Yi0 ,[1:`] (17)
.
The value of the cut is given by `kα + a i=1 min(tα, (d −
i
Pk
i + 1)β) + i=1 min(bα, (d − i + 1)β) = BF∗ .
Combining (17) with (16), it follows that


A PPENDIX C


(d − i)β
. M IN -C UT FOR IFG, O PTIMALITY OF BF∗ FOR GENERAL `
H Yi0 ,σi0 ,S (j 0 ) |Vm−x , Y(Si ), Yi0 ,[1:`] ≤ min α,
i
t
We now show that for any valid IFG, regardless of the
(18)
specific sequence of failures and repairs, BF∗ is indeed a
The proof of lemma now follows by combining (18) with (15). lower bound on the minimum possible value of any S-T cut.
Consider the variable j 0 appearing in (12), and let j 0 = m −
x for some x, 0 ≤ x ≤ b − 1 so that using (8) we have,
σi0 ,Si (j 0 ) = jm−x . Consider the definition of (jm−x , Vm−x )
in (8); we then know that

H Yi0 ,jm−x |Vm−x , Y(Si ), Yi0 ,[1:`]
≤

H Yi0 ,jp |V, Y(Si ), Yi0 ,[1:`] , (14)

Consider a cut of IFG, and let IFGS and IFGT be the two
disjoint parts associated with nodes S and T , respectively.
Without loss of generality, we only consider cuts such that
IFGT contains at least k external nodes corresponding to active
clusters. Consider a topological sorting of the IFG nodes such
that: 1) an edge exists between two nodes A and B only if A
appears before B in the sorting, and 2) all in-, out-, external,
and repair nodes (if τ > 0) of the cluster Xi (τ ) appear together
in the sorted order, ∀i, τ .
Consider the sequence E of all the external nodes in both
active and inactive clusters in IFGT in their sorted order. Let
Y1 denote the first node in E. Without loss of generality let
Y1 = X1ext (τ1 ), for some τ1 . In this case, consider the subsequence of E which is obtained after excluding all the external
nodes associated with X1 from E. Let Y2 denote the first
external node in this subsequence. We continue in this manner
until we find the first k external nodes {Y1 , Y2 , . . . , Yk } in
E, such that each of the k nodes corresponds to a distinct
physical cluster. Without loss of generality, let us also assume
that Yi = Xiext (τi ), 2 ≤ i ≤ k, for some τi . If τi = 0, then
clearly cluster i contributes (at least) mα to the cut. Thus let
us assume that τi > 0, 1 ≤ i ≤ k.
out
out
Consider the m out-nodes Xi,1
(τi ), . . . , Xi,m
(τi ) that conext
out
nect to Xi (τi ). For each j ∈ [1, m], either Xi,j
(τi ) is
in IFGS or there exists a minimal τi,j ∈ [0, τi ] such that
out
Xi,j
(τi,j ) ∈ IFGT . Consider those values of j ∈ [1, m] for
which all the following conditions hold:
out
in
Xi,j
(τi ), Xi,j
(τi,j ) ∈ IFGT , j ∈ Ri (τi,j − 1),

Xirep (τi,j ) ∈ IFGT .

(19)

Let there be mi ∈ [0, m] of such values, and, without loss of
generality, let them be m−mi +1, . . . , m. Also without loss of
generality, let indices j be sorted in the order of increasing τi,j ,
i.e. j1 < j2 implies τi,j1 ≤ τi,j2 . For each j ∈ [m−mi +1, m],
Σi,j , {j 0 : τi,j 0 = τi,j , j 0 ∈ [m − mi + 1, m]} is a contiguous
set of at most t indices of the nodes with the same τi,j , and
which are repaired together from the same repair node. Let
Si = {distinct (min Σi,j − 1), ∀j ∈ [m − mi + 1, m]} ⊆
[m − mi , m − 1] be the set of indices of the nodes preceding
all contiguous groups Σi,j . Note that by min Σi,j we mean
the minimum element contained in the set Σi,j . The set Si is
in one-to-one correspondence with the set of the repair nodes
in (19) for j ∈ [m − mi + 1, m]. Note that m − mi is always
an element of Si .
in
In order to relay helper data to Xi,j
(τi,j ) for all j ∈
[m−mi +1, m], the number of these repair nodes should be at
least dmi /te, and |Si | ≥ dmi /te. Each of these repair nodes
connects to d external nodes in other clusters. By construction
of E, at most i − 1 of those external nodes can be in IFGT .
Thus, each repair node contributes at least (d − i + 1)β
of external helper data to the cut value. In addition, each
repair node Xirep (τi,j ) connects to ` local nodes. By (19) and
by construction of Si and sorting of τi,j , only nodes with
indices {1, 2, . . . , j 0 } out of these ` can be in IFGT , where
j 0 = min Σi,j − 1 is the corresponding element of Si . Thus,
repair node Xirep (τi,j ) contributes at least (` − j 0 )+ α of local
helper data to the cut value.

The contribution to the cut value of those m − mi indices
of j ∈ [1, m − mi ], which do not satisfy (19), is at least α
each.
Based on the observations above, the overall cut value is
lower-bounded by
mincut(S − T )
k
X
X

 mi 
(` − j 0 )+ α . (20)
(d − i + 1)β +
≥
(m − mi )α +
t
0
i=1
j ∈Si

Consider a particular value of i ∈ [1, k] and the corresponding summation term in (20). Let us assume that m − mi ≥ `,
and mi = ai t + bi ≤ m − `, bi ∈ [0, t − 1]. Then the third term
in (20) is zero, and
(m − mi )α + dmi /te(d − i + 1)β
= mα − (ai t + bi )α + (ai + 1bi >0 )(d − i + 1)β
= mα − ai (tα − (d − i + 1)β) − bi α + 1bi >0 (d − i + 1)β
(1)

≥ `α + (m − `)α − a(tα − (d − i + 1)β)+
−(bα − (d − i + 1)β)+
= `α + a(tα − (tα − (d − i + 1)β)+ )
+(bα − (bα − (d − i + 1)β)+ )
= `α + a min(tα, (d − i + 1)β) + min(bα, (d − i + 1)β)
, Ci ,

where (1) follows, because ai t + bi = mi ≤ m − ` = at + b,
ai ≤ a, and, if ai = a, bi ≤ b.
On the other hand, if m − mi = ` − µi < `, and mi >
m − ` = at + b, ` − (m − mi ) = µi > 0, then we have
X
(m − mi )α + dmi /te(d − i + 1)β +
(` − j 0 )+ α
j 0 ∈Si

≥ (` − µi )α + (a + 1b>0 )(d − i + 1)β + (` − (m − mi ))α
X
+
(` − j 0 )+ α
j 0 ∈Si
j 0 >m−mi

= `α + (a + 1b>0 )(d − i + 1)β +

X

(` − j 0 )+ α

j 0 ∈Si
j 0 >m−mi

≥ Ci ,
where Ci is thePlower-bound for the case m − mi ≥ `.
Since BF∗ = i Ci , it is indeed a lower-bound on the filesize. This proves tightness of 1.

