1

The Storage vs Repair-Bandwidth Trade-off for
Clustered Storage Systems
N. Prakash, Vitaly Abdrashitov and Muriel Médard

arXiv:1701.04909v3 [] 2 Feb 2018

Abstract
We study a generalization of the setting of regenerating codes, motivated by applications to storage systems
consisting of clusters of storage nodes. There are n clusters in total, with m nodes per cluster. A data file is coded
and stored across the mn nodes, with each node storing α symbols. For availability of data, we require that the file
be retrievable by downloading the entire content from any subset of k clusters. Nodes represent entities that can
fail. We distinguish between intra-cluster and inter-cluster bandwidth (BW) costs during node repair. Node-repair in
a cluster is accomplished by downloading β symbols each from any set of d other clusters, dubbed remote helper
clusters, and also up to α symbols each from any set of ` surviving nodes, dubbed local helper nodes, in the host
cluster. We first identify the optimal trade-off between storage-overhead and inter-cluster repair-bandwidth under
functional repair, and also present optimal exact-repair code constructions for a class of parameters. The new tradeoff is strictly better than what is achievable via space-sharing existing coding solutions, whenever ` > 0. We then
obtain sharp lower bounds on the necessary intra-cluster repair BW to achieve optimal trade-off. Under functional
repair, random linear network codes (RLNCs) simultaneously optimize usage of both inter- and intra-cluster repair
BW; simulation results based on RLNCs suggest optimality of the bounds on intra-cluster repair-bandwidth. Our
bounds reveal the interesting fact that, while it is beneficial to increase the number of local helper nodes ` in order
to improve the storage-vs-inter-cluster-repair-BW trade-off, increasing ` not only increases intra-cluster BW in the
host-cluster, but also increases the intra-cluster BW in the remote helper clusters. We also analyze resilience of the
clustered storage system against passive eavesdropping by providing file-size bounds and optimal code constructions.

I. I NTRODUCTION
We consider the problem of designing efficient erasure codes for fault-tolerant data storage in a clustered network
of storage nodes. Nodes within a cluster are connected to each other via one network, while a second network
provides connectivity between clusters. In clustered networks, there is often a differentiation between intra- and
inter-cluster bandwidth costs, and this occurs because of factors like physical distance between the clusters or
some other differentiating characteristic in the communications within and between clusters. Typically, intra-cluster
bandwidth cost is much less than inter-cluster bandwidth cost. A user file is erasure coded and stored across the
nodes in the various clusters. From an availability perspective, it is of interest to encode and store a data file such
that access to a subset of clusters allows reconstruction of the entire uncoded file. We consider nodes as failure
domains, and require efficient repair of failed nodes in any cluster. Repair of a failed node in a cluster is performed
by downloading helper data from other clusters, and also a subset of surviving nodes in the host-cluster. We permit
the possibility that a cluster that aids in the repair of a failed node gathers and processes helper-data from its
various nodes, before sending it to the target-node, in order to decrease inter-cluster repair-bandwidth costs. A good
erasure-code solution allows a desirable trade-off between storage-overhead and the inter- and intra-cluster repair
BW costs for a given availability requirement.
The model described above is motivated by applications to cloud storage settings, where user data is spread
across distinct data-centers. For instance, the clusters could represent geographically separated data centers of a
cloud-service provider or a content-delivery network. All major cloud service providers like Amazon [1], Microsoft
Azure [2] and Akamai [3] provide options for geo-replicating user data in multiple data centers. Geo-replication
across data centers improves both availability and durability of user data. Data-center unavailability occurs owing to
N. Prakash, Vitaly Abdrashitov and Muriel Médard are with the Research Laboratory of Electronics, Massachusetts Institute of Technology,
USA (email: {prakashn, vit, medard}@mit.edu). A part of the results in the paper were presented as part of an invited talk at the 54th Annual
Allerton Conference on Communication, Control, and Computing, 2016, Allerton Park and Retreat Center, Monticello, IL, USA. 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.

2

network or power outages, software bugs and even security vulnerabilities. Note that in the event of unavailability,
data is never lost and thus does not necessitate data-center wide rebuild. While the three systems mentioned above do
not mention erasure coding across data centers, other practical systems indeed consider this possibility. For example,
Facebook’s F4 blob storage system [4] considers storing the xored content of two data centers in a third data-center.
Similarly, the authors of the Hitachi white-paper [5] suggest using Reed-Solomon like codes across data centers for
private clouds consisting of a small number of data-centers. Microsoft Giza [6], a geo-distributed storage system
considers erasure coding data across as many as 11 data centers spread over 3 continents. Giza employs MDS codes
like Reed-Solomon codes across data centers to handle availability requirement during data collection; i.e., a user
connects to the nearest k available data centers (assuming an [n, k] MDS code is used) during data collection to
download the data. The paper notes that (we quote) “cross-DC erasure coding only becomes economically attractive
if 1) there are workloads that consume very large storage capacity while incurring very little cross-DC traffic; 2)
there are enough cross-DC network bandwidth at very low cost”. The paper provides justification for both these
aspects; we refer to [6] for details.
Our model is perhaps even more applicable to the setting of “cloud of clouds”, where user data is spread across
data centers corresponding to multiple cloud service providers. Implementation studies that show the advantages of
using Reed-Solomon-like erasure codes to store data in user-defined cloud-of-clouds appear in [7, 8, 9, 10]. Several
reasons motivate a cloud-of-cloud setting, instead of a single cloud setting. The first is the need for high availability
in a local geographic zone [8] - individual cloud service providers might be limited in their number of geographic
zone specific data centers. Another motivation for a cloud-of-cloud setting is the flexibility to avoid vendor lockin [7, 8]. With an ever increasing number of new cloud providers offering competitive pricing and features, it might
be of interest to migrate from an existing cloud provider to a new one. However, individual cloud providers charge
the users differently for in-network (intra-cluster in our model) and out-of-network (inter-cluster) data movement.
In this scenario, to decrease the cost of migration, it is beneficial to spread data across several providers, so that
the user only needs to migrate data in the less competitive providers to the new provider. Finally, a reason for
providing user-defined cloud-of-clouds is that of privacy concerns [9, 10, 11], where security compromise of any
one cloud provider does not compromise user data.
In this work, we model an entire data-center as a cluster. We restrict ourselves to the storage of a single user
file; the solution provided here can be applied independently to any of the user files. For storage of a single coded
file, we assume an equal number of storage nodes in any of the clusters. While performing data collection, we
assume a cluster to be either completely available or completely unavailable. Such an assumption is sensible in a
multi-data-center cloud setting [5]. In our model, we restrict ourselves to recovery from single node failure. If there
are multiple node failures in the system, it is assumed that the recovery process happens sequentially, one node at
a time. While catastrophic failure of an entire data-center is rare, correlated failures of nodes in a data center are
an important issue reported in practice [12]. In this scenario, in our model, we parametrize the number of nodes,
named local helper nodes, in the host-cluster that can aid in the repair of a node in the host-cluster. Further, to
keep the model simple, we ignore any hierarchical topologies that may be present inside 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.
A straightforward solution that guarantees availability of data, and minimizes inter-cluster repair-bandwidth costs
is simply to use a product code consisting of two Maximum Distance Separable (MDS) codes - one across the
clusters, and another within a cluster. While the solution entirely eliminates any inter-cluster bandwidth cost, it
suffers from poor storage-overhead owing to the need to have redundancy in every cluster. At the other extreme, it
is also possible to achieve highly optimized storage cost, at the expense of inter-cluster repair-bandwidth, by using
minimum storage regenerating (MSR) codes [13] across the clusters. For instance, if we assume there are n clusters
in total, then (n, k) MSR codes across the clusters ensure that data is retrievable by accessing (entire) content of
any k clusters. However, the solution suffers from high inter-cluster repair-bandwidth cost. Our goal in this work,
at a high level, is to explore alternate solutions which can smoothly trade-off storage-overhead against inter-cluster
repair-bandwidth for given availability requirements. We show that it is indeed possible to achieve (see Fig. 6)
operating points which are strictly better than those obtained by space-sharing between product MDS codes and
MSR codes. We also characterize the amount of intra-cluster repair-bandwidth needed for achieving the optimal
trade-off between storage-overhead and inter-cluster repair bandwidth.
For the rest of the introduction, we first provide an abstract description of the system model used in this work.

3

Cluster 1

Data Collection

Cluster n
Node 1

Cluster 1
Expensive links
Node m

Cluster

Cheap links

Cluster k

(a) Data Collection

(b) Node Repair

Fig. 1. System model for data collection and Node repair in a clustered storage network. Data Collection is accomplished by downloading
entire contents of any k clusters. Repair of a failed node in a cluster is accomplished by contacting (i) any ` surviving nodes in the
host-cluster, and downloading all their content, and (ii) any d other clusters, and downloading β symbols from each of them.

This is followed by a discussion of other related system models in the literature, a summary of our results, and
also an example of the proposed erasure-coding solution.
A. System Model
We propose a natural generalization of the setting of regenerating codes (RC) [13] for clustered storage networks.
The network consists of n clusters, with m nodes in each cluster. The network is fully connected such that any
two nodes within a cluster are connected via an intra-cluster link, and any two clusters are connected via an intercluster link. A node in one cluster that needs to communicate with another node in a second cluster does so via
the corresponding inter-cluster link. A data file of size B symbols is encoded into nmα symbols, and stored across
the nm nodes such that each node stores α symbols. The symbols are assumed to come from a finite field Fq of
q elements. For data collection we have an availability constraint such that the entire content of any k clusters be
sufficient to recover the original data file (Fig. 1). As mentioned before, nodes represent failure domains, and we
restrict ourselves to the case of efficient recovery from single node failure. Node repair is parametrized by three
parameters d, β and `. We assume that the replacement of a failed node is in the same cluster as the failed node.
The replacement node downloads β symbols each from any set of d other clusters, dubbed remote helper clusters.
The β symbols from any of the remote helper clusters are possibly a function of the mα symbols present in the
cluster - we assume that any one of the nodes in the cluster takes responsibility for computing these β symbols
before passing them outside the cluster1 . Further, we also permit the replaced node to download (entire) content
from any set of ` other nodes, dubbed local helper nodes, in the host cluster, during the repair process. The quantity
dβ represents the inter-cluster repair-bandwidth. We refer to the overall code as the generalized regenerating code
(GRC) Cm with parameters {(n, k, d)(α, β)(m, `)}.
The model reduces to the setup of RCs in [13], when m = 1 (in which case, ` = 0 automatically). We shall refer
to the setup in [13] as the classical setup or classical regenerating codes. Our generalization has two additional
parameters ` and m when compared with the classical setup. As in the classical setup we consider both the notions
of functional and exact repair. Under exact repair, the content of the repaired node is identical to that of the failed
node; while in functional repair, the repair content permits data collection and repair of additional failed nodes. The
first goal of the paper is to obtain a trade-off between storage-overhead nmα/B and inter-cluster repair-bandwidth
1
One could also assume the presence of a dedicated compute unit to compute the helper data. Such an assumption allows us to enforce
a symmetric demand on the usage of intra-cluster bandwidth for all the nodes in the remote helper cluster. We will rely on the presence of
such dedicated compute units in the information flow graphs (see Section III) used to derive file-size upper bounds.

4

TABLE I
N OTATION USED IN OUR S YSTEM M ODEL . T HE LAST THREE PARAMETERS RELATE TO INTRA - CLUSTER REPAIR - BANDWIDTH
Symbol
n
m
k
d
`
q
α
β
γ
`0
γ0

Definition
total number of clusters in the system
number of storage nodes in each cluster
number of clusters required for data collection
number of remote helper clusters providing helper data during node repair
number of local helper nodes providing helper data during node repair
finite field size for data symbols
number of symbols each storage node holds for one coded file
size of helper data downloaded from each remote helper cluster during node repair, in symbols
size of helper data downloaded from each local helper during node repair, in symbols
number of nodes in a remote helper cluster that contribute toward computing the β helper symbols of the cluster
size of the data provided by each of `0 nodes at remote helper cluster to compute the cluster helper data, in symbols

dβ for an {(n, k, d)(α, β)(m, `)} GRC. We further note that, unlike the classical setup, the generalized setup
permits d < k . In our model, whenever d > 0, we assume that the encoding function does not introduce any local
dependence among the content of the various nodes of a cluster2 ; for example, the model excludes the possibility
of a local parity node within a cluster, which would hold the component-wise sum in Fαq of the other nodes’ data.
As we shall show, the case d = 0 is a special one where local dependence is necessary.
The model described above does not consider intra-cluster bandwidth incurred during repair. Intra-cluster bandwidth is needed, firstly, to compute the β symbols in any remote helper cluster, and, secondly, to download content
from ` local helper nodes in the host cluster. In order to characterize the amount of intra-cluster bandwidth that is
needed to establish optimal trade-off between storage-overhead and inter-cluster repair-bandwidth, we consider the
repair model shown in Fig. 1(b). In this model, the replacement node downloads at most γ, γ ≤ α symbols from
each of the ` local helper nodes from the host-cluster. With regard to a remote helper cluster, we assume that the β
symbols contributed by it are only a function of at most `0 , `0 ≤ m nodes of the cluster. We make the assumption
that any set of `0 nodes can be used to compute the β symbols. Further, we limit the amount of data that each of
these `0 nodes can contribute to at most γ 0 , γ 0 ≤ α symbols. A second goal of this paper is to identify necessary
requirements on the parameters γ, `0 , γ 0 that are needed to guarantee optimal trade-off between storage-overhead
and inter-cluster repair-bandwidth.
A summary of the various parameters used in the description of the system model appears in Table I.

B. Related Work
Regenerating codes were originally introduced in [13] for simultaneously optimizing storage overhead and repair
bandwidth for flat storage systems. By a flat storage system, it is meant that every node in the storage system is
connected to every other storage node via some logical link, where all logical links incur the same bandwidth cost
for communication per bit. Further, the data collector also connects to any of the storage nodes via links of similar
cost. There has since then been significant progress in the area of classical RCs in terms of code constructions,
finding optimal trade-offs under exact repair, and practical implementation. Below, we review variations of RCs
that have been proposed for non-flat topologies, and see how our model relates to these existing variations. We
shall also comment on how the model of locally repairable codes [14] relates to our model.
1) Regenerating Code Variations for Clustered Topologies: Regenerating code variations for data-center like
topologies consisting of racks and nodes are considered in [15, 16, 17, 18, 19, 20]. In [15], [17] and [18], the
authors distinguish between inter-rack (inter-cluster) and intra-rack (intra-cluster) bandwidth costs. Further, the
works [15] and [17] permit pooling of intra-rack helper data to decrease inter-rack bandwidth. Also, all three works
allow taking help from host-rack nodes during repair. Unlike our model, for data collection all three works simply
require file retrievability from any set of k nodes irrespective of the racks (clusters) to which they belong. In other
words, the notion of clustering applies only to repair, and not data collection, and this is a major difference with
2

b i , where m
b is the message vector of length B,
Under linear encoding, the coded content of cluster i, 1 ≤ i ≤ n can be written as mG
and Gi is a B × mα matrix. In this case, when we say that the encoding not introduce local dependence, we mean that the matrix Gi has
full column-rank

5

respect to our model. Thus while these variations are suitable for modeling the node-rack topologies present within
a data center, they do not model situation of erasure coding across data centers with the availability requirement as
considered in this work. The work [16] applies the theoretical results of [15] for the practical setting of Hadoop file
system. The work in [19] is a variation of that in [18] for a two-rack model, where the per-node storage capacity of
the two racks differ. In [20], the authors consider a two-layer storage setting like ours, consisting of several blocks
(analogous to clusters as considered in this work) of storage nodes. A different clustering approach is followed
for both data collection and node repair. For data collection, one accesses kc nodes each from any of bc blocks.
Though [20] focuses on node repair, the model assumes possible unavailability of the whole block where the failed
node resides, and as such uses only nodes from other blocks for repair. Further, unlike our model in this work,
the authors do not differentiate between inter-block and intra-block bandwidth costs. The framework of twin-codes
introduced in [21] is also related to our model and implicitly contains the notion of clustering. In [21] nodes are
divided into two sets. For data collection, one connects to any k nodes in the same set. Recovery of a failed node
in one set is accomplished by connecting to d nodes in the other set. However, there is no distinction between
intra-set and inter-set bandwidth costs, and this becomes the main difference with our model.
2) Regenerating Code Variations for Heterogeneous Systems: Several works [22, 23, 24, 25, 26, 27] study
variations of RCs in varied settings, with different combinations of node capacities, link costs, and amount of
data-download-per-node. The main difference between our model and these works is that none of them explicitly
considers clustering of nodes while performing data collection. In [22], the authors introduce flexible regenerating
codes for a flat topology of storage nodes, where uniformity of download is enforced neither during data collection,
nor during node-repair. References [23], [24] consider systems where the storage and repair-download costs are
non-uniform across the various nodes. The authors of [23], as in [22], allow a replacement node to download an
arbitrary amount of data from each helper node. In [25], nodes are divided into two sets, based on the cost incurred
while these nodes aid during repair. As noted in [19], the repair model of [25] is different from a clustered network,
where the repair cost incurred by a specific helper node depends on which cluster the replacement node belongs
to. The works of [26] and [27] focus on minimizing regeneration time rather regeneration bandwidth in systems
with non-uniform point-to-point link capacities. Essentially, each helper node is expected to find the optimal path,
perhaps via other intermediate nodes, to the replacement node such that the various link capacities are used in a
way to transfer all the helper data needed for repair in the shortest possible time. It is interesting to note both of
these works permit pooling of data at an intermediate node, which gathers and processes any relayed data with its
own helper data. Recall that our model (and the one in [15]) also considers pooling of data within a remote helper
cluster, before passing on to the target cluster.
3) Locally Repairable Codes: Locally repairable codes (LRCs), introduced in [14], are motivated by the need
to carry out efficient node repair in hierarchical storage systems, such as data centers. The subject of LRCs, like
regenerating codes, has attained significant attention both in theory and practice, since its introduction. Recovery of
a node failure within a cluster is first attempted locally, in order to minimize cross-cluster bandwidth; if too many
nodes in the cluster are unavailable, global parity nodes, spread across various clusters, aid in recovery. However,
LRCs do not model clustering of nodes while carrying out data collection, and this is once again a major difference
with our model. To draw further similarities with LRCs, we note that in our model, during the repair of a node,
the helper data from the ` nodes from the same cluster can be considered as local-helper data. However if d > 0,
unlike in LRCs, local-helper data alone is not sufficient for single-node-repair, since in this work we assume the
encoding function of the generalized regenerating code to introduce no dependency among the content of the m
nodes in any cluster. For d > 0, lack of dependencies within each cluster reduces storage overhead when compared
to LRCs; at the same time, local-helper data allows us to achieve a trade-off between storage-overhead and the
inter-cluster-repair-bandwidth better than that of a system with m stacked classical RCs, in which the set of i-th
nodes in all clusters stores the data encoded with i-th RC. The case d = 0 corresponds to one having no remote
helper clusters, so that the repair is carried out entirely locally. The difference in this case of d = 0 with model of
LRCs is notion of clustering of nodes, while performing data collection.
A tabular summary of related works appears in Table II.

6

TABLE II
S UMMARY OF RELATED WORKS ,
Reference

AND KEY DIFFERENCES FROM GENERALIZED REGENERATING CODES

(GRC)

Focus
RCs in clustered topologies

Hu et al. [15], Sohn
et al. [17], Gastón et al.
[18]

Rack-based topology with cluster-based repair, allow use of cheaper local-rack helper data. [15] and [17]
permit pooling of intra-rack helper data to decrease inter-rack bandwidth. Unlike GRC, the works assume
node-based data collection with no notion of clustering for data collection

Pernas et al. [19]

Similar to Gastón et al. [18] with 2 racks with different per-node storage

Calis and Koyluoglu
[20]

Two-layered storage with nodes grouped in blocks, block failure model, repair and data collection from
fixed number of nodes from surviving blocks. All links have same costs

Rashmi et al. [21]

Two sets of nodes, repair from d nodes of the other set, data collection from k nodes of any single set.
All links have same costs

Shah et al. [22]

Non-uniform amount of data downloaded from nodes during repair or data collection, without any notion
of clustering

Yu et al. [23], Ernvall
et al. [24]

Non-uniform storage sizes and repair BW costs

Akhlaghi et al. [25]

Repair BW cost can take two different values, depending on the helper node used, this is different from
clustering

Li et al. [26], Wang
et al. [27]

Aim to transmit the repair helper data in shortest amount of time by finding the optimal path from helper
nodes to replacement nodes through a network with non-uniform link capacities

Gopalan et al. [14]

Inherent notion of clustering for node repair, and single node is performed locally with the help of other
nodes in the clusters. Thus unlike GRC, LRCs assume dependency among nodes in a cluster for single
node repair. Further, there is no notion of clustering for data collection.

RCs in heterogeneous systems

C. Our Results
1) Upper Bound on File Size B : Under the setting of functional repair, the file-size B is shown to be upper
bounded by
B ≤ B

∗

= `kα + (m − `)

k−1
X

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

(1)

i=0

where we use the notation a+ to mean max(a, 0), for any integer a. The bound is shown by considering the
information-flow graph (see Section III) under functional-repair, and calculating the minimum cut. For any finite
information-flow graph, the achievability of (1) follows from results in network coding [28]. This establishes the
optimality of (1) when we know an upper bound on the number of node failures that occur during the life-time of
the system. In practice, random linear network codes (RLNCs) [29] can be used to achieve near-optimal operating
points.
For fixed values of B = B ∗ , n, k, d > 0, `, m, (1) gives a normalized trade-off (see Fig. 2) between storageoverhead nmα/B and inter-cluster-repair-bandwidth-overhead dβ/α (see Section IV-A as to why we refer to dβ/α
as repair-bandwidth-overhead). For any m, when ` = 0, the trade-off is exactly same as that of the classical
regenerating codes [13]. When ` > 0 (implies m > 1), the trade-off is strictly better than that of the classical setup.
2) Optimal Code Constructions: We present optimal codes for the minimum storage-overhead and the minimum
inter-cluster repair-bandwidth-overhead operating points of the trade-off, for a class of parameters and under the
setting of exact repair. These two operating points corresponding to MSR and MBR codes, respectively. The
operating points of the MSR and MBR codes are characterized by relations B = mkα and α = dβ respectively.
The construction works by suitably combining ` [n, k] vector MDS codes over Fαq and (m−`) classical exact-repair
MSR (MBR) codes. We also present an optimal code construction for functional-repair, which tolerates an arbitrary

7

MSR

Increasing
nodes per cluster
Classical trade-off

MBR

Fig. 2. Trade-off between storage-overhead nmα/B and inter-cluster repair-bandwidth-overhead dβ/α, for an (n = 5, k = 4, d = 4)
clustered storage system, with ` = m − 1.
1/26

3

number of failures , for the case ` = m − 1, d ≥ k . The code is constructed by combining m − 1 [n, k] vector
MDS codes over Fαq , and an {(n, k, d), (α, β)} functional-repair code from [30] for the classical setting. The code
construction in [30] is an instance of a functional-repair code for the classical setting, which tolerates an arbitrary
number of failures and repairs for the duration of operation of the system.
3) Lower bound on Intra-Cluster Bandwidth Related Parameters: We calculate lower bounds on the intra-clusterbandwidth related parameters γ, `0 , γ 0 , shown in Fig. 1, under assumption that (1) is achieved with equality. While
studying the impact of any one of these parameters, we ignore the effects of the other two; for example, the lower
bound on γ is obtained under the assumption that `0 = m and γ 0 = α, etc.
Under functional repair with d > 0, the per-node intra-cluster bandwidth needed from the host-cluster is lower
bounded by
γ ≥ γ ∗ = α − (d − k + 1)+ β.

(2)

When d < k , the bound gives γ ≥ α, i.e. the entire content of the local helper nodes must be used. For d ≥ k , at
the MBR point characterized by α = dβ , the bound gives γ ≥ (k − 1)β , and at the MSR point characterized by
α = (d − k + 1)β , the bound gives γ ≥ 0. The trivial bound at the MSR point is indeed optimal, since optimal
(achieving equality in (1)) codes at the MSR point can be achieved by simply stacking m classical (n, k, d), (α, β)
MSR codes. In this case, no local help is needed for repair, and hence γ = 0 is indeed optimal at the MSR point. In
fact, under functional repair, the bound in (2) is optimum not just at the MSR point; we prove the converse statement
that, as long as γ ≥ γ ∗ , it is indeed possible to achieve the optimal file-size in (1) for any set of parameters, as
long as there is a known upper bound on the number of repairs in the system.
We provide bounds for the parameters `0 and γ 0 which characterize intra-cluster bandwidth from remote helper
cluster under the assumption 4 that α ≥ (d − k + 2)β , and d ≥ k . Specifically we show the parameter `0 is no less
than m, i.e., `0 = m, and
β
.
(3)
m−`
Under functional repair, RLNCs simultaneously optimize usage of both inter-cluster and intra-cluster bandwidths.
Our simulations based on RLNCs indicate the tightness (achievability) of the bound in (3), under functional repair
(see Fig. 3). We do not have an analytical converse for this bound.
γ0 ≥

3
The network-coding based achievability works only if there is a known upper bound on the number of repairs that occur over the duration
of operation of the system.
4
The values of α in the range (d − k + 2)β < α ≤ (d − k + 1)β corresponds to the region in the trade-off between the minimum-storage
operating point and the next corner point. The bound in (3) does not apply when α is in this range.

8

0.8

=4
=3

0.7
0.6
0.5

1.0

0.8
0.6
0.4
0.2
0
0

0.0
0

10

20

30

# of repairs

40

50

(a) Effect of local cluster repairbandwidth γ, for an (n = 3, k = 2, d =
2), (` = 2, m = 3), (α = 8, β =
4), `0 = m, γ 0 = α system.

Probability of decoding

1.0

0.9

Probability of decoding

Probability of decoding

1.0

0

=3
=2
10

0.8
0.6
0
0

0.4

=2
=1

0.2
0.0

20

30

# of repairs

40

50

(b) Effect of number of remote helper
nodes `0 for an (n = 3, k = 2, d =
2), (` = 1, m = 3), (α = 8, β =
4), γ = γ 0 = α system.

0

10

20

30

# of repairs

40

50

(c) Effect of remote helper cluster
repair-bandwidth γ 0 , for an (n = 3, k =
2, d = 2), (` = 1, m = 3), (α =
8, β = 4), `0 = m, γ = α system.

Fig. 3. Simulation results showing probability of successful data collection against number of node-repairs performed, for a clustered
storage system employing random linear network codes (RLNCs) with sufficiently large field-size. The three figures respectively indicate
the impact of the intra-cluster-bandwidth related parameters γ, `0 and γ 0 on the probability of decoding.

The bounds on `0 and γ 0 highlight the necessary trade-off between the system capacity B ∗ and the remote
helper intra-cluster bandwidth5 `0 γ 0 = mγ 0 , via parameter `, the key parameter that distinguishes our model from
the classical model. Our bounds reveal the interesting fact that, while it is beneficial to increase the number of
local helper nodes ` in order to improve the storage-vs-inter-cluster-repair-bandwidth trade-off, increasing ` not only
increases intra-cluster repair-bandwidth in the host-cluster, but also increases the intra-cluster repair-bandwidth in the
remote helper clusters. For example, if we consider MBR codes (having minimum inter-cluster-repair-bandwidth),
we see that their storage-overhead approaches that of MSR codes for large m as ` gets close to m. However, a
high value of ` also increases the remote helper cluster bandwidth; indeed, mγ 0 surges as m − ` approaches 1; see
Fig. 4 for an illustration.
4) Security under Passive Eavesdropping - Bounds and Codes: We study resilience of the clustered storage
system against passive eavesdropping. An eavesdropper (say, Eve) gains access to the entire content of any subset
of e clusters, where 1 ≤ e ≤ k . Eve also gets to observe all the helper data downloaded for repair of nodes in these
e clusters. The properties of data collection and disk repair remain same as in the case of no eavesdropper. The
setting is along the lines of that considered in [31], where authors study security under the classical RC framework.
The maximum file size B (s) that can be securely stored such that Eve does not gain any information about the file
is shown to be upper bounded by
B (s) ≤ `(k − e)α + (m − `)

k−1
X

min{α, (d − i)β}.

(4)

i=e

We also present explicit optimal secure codes for the MBR point under the setting of exact repair. Like in the
case of no security, an optimal secure code is constructed by suitably precoding a combination of m component
codes, but this time the component codes themselves are secure codes. A code at the MBR point is constructed
by combining ` secure MDS codes for the wiretap-II channel [32][33], and (m − `) classical exact-repair secure
MBR codes [31][34]. Our security results are straightforward extensions of the security results for classical RCs,
given our own results for the no-security case.

9

Fig. 4. Illustrating the impact of number of local helper nodes on the various performance metrics. We operate at the minimum inter-cluster
repair-bandwidth (MBR) point, with parameters {(n = 12, k = 8, d = n − 1)(α = dβ, β = 2)}. Storage-overhead is mnα
, where B ∗ is
B∗
calculated using (1). Inter-cluster BW is dβ. Local and helper intra-cluster BWs are respectively calculated using (2) and (3). We see that
while ` = m − 1 is ideal in terms of optimizing storage and inter-cluster BW, it imposes the maximum burden on intra-cluster BW.

Cluster 1

Cluster 2

Cluster n

MDS codes

Classical MBR11/26
code

Fig. 5. Illustration of an (n = 4, k = 3, d = 3)(m = 4, ` = 3) generalized regenerating code attaining minimum intra cluster repairbandwidth.

D. An Example
Consider a system consisting of n = 4 clusters, with m = 4 nodes/cluster, where we have the availability
requirement that content from any set of k = 3 clusters suffice for data collection. Let us consider three coding
options, which permit single node repair: (i) A product code consisting of two [n = m = 4, k = 3] simple parity
check codes, one across the clusters, and another within a cluster. In this case, repair happens entirely within a
We note that we quantify the remote helper intra-cluster bandwidth as `0 γ 0 though from Fig. 1, one gets the impression that this is
(` − 1)γ 0 . This discrepancy arises because, in our IFG analysis (see Section III), we assume the presence of a dedicated external compute
node which connects to all the `0 helper nodes and generates the helper data. Such an assumption makes the IFG modeling symmetric with
respect to the helper nodes. The choice of `0 γ 0 instead of (`0 − 1)γ 0 as the amount of helper bandwidth is purely matter of convenience.
The nature of results do not change even if one assumed (`0 − 1)γ 0 as the amount of helper bandwidth.
5

0

10

Classical MSR
Stacked Classical RC
Classical
MBR

Product Code
GRC

Fig. 6. Comparing storage-overhead and inter-cluster repair-bandwidth-overhead of three coding options for an (n = 4, k = 3) clustered
storage system, with m = 4. The three options are (i) product code comprised of two [4, 3] simple parity check codes, (ii) stacking 4
(n = 4, k = 3, d = 3) classical regenerating codes, and (iii) an (n = 4, k = 3, d = 3) generalized regenerating code with ` = 3, operating
at the MBR point.

cluster, and there is no inter-cluster bandwidth. Note that this corresponds to the case of d = 0 in our framework.
(ii) Stacking m classical (n, k, d = 3) RCs - by this we mean that corresponding nodes from the n clusters employ
the classical RCs. This corresponds to the case of ` = 0 in our framework. (iii) A (n, k, d = 3)(m = 4, ` = 3)
GRC, which is constructed as follows (see Fig. 5): We stack m − 1 = 3 [n = 4, k = 3] simple parity check
codes (over the vector alphabet Fαq ) to populate coded data in all but the last nodes of all the clusters. In the
last column (corresponding to the last node of all clusters), we place the sum of the three previous codes plus a
classical (n = 4, k = 3, d = 3)(α = dβ, β = 1) MBR code. Constructions of classical MBR codes appear in [35].
Data collection property of the code is straightforward. For repair of any node, the last node of each of the remote
helper clusters (with the help of the remaining 3 nodes) first extracts the MBR code, and passes the helper data
for the MBR code to the replacement node. The latter regenerates the MBR code content first, and uses the helper
data from the 3 local nodes to finally recover the original stored content. The storage-overhead vs inter-clusterrepair-bandwidth trade-off achieved by these three options is shown in Fig. 6. We see that the framework of GRCs
introduced here, offers operating points which are strictly better than those that can be achieved by space sharing
the first two options.
We note that in the above example, the product-code solution carries the extra advantage of handling nodeavailability during data collection. In other words, when using the product code, one can chose to download
content from any 3 nodes from any of the k clusters. This is sometimes beneficial when the 4th node is temporarily
unavailable. No such feature is present in the GRC. In the current paper, since we deal with the case of recovery
from single node failure, enforcing availability (local dependence within a cluster) essentially implies restricting
oneself to using product codes, and nothing else. A key insight that we wish to convey from Fig. 6. is the fact
that while dealing with single node repair, it is potentially beneficial to sacrifice availability (of nodes during data
collection, offered by product codes) in order to achieve operating points that are strictly better than those obtained
by space sharing the two schemes.
The rest of the document is organized as follows. In Section II, we present simple proof of the file-size bound in
(1) for the special cases d = and ` = 0. As mentioned before, the general case of the file-size bound is based on the
notion of information-flow graph (IFG) models; these IFG models are developed in III, followed by the derivation
of the file-size bound under functional repair for general set of parameters in Section IV. The exact-repair and
functional-repair code constructions appear in Section V. Bounds on parameters relating to intra-cluster bandwidth
under functional repair, are discussed in Section VI. Section VII considers security under passive eaves-dropping.
Finally, our conclusions and directions for future work appear in Section VIII.

11

II. F ILE SIZE BOUND FOR S PECIAL C ASES
In this section, we consider certain special cases of the setting of generalized regenerating codes, and identify
the corresponding storage vs inter-cluster-repair-bandwidth trade-offs. The following cases are considered 1) d = 0,
which corresponds to the case when repair of a node is carried out entirely with the help of other local helper
nodes in the cluster. 2) ` = 0, which corresponds to the case when repair of a node is carried out solely with the
help of remote clusters, without taking any help from local nodes in the host-cluster.
A. Case d = 0 : No Inter-Cluster Help for Repair
When d = 0, node repair is accomplished by contacting any set of ` other nodes in the host cluster. Since any
set of k clusters should be sufficient to decode the whole file, it follows that the file-size B is upper bounded by
B ≤ `kα.

(5)

The achievability of the above bound follows by using an [n, k] × [m, `] product code, with both component codes
being MDS codes over Fαq . In fact, the parameter α is redundant for this case; one may choose α = 1 in practice.
It is clear that there is no storage vs inter-cluster-repair-bandwidth trade-off offered by this case.
B. Case ` = 0: No local helper data
We next consider the special case when repair is performed without any help from nodes in the host-cluster.
∗ denote that maximum
Let Cm denote a GRC of file-size B with parameters {(n, k, d)(α, β)(m, ` = 0)}. Let Bm
possible file-size for any GRC having parameters {(n, k, d)(α, β)(m, ` = 0)}. We note that the code C1 denotes a
classical RC, and under functional-repair, we know that [13]
B1∗ =

k−1
X

min{α, (d − i)β}.

(6)

i=0

Theorem 2.1: The optimal file size under the setting of functional-repair GRCs, for the case of no local helper
nodes, is given by
∗
Bm
= mB1∗ = m

k−1
X

min{α, (d − i)β}.

(7)

i=0

Proof: The achievability part of the proof is straightforward; the optimal code is constructed by simply stacking
m classical codes C1 each of which achieves the bound in (6). By stacking, we mean that the code C1 is deployed
across the corresponding nodes from all n clusters. In this case, note that during node-repair, there is no pooling
of content from various nodes of a remote helper cluster; repair happens as though there is only one code C1 in
the system.
For showing the upper bound on the file size, we note that given a code Cm with file-size B having parameters
{(n, k, d)(α, β)(m, ` = 0)}, one can construct a functional-repair classical regenerating code Cb1 , also with file-size
b , where βb ≤ mβ . For this, we simply assume the contents of all m
B , and having parameters {(n, k, d), (mα, β)}
nodes of any cluster i of Cm , to be the contents of node i of Cb1 , 1 ≤ i ≤ n. Clearly Cb1 retains the data collection
property. For node repair in Cb1 , we perform individual repairs of each of the m nodes, but with the same set of d
remote helper clusters. In this case, we know that
B ≤

k−1
X

b
min{mα, (d − i)β}

(8)

min{mα, (d − i)mβ}

(9)

i=0

≤

k−1
X
i=0

=

m

k−1
X
i=0

min{α, (d − i)β}.

(10)

12

T

S

Fig. 7. An example of the IFG model representing the notion of generalized regenerating codes, when intra-cluster bandwidth is ignored.
In this figure, we assume (n = 3, k = 2, d = 2)(m = 2, ` = 1). The model is a generalization of one the used in [13] for the setting of
classical regenerating codes.

Theorem 2.1 implies that, under functional repair, the normalized trade-off between storage-overhead nmα/B
and inter-cluster-repair-bandwidth-overhead dβ/α for an {(n, k, d)(α, β)(m, ` = 0)} GRC is identical for any m;
specifically, it is identical to the trade-off of an {(n, k, d)(α, β)} functional-repair classical RC.
III. I NFORMATION F LOW G RAPH M ODEL
In this section, we describe the information flow graph (IFG) models used to derive the various bounds in this
work. The models are generalizations of the one used in [13] for the case of classical regenerating codes. Under
functional repair, the problem is one of multicasting the source file to an arbitrary number of data collectors over
the IFG. The IFG characterizes the data flows from the source to a data collector, and also reflects the sequence
of failures and repairs in the storage system. Two models of IFGs will be used; the first one will be used in two
scenarios: 1) to derive the trade-off between storage-overhead and inter-cluster repair-bandwidth overhead. While
obtaining this trade-off, we ignore the effects of intra-cluster bandwidth, 2) to find the optimal local helper node
intra-cluster bandwidth γ , which is needed to establish the optimal trade-off between storage-overhead and intercluster repair-bandwidth overhead. We wish to note that while obtaining the bound on γ , we do not impose any
limitations on γ 0 , `0 , i.e, we assume that γ 0 = α and `0 = m. A second related model will be used while deriving the
lower bounds on the parameters `0 , γ 0 , which relate to the intra-cluster repair bandwidth needed in the remote helper
clusters. In this second model, we shall assume that γ = α, i.e., we ignore the effects of limited local helper-node
intra-cluster bandwidth, while calculating bounds on remote helper-node intra-cluster bandwidth. We describe the
two models next.
A. IFG Model for Storage vs Inter-Cluster Repair Bandwidth Trade-off
Let Xi,j denote the physical node j in cluster i, 1 ≤ i ≤ n, 1 ≤ j ≤ m. Recall that capacity of any node is
in and X out , with an edge of capacity α
α. In the IFG, the physical node is represented by the pair of nodes Xi,j
i,j
in to X out . The nodes X in and X out will be respectively referred to as the in-node and out-node
going from Xi,j
i,j
i,j
i,j
in → X out ) to denote that there is an edge from going
corresponding to the physical node Xi,j . We will write (Xi,j
i,j
in to X out . With a slight abuse of notation, we will let X
in
out
from Xi,j
i,j to also denote the pair (Xi,j , Xi,j ) of the
i,j
ext
out
graph nodes. Cluster i also has an additional external node, denoted as Xi . Each out-node Xi,j , 1 ≤ j ≤ m is
connected to Xiext via an edge of capacity α. The external node Xiext is used to transfer data outside the cluster,
and thus serves two purposes: 1) it represents a single point of contact to the cluster, for a data collector which
connects to this cluster, and 2) it represents the compute unit which generates the β symbols for repair of any node
in a different cluster.

13

T
S

0
0

Failed node

Fig. 8. An example of the second IFG model, with limited intra-cluster bandwidth in the remote helper clusters. The model assumes that
γ = α. In this example, we assume (n = 3, k = 2, d = 2)(m = 2, ` = 1)(`0 = 1).

The source node S represents the original placement of the encoded source file into the nm storage nodes. S
in ), ∀i ∈ [n], ∀j ∈ [m], via links
connects to the in-nodes of all physical storage nodes in their original state (S → Xi,j
of infinite capacity. The sink node T represents a data collector, it connects to the external nodes of an arbitrary
subset of k clusters (Xiext → T ) also via links of infinite capacity.
Each cluster at any moment has m active nodes. When a physical node Xi,j fails, it becomes inactive, and its
bi,j , becomes active instead (see Fig. 7 for an illustration). The replacement node X
bi,j is
replacement node, say X
0
0
ext
regenerated by downloading β symbols from any d nodes in the set {Xi0 , 1 ≤ i ≤ n, i 6= i}. The replacement
out , 1 ≤ j 0 ≤ m, j 0 6= j}. The capacity of the links
node also connects to any subset of ` nodes in the set {Xi,j
0
out
in
0
0
b
{(Xi,j 0 → Xi,j ), 1 ≤ j ≤ m, j 6= j} depend on whether we use the model for finding the inter-cluster-bandwidth
vs storage trade-off, or we use it for finding bounds on local helper bandwidth γ . These links have capacity α and
γ in the former and latter cases, respectively.
In our model, recall that we focus on one repair at a time. In this scenario, along with the replacement of Xi,j
bi,j , we will also copy all the remaining m − 1 nodes, as they are, in the cluster i, and represent them
with X
in , X out ), 1 ≤ j 0 ≤ m, j 0 6= j . We shall also a have a new external node
with new identical pair of nodes (Xi,j
0
i,j 0
for the cluster, which connects to the new m out-nodes. Thus, in the IFG modeling, we say that the entire old
cluster (where the failed node resides) becomes inactive, and gets replaced by a new active cluster. For either data
collection or repair, we connect to external nodes of the active clusters. Note that, at any point in time, a physical
cluster contains only one active cluster in the IFG, and fi inactive clusters in the IFG, where fi ≥ 0 denotes the
total number of failures and repairs experienced by the various nodes in the cluster. We shall use the notation
Xi (t), 0 ≤ t ≤ fi to denote the cluster that appears in IFG after the tth repair associated with cluster i. The clusters
Xi (0), . . . , Xi (fi − 1) are inactive, while Xi (fi ) is active, after fi repairs. The nodes of Xi (t) will be denoted by
in (t), X out (t), X ext (t), 1 ≤ j ≤ m. With a slight abuse of notation, we will let X (t) to also denote the collection
Xi,j
i
i,j
i
in (t), X out (t)); again, with a slight abuse
of all 2m + 1 nodes in this cluster. We write Xi,j (t) to denote the pair (Xi,j
i,j
of notation, we shall use Xi,j (t) to also denote the node j in cluster i after the tth repair (in cluster i). We further
use notation F am(i) to denote the union of all nodes in all inactive clusters, and the active cluster, corresponding
i
to the physical cluster i after t repairs in cluster i, i.e., F am(i) = ∪ft=0
Xi (t). We have avoided indexing F am(i)
with the parameter t as well, to keep the notation simple. The value of t in our usage of the notation F am(i) will
be clear from the context.
B. IFG Model for Finding Bounds on Intra-Cluster Repair Bandwidth
We now describe the model used to obtain lower bounds on the parameters γ 0 , `0 . Unlike in the case of bounds
for file-size B and local helper node intra-cluster bandwidth γ , where we also show converses, for γ 0 and `0 we do

14

not provide converses to the lower bounds. When only dealing with lower bounds, we can significantly simplify
the model described above. In addition to making these simplifications, we also add some structure to the model
to enable usage of γ 0 and `0 . We describe these changes next.
in , X out ), such that
In the second model, each physical node Xi,j is again represented by the pair of nodes (Xi,j
i,j
in → X out ) has capacity α. In this model, an external node(s) is(are) added dynamically to a cluster
the edge (Xi,j
i,j
whenever it aids in either data collection or repair of another node. Each instance of an external node is used exactly
once, either for a repair or a data collection operation. Whenever a physical node Xi,j fails, we say that it becomes
bi,j = (X
b in , X
b out ), becomes active in the same cluster. The remaining
inactive, and its replacement node, say X
i,j
i,j
m − 1 nodes are not replicated, as in the previous model. Thus, in the second model, there is only a single graph
cluster corresponding to a physical cluster. On the graph representation, the replacement node is visually linked to
the replaced failed node with a red dotted line (see Fig. 8 for an example).
We explain the repair and data collection operation in the IFG in more detail next. During repair, the replacement
bi,j connects to any subset of ` active nodes in the same cluster via links of capacity α. It also downloads
node X
bi,j downloads helper
β symbols each from d remote helper clusters via their external nodes. If replacement node X
0
ext
b in ) has
data from cluster i , an external node, Xi0 ,Xi,j , is added to the IFG, such that the edge (Xiext
→ X
0 ,X
i,j
i,j
0 active out-nodes of cluster i0 via links of
capacity β . External node Xiext
also
connects
locally
to
a
subset
of
`
0 ,X
i,j
capacity γ 0 . Note how we index the external node of cluster i0 that aids in the repair of Xi,j . Every time cluster
i0 acts as a remote helper cluster toward the repair of any node, we add a new external node in a manner similar
ext , which in turn connects to
. Finally, a data collector, T , connects to cluster i via the external node Xi,T
to Xiext
0 ,X
i,j
all m active out-nodes in the cluster via links of capacity α. We index the external node also with T since the m
active nodes that form part of the cluster evolves over time.
In comparison with previous model, we do not time-index the sequence of failures in the current model. This
is because, in our proof of bounds for γ 0 and `0 , we only consider system evolutions in which each node fails at
bi,j .
most once. In this case, we find it convenient simply to denote the replacement node of Xi,j as X
IV. F ILE SIZE BOUND FOR G ENERAL PARAMETERS
In this section, we derive the file-size bound in (1) under the setting of functional repair, for arbitrary set of
code parameters. We further use this bound to characterize the storage-overhead vs inter-cluster-repair-bandwidthoverhead trade-off. Intra-cluster bandwidth is ignored in this section. Thus, for the repair of any node, the entire
content of ` local helper nodes can be used; similarly, the entire content (mα symbols) of each remote helper
cluster is used to generate its β helper symbols.
Theorem 4.1: The file size B of a functional repair generalized regenerating code having parameters {(n, k, d)
(α, β) (m, `)} is upper bounded by
B ≤ B ∗ = `kα + (m − `)

k−1
X

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

(11)

i=0

Further, if there is a known upper bound on the number of repairs that occur for the duration of operation of the
system, the above bound is sharp, i.e., B ∗ gives the functional repair storage capacity of the system.
Proof: The proof technique is similar to the proof of the bound under functional repair for the setting of
classical regenerating codes [13]. The problem of functional repair is one of multicasting, and thus for finding the
desired upper bound on the file-size, it is enough if we exhibit a cut in an IFG, for a specific sequence of failures
and repairs, which separates the source from the sink, such that the value of the cut is the desired upper bound. We
shall then show that, for any valid IFG, independent of the specific sequence of failures and repairs, B ∗ is indeed
a lower bound on the minimum possible value of any S − T cut. The achievability result, when there is known
upper bound on the number of failures and repairs, will then follow from results in network coding [28].
We begin with the proof of the upper bound. We consider a sequence of k(m − `) failures and repairs, as
follows: Physical nodes Xi,`+1 , Xi,`+2 , . . . Xi,m fail in this order in cluster i = 1, then in cluster i = 2, and
so on, until cluster i = k . In the IFG, (see Section III-A), this corresponds to the sequence of failures of nodes
X1,`+1 (0), X1,`+2 (1), . . . , X1,m (m − ` − 1), X2,`+1 (0), . . . , X2,m (m − ` − 1), . . . , Xk,m (m − ` − 1), in the respective
order. The replacement node Xi,`+t (t) for Xi,`+t (t − 1), 1 ≤ t ≤ m − ` draws local helper data from Xi,1 (t −

15

T

S

Edge
capacities

Fig. 9. An example of the information flow graph used in cut-set based upper bound for the file-size. In this figure, we assume (n = 3, k =
2, d = 2)(m = 2, ` = 1). We also indicate a possible choice of S − T cut that results in the desired upper bound.

1), Xi,2 (t − 1), · · · , Xi,` (t − 1), and remote helper data from the clusters X1 (m − `), · · · , Xi−1 (m − `) and from
some set of d − min{i − 1, d} = (d − i + 1)+ other active clusters in the IFG. An example is shown in Fig. 9 for
a set of system parameters that is same as those used in Fig. 7.
Let data collector T connect to clusters X1 (m − `), . . . , Xk (m − `). Consider the S − T cut consisting of the
following edges of the IFG:
in (0) → X out (0), i ∈ [k], j ∈ [`]}. Total capacity of these edges is klα.
• {(Xi,j
i,j
in (t)), i0 ∈ {remote helper cluster
• For each i ∈ [k], t ∈ [m − `], either the set of edges {(Xiext
(0) → Xi,`+t
0
in (t)}\[min{i − 1, d}]}, or the edge (X in (t) → X out (t)). Between
indices for the replacement node Xi,`+t
i,`+t
i,`+t
the two possibilities, we
one which has smaller capacity. In this case,P
the total capacity of this part
PkpickPthe
k
+
of the cut is given by i=1 m
j=`+1 min{α, (d − min{i − 1, d})β} = (m − `)
i=1 min{α, (d − i + 1) β}.
P
The value of the cut is given by klα + (m − `) ki=1 min{α, (d − i + 1)+ β} = B ∗ , which proves our upper bound.
In the example on Fig. 9 for (n = 3, k = 2, d = 2)(m = 2, ` = 1), first, m − ` = 1 node fails in cluster 1 and
downloads helper data from clusters 2, 3, second, a node fails in cluster 2 and downloads helper data from clusters
1, 3. The data collector connects to clusters 1, 2. A minimal cut for 2β ≤ α is shown on the figure, and has value
2α + 3β = B ∗ .
We next show that for any valid IFG (independent of the specific sequence of failures and repairs), B ∗ is indeed
a lower bound on the minimum possible value of any S − T cut. Consider any S − T cut, and let IFGS and IFGT
denote the two resultant disconnected parts of the IFG corresponding to the nodes S and T , respectively. Since
node T connects to k external nodes via links of infinite capacity, we only consider cuts such that IFGT has at
least k external nodes corresponding to active clusters. Next, we observe that the IFG is a directed acyclic graph,
and hence there exists a topological sorting of nodes of the graph such that an edge exists between two nodes A
and B of the IFG only if A appears before B in the sorting. Further, we consider a topological sorting such that
all in-, out- and external nodes of the cluster Xi (τ ) appear together in the sorted order, ∀i, τ .
Now, consider the sequence E of all the external nodes (which are part of both active and inactive clusters) in
IFGT in their sorted order. Let Y1 denote the first node in this sequence. Without loss of generality let Y1 ∈ F am(1).
Next, consider the subsequence of E which is obtained after excluding all the external nodes in F am(1) 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. Once again,
without loss of generality, we assume that Yi ∈ F am(i), 2 ≤ i ≤ k . Let us assume that Yi = Xiext (ti ), for some
out (t ), . . . , X out (t ) that connect to X ext (t ). Among these m out-nodes, let
ti . Now, consider the m out-nodes Xi,1
i
i
i,m i
i
ai , 0 ≤ ai ≤ m denote the number of out-nodes that appear in IFGS . Without loss of generality let these be the
out (t ), X out (t ), . . . , X out (t ). Next, corresponding to the out-node X out (t ), a + 1 ≤ j ≤ m, consider its
nodes Xi,1
i
i
i
i
i,2
i,ai i
i,j
out (t), t < t } in the IFG, and let X out (t ), for some t
past versions {Xi,j
≤
t
denote
the first sorted node that
i
i,j
i,j
i
i,j

16

Edge
capacities

Fig. 10. An example of how any S − T cut in the IFG affects nodes in F am(i). In the example, we assume m = 4. With respect to the
description in the text, ai = 2. Further, the node Xi,4 (ti,4 ) is a replacement node in the IFG.

out (t ), a + 1 ≤ j ≤ m} are
appears6 in IFGT . Without loss of generality, let us also assume that the nodes {Xi,j
i,j
i
out
out
out
sorted in the order Xi,ai +1 (ti,ai +1 ), Xi,ai +2 (ti,ai +2 ), . . . , Xi,m (ti,m ). An illustration is provided in Fig. 10.
To obtain a lower bound on the value of the S − T cut, we make the following observations:
out (t ) → X ext (t )), 1 ≤ j ≤ a } are part of the cut. These contribute a total value of a α.
• The ai edges {(Xi,j
i
i
i
i
i
out
in (t ) belongs to IFG , then the
• For any node Xi,j (ti,j ), ai + 1 ≤ j ≤ m, if the corresponding in-node Xi,j
i,j
S
in (t ) → X out (t )) appears in the cut, and contributes a value of α to the cut. Now, consider the
edge (Xi,j
i,j
i,j
i,j
in (t ) belongs to IFG . In this case, consider the following two sub cases:
case when the in-node Xi,j
i,j
T
out (t −1) → X in (t ))
– The node Xi,j (ti,j ) is not a replacement node: This means that, either the edge (Xi,j
i,j
i,j i,j
in
appears in the cut, if ti,j > 0, or the edge (S → Xi,j (ti,j )) appears in the cut, if ti,j = 0. In any case,
the contribution to the overall value of the cut is at least α.
– The node Xi,j (ti,j ) is a replacement node of Xi,j (ti,j − 1): We know that ` local helper nodes and d
external nodes are involved in repair. It is straightforward to see that out of the ` local helper nodes, at
most (j − 1) belong to IFGT . To see this, note that the potential candidates for the local helper nodes that
appear in IFGT correspond to the physical nodes7 Xi,1 , Xi,2 , . . . , Xi,j−1 . The version of the physical node
Xi,j 0 , j 0 > j , if it aids in the repair process, appears in IFGS because of our definition of Xi,j 0 (ti,j 0 ). Next,
note that out of the d external nodes, at most (i − 1) belong to IFGT . In this case, the contribution to the
value of the cut, due to the edges that aid in repair, is lower bounded by (` − j + 1)+ α + (d − (i − 1))+ β .
out
It may be noted that even though Xi,j
(ti,j ) appears in IFGT , the corresponding external node Xiext (ti,j ) appears in IFGS . This is due
ext
to our assumption that Yi = Xi (ti ) is the first external node, corresponding to physical cluster i, that appears in IFGT .
7
It may be noted that we count the physical nodes Xi,1 , . . . , Xi,ai among the possible set of local helpers, although we assume that
Xi,j (ti ), 1 ≤ j ≤ ai appears in IFGS . This is because, we cannot discount the possibility that Xi,j (ti,j 0 − 1) appears in IFGT , for
j ≤ ai , j 0 > ai .
6

17

Based on the observations above, the value of the cut is lower bounded by


k
m
X
X
ai α +
mincut(S − T ) ≥
min(α, (` − j + 1)+ α + (d − (i − 1))+ β)
i=1

= ai kα +

(12)

j=ai +1
k
`
X
X

α+

i=1 j=ai +1

k
X

m
X

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

(13)

i=1 j=max(`,ai )+1

= max(ai , `)kα + (m − max(ai , `))

k
X

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

(14)

i=1

≥ `kα + (m − `)

k
X

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

(15)

i=1

for any ai , 0 ≤ ai ≤ m. This completes the proof of the converse.
Definition 1 (Optimal Code): Code Cm is said to be optimal or capacity achieving, if its file-size B = B ∗ , where
B ∗ is as given in Theorem 4.1.
A. Minimum Storage and Minimum Inter-Cluster Bandwidth Operating Points
We now define the MSR and MBR operating points based on the bound in Theorem 4.1, whenever d > 0. The
operating point dβ = α will be identified with the MBR operating point. An optimal code Cm at the MBR operating
point will be referred to as an MBR code. To see the rationale behind the definition of the MBR operating point,
we recall our assumption that whenever d > 0, the encoding function does not introduce any dependency among
the content of the nodes of a cluster. In this case, assuming that B symbols of the uncoded file are uniformly
distributed over FB
q , it is straightforward to see the necessity of the condition dβ ≥ α for any code Cm .
Towards defining the MSR point, we note that B ≤ `kα + (m − `) min(d, k)α. The MSR code is an optimal
code having B = `kα + (m − `) min(d, k)α, and has the lowest possible inter-cluster repair bandwidth. It is clear
that the parametrization of the MSR operating point depends on relation between d and k . For d ≥ k , the optimal
file-size of B = mkα is achievable only if (d − k + 1)β ≥ α, and thus the operating point (d − k + 1)β = α will
be identified with the MSR operating point. For 1 ≤ d ≤ k − 1, note that B ≤ `kα + (m − `)dα, and equality is
achieved only if β ≥ α. The operating point α = β will be identified with the MSR operating point for the case
when 1 ≤ d ≤ k − 1.
Based on the definition of the MSR and MBR operating points, we note that for d ≥ k , the range of α considered
while plotting the trade-off is given by (d − k + 1)β ≤ α ≤ dβ , and when 1 ≤ d ≤ k − 1, the range of α is given
by β ≤ α ≤ dβ .
V. C ODE C ONSTRUCTIONS
In this section, we describe our optimal code constructions. Two constructions are presented; the first one is an
instance of an exact repair code, and results in optimal codes at the MSR and MBR points under the setting of
generalized regenerating codes; the second construction is a functional-repair regenerating code. Both codes can
withstand any number of repairs for the duration of operation of the system. The exact repair code withstands
any number of repairs by definition, since after each repair the data on all nodes is the same as at the start
of system operation. This logic does not hold for functional repair codes, because the repaired node content is
generally different from the original one. Network-coding based achievability proofs for functional-repair work
only if there is a known upper bound on the number of repairs that occur over the lifetime of the system. Our
functional repair code relies on the construction in [30], which allows our code to operate for arbitrarily many
repairs. For both constructions, we rely on existing optimal classical regenerating codes that are linear. By a linear
regenerating code, we mean that both encoding and repair are performed via linear combinations of either the input
or the coded symbols, respectively. The first construction generates an optimal (n, k, d)(α, β)(m, `) code for any
m, ` ≤ m − 1, 1 ≤ d ≤ n − 1, whenever an optimal (n, k, min(k, d))(α, β) classical exact repair linear regenerating
code exists. Our functional repair code construction is limited to the case ` = m − 1, d ≥ k .

18

For a linear (n, k, d)(α, β) classical regenerating code that encodes a data file of size B symbols, one can
associate a generator matrix G of size B × nα. Without loss of generality, the first α columns of G generates the
content of node 1, and so on. We say that two (n, k, d)(α, β) classical linear regenerating codes C1 and C2 , having
generator matrices G1 and G2 are identical, if G1 = G2 . Since we assume that repair is also a linear operation, it
follows that the set of linear functions that define repair operations can be taken the same for C1 and C2 that are
identical. The following lemma will be used while we prove optimality of the exact-repair construction. The proof
of the lemma is straightforward, and is omitted.
Lemma 5.1: Let {Ci , 1 ≤ i ≤ s, s ≥ 1} denote identical (n, k, d)(α, β) classical exact repair linear regenerating
codes. Let ci ∈ Fnα
q denote a generic codeword of Ci , 1 ≤ i ≤ s, where the first α symbols of ci are the content
of node 1, and so on. Suppose that we P
are given ai ∈ Fq , 1 ≤ i ≤ s such that not every ai is 0, define a new
α
n-length array code C over Fq as C = { si=1 ai ci , ci ∈ Ci }. Then, the code C is an (n, k, d)(α, β) classical exact
repair linear regenerating code over Fq , and is identical to Ci , 1 ≤ i ≤ s.
A. Exact Repair Code Construction
We begin with a description of the code, and then show its data collection and repair properties. The construction
itself is a generalization of the example presented in Section I-D.
Construction 5.2: Let Cj , 1 ≤ j ≤ ` denote [n, k] MDS array codes over Fαq . The amount of data that can be
encoded with these ` codes is `kα. Next, let Cj , ` + 1 ≤ j ≤ m denote (n, k, d0 = min(d, k))(α, β) classical
P
0
exact repair linear regenerating codes (also over Fq ), each having a file size B 0 = k−1
i=0 min(α, (d − i)β). We
require that all the codes Cj , ` + 1 ≤ j ≤ m are identical. For encoding, we first divide the data file of size
B ∗ = `kα + (m − `)B 0 into m stripes, such that first ` have size kα, and the last m − ` have size B 0 . Stripe
j, 1 ≤ j ≤ m is encoded by Cj to generate the coded symbols cj = [c1,j , c2,j , . . . , cnα,j ]T . Next, consider an m × m
invertible matrix A over Fq such that the first the ` rows of A generate an [m, `] MDS code Fq . Let matrix A be
decomposed as


E`×m
.
(16)
Am×m = 
Fm−`×m
Thus, the matrix E`×m generates an [m, `] MDS code. The coded data stored in the various clusters is generated
as follows:
[c01 c02 · · · c0m ] = [c1 c2 · · · cm ]Am×m .

(17)

The content of node j in cluster i is given by [c0(i−1)α+1,j , c0(i−1)α+2,j , . . . , c0iα,j ]T , 1 ≤ i ≤ n, 1 ≤ j ≤ m. This
completes the description of the construction. A pictorial overview of the description appears in Fig. 11.
We next prove optimality property of Construction 5.2.
Theorem 5.3: The code described in Construction 5.2 is an optimal exact repair generalized regenerating code,
0
for any m, ` ≤ m. The optimal code can be constructed whenever
Pk−1 an optimal0 (n, k, d = min(d, k))(α, β) exact
0
repair linear regenerating code exists, having a file size B = i=0 min(α, (d − i)β).
Proof: It is clear that the code in Construction 5.2 has a file size B ∗ , where B ∗ is as given in Theorem 4.1.
Further, the data collection property of the code is also straightforward to check, and this essentially follows from
the facts that 1) the matrix A is invertible, and 2) each of the codes Ci , 1 ≤ i ≤ m is uniquely decodable given its
coded data belonging to any k clusters. Towards examining the repair property of the code let us rewrite (17) as

19

Cluster 1

Cluster 2

Cluster n

generates

MDS codes

regenerating codes

MDS code

Invertible Matrix

Fig. 11. Illustration of the exact repair code construction. We first stack ` MDS codes and (m − `) classical regenerating codes, and then
transform each row via the invertible matrix A. The first ` rows of the matrix A generates an [m, `] MDS code.

follows:
[c01 c02 · · · c0m ] = [c1 c2 · · · cm ]Am×m

(18)

= [CM DS Cregen ] Am×m

 (1)
(1)
cM DS cregen
 (2)

 cM DS c(2)
regen 

 Am×m ,
= 
..
..

.
.


(n)

(19)

(20)

(n)

cM DS cregen

where CM DS = [c1 · · · c` ] and Cregen = [c`+1 · · · cm ]. The
(i − 1)α + 1, . . . , iα of CM DS and Cregen , respectively. Let us
further as follows:

E`×m

Am×m =
Fm−`×m
 T
e1 eT2
= 
f1T f2T

(i)

(i)

matrices cM DS and cregen , 1 ≤ i ≤ n denote rows
also expand the decomposition of matrix A in (16)

(21)


···

eTm

···

T
fm


,

(22)

where eTj and fjT , 1 ≤ j ≤ m denote the j th column of the matrices E and F , respectively. Based on (20) and (22),
it can be seen that the content of node j in cluster i is given by
 T 
h
i ej
(i)


cM DS c(i)
(23)
regen
T
fj
Given the notation above, without loss of generality, consider repairing node ` + 1 in cluster 1 with the help of 1)
the first ` local nodes in cluster 1 and 2) clusters 2, . . . , d0 + 1. Let us first examine the role of the ` local nodes in
the repair process. Let E 0 and F 0 denote the first ` columns of E and F , respectively. By assumption, E generates
an [m, `] MDS code, and hence the submatrix E 0 is invertible. In this case, the content from the ` local nodes can
be put together to generate



 T 
h
i E0
h
i e`+1
(1)
(1)
 c(1)

,
 E 0−1 eT`+1 = c(1)

(24)
M DS cregen
M DS cregen
0
T
b
F
f`+1

20

Incorrect component

Regeneration

Cluster 1

Helper data for
Cluster

Correcting the local helper
෢𝑡 to 𝑓 𝑡
data component from 𝑓

Fig. 12.

An illustration of the node repair process for exact repair generalized regenerating code obtained in Construction 5.2.

where b
fjT = F 0 E 0−1 eT`+1 . Thus, the local helper nodes serve to recover the part corresponding to the MDS-codes’
(1)
(1)
T differs from the original
components given by cM DS eT`+1 . However, the regenerating-codes’ components cregenb
f`+1
(1)
T .
cregen f`+1
the role of the d0 remote helper clusters. We know that the data stored in cluster i is given by
h Let us next examine
i
(i)
(i)
(i)
cM DS cregen A. Since matrix A is invertible, the vector cregen can be recovered from this. Now, if we define the
nP
o
m−`
bj )c`+j , c`+j ∈ C`+j , we know from Lemma 5.1 that Cbi is an (n, k, d0 )(α, β) classical
code Cbi =
(f
−
f
j
j=1
exact repair linear regenerating code, which is identical to Cj , ` + 1 ≤ j ≤ m. Thus, cluster i, 2 ≤ i ≤ d0 + 1
generates and passes the helper data (β symbols) toward the repair of the first vector symbol for the code Cbi . The
(1)
replacement node regenerates cregen (fjT − b
fjT ) using the helper data from the d0 remote clusters, and combines it
with the local helper data (see (24)) to correct the regenerating-codes’ components, and restore the content of the
lost node. A pictorial illustration of the repair process is shown in Fig. 12.
B. A Functional Repair Code for Arbitrary Number of Failures
In this section, we show the existence of optimal functional repair codes over a finite field that can tolerate
an arbitrary number of repairs for the duration of operation of the system. We show the existence for any
(n, k, d)(α, β)(m, ` = m − 1). The code construction is similar to the one used in the example in Section I-D, and
combines m − 1 MDS array codes C1 , . . . , Cm−1 with an (n, k, d)(α, β) functional repair code Cm for the classical
setting. The code Cm is one that can tolerate an arbitrary number of repairs for the duration of operation of the
system. The following lemma is a direct consequence of Theorem 3 and the description in Section V of [30], and
guarantees the existence of the code Cm that we use here.
Lemma 5.4: For any (n, k, d)(α, β), there exists an optimal deterministic classical functional repair linear regenerating code over Fq that can tolerate an arbitrary number of repairs for the duration of operation of the system,
whenever q > q0 , where q0 is entirely determined by the parameters (n, k, d)(α, β), and is independent of the
number of repairs performed over the lifetime of the code.
In the above lemma, by a deterministic regenerating code, we mean that the regenerated data corresponding to
a repair operation of a given physical node is uniquely determined given the content of the helper nodes. As we
shall see, the fact the code is deterministic is important to ensure the data collection property of our functional
repair construction.
Below, we first describe the code construction, along with the repair procedure, and then show the optimality
property of the code. In the following construction, we assume that the characteristic of the finite field Fq is 2; i.e.,
q = 2w for some w > 0. The assumption is made only for the ease of description, the construction can be modified
to accommodate finite fields of any characteristic.

21

Construction 5.5: Let Cj , 1 ≤ j ≤ m − 1 denote [n, k] MDS array codes over Fαq . The amount of data that
can be encoded with these m codes is (m − 1)kα. Next, let Cm denote an (n, k, d0 = min(d, k))(α, β) classical
functional repair
code whose existence is guaranteed by Lemma 5.4. The code Cm has a file
P linear regenerating
0 − i)β). For encoding, we first divide the data file of size B ∗ = `kα + (m − `)B 0
size B 0 = k−1
min(α,
(d
i=0
into m stripes, such that first m − 1 have size kα, and the last one has size B 0 . Stripe j, 1 ≤ j ≤ m is encoded
by Cj to generate the coded symbols cj = [c1,j , c2,j , . . . , cnα,j ]T . The arrangement of coded data in the various
nodes is identical to that in the example in Section I-D. Thus, node j, 1 ≤ j ≤ m − 1 in cluster i stores the
vector [c(i−1)α+1,j , c(i−1)α+2,j , . . . , ciα,j ]T . Node m in cluster i stores the sum of the content of m − 1 nodes with
T
symbols
[c(i−1)α+1,m
Pm
P,mc(i−1)α+2,m , . . . , ciα,m
Pm] of theT regenerating code Cm , i.e., content of node m is given by
[ j=1 c(i−1)α+1,j , j=1 c(i−1)α+2,j , . . . , j=1 ciα,j ] . This completes the description of the initial layout of the
coded data. Since the code is a functional repair code, the code description is not complete unless we specify the
procedure for node repair, as well. We do this next.
Node Repair: Let Yi,j (t) ∈ Fαq denote the content of node j in cluster i, after the tth , t ≥ 0 repair, anywhere in
the system. The quantities {Yi,j (0), 1 ≤ i ≤ n, 1 ≤ j ≤ m} denote P
the initial content
and are
Pmpresent in the system,
Pm
as described above. The repair procedure is such that the vector [ m
Y
(t),
Y
(t),
.
.
.
,
Y
(t)]T
n,j
1,j
2,j
j=1
j=1
j=1
remains as a valid codeword of the functional repair regenerating code Cm , for every t ≥ 0 (to be proved in Theorem
5.6). Clearly, the above statement is true for t = 0. The repair procedure can be described recursively as follows: Let
th
0
0
0 remote helper clusters, say i, internally computes
the
Pmt repair be associated with node i in cluster j . Each of the d P
m
j=1 Yi,j (t − 1), and passes the β symbols toward the repair of
j=1 Yi0 ,j (t − 1). The replacement node first of
P
m
b
all regenerates Yi0 (t − 1), as the replacement of j=1 Yi0 ,j (t − 1), given the helper data from the d remote clusters.
Next, since ` = m − 1, the replacement node gets access to local helper data {Yi0 ,j (t − 1), 1 ≤ j ≤ m, j 6= j 0 }.
The content that is eventually stored in the replacement node is computed as follows:
Yi0 ,j 0 (t) =

m
X

Yi0 ,j (t − 1) + Ybi0 (t − 1).

(25)

j=1
j6=j 0

Also, for any (i, j) 6= (i0 , j 0 ), we assume that
Yi,j (t) = Yi,j (t − 1).

(26)

This completes the description of the repair process and the code construction.
In the following theorem, we argue the optimality property of the above construction. Specifically, we show that
the code retains the functional repair and data collection properties, after every repair. We assume that the data
collector is aware of the entire repair-history of the system. By this we mean that the data collector is aware of
1) the exact sequence of t failures and repairs that has happened in the system, and 2) the indices of the remote
helper clusters that aided in each of the t repairs.
Theorem 5.6: The code described in Construction 5.5 is an optimal (n, k, d)(α, β)(m, ` = m − 1) functional
repair generalized regenerating code.
Proof: It is clear that the code in Construction 5.5 has a file-size B ∗ , as given by TheoremP4.1. Toward
showing that the code retains functional repair property, it is sufficient if we show that the vector [ m
j=1 Y1,j (t),
Pm
Pm
T remains as a valid codeword of the functional repair regenerating code C , for
Y
(t),
.
.
.
,
Y
(t)]
m
j=1 2,j
j=1 n,j
every t ≥ 0. We do this inductively. Clearly, the statement is true for t = 0. Let us next assume that the statement
is true for t = t0 ≥ 0, and show its validity for t = t0 + 1. Assume that the (t0 + 1)th repair is associated with
node j 0 in cluster i0 . The relation between the content ofP
the various nodes before and after the (t0 + 1)th repair are
0
obtained via (25) and (26). In this case, the quantities { m
j=1 Yi,j (t + 1), 1 ≤ i ≤ n} are given by
m
X

Yi0 ,j (t0 + 1)

j=1
m
X
j=1

0

Yi,j (t + 1)

(a)

=

=

Ybi0 (t0 ),
m
X
j=1

Yi,j (t0 ), 1 ≤ i ≤ n, i 6= i0 ,

(27)

(28)

22

S

Edge Capacities

T

Fig. 13. An illustration of the evolution of the k-th cluster of the information flow graph used in cut-set based lower bound for γ in
Theorem 6.1. In this figure, we assume that m = 4, ` = 2. Nodes 3, 4, 1 fail in this respective order. For the repair of node 3, nodes 1 and
2 act as the local helper nodes. For the repair of the remaining two nodes, nodes 2 and 3 act as the local helper nodes. Also indicated is
our choice of the S-T cut used in the bound derivation.

b0 0
where (a) follows
Pmfrom our 0 assumption that the finite field Fq has characteristic 2. Now, recall that Yi (t ) is the
replacement
of j=1 Yi0 ,j (t ), which is regenerated using the helper data generated using d elements of the set
Pm
{ j=1 Yi,j (t0 ), 1 ≤ i ≤ n, i 6= i0 }. Combining with the induction hypothesis for t = t0 , it follows that the induction
statement holds good for t = t0 + 1 as well. This completes the proof of functional repair property of the code.
Let us next see how data collection is accomplished after t, t ≥ 0 repairs in the system. Without loss of generality
assume that a data collector connects to clusters P
1, 2, . . . , k , and
accesses {Yi,j (t),
Pm
P1m≤ i ≤ k, T1 ≤ j ≤ m}. The
data collector as a first step computes the vector [ m
Y
(t),
Y
(t),
.
.
.
,
1,j
2,j
j=1
j=1
j=1 Yk,j (t)] , and uses this to
decode the data corresponding to the code Cm . Now, recall the fact that the code Cm is deterministic, and also our
assumption that the data collector is aware of the entire repair-history of the system. In this case, having decoded
Cm , using (25) and (26), the data collector can iteratively recover {Yi,j (t0 ), 1 ≤ k ≤, 1 ≤ j ≤ m}, for t ≥ t0 ≥ 0 by
starting at t0 = t and proceeding backwards until the content at t0 = 0 is recovered (essentially, we are rewinding
the system by eliminating the effects of all the repairs, starting from the last one and proceeding backwards in
time). Finally, from Construction 5.5, we know that the content {Yi,j (0), 1 ≤ k ≤, 1 ≤ j ≤ m − 1} is the stacked
coded data corresponding to the m − 1 [n, k] MDS coded C1 , . . . , Cm−1 , and thus these codes can also be decoded.
The completes the proof of data collection, and also the theorem.

VI. I NTRA - CLUSTER BANDWIDTH FOR O PTIMAL C ODES
We now turn our attention to calculate the amount of intra-cluster repair bandwidth that is needed for a
(n, k, d)(α, β)(m, `) code Cm to have optimal file-size B ∗ , given by Theorem 4.1. As discussed in Section I-A,
there are two contributors to intra-cluster repair bandwidth: 1) the local helper bandwidth γ , which is the amount
of data that each of the local helper nodes contributes to repair, and 2) the remote helper bandwidth γ 0 , which is
amount of the data that each of the `0 nodes of a remote helper cluster contribute toward computing the β symbols
of the cluster. In this section, we study individually the minimum requirements on the parameters γ , γ 0 and `0 . For
obtaining lower bound on γ , we continue to work with the IFG model in Section III-A, except for the fact that
links that connect the local helper out-nodes to the in-node of the replacement node, will have a capacity γ , instead
of α. The IFG model in Section III-B will be used when we compute lower bound on γ 0 and `0 . We also prove the
tightness of the bound on γ via a converse; however, no such converse is known to us regarding the bound on γ 0 .
We note that, while computing the bound on γ , we ignore the effects of limited γ 0 and `0 (and vice versa), i.e., we
assume that `0 = m and γ 0 = α. Further, the bounds on γ and γ 0 (or `0 ) are obtained under the assumptions that
d > 0 and d ≥ k , respectively.

23

A. Bound on Local Helper Node Intra-cluster Repair Bandwidth, γ
Theorem 6.1: For an optimal functional repair generalized regenerating code with parameters {(n, k, d > 0),
(α, β), (m, `)}, γ 0 = α, `0 = m, local helper node bandwidth γ is lower-bounded by
γ ≥ γ ∗ , α − (d − k + 1)+ β.

(29)

Further, if there is a known upper bound on the number of repairs that occur over the life-time of the system, the
above bound is sharp; i.e., the functional repair capacity of the system remains as B ∗ as long as γ ≥ γ ∗ .
Proof: For the bound, we consider a system evolution similar to that used in proof of Theorem 4.1, and
demonstrate a cut-set whose value depends on γ . The lower bound on γ follows from the observation that the value
of this cut is necessarily lower bounded by B ∗ for a capacity-achieving code. We shall then prove that, as long as
γ ≥ γ ∗ , the min-cut of any valid IFG is necessarily lower bounded by B ∗ ; in this case, like in the proof of Theorem
4.1, we know that the functional repair capacity remains as B ∗ , as long as there is a known upper bound on the
number of repairs in the system. We start with the proof of the lower bound. Consider the same system evolution as
in the proof of the bound in Theorem 4.1, except for the k -th cluster accessed by the data collector. Thus, physical
nodes Xi,`+1 , Xi,`+2 , . . . Xi,m fail in this order in cluster i = 1, then in cluster i = 2, and so on, until cluster
i = k − 1. Note that each of the first k − 1 clusters experiences a total of m − ` node failures. For cluster k , we
consider failure of m−`+1 nodes, corresponding to physical nodes Xk,`+1 , Xk,`+2 , . . . Xk,m , Xk,1 in this respective
order. In terms of the notation introduced in III-A, the sequence of failures in the k th cluster correspond to IFG
nodes Xk,`+1 (0), Xk,`+2 (1), . . . , Xk,m (m − ` − 1), Xk,1 (m − `). For the repair of Xk,`+1 (0), the local helper nodes
used are Xk,1 (0), Xk,2 (0), . . . , Xk,` (0). For the repair of any of the remaining nodes Xk,(`+t) mod (m)+1 (t), 1 ≤
t ≤ m − `, the local helper nodes used are Xk,2 (t), Xk,3 (t), . . . , Xk,`+1 (t). Also, clusters X1 (m − `), X2 (m −
`), . . . , Xmin(d,k−1) (m − `) are included in the set of remote clusters that aid in the repair of the m − ` + 1 nodes
in the k th cluster. An illustration of the IFG, for the k th cluster is shown in Fig. 13. Note in this figure that the
edges corresponding to local help have capacity γ .
Let data collector T connect to clusters X1 (m − `), . . . , Xk−1 (m − `), Xk (m − ` + 1). Consider an S -T cut in
the IFG that partitions the graph nodes in clusters 1, · · · , k − 1 in the same way as in Theorem 4.1; however it
differs in the way the nodes of cluster k are partitioned. The overall set of edges in the cut-set is given as below:
Clusters 1, . . . , k − 1:
in (0) → X out (0), i ∈ [k − 1], j ∈ [`]}. Total capacity of these edges is (k − 1)lα.
• {(Xi,j
i,j
in (t)), i0 ∈ {remote helper cluster
(0) → Xi,`+t
• For each i ∈ [k − 1], t ∈ [m − `], either the set of edges {(Xiext
0
in
in (t) → X out (t)). Between the
indices for the replacement node Xi,`+t (t)}\[min{i − 1, d}] or the edge (Xi,`+t
i,`+t
two possibilities, we pick
the
one
which
has
smaller
sum-capacity.
In
this
case,
the
total
capacity of this part
P
Pm
Pk−1
of the cut is given by k−1
min{α,
(d
−
min{i
−
1,
d})β}
=
(m
−
`)
min{α,
(d − i + 1)+ β}.
i=1
j=`+1
i=1
Cluster k :
out (0) → X in
• (Xk,1
k,`+1 (1)) of capacity γ .
in
out (0)), ∀j ∈ [2, `]. Total capacity of these edges is (` − 1)α.
• (Xk,j (0) → Xk,j
in
0
• Either the set of edges {(Xiext
(0) → Xk,(`+t)
0
mod (m)+1) (t + 1)), i ∈ {remote helper cluster indices for
in
the replacement node Xk,(`+t) mod (m)+1) (t + 1)}\[min{i − 1, d}], 0 ≤ t ≤ (m − `)} or the set of edges
in
out
{(Xk,(`+t)
mod (m)+1) (t + 1) → Xk,(`+t) mod (m)+1) (t + 1)), 0 ≤ t ≤ (m − `)}. Among the two sets, we
pick the one which has smaller sum-capacity. In this case, the total capacity of these edges is (m − ` +
1) min{α, (d − k + 1)+ β}.
The value (say, Ccut ) of the cut is given by
Ccut = (k − 1)`α + (m − `)

k−2
X

min{α, (d − i)+ β} + γ + (` − 1)α + (m − l + 1) min{α, (d − k + 1)+ β}

i=0

= k`α + (m − `)

k−1
X

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

i=0

= B ∗ − α + min{α, (d − k + 1)+ β} + γ.

24

T

S

Edge Capacities

Fig. 14. An illustration of the IFG used in cut-set based lower bound for γ 0 in Theorem 6.2. In this example, we assume (n = 3, k =
2, d = 3)(m = 2, ` = 1)(`0 = 2, γ = α). The second node fails in clusters 1 and 2 in the respective order. Also indicated is our choice of
the S-T cut used in the bound derivation.

Since we assume an optimal code, it must be true that Ccut ≥ B ∗ , which results in γ ≥ α − min{α, (d − k + 1)+ β}.
Finally, note that α − min{α, (d − k + 1)+ β} = γ ∗ in the two cases d < k , and d ≥ k . The equivalence for the
case d ≥ k follows since we only consider α ≥ (d − k + 1)β , when d ≥ k (see Section IV-A).
We next prove the converse, where we show that, as long as γ ≥ γ ∗ , the min-cut of any valid IFG is necessarily
lower bounded by B ∗ . Toward this, consider the proof of converse part of Theorem 4.1, where we obtained a
lower bound on the min-cut of any valid IFG. One can repeat the sequence of arguments exactly as in the proof
of converse part of Theorem 4.1, except with the change that the edges corresponding to local help have capacity
γ (instead of α). In this case, it can be seen that instead of (12), we get the following lower bound on min-cut:


k
m
X
X
ai α +
mincut(S − T ) ≥
min(α, (` − j + 1)+ γ + (d − (i − 1))+ β)
(30)
i=1

j=ai +1

In the above expression, observe that if γ ≥ γ ∗ , we have
(` − j + 1)+ γ + (d − (i − 1))+ β ≥ α,

(31)

whenever j ≤ `, i ≤ k . In this case, it follows that (30) can be written as (13). It is then clear that mincut(S − T )
is indeed lower bounded by B ∗ as long as γ ≥ γ ∗ . This completes the proof of the converse, and also the theorem.

B. Bounds on `0 , γ 0
In this section, we provide bounds on the parameters γ 0 and `0 . We use the second IFG model in Section III-B
here. Recall that in our setting, for any of the remote helper clusters, we allow any subset of `0 nodes in the cluster
to be used to generate the β symbols contributed by the cluster. Also, in this section, we make the assumption that
the number of remote helper clusters d ≥ k .
Theorem 6.2: For an optimal functional repair generalized regenerating code with parameters {(n, k, d ≥ k)
(α, β), (m, `)}, γ = α, `0 = m, the remote helper-node repair bandwidth γ 0 is lower-bounded by
γ 0 ≥ β/(m − `),

(32)
(33)

whenever α ≥ (d − k + 2)β .

25

Proof: We consider data collection from clusters 1 to k . Before data collection, the system experiences k(m−`)
repairs. Nodes ` + 1, . . . , m fail and get repaired in cluster 1 in this respective order. This is followed by failure
and repair of nodes ` + 1, . . . , m in cluster 2, and so on, until we consider failure and repair of nodes ` + 1, . . . , m
in cluster k . In terms of physical nodes, it may be noted that this is the same sequence of failures that was
considered in the proof of Theorem 4.1; however, in here, we will impose additional restrictions on the choice of
the remote helper clusters. In this proof, external help is taken from the set of the first d + 1 clusters, excluding
the cluster where the failed node resides. Thus, for the repair of Xi,j , the indices of remote helper clusters are
{1, . . . , i − 1, i + 1, . . . , k, k + 1, . . . , d + 1}. The choice of local helper nodes remain same as in the proof of
Theorem 4.1, where we used the first ` nodes in the cluster. An illustration of the IFG is shown in Figure 14.
It can be seen that the following cut-set separates the source from the data collector:
in → X out ), i ∈ [k], j ∈ [`]}. Total capacity of these edges is k`α.
• {(Xi,j
i,j
• For each i, 1 ≤ i ≤ k , the edge set with smaller capacity out of A1 (i) ∪ A2 (i) and A3 (i) where
b in ), i0 ∈ [k + 1, d + 1], j ∈ [` + 1, m]}. Total capacity of edges in A1 (i) is
– A1 (i) , {(Xiext
→ X
0
i,j
b in , X
b out ) is simply the replacement node for the failed node (X in , X out ),
(d−k+1)(m−`)β . Recall that (X
i,j
i,j
i,j
i,j
in the second IFG model that is used here.
ext ), j ∈ [` + 1, m], i0 ∈ [i + 1, k], j 0 ∈ [` + 1, m]}. Total capacity of edges in
– A2 (i) , {(Xiout
0 ,j 0 → Xi0 ,X
i,j
A2 (i) is (m − `)(k − i)(m − `)γ 0
b out ), j ∈ [` + 1, m]}. Total capacity of edges in A3 (i) is (m − `)α.
b in → X
– A3 (i) , {(X
i,j
i,j
The capacity of the cut-set is given by
Ccut = k`α + (m − `)

k
X

min{α, (d − k + 1)β + (k − i)(m − `)γ 0 }.

(34)

i=1

Since we consider optimal codes, we have
Ccut ≥ B ∗ = k`α + (m − `)

k
X

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

(35)

i=1

In this case, since we assume that α ≥ (d − k + 2)β , we claim that
γ 0 ≥ β/(m − `).

(36)

To see why (36) is true, if we suppose on the contrary that (m − `)γ 0 < β , we have
(d − k + 1)β + (k − i)(m − `)γ 0 < (d − i + 1)β, 1 ≤ i ≤ k − 1.

(37)

The above equation implies that
min{α, (d − k + 1)β + (k − i)(m − `)γ 0 } ≤ min{α, (d − i + 1)β}, 1 ≤ i ≤ k − 2
0

min{α, (d − k + 1)β + (k − i)(m − `)γ } < min{α, (d − i + 1)β}, i = k − 1,

(38)
(39)

where (39) follows from the assumption that α ≥ (d − k + 2)β . Clearly, adding up the two corresponding sides
(L.HS. and R.H.S.) of (38) and (39), and comparing them contradicts the fact that Ccut ≥ B ∗ . Thus, it must be
true that γ 0 ≥ β/(m − `), whenever α ≥ (d − k + 2)β .
The following theorem establishes the necessary condition on `0 for optimal codes. The proof is along the lines
of proof of Theorem 6.2, and is omitted.
Theorem 6.3: For an optimal functional repair GRC with parameters {(n, k, d ≥ k) (α, β), (m, `)}, γ = γ 0 = α,
whenever α ≥ (d − k + 2)β , each remote helper cluster must necessarily access all the m nodes in the cluster while
generating the β symbols; i.e., whenever α ≥ (d − k + 2)β , we have `0 = m for an optimal functional repair GRC.
VII. S ECURITY U NDER PASSIVE E AVESDROPPING
In this section, we analyze resilience of the clustered storage system against passive eavesdropping. Our model
of clustered storage systems is in part motivated by the need to provide security against an eavesdropper who may
gain access to a subset of the clusters. In this context, we extend result in Theorem 4.1 to settings that require
security. Below, we first introduce the model for security, and then present the revised file bound. Optimal code
construction for security can be provided along the same lines of Construction 5.2.

26

A. Passive Eavesdropper Model
The security model is along the lines of the passive eavesdropper model considered in [31], where the authors
study security under the classical regenerating code framework. An eavesdropper (say, Eve) gains access to the
entire content of any subset of e clusters, where 1 ≤ e ≤ k . Eve also gets to observe all the helper data that gets
downloaded for repair of any node in these e clusters. Eve is passive in the sense that Eve does not change any
stored or repair data. The properties of data collection and disk repair remain same as in the case of no eavesdropper
(see Section I-A). In this model we 1) ignore the effects of intra-cluster bandwidth, and 2) restrict ourselves to the
setting of deterministic exact repair codes. By deterministic exact repair code, we mean that the helper data for
the repair of any node is uniquely determined given the indices of the failed node, local helper nodes and remote
helper clusters. We avoid the possibility that the same set of helpers can pass two possible sets of helper data for
the repair of the same node.
We wish to store a file such that Eve does not gain any information about it, by having eavesdropped into any
subset E of e clusters. To be precise, let F (s) denote the random variable corresponding to the data file that gets
(s)
securely stored. We assume the file F (s) to be uniformly distributed over FqB , and thus B (s) denotes the file-size.
We wish to ensure that the mutual information I(F (s) ; data observed by Eve) = 0. Note that the data observed by
Eve not only includes the content of the E clusters, but also any inter-cluster helper data that is received toward
(s)
the repair of nodes in these clusters. We shall write Cm to denote a secure generalized regenerating code, and its
parameter set will be identified with {(n, k, d), (α, β), (m, `), (e)}.
B. File Size Under Exact Repair
In this section, we obtain an upper bound on the file-size B (s) of the exact repair secure generalized regenerating
(s)
code Cm . To derive the bound, we use information theoretic techniques similar to those used in [36], [31]. We
begin with some necessary notation. Let Yi,j ∈ Fαq , 1 ≤ i ≤ n, 1 ≤ j ≤ m denote the content stored in node j of
cluster i. We write Yi to denote [Yi,1 . . . Yi,m ], 1 ≤ i ≤ n. The property of data collection requires that


H F (s) |{Yi , i ∈ S}
= 0 ∀S ⊂ [n], |S| = k,
(40)
where H(.) denotes the entropy function computed with respect to log q . Next, consider the repair of node j in
cluster i. Let H ⊂ [n]\{i}, |H| = d, and L ⊂ [m]\{j}, |L| = ` respectively denote the indices of remote helper
0
clusters and local helper nodes that aid in the repair process. Let ZiH,L
0 ,i,j denote helper data passed by cluster i . Recall
H,L
our assumption that the exact repair code is deterministic, and thus Zi0 ,i,j is uniquely determined as a function of
(i, j), {Yi,j 0 , j 0 ∈ L} and {Yi0 , i0 ∈ H}. The property of exact repair is jointly characterized by the following set of
inequalities:


0
H ZiH,L
|Y
= 0,
(41)
0 ,i,j
i


H ZiH,L
≤ β,
(42)
0 ,i,j


0
0
H Yi,j |{ZiH,L
= 0, ∀H ⊂ [n]\{i0 }, |H| = d, ∀L ⊂ [m]\{j 0 }, |H| = `.
(43)
0 ,i,j , Yi,j 0 , i ∈ H, j ∈ L}
Next, define Ui to denote the collection of all the inter-cluster helper data ever received toward the repair of nodes
in cluster i, i.e.,
0
Ui = {ZiH,L
0 ,i,j , for all choices of i , j, H, L}.

(44)

The property of being secure against the passive eavesdropper Eve is equivalent to saying that
I(F (s) ; {Yi , Ui , i ∈ E}) = 0, ∀E ⊂ [n], |E| = e.

(45)

The following theorem characterizes the file-size bound under passive eavesdropping.
Theorem 7.1: The file-size of a secure exact-repair deterministic generalized regenerating code having parameters
{(n, k, d), (α, β), (m, `), (e)} is upper bounded by
B

(s)

≤ `(k − e)α + (m − `)

k−1
X
i=e

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

(46)

27

Proof: Without loss of generality, let us assume that E = {1, 2, . . . , e}. Using (45), the file-size B (s) is given
by
B (s) = H(F (s) ) = H(F (s) |{Yi , Ui , i ∈ E}) ≤ H(F (s) |{Yi i ∈ E}).

(47)

From (40), we further get that
H(F (s) |{Yi i ∈ E}) ≤ H({Yi , i ∈ {e + 1, . . . , k}}|{Yi i ∈ E}).

(48)

Combining (47) and (48), we get
B (s) ≤ H({Yi , i ∈ {e + 1, . . . , k}}|{Yi i ∈ E})
k
X
=
H(Yi |Y1 , . . . , Yi−1 )

=

i=e+1
k X
m
X

(49)
(50)

H(Yi,j |Yi,1 , . . . , Yi,j−1 , Y1 , . . . , Yi−1 )

(51)

i=e+1 j=1

=

k X
`
X

H(Yi,j |Yi,1 , . . . , Yi,j−1 , Y1 , . . . , Yi−1 ) +

i=e+1 j=1

k
m
X
X

H(Yi,j |Yi,1 , . . . , Yi,j−1 , Y1 , . . . , Yi−1 )

i=e+1 j=`+1

(52)
≤ `(k − e)α +

k
m
X
X

H(Yi,j |Yi,1 , . . . , Yi,j−1 , Y1 , . . . , Yi−1 )

(53)

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

(54)

i=e+1 j=`+1

≤ `(k − e)α +

m
k
X
X
i=e+1 j=`+1

= `(k − e)α + (m − `)

k−1
X

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

(55)

i=e

where (54) follows from (41)-(43). This completes the proof of the upper bound.
As before, whenever d > 0, we associate the operating point α = dβ with the minimum repair bandwidth secure
regenerating codes. Construction 5.2 can be easily adapted to construct optimal secure exact repair codes at the
MBR point. In the modified construction, one combines ` secure MDS codes for the wiretap-II channel [32][33],
and (m − `) classical exact-repair secure MBR codes [31][34]. The construction and proof of optimality are similar
to Construction 5.2; we avoid a full description here. A pictorial illustration of the secure code construction appears
in Fig. 15. Finally, we note that the bound in (55) is weak at the
it is known that classical
PMSR point, since +
exact-repair secure MSR codes in general cannot achieve file size k−1
min{α,
(d
−
i)
β} = (k − e)α [37, 38].
i=e
It is an interesting question as to whether the analysis like in [37, 38] can be used to provide a tighter bound for
secure MSR codes under the framework of GRCs considered in this paper.
VIII. C ONCLUSIONS
To conclude, we study the problem of storage-overhead vs repair-bandwidth overhead in clustered storage systems.
The notion of clustering is used in both data collection and node repair. For data collection, we require retrievability
using content from any set of k clusters. For node repair, we take the help of surviving local nodes in the host
cluster, as well as from other remote clusters. We first characterize the optimal file-size that is achievable while
ignoring intra-cluster bandwidth costs, and then obtain bounds on intra-cluster bandwidth costs that is needed to
achieve this file-size. Our results show that while it is beneficial to increase the number of local helper nodes (`)
during repair in order to simultaneously improve both storage and inter-cluster bandwidth costs, increasing ` has an
adverse effect on intra-cluster repair bandwidth. Our bounds on file-size and intra-cluster bandwidth give guidelines
for choosing the desired number of local helper nodes in practice, based on the relative costs of the various metrics.

28

Cluster 1

Cluster 2

Same as before,
with no security

Cluster n

generates

Secure codes for wiretap-II

MDS code

Secure MBR codes

Pick Secure Codes here

Invertible Matrix

Fig. 15. Illustration of the exact repair secure code construction. We first stack ` secure-MDS codes for the wiretap-II channel, and (m − `)
classical secure MBR codes, and then transform each row via the invertible matrix A. The first ` rows of the matrix A generate an [m, `]
MDS code.

We present constructions of optimal exact and functional repair codes, which enable operating points for clustered
systems that are not achievable via previously known coding solutions. We also analyze the resilience of the system
against passive eavesdropping.
Two key questions remain at the end of this work. Firstly, our bounds on intra-cluster bandwidth are derived
under the assumption of functional repair. It is unclear if these bounds hold under exact repair; specifically at the
minimum-inter-cluster bandwidth operating point. The exact repair constructions in this paper, although they have
optimal file-size (and inter-cluster bandwidth), incur the maximum possible intra-cluster bandwidth. Secondly, the
bound on any one of the intra-cluster bandwidth related parameters (say, γ ) was derived without limiting the other
two other parameters (γ 0 , `0 ). It is of special interest to know the simultaneously optimality of the the bounds in
(2) and (3). We believe that a first step in this direction would be to prove a converse statement (achievability) to
(3). Achievability of (3) is indeed suggested by RLNC-based simulations.
Finally, model extensions of interest include the case of simultaneous recovery from multiple node failures in
a given cluster. While studying recovery for multiple node failures, it is of interest to consider presence of local
parity relations in each cluster, even when d > 0.
R EFERENCES
[1] “AWS storage services overview,” Amazon Web Services Whitepapers, 2016. [Online]. Available:
https://d0.awsstatic.com/whitepapers/Storage/AWS%20Storage%20Services%20Whitepaper-v9.pdf
[2] “Azure storage replication,” Microsoft Azure Documentation. [Online]. Available: https://docs.microsoft.com/
en-us/azure/storage/storage-redundancy
[3] “Netstorage,” Akamai Media Delivery Solutions: Product Brief. [Online]. Available: https://www.akamai.com/
us/en/multimedia/documents/product-brief/netstorage-product-brief.pdf
[4] S. Muralidhar, W. Lloyd, S. Roy, C. Hill, E. Lin, W. Liu, S. Pan, S. Shankar, V. Sivakumar, L. Tang et al., “f4:
Facebooks warm blob storage system,” in Proceedings of the 11th USENIX conference on Operating Systems
Design and Implementation. USENIX Association, 2014, pp. 383–398.
[5] 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.
[6] Y. L. Chen, S. Mu, J. Li, C. Huang, J. Li, A. Ogus, and D. Phillips, “Giza: Erasure
coding objects across global data centers,” in 2017 USENIX Annual Technical Conference (USENIX
ATC 17). Santa Clara, CA: USENIX Association, 2017, pp. 539–551. [Online]. Available: https:
//www.usenix.org/conference/atc17/technical-sessions/presentation/chen-yu-lin
[7] 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.

29

[8] S. Mu, K. Chen, P. Gao, F. Ye, Y. Wu, and W. Zheng, “µlibcloud: Providing high available and uniform
accessing to multiple cloud storages,” in Grid Computing (GRID), 2012 ACM/IEEE 13th International
Conference on. IEEE, 2012, pp. 201–208.
[9] A. Bessani, M. Correia, B. Quaresma, F. André, 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.
[10] 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.
[11] P. F. Oliveira, L. Lima, T. T. V. Vinhoza, J. Barros, and M. Médard, “Coding for trusted storage in untrusted
networks,” IEEE Transactions on Information Forensics and Security, vol. 7, no. 6, pp. 1890–1899, Dec 2012.
[12] 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.
[13] 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.
[14] P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the locality of codeword symbols,” Information
Theory, IEEE Transactions on, vol. 58, no. 11, pp. 6925–6934, 2012.
[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] Y. Hu, X. Li, M. Zhang, P. P. Lee, X. Zhang, P. Zhou, and D. Feng, “Optimal repair layering for erasure-coded
data centers: From theory to practice,” arXiv preprint arXiv:1704.03696, 2017.
[17] J. Sohn, B. Choi, S. W. Yoon, and J. Moon, “Capacity of clustered distributed storage,” CoRR, vol.
abs/1610.04498, 2016. [Online]. Available: http://arxiv.org/abs/1610.04498
[18] B. Gastón, J. Pujol, and M. Villanueva, “A realistic distributed storage system: the rack model,” arXiv preprint
arXiv:1302.5657, 2013.
[19] 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, July 2013,
pp. 1237–1241.
[20] G. Calis and O. O. Koyluoglu, “Architecture-aware coding for distributed storage: Repairable block failure
resilient codes,” CoRR, vol. abs/1605.04989, 2016. [Online]. Available: http://arxiv.org/abs/1605.04989
[21] K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Enabling node repair in any erasure code for distributed storage,”
in Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on, July 2011.
[22] N. B. Shah, K. V. Rashmi, and P. V. Kumar, “A flexible class of regenerating codes for distributed storage,”
in 2010 IEEE International Symposium on Information Theory, June 2010, pp. 1943–1947.
[23] Q. Yu, K. W. Shum, and C. W. Sung, “Tradeoff between storage cost and repair cost in heterogeneous
distributed storage systems,” Transactions on Emerging Telecommunications Technologies, vol. 26, no. 10, pp.
1201–1211, 2015.
[24] T. Ernvall, S. El Rouayheb, C. Hollanti, and H. V. Poor, “Capacity and security of heterogeneous distributed
storage systems,” IEEE Journal on Selected Areas in Communications, vol. 31, no. 12, pp. 2701–2709, 2013.
[25] S. Akhlaghi, A. Kiani, and M. R. Ghanavati, “Cost-bandwidth tradeoff in distributed storage systems,”
Computer Communications, vol. 33, no. 17, pp. 2105–2115, 2010.
[26] J. Li, S. Yang, X. Wang, and B. Li, “Tree-structured data regeneration in distributed storage systems with
regenerating codes,” in INFOCOM, 2010 Proceedings IEEE. IEEE, 2010, pp. 1–9.
[27] Y. Wang, D. Wei, X. Yin, and X. Wang, “Heterogeneity-aware data regeneration in distributed storage systems,”
in IEEE INFOCOM 2014 - IEEE Conference on Computer Communications, April 2014, pp. 1878–1886.
[28] R. Koetter and M. Médard, “An algebraic approach to network coding,” IEEE/ACM Transactions on
Networking, vol. 11, no. 5, pp. 782–795, Oct 2003.
[29] 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,
Oct 2006.
[30] Y. Wu, “Existence and construction of capacity-achieving network codes for distributed storage,” IEEE Journal
on Selected Areas in Communications, vol. 28, no. 2, pp. 277–288, February 2010.
[31] S. Pawar, S. E. Rouayheb, and K. Ramchandran, “Securing dynamic distributed storage systems against
eavesdropping and adversarial attacks,” IEEE Transactions on Information Theory, vol. 57, no. 10, pp. 6734–

30

6753, Oct 2011.
[32] L. H. Ozarow and A. D. Wyner, WireTap Channel II, 1984.
[33] A. Subramanian and S. W. McLaughlin, “MDS codes on the erasure-erasure wiretap channel,” CoRR, vol.
abs/0902.3286, 2009. [Online]. Available: http://arxiv.org/abs/0902.3286
[34] N. B. Shah, K. V. Rashmi, and P. V. Kumar, “Information-theoretically secure regenerating codes for distributed
storage,” in Global Telecommunications Conference (GLOBECOM 2011), 2011 IEEE, Dec 2011, pp. 1–5.
[35] 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,” Information Theory, IEEE Transactions on, vol. 57,
no. 8, pp. 5227–5239, 2011.
[36] N. B. Shah, K. V. Rashmi, P. V. Kumar, and K. Ramchandran, “Distributed storage codes with repair-bytransfer and nonachievability of interior points on the storage-bandwidth tradeoff,” IEEE Transactions on
Information Theory, vol. 58, no. 3, pp. 1837–1852, March 2012.
[37] B. Sasidharan, P. V. Kumar, N. B. Shah, K. Rashmi, and K. Ramachandran, “Optimality of the product-matrix
construction for secure msr regenerating codes,” in Communications, Control and Signal Processing (ISCCSP),
2014 6th International Symposium on. IEEE, 2014, pp. 10–14.
[38] A. S. Rawat, “A note on secure minimum storage regenerating codes,” arXiv preprint arXiv:1608.01732, 2016.

