Centralized Multi-Node Repair Regenerating Codes
Marwen Zorgui, Student Member, IEEE, Zhiying Wang, Member, IEEE

arXiv:1706.05431v1 [cs.IT] 16 Jun 2017

Abstract
In a distributed storage system, recovering from multiple failures is a critical and frequent task that is crucial for maintaining
the system’s reliability and fault-tolerance. In this work, we focus on the problem of repairing multiple failures in a centralized
way, which can be desirable in many data storage configurations, and we show that a significant repair traffic reduction is possible.
The fundamental functional tradeoff between the repair bandwidth and the storage size for functional repair is established. Using
a graph-theoretic formulation, the optimal tradeoff is identified as the solution to an integer optimization problem, for which a
closed-form expression is derived. Expressions of the extreme points, namely the minimum storage multi-node repair (MSMR)
and minimum bandwidth multi-node repair (MBMR) points, are obtained. We describe a general framework for converting single
erasure minimum storage regenerating codes to MSMR codes. The repair strategy for e failures is similar to that for single failure,
however certain extra requirements need to be satisfied by the repairing functions for single failure. For illustration, the framework
is applied to product-matrix codes and interference alignment codes. Furthermore, we prove that functional MBMR point is not
achievable for linear exact repair codes. We also show that exact-repair minimum bandwidth cooperative repair (MBCR) codes
achieve an interior point, that lies near the MBMR point, when k ≡ 1 mod e, k being the minimum number of nodes needed
to reconstruct the entire data. Finally, for k > 2e, e | k and e | d, where d is the number of helper nodes during repair, we show
that the functional repair tradeoff is not achievable under exact repair, except for maybe a small portion near the MSMR point,
which parallels the results for single erasure repair by Shah et al.
Index Terms
Regenerating codes, distributed storage, multi-node repair, minimum storage, minimum bandwidth.

I. I NTRODUCTION
Ensuring data reliability is of paramount importance in modern storage systems. Reliability is typically achieved through the
introduction of redundancy. Traditionally, simple replication of data has been adopted in many systems. For instance, Google
file systems opted for a triple replication policy [12]. However, for the same redundancy factor, replication systems fall short on
providing the highest level of reliability. On the other hand, erasure codes can be optimal in terms of the redundancy-reliability
tradeoff. In erasure codes, a file of size M is divided into k fragments, each of size M
k . The k fragments are then encoded
into n fragments using an (n, k) maximum distance separable (MDS) code and then stored at n different nodes. Using such
a scheme, the data is guaranteed to be recovered from any n − k node erasures, providing the highest level of worst-case
data reliability for the given redundancy. However, traditional erasure codes suffer from high repair bandwidth. In the case
of a single node erasure, they require downloading the entire data of size M to repair a single node storing a fragment of
size M
k . This expansion factor made erasure codes impractical in some applications using distributed storage systems. In the
last decade, the repair problem has gained increasing interest and motivated the research for a new class of erasure codes
with better repair capabilities. The seminal work in [10] proposed a new class of erasure codes, called regenerating codes,
that optimally solve the repair bandwidth problem. Interestingly, the authors in [10] proved that one can significantly reduce
the amount of bandwidth required for repair and the bandwidth decreases as each node stores more information. Formally,
suppose any k out of n nodes are sufficient to recover the entire file of size M. Assuming that d nodes, termed helpers, are
participating in the repair process, denoting the storage capacity of each node by α and the amount of information downloaded
from each helper by β, then, an optimal (M, n, k, d, α, β) regenerating code satisfies
M=

k−1
X

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

(1)

i=0

The equation describes the fundamental tradeoff between the storage capacity α and the bandwidth β. Two extreme points
can be obtained from the tradeoff. Minimum storage regenerating (MSR) codes correspond to the best storage efficiency with
α= M
k , while minimum bandwidth regenerating (MBR) codes achieve the lowest possible bandwidth at the expense of extra
storage per node.
If we recover the exact same information as the failed node, we call it exact repair, otherwise we call it functional repair.
Using network coding [2], [16], it is possible to construct functional regenerating codes satisfying (1) [10]. Following the
seminal work in [10], there has been a flurry of interest in designing exact regenerating codes achieving the optimal tradeoff,
focusing mainly on the extreme MSR and MBR points, e.g., [5], [14], [23], [28], [30], [33], [35], [37], [39], [42]. For interior
M. Zorgui and Z. Wang are with the Center for Pervasive Communications and Computing, University of California at Irvine, Irvine, CA 92697 USA
(e-mail: mzorgui@uci.edu, zhiying@uci.edu). Part of this work has been presented in the 54th Annual Allerton Conference on Communication, Control, and
Computing (Allerton), 2016 [43] and IEEE International Symposium on Information Theory, 2017 [44].

points that are between the MBR and MSR points in the tradeoff of (1), [29] showed that most points are not achievable for
exact repair.
The aforementioned references, as most of the studies on regenerating codes in the literature, focus on the single erasure
repair problem. However, in many practical scenarios, such as in large scale storage systems, multiple failures are more frequent
than a single failure. Moreover, many systems (e.g., [4]) apply a lazy repair strategy, which seeks to limit the repair cost of
erasure codes: instead of immediately repairing every single failure, one waits until e erasures occur, e ≤ n − k, then, the
repair is done by downloading the equivalent of the total information in the system to regenerate the erased nodes. However,
a natural question of interest is, whether we can reduce the amount of download in such scenarios.
In this work, we consider the repair problem of multiple erasures in a centralized manner. The framework requires the content
of any k out of n nodes in the system to be sufficient to reconstruct the entire data. Upon failure of e nodes in the system,
the repair is carried out by contacting any d nodes (helpers) out of the n − e available nodes, d ≤ n − e, and downloading
β amount of information from each of the d helpers. Our objective is to characterize the functional repair tradeoff between
the storage per node α and the repair bandwidth β under the centralized multiple failure repair framework. Under functional
repair, the repaired nodes are not necessarily the same as the failed nodes. Exact-repair however requires that the replacement
nodes recover exactly the content of the failed nodes. We also seek to investigate the achievability of the functional tradeoff
under exact repair.
The centralized repair framework is applicable to many practical situations. Indeed, there are situations in which, due to
architectural constraints, it is more desirable to regenerate the lost nodes at a central server before dispatching the regenerated
content to the replacement nodes [4]. For instance, one can think of a rack-based node placement architecture [27] in which
failures frequently occur to nodes corresponding to a particular rack. In this scenario, a centralized repair of the entire rack
is favorable to repairing the rack on the per-node basis. Furthermore, [27] showed that a centralized repair framework can
have interesting applications to communication-efficient secret sharing. Finally, centralized repair can be used in a broadcast
network, where the repair information is transmitted to all replacement nodes (e.g. [17]). For the above reasons, characterizing
the repair-bandwidth tradeoff under the centralized repair framework is important from both an information-theoretic and also
a practical perspective.
A. Related work
Cooperative regenerating codes (also known as coordinated regenerating codes) have been studied to address the repair of
multiple erasures [18], [31] in a distributed manner. In this framework, each replacement node downloads information from d
helpers in the first stage. Then, the replacement nodes exchange information between themselves before regenerating the lost
nodes. Cooperative regenerating codes achieving the extreme points on the cooperative tradeoff have been developed: minimum
storage cooperative regenerating (MSCR) codes [20], [31] and minimum bandwidth cooperative regeneration (MBCR) codes
[36]. In [20], the authors showed that, given an instance of linear exact MSR codes, it is possible to construct an instance of
exact linear MSCR codes for 2 erasures.
The number of nodes involved in the repair of a single node, known as locality, is another important measure of node repair
efficiency [13]. Various bounds and code constructions have been proposed in the literature [13], [34]. Recent works have
investigated the problem of multiple node repair under locality constraints [24], [32].
The problem of centralized repair has been considered in [6], in which the authors restricted themselves to MDS codes,
corresponding to the point of minimum required storage per node. [6] showed the existence of MDS codes with optimal repair
bandwidth in the asymptotic regime where the storage per node (as well as the entire information) tends to infinity. In [38],
the authors proved that Zigzag codes, which are MDS codes designed initially for repairing optimally single erasures [35],
can also be used to optimally repair multiple erasures in a centralized manner. In [27], the authors independently proved that
multiple failures can be repaired in Zigzag codes with optimal bandwidth. Moreover, [27] defines the minimum bandwidth
multi-node repair codes as codes satisfying the property of having the downloaded information dβ matching the entropy of e
nodes. Based on that, the authors derived lower bound on β for systems having a certain entropy accumulation property and
then showed achievability of the minimum bandwidth using MBCR codes. However, the optimal storage size per node α is not
known under these codes. In [41], the authors presented an explicit MDS code construction that provide optimal repair for all
e ≤ n−k and k ≤ d ≤ n−e simultaneously. The authors in [17] studied the problem of broadcast repair for wireless distributed
storage which is equivalent to the model we study in this paper. It is worth pointing out that the previous constructions are
for high-rate codes, with large subpacketization α. For scalar MDS codes, i.e., β = 1, it is shown that exact-repair cannot be
achieved when nk > 12 + n2 . In [21], the authors presented an approach that enables single erasure MSR codes to recover from
multiple failures simultaneously with optimal bandwidth. Based on simulation, [21] showed that their approach can provide
efficient recovery of most of the failure patterns, but not all of them. The repair problem of Reed Solomon codes has been
investigated in [15]. Repairing multiples failures in Reed Solomon codes has been investigated in [8], [9]. In [7], the authors
proved that the interference alignment MSR construction of [33], originally designed for repairing any single node failure,
can recover from multiple failures in a cooperative way. Specifically, it is shown that any set of systematic nodes, any set of
parity-check nodes, or any pair of nodes can be repaired cooperatively with optimal bandwidth.

MSMR point

MBMR point

e=1

X [25], [33], [35]

X [25]

1<e<k

X [6], [41], [Sections
IV-B, IV-C,IV-D]

✗ (for linear codes)
[Section V]

e≥k

X Section IV-A

XSection IV-A

Interior points
✗, except maybe for a small portion near the MSMR
point [29].
• if k ≡ 1 mod e: an interior point near the MBMR
point is achievable [Section V-D].
• if e | k, e | d, k > 2e : ✗, except maybe for a small
portion near the MSMR point [Section VI].
X Section IV-A

TABLE I: Summary of achievability results of functional repair tradeoff under exact repair for an (n, k, d, e, α, β) distributed
storage system. The symbol X denotes achievability while ✗ denotes non-achievability, both of which are under exact repair.

B. Contributions of the paper
The main contributions of this paper are summarized as follows.
• We first establish the explicit tradeoff between the repair bandwidth and the storage size for functional repair. We obtain
the tradeoff using information flow graphs. From the functional tradeoff, we characterize the minimum storage multi-node
repair (MSMR) point, and the minimum bandwidth multi-node repair (MBMR) point.
• When the number of erasures e satisfies e ≥ k, k being the minimum number of nodes needed to reconstruct the entire
data, the tradeoff reduces to a single point, for which we provide an explicit code construction.
• We formalize a construction for exact-repair MSMR codes. Given an instance of an exact linear MSR code, we present
a framework to construct an instance of an exact linear MSMR regenerating code. We note here that [21] and [20]
used similar approach for their numerical results and MSCR codes, respectively. Based on this framework, we study the
product-matrix (PM) MSR codes [25] and the interference alignment (IA) construction in [33]. We prove the existence
of PM and IA MSMR codes for any number of failures e, e ≤ n − k. Moreover, for the IA code, we prove that one can
always efficiently recover from any set of e ≤ n−k node failures as long as the failed nodes are either all systematic nodes
or all parity nodes; for failures including both systematic and parity nodes, we derive explicit design conditions under
which exact recovery is ensured, for some particular system parameters. We note here that unlike previous constructions,
our codes are applicable when the code rate is low and use small subpacketization size of α = k − 1 or k.
• We prove that, to our surprise, functional minimum bandwidth multi-node repair point is not achievable for linear exact
repair codes, while linear codes achieve such point for single erasure [25].
• We show that exact-repair minimum bandwidth cooperative repair (MBCR) codes achieve an interior point, that lies near
the MBMR point, when k ≡ 1 mod e.
• We show that the functional repair tradeoff is not achievable under exact repair for interior points between MBMR and
MSMR points, except for maybe a small portion near the minimum storage multi-node repair point, which parallels the
results for single erasure repair [29], for e | k, e | d, k > 2e. The achievability of the functional tradeoff under exact repair
is summarized in Table I.
• Finally, we study the repair problem of multiple erasures in MBR regenerating codes and present an MBR construction
with optimal repair, simultaneously for varying number of helpers and varying number of erasures.
C. Organization of the paper
The remainder of the paper is organized as follows. A description of the system model is provided in Section II. The
analysis of the functional tradeoff is detailed in Section III. Section IV-A describes our code construction for the case e ≥ k. In
Section IV-B, we describe the MSMR codes framework and its application to the product-matrix and the interference alignment
codes. We prove the non-achievability of MBMR codes under linear exact repair in Section V. The non-achievability of the
interior points under exact repair is investigated in Section VI. The repair of multiple erasures for an MBR code is presented
in Section VII. Section VIII draws conclusions.
Notation. The superscript t is used to denote the transpose of a matrix. For a matrix A, |A| denotes its determinant and
Ai,j refers to its entry at position (i, j). ei denotes the standard basis vector whose dimension is clear from the context. For a
set A, A\{i} denotes the resultant set after removing item i, while |A| denotes the size of A. In denotes the identity matrix
of size n and diag{λ1 , . . . , λn } denotes the diagonal matrix with the corresponding elements. [n] denotes the set of elements
{1, . . . , n}. The symbol δ{j=l} is 1 if j = l and 0 otherwise. The notations e | k and e ∤ k are used to denote whether k is a
multiple of e, or not, respectively. u = [u1 , . . . , um ] denotes a vector of length m.

II. S YSTEM

MODEL AND MAIN RESULTS

The centralized mutli-node repair problem is characterized by parameters (M, n, k, d, e, α, β). We consider a distributed
storage system with n nodes storing M amount of information. The data elements are distributed across the n storage nodes
such that each node can store up to α amount of information. The system should satisfy the following two properties:
• Reconstruction property: a data collector (DC) connecting to any k ≤ n nodes should be able to reconstruct the entire
data.
• Regeneration property: upon failure of e nodes, a central node is assumed to contact d helpers, d ≥ k, and download β
amount of information from each of them. New replacement nodes join the system and the content of each is determined
by the central node. β is called the repair bandwidth. The total bandwidth is denoted γ = dβ.
We consider functional repair and exact repair. In the former case, the replacement nodes are not required to be exact copies
of the failed nodes, but the repaired code should satisfy again the above two properties. Our objective is to characterize the
tradeoff between the storage per node α and the repair bandwidth β under the centralized multiple failure repair framework.
On the optimal tradeoff, the minimum bandwidth mutli-node repair (MBMR) point has the minimum possible β, and the
minimum storage mutli-node repair (MSMR) point has the minimum
α.

 possible
In the paper, we will use the notation k = ae + r, such that a = ke and r = k mod e.
We state our main theorems that will be proved in the sequel of the paper. The first result is the explicit functional repair
tradeoff of α and β.
Theorem 2. For fixed system parameters (M, n, k, d, e, α, β), functional regenerating codes satisfying the centralized multinode repair condition exist if and only if
⌈k/e⌉

M ≤ f (u∗ ) =

X

min(u∗i α, (d −

i=1

i−1
X

u∗j )β)

(2)

j=1

where


[k],




[e, . . . , e],


| {z }


 a times
∗
u = [r, e, . . . , e],

| {z }



a times




[e,
.
. . , e, r],

 | {z }

if k ≤ e,
else if k = ae,
else if k = ae + r and α ≤

d+ar−ae
β,
r

(3)

otherwise,

a times

where 0 < r < e.
The next result combines Theorem 5 and 9, that give constructions of MSMR codes for exact repair.
Theorems 5 and 9. There exists interference alignment MSMR codes and product-matrix MSMR codes, defined over large
enough finite field, such that any e ≤ n − k erasures can be optimally repaired.
The next statement is a combination of Theorem 10 and Theorem 11, which states that MBMR point is not achievable for
linear exact repair codes.
Theorems 10 and 11. Exact linear regenerating MBMR codes do not exist when 1 < e < k.
The following result is a combination of Theorem 13 and Theorem 14, shows the non-feasibility of most interior points for
exact repair.
Theorems 13 and 14. For e|d, e|k, k > 2e and any given values of M, exact-repair regenerating codes do not exist for points
lying in the interior of the storage-bandwidth tradeoff, except for maybe a small portion near the MSMR point.
III. F UNCTIONAL

STORAGE - BANDWIDTH TRADEOFF

In this section, we study the fundamental tradeoff between the storage size α and the repair bandwidth β for e erasures
under functional repair. We use the technique of evaluating the minimum cut of a multi-cast information flow graph similar to
the single erasure codes [10] and the cooperative regenerating codes [31].
A. Information flow graphs
The performance of a storage system can be characterized by the concept of information flow graphs (IFGs). Our constructed
IFG depicts the amount of information transferred, processed and stored during repair. We design our IFG with the following
different kinds of nodes (see Figure 1). It contains a single source node s that represents the source of the data object. Each
storage node i of the IFG is represented by two distinct nodes: an input storage node xiin and an output storage node xiout . Each
node xiout is connected to its input node xiin with an edge of capacity α, reflecting the storage constraint of each individual
node. The information flow graph is formed with n initial nodes, each with storage size α connected to the source node with

Fig. 1: Example of an information flow graph: k = 3, d = 4, n = 6, e = 2. The unlabeled edges have capacity ∞.
Nodes 1 and 2 are repaired in the first stage and nodes 3 and 4 are repaired in the second stage. A data collector connecting
to any 3 nodes should be able to recover the entire information.
edges of capacity ∞. The IFG evolves with time. Upon failure of e nodes, e new nodes simultaneously join the system. Each
of the replacement nodes xj is similarly represented by an input node xjin and an output node xjout , linked with an edge of
capacity α. To model the centralized repair nature of the system, we add a virtual node xivirt that links the d helpers to the
new storage nodes. Likewise, the virtual node consists of an input node xivirt,in and an output node xivirt,out . The input node
xivirt,in is connected to the d helpers with edges each of capacity β. The output node xivirt,out is connected to the input node
xivirt,in with an edge of capacity eα, reflecting to the overall size of the data to be stored in the new replacement nodes. The
output node xivirt,out is then connected to the input nodes xjin of the replacement nodes, with edges of capacity ∞.
Each IFG represents one particular history of the failure patterns. The ensemble of IFGs is denoted by G(n, k, d, e, α, β).
For convenience, we drop the parameters whenever it is clear from the context. Given an IFG G ∈ G, there are nk different
data collectors connecting to k nodes in G. The set of all data collector nodes in a graph G is denoted by DC(G). For an IFG
G ∈ G and a data collector t ∈ DC(G), the minimum cut (min-cut) value separating the source node s and the data collector
t is denoted by mincutG (s, t).

B. Network coding analysis
The key idea behind representing the repair problem by an IFG lies in the observation that the repair problem can be cast
as a multicast network coding problem [10]. Celebrated results from network coding [2], [16] are then invoked to establish
the fundamental limits of the repair problem.
According to the max-flow bound of network coding [2], for a data collector to be able to reconstruct the data, the min-cut
separating the source to the data collector should be larger or equal to the data object size M. Considering all possible data
collectors and all possible failure patterns, the following condition is necessary and sufficient for the existence of regenerating
codes satisfying the reliability constraint:
min min mincutG (s, t) ≥ M.

(4)

G∈G t∈DC(G)

Analyzing the minimum cut of all IFGs result in the following theorem.
Theorem 1. For fixed system parameters (M, n, k, d, e, α, β), regenerating codes satisfying the centralized multi-node repair
condition exist if and only if


g
i−1
X
X
uj )β) , min f (u),
min(ui α, (d −
M ≤ min 
i=1

where

f (u) =

(5)

u∈P

u∈P

g
X
i=1

min(ui α, (d −

j=1

i−1
X

uj )β),

(6)

g
X

(7)

j=1

P = {u : 1 ≤ ui ≤ e such that

i=1

ui = k, g ≤ k}.

We note that (5) was also independently developed in [27].
Proof: Define a recovery scenario u ∈ P as follows. A data collector DC connects to a subset of k nodes {xiout : i ∈ I},
where I is the subset of contacted nodes. The size of the support of u corresponds to the number of repair groups of size e
taking part in the reconstruction process, while ui corresponds to the number of nodes contacted from repair group i.
As all incoming edges of DC have infinite capacity, we only examine cuts (Ū , U ) with S ∈ U and {xiout : i ∈ I} ⊆ Ū .
Every directed acyclic graph has a topological sorting, which is an ordering of its vertices such that the existence of an edge
x → y implies x < y. We recall that nodes within the same repair group are repaired simultaneously. Since nodes are sorted,
nodes considered at the i−th step cannot depend on nodes considered at j−th step with j > i.
Considering the i-th group, consider the case | xiin ∈ U | = m and the remaining nodes are such that xiin ∈ Ū .
• if xiin ∈ U , then the contribution of each node is α. The overall contribution of these nodes is mα.
• else: xiin ∈ Ū , then if xivirt,out ∈ U , the contribution of this node is ∞. Thus, we only consider the case xivirt,out ∈ Ū . Then,
we discuss two cases
i
• if xvirt,in ∈ U , the contribution to the cut is eα.
i−1
P
uj edge come from output nodes in Ū . Thus,
• else, since the i-th group is the topologically i-th repair group, at most
j=1

the contribution is (d −

i−1
P

uj )β. Thus, the contribution of this node is min(eα, (d −

i−1
P

j=1

j=1

we do not need to account for other similar nodes.

uj )β). Note that xivirt,out ∈ Ū ,

Thus, if m = ui , the contribution of the i-th repair group is ui α. If m < ui , the contribution is mα + min(eα, (d −
which can be reduced to min(eα, (d −

i−1
P

uj )β) if m = 0. Thus, to lower the cut, either m = ui in the case of (d −

i−1
P

uj )β),

j=1
i−1
P

uj )β >

j=1

j=1

ui α or m = 0 otherwise. Thus, the total contribution of the i-th repair group is
min(ui α, (d −

i−1
X

uj )β).

j=1

Finally, summing all contributions from different repair groups and considering the worst case for u ∈ P implies that


min min mincutG (s, t) = min 
G∈G t∈DC(G)

u∈P

g
X

min(ui α, (d −

i−1
X
j=1

i=1



uj )β) ,

with P defined as in (7). Therefore, the existence of regenerating codes is guaranteed by [2] as long as
M ≤ min min mincutG (s, t)1 .
G∈G t∈DC(G)

C. Solving the minimum cut problem
In this section, we derive the structure of the optimal scenario u in (5) for any set of parameters (α, β). For instance, we
show that for ae < k ≤ (a + 1)e, the number of optimal repair groups g ∗ (the support of u) is equal to a + 1. The result is
formalized in the following theorem. Recall that we denote a = ⌊k/e⌋, r = k mod e.
Theorem 2. For fixed system parameters (M, n, k, d, e, α, β), functional regenerating codes satisfying the centralized multinode repair condition exist if and only if
⌈k/e⌉

M ≤ f (u∗ ) =

X

min(u∗i α, (d −

i=1

i−1
X

u∗j )β)

(8)

j=1

where

[k],





[e, . . . , e],


| {z }


 a times
u∗ = [r, e, . . . , e],

| {z }



a times




[e, . . . , e, r],

 | {z }

if k ≤ e,
else if k = ae,
else if k = ae + r and α ≤

d+ar−ae
β,
r

(9)

otherwise,

a times

1 Strictly speaking, this is only valid when the number of failures/repairs is bounded. A rigorous proof is required to drop the boundedness assumption as
[31], [40]

where 0 < r < e.
We denote by [v, u, w] the vector that is the concatenation of the vectors v, u, w. The next lemma shows that the minimum
cut can be obtained by optimizing any subsequence of u first. The proof follows directly from the definition of f () in (5) and
is omitted.
P
P
Lemma 1. Consider vectors v, w, u, u′ such that i ui = i u′i . If
f (u) ≥ f (u′ ),

(10)

f ([v, u, w]) ≥ f ([v, u′ , w]).

(11)

then,

In proving the result of Theorem 2, we first characterize the optimal solution in the case of k ≤ e. Insight and intuition
gained from the first case are used to motivate and derive the general solution. We first state the following lemma, which
represents a key step towards proving our result.
Lemma 2. Let α, β, u1 , u2 , d, e, l be non-negative reals such that u1 + u2 = s ≤ e, then the following inequality holds
f ([u1 , e, . . . , e, u2 ]) ≥ min(f ([s, e, . . . , e]), f ([e, . . . , e, s])),
| {z }
| {z }
| {z }
l times

where f (u) is defined as in (6).

l times

l times

Proof: To prove the result, we cast it as an optimization problem:
minimize
u=[u1 ,u2 ]

subject to

min(u1 α, dβ) +

l−1
X

min(eα, (d − ie − u1 )β) + min(u2 α, (d − (l + 1)e − u1 )β)

i=0

0 ≤ u1 ≤ s,
0 ≤ u2 ≤ e,
u1 + u2 = s.

(12)

Substituting u2 by s − u1 in (12), using the identity min(a, b) =
equivalent to

minimize − u1 lβ − |u1 α − dβ| −
u1

subject to

l−1
X

a+b−|a−b|
2

and after eliminating constant terms, (12) becomes

|eα − dβ + ieβ + u1 β| − |sα − u1 (α − β) − (d − le)β|

i=0

0 ≤ u1 ≤ s.

(13)

The objective function in (13), as a function of u1 , is concave on the interval [0, s]. The concavity is due to the convexity
of x → |x|. Therefore, the minimum is achieved at one of the extreme values. Equivalently, u∗1 = s or u∗1 = 0.
1) Case k ≤ e: In this scenario, connecting to k nodes from the same repair group yields the worst case scenario from an
information flow perspective. Given a particular repair scenario characterized by a vector u, for any two adjacent repair groups
(i.e., two adjacent entries in u) with u1 and u2 nodes respectively, we have u1 + u2 ≤ e. One can combine these two groups
into a single repair group to achieve a lower cut value. Indeed, from the cut expression in (5), the contribution of the initial
set [u1 , u2 ] to the cut is min(u1 α, lβ) + min(u2 α, (l − u1 )β), for some l. After combining the groups into a single repair
group, the contribution of the newly formed repair group is min((u1 + u2 )α, lβ), which is lower than the initial contribution
by virtue of Lemma 2, thus achieving a lower cut. This means that starting from an IFG, we construct a new IFG that has one
less repair group and lower min-cut value. This process can be repeated until we end up with a single repair group consisting
of k ≤ e nodes, which corresponds to the minimum cut over all graphs in this case.
Therefore, the tradeoff in (5) is simply characterized by M ≤ min(kα, dβ). Moreover, αMSMR = αMBMR = M
k
and βMSMR = βMBMR = M
d . Equivalently, the functional storage bandwidth tradeoff reduces to a single point given
M
by (αMSMR , βMSMR ) = (αMBMR , βMBMR ) = ( M
k , d ).
2) Case e < k: Motivated by the previous case, the intuition is that, given a scenario u, one should form a new scenario
which exhibits as many groups of size e as possible. Subsequently, one constructs a scenario u such that all its entries, except
maybe one entry, are equal to e. Lemma 2 addresses the case u1 + u2 ≤ e. Generalizing it to the case where e ≤ u1 + u2 ≤ 2e
follows the same approach.
Lemma 3. Assume that u1 + u2 = e + s and 0 ≤ u1 , u2 , s ≤ e. Then, the following inequality holds

f ([u1 , e, . . . , e, u2 ]) ≥ min(f ([s, e, . . . , e]), f ([e, . . . , e, s])),
| {z }
| {z }
| {z }
l times

where f (u) is defined as in (6).

l+1 times

(14)

l+1 times

Proof: First, we notice that u1 = e + s − u2 ≥ s as u2 ≤ e. Then, the proof follows along similar lines as that of Lemma 2
by replacing the constraint in (13) by s ≤ u1 ≤ e.
For a fixed β, we denote the min-cut corresponding to u = [e, . . . , e, r, e, . . . , e], as a function of α, by Cj (α), j = 0, . . . , a.
| {z } | {z }
jtimes

a−j times

As will be shown later in the proof of Theorem 2, a careful analysis of the behavior of the a + 1 different scenarios Cj (α) is
needed to determine the overall optimal scenario leading the lowest minimum cut. We state the result in the following lemma,
whose proof is relegated to Appendix A.
Lemma 4. There exists a point αc (a) ∈ [ de β, dr β] such that, for any 0 ≤ j ≤ a,
(
≥ C0 (α), if α ≤ αc (a),
Cj (α)
≥ Ca (α), if α ≥ αc (a),

(15)

with
d + ar − ae
β.
(16)
r
Proof of Theorem 2: Now that we have the necessary machinery, we proceed as follows: given any scenario u, we keep
combining and/or changing repair groups by means of successive applications of Lemma 2 and Lemma 3 on subsequences of
u until we can no longer reduce the minimum cut. By Lemma 1 we reduced the overall minimum cut. The algorithm converges
because at each step, either the number of repair groups in u is reduced by one, or the number of repair groups of full size e
is increased by one. As the number of repair groups is lower bounded by a + 1, and as the number of repair groups of full
size e is upper bounded by a, the algorithm must converge after a finite number of steps. It can be seen then that the above
reduction procedure has a finite number of outcomes, given by
• u = [e, . . . , e] if k = ae,
| {z }
αc (a) =

a times

•

u = [e, . . . , e, r, e, . . . , e] when k = ae + r,
| {z } | {z }
jtimes

a−j times

with 0 < r < e and j ∈ {0, . . . , a}.
Therefore, if e | k, then the optimal scenario corresponds to considering exactly a repair groups. On the other hand, if e ∤ k,
then, it is optimal to consider exactly a + 1 repair groups. However, the optimal position of the repair group with r nodes
needs to be determined. Then, using Lemma 4, the result in Theorem 2 follows.
Example 1. Let u = [1, 3, 2, 3, 2] with e = 3. Then, one can start by reducing the first three repair groups [1, 3, 2]. This leads
to u = [3, 3, 3, 2]. Another approach would be to consider the set [2, 3, 2]. Reducing this set leads to either u = [1, 3, 3, 3, 1] or
u = [1, 3, 1, 3, 3]. Reducing further u = [1, 3, 3, 3, 1] leads to u = [2, 3, 3, 3] or u = [3, 3, 3, 2]. Reducing u = [1, 3, 1, 3, 3] leads
to u = [3, 2, 3, 3] or u = [2, 3, 3, 3]. It remains to compare the cuts given by u = [3, 3, 3, 2], u = [3, 3, 2, 3], u = [3, 2, 3, 3]
and u = [2, 3, 3, 3]. Following Theorem 2, either u = [2, 3, 3, 3] or u = [3, 3, 3, 2] gives the lowest min-cut.
D. Explicit expression of the tradeoff
Having characterized the optimal scenario generating the minimum cut in the last section, we are now ready to state the
admissible storage-repair bandwidth region for the centralized multi-node repair problem, the proof of which is in Appendix B.
Theorem 3. For an (M, n, k, d, e, α, β) storage system, there exists a threshold function α∗ (M, n, k, d, γ, e) such that for
any α ≥ α∗ (M, n, k, d, e, β), regenerating codes exist. For any α < α∗ (M, n, k, d, e, β), it is impossible to construct codes
achieving the target parameters. The threshold function α∗ (M, n, k, d, γ, e) is defined as follows:
• if k ≤ e, then: α∗ = M
k , γ ∈ [M, +∞),
• else if k = ae, then:
(
M
γ ∈ [f0 (a − 1), +∞),
∗
k ,
(17)
α = M−γg
0 (i)
,
γ
∈ [f0 (i − 1), f0 (i)], i = a − 1, . . . 1,
ie

Optimal Tradeoff, M=1,k=8,d=10

0.2

Minimum Bandwidth Multi-node
Repair (MBMR)

0.19

e=1
e=2
e=3
e=4
e=8

Storage per node α

0.18
0.17
0.16

Minimum Storage
Multi-node Repair (MSMR)

0.15
0.14
0.13
0.12
0.01

Interior
Points
0.02

0.03

0.04

0.05

0.06

0.07

0.08

0.09

0.1

Bandwidth from a helper β

Fig. 2: Multi-node repair tradeoff: k = 8, d = 10, M = 1, e ∈ {1, 2, 3, 4, 8}.
• else: k = ae + r with 1 ≤ r ≤ e − 1, then:

M

γ ∈ [fr (a − 1), +∞),

k,
M−γgr (i)
∗
, γ ∈ [fr (i − 1), fr (i)], i = a − 1, . . . 1,
α =
r+ie

M−γgr (0)
dM


, γ ∈ [ (a+1)d−e
, fr (0)],
r
(a+1
2 )

(18)

where

2edM
,
(19)
−k 2 − r2 + e(k − r) + 2kd − e2 (i2 + i) − 2ier
(a − i)(−2r + e + 2d − ae − ei)
gr (i) =
.
(20)
2d
The functional repair tradeoff is illustrated in Figure 2 for multiple values of e ∈ {1, 2, 3, 4, 8} for k = 8, d = 10 and
M = 1.
fr (i) =

Remark 1. In the case of e|k, e|d, the following equality holds for all points on the tradeoff
M=

a−1
X

a−1

min(eα, (d − ie)β) ⇐⇒

i=0

M X
d
min(α, ( − i)β).
=
e
e
i=0

Therefore, the tradeoff between α and β is the same as the single erasure tradeoff of a system with reduced parameters given
k
d
by M
e , e = a and e . The expression of the tradeoff in this case can be recovered from [10] with the appropriate parameters.
We now have the expressions of the two extremal points on the optimal tradeoff. We focus on the case e < k, as otherwise
the optimal tradeoff reduces to a single point.
MSMR. The MSMR point is the same irrespective of the relation between k and e, and it is given by
ed
M
M
, γMSMR =
.
k
k d−k+e
MBMR. Interestingly, the MBMR point depends on whether e divides k or not.
αMSMR =

(21)

• If k = ae, we obtain
γMBMR =

−k 2

dM
2edM
,
=
+ ek + 2kd
da − e a2

(22)

γMBMR
.
(23)
e
The amount of information downloaded for repair is equal to the amount of information stored at the e replacement nodes.
This property of the MBMR point is similar to the minimum bandwidth point in the single erasure case [10] and also the
minimum bandwidth cooperative repair point [31].
αMBMR =

• If k = ae + r, we obtain
dM
2edM
,
(24)
=
(k − r + e)(2d − k + r)
d(a + 1) − e a+1
2
d + ar − ea
.
(25)
αMBMR = γMBMR
rd
This situation is novel for multiple erasures as the e nodes need to store more than the overall downloaded information. This
is an extra cost in order to achieve the low value of the repair bandwidth. However, later we will see that for both e|k and
e ∤ k, the total bandwidth at MBMR is equal to the entropy of the failed nodes (see Lemma 6 and Lemma 11):
γMBMR =

H(W[e] ) = dβ,

(26)

where W[e] is the information stored in e nodes.
Remark 2. From the statement of Theorem 2, we note that if we only consider points between the MSMR and the MBMR
points, then the scenario u = [r, e, . . . , e] always generates the lowest cut.
Remark 3. We compare the centralized repair scheme repairing e nodes to a separate strategy repairing each of the e nodes
separately using single erasure regenerating codes. We fix k, α and M.
Case I: both strategies use d helpers. The separate strategy generates a total bandwidth given by edβ1 , while the centralized
repair generates dβe , where the subscript indicates the number of erasures. For simplicity, we assume that e | k. The case e ∤ k
can be treated in a similar way. For points on the multi-node repair tradeoff, we have
M=

a−1
X

min(eα, (d − je)βe ).

j=0

Consider a point with the same α and d on the single erasure tradeoff, we write

M=

a−1
X

min(eα, (d − je)βe )

j=0

=

k−1
X

min(α, (d − e)β1 )

j=0

=

a−1 X
e−1
X

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

j=0 i=0

≤

a−1
X

e min(α, (d − je)β1 )

j=0

=

a−1
X

min(eα, (d − je)eβ1 ).

j=0

2eM
It follows that βe ≤ eβ1 with equality if and only if e = 1. Moreover, we note that βe,min = −k2 +ek+2kd
≤ eβ1,min =
2eM
.
Therefore,
for
any
storage
capacity
α,
multi-node
repair
requires
strictly
less
bandwidth
than
a
separate
strategy
2
−k +k+2kd
for the same number of helpers d.
Case II: multi-node repair uses d − e + 1 helpers, and separate repair uses d helpers. In this case, the original number of
available nodes that can serve as helpers is assumed to be d, and e ≥ 1 erasures occur within the available nodes. Then a
separate strategy may generate smaller bandwidth for some values of α, as illustrated by Figure 3. However, as d is sufficiently
large, we observe that multi-node repair with d − e + 1 helpers performs better than a separate strategy for all values of
ed
α. Moreover, for MSMR point, the separate repair bandwidth is γseparate = e M
k d−k+1 , and centralized repair bandwidth is
ede
M
γMSMR = k de −k+e . It follows that a centralized repair is always better that a lazy repair strategy, specifically, for e > 2,

γMSMR
d − (e − 1)
=
< 1.
γseparate
d
IV. E XACT MSMR CODES

(27)

CONSTRUCTIONS

In the remaining of the paper, we study exact-repair. In this section, we analyze the case k ≤ k and then construct MSMR
codes when e < k. Later, we study the feasibility of MBMR codes and the interior points under exact repair.

Optimal Tradeoff, M=1,k=7

0.3

e=1,d=9
e=3,d=9
e=3,d=7

0.28

Storage per node α

0.26
0.24
0.22
0.2
0.18
0.16
0.14
0.12
0.5

1

1.5

Total bandwidth from helpers γ

Fig. 3: Centralized multi-node repair vs separate repair strategy: k = 7, M = 1. Separate repair strategy uses d = 9 to repair
3 nodes successively while multi-node repair is plotted for d = 7 and d = 9.
A. Construction when k ≤ e
In the case of k ≤ e, the optimal tradeoff becomes a single point, so our MSMR construction in this section is also an
M
MBMR code. The optimal parameters satisfy α = M
k , β = d and γ = M. We note that the overall repair bandwidth and the
reconstruction bandwidth are the same. Therefore, one can achieve α and γ, by dividing the data into k packets and encoding
them using (n, k) MDS code (for example, a Reed-Solomon code). The repair can be done by downloading the full content
of any k out of d helpers while not contacting d − k nodes. Such repair is asymmetric in nature. We describe one approach
for achieving the repair with equal contribution from d helpers.
1) Divide the original file into kd symbols/packets (that is M = kd) and encode them using an (nd, kd) MDS code.
2) Store the encoded packets at n nodes, such that each node stores α = d encoded packets.
3) For reconstruction, from any k nodes, we obtain kd different symbols. By virtue of the MDS property, we can reconstruct
the data.
4) For repair, each helper node transmits any β = M
d = k symbols. The replacement nodes receive dk different coded
symbols, which are sufficient to reconstruct the whole data and thus regenerate the missing symbols.
Remark 4. The above procedure works for a specific predetermined d. However, it can be generalized to support any value of
d satisfying k ≤ d ≤ n − e. For instance, let δ = lcm(k, k + 1, k + 2, . . . , n − e) (lcm denotes the least common multiple). The
kδ
file of size M is then divided into kδ packets and encoded into nδ with an MDS code. Each node then stores α = M
k = k = δ
δ
M
coded symbols. For repair with d helpers, for any k ≤ d ≤ n − e, each node transmits any β = d = k d coded symbols for
his node. Similarly, it can be seen that reconstruction is always feasible. Note that the constraint of the field size arises from
the need for an (nδ, kδ) MDS code. The field size needs to be no less than nδ, e.g. Reed Solomon codes.
B. Minimum storage codes framework
In the following sub-sections, we discuss an explicit MSMR code construction method using existing MSR codes designed
for single failures. We first describe the general framework, and then present two specific codes.
The framework described in this section has been developed in [21] for numerical simulations. We present it here in
α
a formal way. Consider an instance of an exact linear (n, k, d, α, β) MSR code, where β = d−k+1
. Consider e nodes,
indexed with f1 , . . . , fe , and other distinct d − e + 1 nodes, indexed with h1 , . . . , hd−e+1 , such that d − e + 1 ≥ k. Let
H = {f1 , . . . , fe , h1 , . . . , hd−e+1 } and define Hfj = H\{fj }. Consider the repair algorithm corresponding to failed node fj
and helper nodes Hfj . We denote by sH
h,fj the information sent by node h to repair node fj , for helpers h ∈ Hfj . We drop
the superscript H when it is clear from the context. The size of sh,fj is β symbols.
Now we construct an (n, k, d − e + 1, e, α, eβ) MSMR code. Upon failure of the e nodes f1 , . . . , fe , the centralized node
carrying the repair connects to the set of d − e + 1 helpers h1 , . . . , hd−e+1 . Each helper node hi transmits eβ symbols given
by ∪ej=1 {shi ,fj }. One can check that the parameters of an MSMR code in (21) are satisfied with equality.
The approach consists in using the underlying MSR repair procedure for each of the e failed nodes. Note that shi ,fj can be
obtained from the d− e + 1 helpers, for i ∈ [d− e + 1]. To this end, we need to reconstruct sH
fi ,fj for all {(i, j), i, j ∈ [e], i 6= j},
which we treat as unknowns. Let Ei,j (·) denote the encoding function used to encode the information sent from node hi to

node fj . Also, let Di (·) denote the decoding function used by the MSR code to repair node fi given information from d
helpers. Then, we write
sH
fi ,fj = Ei,j (wfi )
= Ei,j (Di (sH
h,fi , h ∈ Hfi )),

(28)

where wj denotes the content of node j, i, j ∈ [e], i 6= j. Equation (28) generates e(e − 1) linear equations in e(e − 1)
unknowns. Let s be a vector containing the unknowns sfi ,fj . Then, we seek to form a system of linear equations as
As = b,

(29)

where A is a known (e(e − 1) × e(e − 1)) matrix and b is a known (e(e − 1) × 1) vector. If A is non-singular, one can
thus recover s. Then, the centralized node can recover the failed node wfi as wfi = Di (sh,fi , h ∈ Hfi ). We adopt the above
approach throughout the section.
Remark 5. While the described framework applies to codes with arbitrary rates, we focus in the sequel on low-rate codes.
For instance, for a target MSMR code with rate 21 , the construction in [41] yields a storage size α = k 2k−1 , while applying
the above approach to IA codes or to PM codes results in a smaller storage size α = k.
C. Product-matrix codes
In this section, we construct MSMR codes for any e erasures based on product-matrix (PM) codes [25]. The PM framework
allows design of MBR codes for any value of d and design of MSR codes for d ≥ 2k − 2. Moreover, the PM construction
enjoys simple encoding and decoding and ensures optimal repair of all nodes. Product-matrix MSR codes are a family of
scalar MSR codes, i.e., β = 1, designed for parameters d ≥ 2k − 2. We first focus on the case d = 2k − 2. Under this setup,
α = d − k + 1 = k − 1. The codeword is represented by an (n × α) code matrix C such that its ith row corresponds to the α
symbols stored by the ith node. Each code matrix is given by
 


S
(30)
C = ΨM, Ψ = Φ ΛΦ , M = 1 ,
S2

where Ψ is an (n × d) encoding
 matrix and M is an (d × α) message matrix, S1 and S2 are (α × α) symmetric
matrices
α+1
constructed such that the α+1
entries
in
the
upper-triangular
part
of
each
of
the
two
matrices
are
filled
up
by
distinct
2
2
message symbols. Φ is an (n × α) matrix and Λ is an (n × n) diagonal matrix. The elements of Ψ should satisfy:
1) any d rows of Ψ are linearly independent;
2) any α rows of Φ are linearly independent;
3) the n diagonal elements of Λ are distinct.
The
above conditions
may be met by choosing Ψ to be a Vandermonde matrix, in which case its ith row is given by ψit =


d−1
α
. It follows that Λ = diag{λα
1 λi · · · λi
1 , . . . , λn }. In the following, we assume that Ψ is a Vandermonde matrix.
t
Repair of a single erasure in PM codes. The single erasure repair algorithm [25] is reviewed
the
 below. t Let wi αdenote
t
α t
t
th
t
t
content stored at a failed node. Let φi be the i row of Φ. Then, wi = ψi M = φi λi φi M = φi S1 + λi φti S2 . Let
t
t
Hi = {h1 , . . . , hd } denote the set of d helpers. Each
 helper h transmits sh,i = wh φi = ψh M φi to the replacement node, who
t
obtains ΨHi M φi , where ΨHi = ψh1 · · · ψhd . Note that ΨHi is invertible by construction. Thus, using the symmetry of
t
S1 and S2 , we obtain (M φi )t = φti S1 φti S2 . We can then reconstruct wit = φti S1 + λα
i φi S2 .
Repair of multiple erasures in PM codes. Given the symmetry of PM codes, we can assume w.l.o.g that nodes in E =
{1, . . . , e} have failed. Define Ei = E\{i}. Let H = {1, . . . , d + 1}. The centralized node connects to nodes {e + 1, . . . , d + 1}.
Each helper node h transmits {ψht M φj , j ∈ E}.
Let s = [s1,2 , s2,1 , . . . , s1,e , se,1 , . . . , se−1,e , se,e−1 ]t . Our goal is to express explicitly A and b as in (29).
Consider the repair of node i ∈ E by the set of helpers in Hi = H\{i}. From the previous subsection, we write

It follows that

 −1

wi = Iα λα
i Iα ΨHi sHi , such that


ΨtHi = ψ1 · · · ψi−1 ψi+1 · · · ψd+1 ,


stHi = s1,i · · · si−1,i si+1,i · · · sd+1,i .
si,j = φtj wi

 −1 X
t
= φtj λα
sl,i el,i )
i φj ΨHi (
l∈Hi

(31)
(32)
(33)

(34)
(35)

=

X 
( φtj

l∈Ei

d+1
X 
 −1
t
λα
φ
Ψ
e
)s
+
( φtj
i j
Hi l,i l,i
l=e+1

Here we use the column standard basis el and denote

el,i

 −1
t
λα
i φj ΨHi el,i )sl,i ,

(
el ,
l < i,
=
el−1 , l > i.

(36)

(37)

Note that the second term in (36) is known from the helpers. Moreover, to compute (36), one may use the inverse of
Vandermonde’s matrix formula [19]. Let h ∈ {1, . . . , d}, we have
γh (l, i)
γh (l, i)
= Pd
,
j−1
m∈Hi \{l} (λl − λm )
j=1 γj (l, i)λ

Q
(Ψ−1
Hi el,i )h =

(38)

where the subscript h in (·)h means the h-th entry, and

X

γh (l, i) = (−1)d−h

λm1 . . . λmd−h .

(39)

m1 <...<md−h ∈Hi \{l}

As

Q

m∈Hi \{l}

(λ − λm ) =

Pd

h=1

γh (l, i)λi−1 , we obtain


φtj

 −1
t
λα
i φj ΨHi el,i =

Pα

h−1
α
h=1 (γh (l, i) + λi γh+α (l, i))λj
.
Pd
h−1
h=1 γh (l, i)λl

(40)

Therefore, one can construct A and b in (29) as follows:
• The entries of b are indexed with (i, j), corresponding to si,j . The entry of b at index (i, j) is given by
 −1
Pd+1  t
t
λα
i φj ΨHi el,i )sl,i .
l=e+1 ( φj
• Index the e(e − 1) rows (and columns respectively) of A with (i, j). A has zero in all entries except: For every row in
A indexed by (i, j):
– the entry at column indexed by (i, j) is -1.

 −1
t
– for l ∈ Ei , entry at column indexed by (l, i) is given by φtj λα
i φj ΨHi el,i as in (40).
For clearer presentation, we first prove the existence of product-matrix MSMR codes for 2 erasures, and then prove for
general e.
Theorem 4. There exists (n, k, 2k − 3, 2, k − 1, 2) product-matrix MSMR codes, defined over large enough finite field, such
that any two erasures can be optimally repaired.
Proof: In this case, the matrix A is given by

−1
A=  t
−1
t
φ1 λα
φ
2 1 ΨH2 e1,2

 t
φ2

 −1

t
λα
1 φ2 ΨH1 e2,1
.
−1

(41)

From (38), noting that H1 \{2} = H2 \{1}, we obtain


 t
 −1
 −1
t
α t
|A| = 1 − φt2 λα
1 φ2 ΨH1 e2,1 φ1 λ2 φ1 ΨH2 e1,2
α
P
(
λh−1
(γh (1, 2) + λα
α
1 γh+α (1, 2))) X
2
h=1
=1− d
(
λh−1
(γh (1, 2) + λα
2 γh+α (1, 2)))
1
d
P h−1
P
h−1
λ2 γh (1, 2)
λ1 γh (1, 2) h=1
h=1

(42)

(43)

h=1

N (λ1 , . . . , λd+1 )
.
,1−
D(λ1 , . . . , λd+1 )

(44)

|A| can be viewed as a rational function of (λ1 , . . . , λd+1 ), as N and D are polynomials in (λ1 , . . . , λd+1 ). We want to show
that the following polynomial is not zero:
P (λ1 , . . . , λd+1 ) , D(λ1 , . . . , λd+1 )|A|
= D(λ1 , . . . , λd+1 ) − N (λ1 , . . . , λd+1 ).
Let yα = (−1)α λ3 · · · λα+2 , yα−1 = (−1)α−1 λ3 · · · λα+1 . Then, it can be seen that P contains the term

(45)
(46)

α−1
α−1
yα yα−1 (λd−1
+ λd−1
− λα
− λα
),
1 λ2
2 λ1
1
2

which is not zero. Hence, P (λ1 , . . . , λd+1 ) is a non-zero polynomial. The PM construction, when based on a Vandermonde
α
α
α
matrix, requires λα
1 6= λ2 [25], or equivalently, g(λ1 , λ2 ) , λ1 − λ2 6= 0. Let Q(λ1 , . . . , λn ) denote the polynomial obtained
by sweeping across the different set of helpers and failure patterns, taking the product of all corresponding polynomials P ,
and also multiplied by all g for all pairs of two nodes. Then, Q is not identically zero. By Combinatorial Nullstellensatz [3],
we can find assignments of the variables {λ1 , . . . , λn } over a large enough finite field, such that the polynomial is not zero.
Equivalently, we can guarantee the successful efficient recovery of any two erasures among the n storage nodes.
Theorem 5. There exists (n, k, 2k − e − 1, e, k − 1, e) product-matrix MSMR codes, defined over large enough finite field,
such that any e erasures can be optimally repaired.
Proof: Entries in each column
indexed by si,j in A is either −1 or some other (e − 1) non-zero entries whose denominator
Q
is the same and given by
(λi − λm ). We multiply this common denominator to all entries in the column si,j , for all
m∈H\{i}

pairs i 6= j. When λi ’s are chosen to be distinct, this does not change the singularity of A. Denote this transformed matrix by
B. Using (40), the entry of B in row (i, j) and column (l, m) is a polynomial in λ1 , . . . , λd+1 :

B(i,j),(l,m)

 Pd

γh (i, j)λh−1
,
l = i, m = j,
−
i

Pα h=1
h−1
α h−1
=
+
γ
(l,
i)λ
λ
γ
(l,
i)λ
,
m = i,
h
h+α
i j
j
h=1


0,
otherwise.

Notice that e + α − 1 ≤ k − 1 + α − 1 = d − 1. Let y = (−1)α−1 λe+1 · · · λe+α−1 , which is a term in γα+1 (i, j) for all (i, j)
by (39). We observe that there is a single term ±yλα
i in the polynomial B(i,j),(l,m) for the non-zero entries of B.
Recall that the Leibniz formula for determinant of a m × m matrix B is given by
X
Y
bσ(i),i ,
(47)
|B| =
sgn(σ)
σ

i

where σ is a permutation from the permutation group Sm , sgn is the sign function of permutations, and bi,j is the entry (i, j)
of B.
Q
e−1
Claim 1. The term T = ei=1 (yλα
in |B| has a non-zero coefficient.
i )
Claim 1 implies that |B| is not a zero polynomial. Then, proceeding as in the proof in Theorem 4, by Combinatorial
Nullstellensatz [3], we can find assignments of the variables {λ1 , . . . , λn } over a large enough finite field, such that the code
guarantees optimal recovery of any set of e erasures.
Next, we prove Claim 1. Note that the term T can be created if and only if we take the single term ±yλi in the non-zero
entries of B ( depending on the permutation σ). Therefore, it is easy to see that the coefficient of term T in |B| is the
determinant of the following matrix C ∈ Re(e−1)×e(e−1) :


−1, l = i, m = j,
(48)
C(i,j),(l,m) = 1,
m = i,


0,
otherwise.

One can verify that C is diagonalizable, and the eigenvalues are:
t
• Eigenvalue e − 2 has multiplicity 1, and corresponding (right) eigenvector (1, 1, . . . , 1) .
Pe
t
• Eigenvalue −2 has multiplicity e−1, and corresponding eigenspace {(x1,2 , . . . , xe,e−1 ) : xi,j = xi,1 , ∀j ∈ [e],
i=1 xi,1 =
0} of dimension e − 1.
P
t
• Eigenvalue −1 has multiplicity e(e − 2), and corresponding eigenspace {(x1,2 , . . . , xe,e−1 ) :
1≤i≤e,i6=j xi,j = 0, ∀j ∈
[e]} of dimension e(e − 2).
When e > 2, the eigenvalues of C are non-zero, and |C| 6= 0. Therefore, Claim 1 is proved and the theorem statement follows.
Remark 6. There exists product-matrix MSMR codes, defined Q
over large enough finite field, that simultaneously repair any
n−k
e ∈ [n − k] erasures with optimal bandwidth. Indeed, let Q = e=2 Qe , where Qe is the polynomial corresponding to the
α
code constraints for eQerasures. Recall that the reconstruction process for PM codes requires that αα
i − αj 6= 0 for αi 6= αj .
α
α
Let g(λ1 , . . . , λn ) = 1≤i<j≤n (λj − λi ). Let P (λ1 , . . . , λn ) = g(λ1 , . . . , λn )Q(λ1 , . . . , λn ). By Theorem 4 and Theorem 5,
P is not zero and the result follows by Combinatorial Nullstellensatz.
Example 2. Consider the product-matrix code with n = 11, k = 6, d = 10, α = 5. The code is defined over F26 with
α
i−1
Λ = diag{λα
with g being the generator of the multiplicative group of F26 . Recall that with the
1 , . . . , λ11 } and λi = g

above choice of λi , any field of size at least nα = 55 is sufficient
to meet the PM code requirements [25]. We first consider

repair of e = 2 erasures. One can check that out of the 11
2 = 55 possible 2 failure patterns, 2 patterns are not recoverable
according
to (29): E ∈ {{1, 2}, {10, 11}}. Considering the same code structure, for e = 3 erasures, one observes that out of the

11
3 = 165 possible 3 failure patterns, 5 patterns are not recoverable: E ∈ {{1, 2, 11}, {2, 3, 7}, {2, 4, 8}, {3, 4, 7}, {5, 9, 10}}. It
is worth noting that a lazy repair strategy can be beneficial in the following way: if nodes 10 and 11 failed, i.e., E = {10, 11},
then one can optimally repair any 3 erasures E ∈ {{i, 10, 11}, i 6= 10, i 6= 11}. Finally, as suggested by Theorem 4 and
Theorem 5, we find that increasing the underlying field size to F28 suffices to ensure optimal repair of all two and three
erasure patterns in this scenario.
Remark 7. Following the code shortening procedure described in [25], we construct an (n, k, d − e + 1, e, k − 1, e) productmatrix MSMR codes with optimal repair for any e ∈ [n − k] erasures such that 2k − 2 ≤ d ≤ n − 1. First, as described in
Remark 6, we consider an (n + (d − 2k − 2), k + (d − 2k − 2), d + (d − 2k − 2) − e + 1, d − k + 1, 1) product-matrix MSMR
′
code C in systematic form. The top (d − 2k − 2) rows (corresponding to α(d − 2k − 2) information elements over Fq , or
′
d − 2k − 2 systematic nodes) of C are set to all zero. Then, the target code C is formed by deleting the first (d − 2k − 2)
′
rows in each code matrix of C . It can be seen that the repair procedure for e erasures in C can be done by invoking that of
′
the original code C , which leads to the result.
D. Interference Alignment codes
In this section, we show the existence of MSMR codes from Interference alignment (IA) codes for e = 2 erasures. Moreover,
we show that for any e ≤ k erasures from only the systematic (or only the parity) nodes, optimal repair bandwidth can be
achieved.
The scalar MSR IA code construction in [33] is based on interference alignment techniques. The code is systematic and
defined over a finite field Fq with optimal repair bandwidth for the cases nk ≤ 21 and d ≥ 2k − 1. We focus on the case
(n = 2k, d = 2k − 1). In this scenario, the storage size is α = d − k + 1 = k.
′
Notation. For an invertible matrix B, we define B ′ , (B −1 )t : columns of B constitute the dual basis of the column vectors
of B. We use the following symbols to denote the flow of information during repair operations.
• si,j : from systematic node i to parity node j.
• ri,j : from systematic node i to systematic node j.
′
• si,j : from parity node i to systematic node j.
′
• ri,j : from parity node i to parity node j.
The IA code is constructed as below. Consider k linearly independent vectors {v1 , . . . , vk }, vi ∈ Fkq , i ∈ [k]. Let


′
V = v1 , . . . , vk , U = κ−1 V P,

(49)

where every submatrix of the (k × k) matrix P is invertible and κ is an arbitrary non-zero constant in Fq satisfying κ2 − 1 6= 0.
′
′
′
Let wl , l ∈ [k] denote the content of systematic node l and wi the content of parity node i , i ∈ [k]. Let ui , vi , ui , vi be the
i-th column of U, V, U ′ , V ′ , respectively. Then, we have
′

wit =

k
X

(i)

(i)

wjt Gj , Gj = ui vjt + Pj,i I,

(50)

j=1

(i)

such that the matrix Gj indicates the encoding submatrix for parity node i, associated with information unit j.
Repair of a systematic node. Assume systematic node l fails. The general repair procedure is described in [33]. In this section,
we explicitly develop the exact expression of wl as it would be needed later in repairing multiple erasures. Each systematic
′
′
′
′
′
(i) ′
node j ∈ [k]\{l} transmits rj,l = wjt vl . Each parity node i ∈ [k] transmits si,l = wi t vl . Noting that Gj vl = δ{j=l} ui +Pj,i vl ,
it follows that
X
′
′
si,l = wlt (ui + Pl,i vl ) +
Pj,i rj,l .
(51)
j6=l

Canceling the interference from systematic nodes, and arranging the contributions of parity nodes in matrix form, we write


′

s1,l −

P

Pj,1 rj,l



 t
′
u1 + Pl,1 vl t


j6=l
 

..
..
=

.
.


P
′

 ′
t
sk,l −
Pj,k rj,l
uk + Pl,k vl t
j6=l




 wl

(52)

1 t
P (I + κel etl )V −1 wl ,
(53)
κ
where the last equality is obtained by substituting U by its expression in (49). Using the Sherman-Morrison formula, for an
invertible square matrix A of size k × k and vectors u, v of length k,
=

(A + uv t )−1 = A−1 −
′

we obtain that ( κ1 P t (I + κel etl )V −1 )−1 = U −

A−1 uv t A−1
,
1 + v t A−1 u

(54)

κ2
t ′
1+κ V el el P ,

it follows that

 ′
P
Pj,1 rj,l
s1,l −


j6=l

′ 
′
κ2
..
.
V el etl P ) 
wl = (U −
.


1+κ
P

 ′
sk,l −
Pj,k rj,l

(55)

j6=l

Repair of a parity node. The repair of a parity node is optimally achieved through the duality property of IA codes that
results in a structure that is also conducive to interference alignment. Indeed, inverting the roles of parity and systematic nodes,
it follows from [33] that
wi =

k
X

′

′

′

(i)

(i)

wjt Gj ; Gj

=

j=1

′ ′
′
1
(vi ujt − κ2 Pi,j I).
2
1−κ

(56)
′

′

Assume parity node l fails, then systematic node i transmits si,l = wit ul and parity node j sends rj,l = wjt ul . Note that
′

(i)

Gj ul =

1
2
1−κ2 (−κ uj

′

+ δ{j=l} vi ). It follows that
′

si,l = wl t

X −κ2 ′ ′
′
1
2 ′
(v
−
κ
P
u
)
+
P r .
l
i,l
1 − κ2 i
1 − κ2 i,j j,l

(57)

j6=l

Combining information from different helpers and after simplification, we obtain







s1,l +

κ2
1−κ2

P

′

′

P1,j rj,l



 ′t

′
v1 − κ2 P1,l utl


1 
 ′
..
..
=
 wl
.
.
 1 − κ2 
′
′ 
t
2 ′
t
κ2 P ′
vk − κ Pk,l ul
Pk,j rj,l
sk,l + 1−κ2
j6=l

(58)

j6=l

=

′
′
κ
P (I − κel etl )U t wl ,
1 − κ2

(59)

′

where the last equality is obtained by replacing V −1 = κP U t . Inverting the system of equations and using the ShermanMorrison formula, we obtain

′ 
κ2 P ′
P1,j rj,l
s1,l + 1−κ
2


j6=l


′
′
t
.
2
t 
.
..
(60)
wl = ((1 − κ )V + (1 + κ)U el el P ) 

P

2
′
′ 
κ
Pk,j rj,l
sk,l + 1−κ2
j6=l

Repair of multiple erasures. We start by deriving the equations relating the different unknowns as in (29). From (55), we
write
sl,m = utm wl

(61)




′
κ
t
t
t ′ 
= (um U −
u V el el P ) 
1+κ m

2

′

s1,l −

′

sk,l −

P

Pj,1 rj,l

j6=l

..
.
P

j6=l

Pj,k rj,l








(62)

=

(etm





κ
t ′ 
−
Pl,m el P ) 
1+κ


′

s1,l −

′

sk,l −

P

Pj,1 rj,l

j6=l

..
.
P

Pj,k rj,l

j6=l





,



(63)

where the equality is obtained by noting that U t V = κ1 P t . To illustrate the equations as in (28), let us consider the information
transferred among 3 systematic l1 , l2 , l3 ∈ [k] and 3 parity nodes m1 , m2 , m3 ∈ [k], and denote by all other transferred
information as “rest”. It follows that,
′
′
′
κ
Pl1 ,m1 etl1 P )(em1 sm1 ,l1 + em2 sm2 ,l1 − P t el2 rl2 ,l1 − P t el3 rl3 ,l1 ) + rest
1+κ
′
′
′
′
κ
κ
= (1 −
−(
− Pl2 ,m1 rl2 ,l1 − Pl3 ,m1 rl3 ,l1 + rest.
)s
)s
Pl ,m P
Pl ,m P
1 + κ 1 1 l1 ,m1 m1 ,l1
1 + κ 1 1 l1 ,m2 m2 ,l1
Similarly, starting from (55), we write

sl1 ,m1 = (etm1 −

′

rl1 ,l2 = vl2t wl1

(64)

(65)



′
′
′ 
κ2
= vl2t (U −
V el1 etl1 P ) 

1+κ




′ 
t
= κel2 P 


′

P

′

s1,l1 −
′

sk,l1 −

pj,1 rj,l1

pj,k rj,l1

j6=l1

′

s1,l1 −

P

pj,1 rj,l1

j6=l1

..
.
P

′

pj,k rj,l1
sk,l1 −
j6=l1


j6=l1

..
.
P

′

′








(66)



,



(67)

where the equality is obtained by noting that V t U = κP . It follows that
′

′

′

rl1 ,l2 = κetl2 P (sm1 ,l1 em1 + sm2 ,l1 em2 − P t el2 rl2 ,l1 − P t el3 rl3 ,l1 ) + rest
′

′

′

′

= (κPl2 ,m1 )sm1 ,l1 + (κPl2 ,m2 )sm2 ,l1 − κrl2 ,l1 + rest.

(68)
(69)

Proceeding in a similar way, starting from (60), we obtain
′

′

′

sm,l = vl t wm

(70)




′
′
t
t
2
t 
= vl ((1 − κ )V + (1 + κ)U em em P ) 



s1,m +

sk,m +

s1,m +

′

′

t

sm1 ,l1 = ((1 − κ2 )etl + (1 + κ)κPl,m em P t )(sl1 ,m1 el1 + sl2 ,m1 el2 +
′

′

κ2
1−κ2

κ2
1−κ2

P

′

P
P

j6=m

′

P1,j rj,m

′

j6=m

j6=m

..
.
κ2
1−κ2

P

j6=m

..
.



′
t
= ((1 − κ2 )etl + (1 + κ)κPl,m em P t ) 


sk,m +

It follows that

κ2
1−κ2

′

Pk,j rj,m

′

′

P1,j rj,m

′

′

Pk,j rj,m










(71)



.



(72)

′
′
′
′
κ2
κ2
+
r
P
e
P em3 rm3 ,m1 ) + rest
m
2 m2 ,m1
2
2
1−κ
1−κ
(73)
′

′

= (1 − κ2 + κ(1 + κ)Pl1 ,m1 Pl1 ,m1 )sl1 ,m1 + (κ(1 + κ)Pl1 ,m1 Pl2 ,m1 )sl2 ,m1 + (κ2 Pl1 ,m2 )rm2 ,m1
′

′

+ (κ2 Pl1 ,m3 )rm3 ,m1 + rest.
Similarly, starting from (60), we write

(74)

′

′

rm1 ,m2 = utm2 wm1

(75)




t
′
= utm2 ((1 − κ2 )V + (1 + κ)U em1 em1 P t ) 




s1,m1 +



1 − κ2 t
e m2 P t 

κ

sk,m1 +

=

It follows that

κ2
1−κ2

j6=m1

..
.
2

κ
1−κ2

P
P

j6=m1

′

s1,m1 +

κ
1−κ2

sk,m1 +

′

′

Pk,j rj,m1

2

κ
1−κ2

P

j6=m1

..
.

P1,j rj,m1

′

2

P

j6=m1





.



′

′

P1,j rj,m1

′

′

Pk,j rj,m1








(76)

(77)

′
′
′
′
1 − κ2 t
κ2
κ2
(78)
P em2 rm2 ,m1 +
P em3 rm3 ,m1 ) + rest
em2 P t (sl1 ,m1 el1 + sl2 ,m1 el2 +
2
2
κ
1−κ
1−κ
′
1 − κ2
1 − κ2
=(
(79)
Pl1 ,m2 )sl1 ,m1 + (
Pl2 ,m2 )sl2 ,m1 + κrm2 ,m1 + rest.
κ
κ
Equations (64), (69), (74) and (79) can thus be used to derive A and b as defined in (29). In the following theorem, we show
that the IA code already provides optimal repair for systematic (respectively parity) failures, without the need to modify the
coding matrices.
′

rm1 ,m2 =

Theorem 6. In the interference alignment MSR code [33], it is possible to optimally repair any set of e ≤ k systematic
(respectively parity) failures.
t

Proof: Assume w.l.o.g that nodes {1, . . . , e} have failed. Let s = r1,2 , r2,1 , . . . , re−1,e , re,e−1 . Then, from (69), it
follows that A is a block-diagonal matrix given by


1 κ

κ 1




..
A=
(80)
.
.



1 κ
κ 1
e(e−1)

It follows that |A| = (1 − κ2 ) 2
parity nodes using equation (79).

6= 0 as κ2 6= 1 by design. The same procedure applies to any set of e failures among

Theorem 7. The interference alignment MSR code achieves optimal simultaneous repair of one systematic node l and one
parity node m if Pl,m (P −1 )m,l 6= 1.
Proof: Assume that systematic node l and parity node m failed. From (64), we obtain
sl,m = (1 −

′
′
κ
Pl,m Pl,m )sm,l + constant,
1+κ

(81)

Similarly, from (74), we obtain
′

′

sm,l = (1 − κ2 + κ(1 + κ)Pl,m Pl,m )sm,l + constant.

(82)

′

Let s = [sl,m , sm,l ]t . Then, A is given by
"

−1
A=
′
1 − κ2 + κ(1 + κ)Pl,m Pl,m

1−

′
κ
1+κ Pl,m Pl,m

−1
′

#

.

(83)

It follows that, after simplification, |A| 6= 0, which implies that κ2 (Pl,m Pl,m − 1)2 6= 0 ⇐⇒ Pl,m (P −1 )m,l 6= 1, as κ 6= 0.
Combining Theorems 6 and 7 we know that (2k, k, 2k − 2, 2, k, 2) MSMR codes for 2 erasures can be constructed through
IA codes. We point out that Theorems 6 and 7 have been derived in [7] for cooperative repair, using a different technique.
Recall that MSCR codes are in particular MSMR codes [27]. However, their technique cannot be extended to more than two
node failures including systematic and parity nodes [7].

Theorem 8. The interference alignment MSR code achieves optimal simultaneous repair of:
−1
• two systematic failures l1 , l2 and one parity failure m if 1 − Pl1 ,m (P
)m,l1 − Pl2 ,m (P −1 )m,l2 6= 0,
−1
)m1 ,l − Pl,m2 (P −1 )m2 ,l 6= 0,
• one systematic failure l and two parity failures m1 , m2 if 1 − Pl,m1 (P
• three systematic failures l1 , l2 , l3 and one parity failure m if
1 − Pl1 ,m (P −1 )m,l − Pl2 ,m (P −1 )m,l2 − Pl3 ,m (P −1 )m,l3 6= 0,
•

one systematic failure l and three parity failures m1 , m2 , m3 if
1 − Pl,m1 (P −1 )m1 ,l − Pl,m2 (P −1 )m2 ,l − Pl,m3 (P −1 )m3 ,l 6= 0,

•

two systematic failures l1 , l2 and two parity failures m1 , m2 if
1 − Pl1 ,m1 (P −1 )m1 ,l1 − Pl1 ,m2 (P −1 )m2 ,l1 − Pl2 ,m1 (P −1 )m1 ,l2 − Pl2 ,m2 (P −1 )m2 ,l2
+ Pl1 ,m1 (P −1 )m1 ,l1 Pl2 ,m2 (P −1 )m2 ,l2 + Pl1 ,m2 (P −1 )m2 ,l1 Pl2 ,m1 (P −1 )m1 ,l2
− Pl1 ,m1 (P −1 )m1 ,l2 Pl2 ,m2 (P −1 )m2 ,l1 − Pl1 ,m2 (P −1 )m2 ,l2 Pl2 ,m1 (P −1 )m1 ,l1 6= 0.

Proof: The proof follows along similar lines as Theorem 7 by constructing A using (64), (69), (74) and (79). The explicit
expression of |A| can then be obtained using the Symbolic Math Toolbox of MATLAB, from which the above conditions can
be readily obtained.
Combining Theorems 6 and 8 we know that (2k, k, 2k − e, e, k, e) MSMR codes for e = 3, 4 erasures can be constructed
through IA codes.
Remark 8. Deriving an exact condition under which the recovery of multiple failures for large e is not straightforward.
However, we suspect that the general formula is given by the following expression


p 
s
|A| = k 2sp (1 − k 2 )(2)+(2) 
1 −

X

X

X

(sgn(σ)

I⊂S,J⊂P,
σ∈ΠI,J σ′ ∈ΠI,J
|I|=|J|≤min(s,p)

Y
i∈I

′

Pi,σ(i) )(sgn(σ )

Y

j∈J

e


′
Pj,σ′ (j) )
 ,

(84)

where ΠI,J is the group of permutations between the two sets I and J (I and J are ordered in increasing order), and sgn(σ)
refers to the sign of a permutation σ, counting the number of inversions in σ, and given by
P

sgn(σ) = (−1)i1 <i2 ∈I

1σ(i1 )>σ(i2 )

.

(85)

For example, if I = {1, 2, 3}, J = {2, 3, 4} and σ(1) = 3, σ(2) = 4, σ(3) = 2. Then, sgn(σ)=1.
One can check that the formulas in Theorem 6, Theorem 7 and Theorem 8 satisfy (84). A general proof of (84) is still open.
Example 3. Consider the IA code with n = 8, k = 4, d = 7, α = 4. The code is defined over F25 with P being a Vandermonde
matrix


1 1 1 1
1 2 4 8 

(86)
P =
1 4 16 10 .
1 8 10 26
Using Theorem 6, Theorem 7 and Theorem 8, one can check that every two, three and four erasures can be repaired optimally
using our repair framework.
In the following theorem, we provide an existence proof of IA MSMR codes for multiple erasures.
Theorem 9. There exists (2k, k, 2k − e, e, k, e) interference alignment MSMR codes, defined over large enough finite field,
such that any e ≤ k erasures can be optimally repaired.
Proof: From Theorem 6, we know that if the errors are all either systematic or parity nodes, then efficient repair is
possible. Thus, we only need to analyze the case of a mixture of systematic and parity nodes failures.
Consider e ≤ k failures consisting of q systematic nodes and p parties nodes, described by the sets Q and P. W.lo.g, assume
′
′
′
that Q = [q] and P = [p]. Let s denote the vector of unknowns such that pairs (ri,j , rj,i ), (ri,j , rj,i ) and (si,j , sj,i ) are grouped
′
together. Using (64), (69), (74) and (79), we construct A as in (29). Denote the determinant of A as F (κ, Pi,j , Pi,j , i ∈ Q, j ∈
′
′
P) , |A|. The rows and columns of A are indexed with {ri,j , si,j , ri,j , si,j }. Let Mi,j denote the minor in A corresponding

′

s1,1

′

s1,1



−1
1 − κ2 + κ(κ + 1)P P ′
11 11


0

A=

0


0
′

κ(κ + 1)P11 P21

r1,2

r2,1

s2,1

s2,1

−1
′
κP21
0

0
0
−1
−κ

−P21
0
−κ
−1

0
′
κ(κ + 1)P21 P11
0
0

0
0
0
′
κP11

0
0

−P11
0

0
0

−1
′
1 − κ + κ(κ + 1)P21 P21

1−

′
κP11 P11

κ+1

2

′









′ 
κP21 P21 
1 − κ+1
−1

s1,1
′

s1,1
r1,2

(90)

r2,1
s2,1
′

s2,1

(−1)i+j N

j,i
to Ai,j . Similarity, Ni,j denotes the minor in P corresponding to Pi,j . As P ′ = (P −1 )t , Pi,j =
, one observes that
|P |
F is a rational function in (κ, Pi,j , (i, j) ∈ Q × P).
Claim 2. F is not identically zero for any q, p ≥ 0, q + p = e ≤ k.
If Claim 2 holds, then the theorem is proved due to the following argument. By symmetry any e-erasure pattern corresponds
to a non-zero rational function F . Recall from [33], the reconstruction process requires that every submatrix
Q of P is invertible.
This can be translated into a polynomial constraint given by Q(Pi,j , i ∈ Q, j ∈ P) 6= 0. Let T , Q e erasures F . Here the
product is over all possible e erasures, and the rational function F depend on the erasure pattern. Then, it follows that T is a
non-zero rational polynomial in (κ, Pi,j , (i, j) ∈ [k] × [n − k]). By Combinatorial Nullstellensatz [3], we can find assignments
of the variables (κ, {Pi,j }) over a large enough finite field, such that the code guarantees optimal recovery of any set of e
erasures.
Next, we prove Claim 2. We assume first that q ≤ k2 . Let

Pi,j = 0 ∀ (i, j) ∈ Q × P.

(87)

Note that one can always construct a (normalized) invertible matrix P satisfying (87), so we can assume |P | = 1. Thus F is
a polynomial. We will show
′
′
F (κ, Pi,j = 0, Pi,j
, (i, j) ∈ Q × P) = F (κ, Pi,j = 0, Pi,j
= 0, (i, j) ∈ Q × P) 6=0,

(88)

′
, (i, j) ∈ Q × P) 6= 0.
F (κ, Pi,j , Pi,j

(89)

which implies

′
′
To this end, we first prove that F (κ, Pi,j = 0, Pi,j
, (i, j) ∈ Q × P), viewed as a polynomial of (κ, {Pi,j
}), does not depend
′
′
on {Pi,j }. From (69) and (74), one can check that Pi,j appears in A at entries given by
• Ar ,s′ for l ∈ Q\{i},
l,i j,l
• As′ ,r ′
for m ∈ P\{j}.
m,i

j,m

For any l ∈ Q\{i}, consider the two columns in A indexed by rl,i and ri,l . Both columns have non-zero entries only at rows
indexed with rl,i and ri,i . Then, after removing entries at row rl,i , it follows that both columns become linearly dependent, as
both columns are scalar multiples of the same standard basis vector. Thus, the minor of A satisfies Mrl,i ,s′ = 0.
j,l
The example in (90) illustrates
failures, given by nodes 1 and 2, and one parity failure, given
 the ′case of two systematic
′ 
parity node 1. In this case s = s11 , s11 , r12 , r21 , s21 , s12 . Setting Pi,j = 0 for all i, j and looking at the submatrix of A by
′
removing row r1,2 and column s2,1 in (90), it can be seen that columns r1,2 , r2,1 are dependent, hence its corresponding minor
Mr1,2 ,s′ = 0.
2,1

′

′

Similarly, for any m ∈ P\{j}, consider the two rows in A indexed by rj,m and rm,j . Both rows have non-zero entries
′
′
′
only at columns indexed with rj,m and rm,j . Then, after removing entries at column rj,m , it follows that both rows become
linearly dependent. Thus, Ms′ ,r′ = 0.
m,i

j,m

′

′

The minors in A of all terms corresponding to Pi,j are thus equal to zero. Therefore, w.l.o.g, one can assume that Pi,j =
0∀(i, j) ∈ Q × P. It follows that A is block-diagonal
matrix

 such that
−1 −κ
• Row/column pairs (ri,j , rj,i ) correspond to
,
−κ −1
′
′
−1 κ
• Row/column pairs (ri,j , rj,i ) correspond to
,
 κ −1 
′
−1
1
• Row/column pairs (si,j , sj,i ) correspond to
.
1 − κ2 −1
• Other entries are 0.
q
p
Therefore, |A| = κ2qp (1 − κ2 )(2)+(2) 6= 0, as κ 6= 0 and κ2 6= 1.

′

Assume now that q > k2 . Then, p ≤ k2 . Proceeding similarly, one can show that if Pij = 0∀(i, j) ∈ Q × P, then, all terms
p
r
Pij have no impact on |A| and one obtains similarly |A| = κ2rp (1 − κ2 )(2)+(2) .
V. N ON - EXISTENCE OF

EXACT

MBMR REGENERATING

CODES

In this section, we explore the existence of linear exact MBMR regenerating codes for e < k. Unlike the single erasure repair
problem [25] and the cooperative repair problem [36], we prove that linear exact regenerating codes do not exist. Following
[25], [36], we proceed by investigating subspace properties linear exact MBMR codes should satisfy. Then, we prove that the
derived properties over-constrain the system.
A. Subspace viewpoint
Linear exact regenerating codes for the MBMR point can be analyzed from a viewpoint based on subspaces. A linear storage
code is a code in which every stored symbol is a linear combination of the M source symbols. Let f denote an M-dimensional
vector containing the source symbols. Then, any symbol x can be represented by a vector h satisfying x = f t h such that
h ∈ F M , F being the underlying finite field. The vectors h define the code. A node storing α symbols can be considered
(i)
(i)
as storing α vectors of the code. Node i stores h1 . . . hα . It is easy to see that
operations
P linear
P performed on the stored
symbols are equivalent to the same operations performed on the these vectors:
γi f t hi = f t ( γi hi ). Thus, each node is
said to store a subspace of dimension at most α. We write WA to denote the subspace stored by all nodes in the set A, A ⊆ [n].
For regeneration, each node passes β symbols. Equivalently, each node passes a subspace of dimension at most β. We denote
the subspace passed by node j to repair set L
R of e nodes by SjR . The subspace passed by a set of nodes A to repair a set R
R
of e nodes is denoted by SA . The notation j Xj denotes the direct sum of subspaces Xj .
R
Notation. For a general exact regenerating code, which can be nonlinear, we use by abuse of notation WA , SA
to represent
the random variables of the stored information in nodes A, and of the transmitted information from helpers A to failed nodes R.
Properties that hold using entropic quantities for a general code do hold when considering linear codes. For instance, consider
two sets A and B. Then, we note the following
H(WA ) → dim(WA ),
H(WA |WB ) → dim(WA ) − dim(WA ∩ WB ),

(91)
(92)

I(WA , WB ) → dim(WA ∩ WB ),

(93)

where the symbol → means translates to. When results hold for general codes, we only prove for the entropy properties, and
the proof for the subspace properties of linear codes is omitted. All results on entropic quantities are for general codes, and all
results on subspaces are for linear codes. Moreover, all results in this section refers to properties of optimal exact multi-node
repair codes with k > e (constructions for k ≤ e are presented in Section IV-A), some of which are specific to MBMR codes
and will be noted.
In this section, we focus on symmetric codes. Namely, the results do not depend on the indices of the nodes. Note that one
can always construct a symmetric code form a non-symmetric code [11]. We now start by proving some properties that exact
regenerating codes should satisfy. We note that it is also presented in [38, Lemma 4].
Lemma 5. Let B ⊆ [n] be a subset of nodes of size e, then for an arbitrary set of nodes A, such that 0 ≤ |A| ≤ d, B ∩ A = ∅,
B
H(WB |WA ) ≤ H(WB |SA
) ≤ min(eα, (d − |A|)β).

(94)

Proof: If nodes B are erased, consider the case of having nodes A and nodes C as helper nodes, |C| = d − |A|. Then,
the exact repair condition requires
B
B
0 = H(WB |SA
, SC
)
B
B B
= H(WB |SA
) − I(WB , SC
|SA )
B
B
≥ H(WB |SA
) − H(SC
)
B
≥ H(WB |SA
) − (d − |A|)β.
B
B
), and the results follows.
) ≤ H(WB ) ≤ |B|α, H(WB |WA ) ≤ H(WB |SA
Moreover, we have H(WB |SA
In the next two subsections, we focus on the cases where e | k and e ∤ k, respectively.

B. Case e | k
Note that in this case since e < k, we have k ≥ 2e. Recall from Theorem 2 that points on the optimal tradeoff satisfy
M=

a−1
X
j=0

min(eα, (d − je)β).

(95)

Points between and including MSMR and MBMR satisfy
d−k+e
d
β ≤ α ≤ β.
(96)
e
e
Lemma 6. (Entropy of data stored): Consider points on the optimal tradeoff. For an arbitrary set L of storage nodes of size
e, and a disjoint set A such that |A| = em < k for some integer m,
H(WL ) = eα,

(97)

H(WL |WA ) = min(eα, (d − em)β).

(98)

dim(WL ) = eα,

(99)

dim(WL ) − dim(WL ∩ WA ) = min(eα, (d − em)β).

(100)

For linear codes,

Proof: By reconstruction requirement, we write
M = H(W[k] )

(101)

= H(W[e] ) +

a−1
X

H(W{ej+1,...,e(j+1)} |W[je] )

(102)

a−1
X

(103)

j=1

≤ min(eα, dβ) +

min(eα, (d − ej)β)

j=1

= M,

(104)

where (103) uses Lemma 5. Thus, all inequalities must be satisfied with equality.
Remark 9. Lemma 6 states that the contents of any group of e nodes are independent. In particular, for each node i, we have
H(Wi ) = α. For a set A of nodes, |A| ≤ e, H(WA ) = |A|α.
Corollary 1. At the MBMR point, for any set L of size e and disjoint set A of size |A| = em < k, we have
dim(WL ∩ WA ) = emβ.
Proof: By Lemma 6 and eα = dβ,
dim(WL ) − dim(WL ∩ WA ) = min(eα, (d − em)β)
= (d − em)β.
Using the fact that dim(WL ) = eα = dβ, we obtain the result.
Lemma 7. For any set E of size e, and a disjoint set A of size d, the MBMR point satisfies
M
WE =
SjE , dim(SjE ) = β.
j∈A

SjE

SjE′
SjE

E
are linearly independent. For every set Q ⊆ A, dim(SQ
) = |Q|β. Moreover, each subspace has to
⊆ WE .
P
Proof: For exact repair, we need WE ⊆ SjE . Thus,

The subspaces
and
be in the span of WE :

j

X
SjE ) ≤ dβ.
dβ = eα = dim(WE ) ≤ dim(
j

Thus, every inequality has to be satisfied with equality.
Lemma 8. At the MBMR point, for any set E of e nodes and any other disjoint set Q of size |Q| ≤ k − e, we have
E
E
SQ
= WE ∩ WQ , dim(WE ∩ WQ ) = dim(SQ
) = |Q|β.

(105)

Proof: Consider Q nodes such that |Q| ≤ k − e helping in the repair of a set E of e nodes. Let J contains Q such that
|J| = k − e. Denote Qc = J\Q. From Corollary 1, we have dim(WE ∩ WJ ) = (k − e)β. On the other hand, from Lemma 7,
we have dim(SJE ) = (k − e)β and SJE ⊆ WE . Moreover, by definition, SJE ⊆ WJ . Thus, SJE ⊆ WE ∩ WJ . As the dimensions

E
match, it follows that SJE = WE ∩ WJ . Note that SA
⊆ WE ∩ WA holds for any subset A of size |A| ≤ d. Now, we write

SJE = WE ∩ WJ = WE ∩ (WQ + WQc )
⊇ WE ∩ WQ + WE ∩ WQc
E
E
E
⊇ SQ
+ SQ
c = SJ .

This implies that all inclusion inequalities have to be satisfied with equality and the result follows.
The next lemma plays an important role in establishing the non-existence of exact MBMR codes. It only holds true when
e ≥ 2, which conforms with the existence of single erasure MBMR codes.
Lemma 9. Consider the MBMR point. When e ≥ 2, for any set of e + 2 ≤ k nodes, labeled 1 through e + 2, it holds that
dim(We+2 ∩ W[e+1] ) = dim(We+2 ∩ W[e] ) = β.

(106)

Proof: We have
dim(W[e+2] ) = dim(W[e] ) + dim(We+1 + We+2 )
− dim(W[e] ∩ (We+1 + We+2 ))
= eα + 2α − 2β,
where the second equality follows from Lemma 6, Lemma 8. On the other hand, we write
dim(W[e+2] ) = dim(W[e] )
+ dim(We+1 ) − dim(We+1 ∩ W[e] )
+ dim(We+2 ) − dim(We+2 ∩ W[e+1] )
= eα + 2α − β − dim(We+2 ∩ W[e+1] ).
The lemma follows from equating both equations.
Theorem 10. Exact linear regenerating MBMR codes do not exist when 2 ≤ e < k and e | k.
Proof: Assuming that there exists an exact-repair regenerating code, we consider the first e nodes. Then, these nodes store
linearly independent vectors. We write, for i = 1, . . . , e, Wi = Vi1 Vi2 where Vi,1 contains β linearly independent columns
and Vi,2 contains the remaining (α − β) basis vectors for node i. Now, consider node e + 1. We have dim(We+1 ∩ W[e] ) = β
by Lemma 9. That means that node e + 1 contains β columns, linearly dependent on the columns from the first e nodes. Since
the first e nodes should be linearly independent, w.l.o.g, we can assume that the β dependent vectors of node e + 1, denoted
by Ve+1,1 , is of the form
Ve+1,1 =

e
X

Vi,1 xi ,

(107)

i=1

such that xi 6= 0β×1 ∀i = 1, . . . , e. Now, consider node e + 2. From Lemma 9, node e + 2 contains (α − β) vectors linearly
independent form vectors in nodes 1 through e + 1. The remaining basis vectors of node e + 2 (which are linearly independent
of the (α − β) vectors) are denoted by Ve+2,1 . Now, to repair any set of e nodes from the set of first e + 1 nodes, node e + 2
can only pass Ve+2,1 . Otherwise, Lemma 8 will be violated. Then, this implies that Ve+2,1 ⊆ WJ , for all J ⊆ {1, . . . , e + 1}
such that |J| = e. Then, it can be seen that Ve+2,1 can only be of the same form in (107)
Ve+2,1 =

e
X

Vi,1 yi , such that yi 6= 0β×1 ∀i = 1, . . . , e.

i=1

Similar reasoning applies to node i for i = e + 3, . . . , k + 1 to conclude that Vi,1 can be written as in (107).
Now, assume the first e nodes fail. Then, node i can only pass Vi,1 for i = e + 1, . . . k + 1. We recall from Lemma 8
[e]
that Si = Wi ∩ W[e] . The total number of vectors passed by these nodes is (k − e + 1)β ≥ (e + 1)β. On the other hand,
from (107), all Vi,1 are generated by eβ nodes. Thus, the set {Vi,1 , i = e + 1, . . . , k + 1} must be linearly dependent, which
contradicts the linear independence property of the passed subspaces passed for repair, as stated by Lemma 7.
C. Case e ∤ k
Recall that from the analysis of Theorem 2, for e ∤ k, at the MBMR point, two scenarios generate the same minimum cut:
u1 = [r, e, . . . , e] and u2 = [e, . . . , e, r].

Equivalently, we have
M = f (u1 ) = f (u2 ),

(108)

where f () is defined as in (6).
Moreover, all points on the tradeoff satisfy
M = min(rα, dβ) +

a−1
X

min(eα, (d − r − ie)β) = f (u1 ).

(109)

i=0

Points between and including MSMR and MBMR satisfy

d + ar − ae
d−k+e
β≤α≤
β.
(110)
e
r
Properties satisfied by exact regenerating codes developed in the previous section extend to the case e ∤ k with slight
modifications. We state the properties without detailed proofs as the techniques are the same.
Lemma 10. Consider points on the optimal tradeoff. For an arbitrary set R of storage nodes of size r, and a set A such that
|A| = je + r < k for some integer j ≤ a − 1, for all exact-regenerating codes operating on the functional tradeoff, it holds
that
H(WR ) = rα,
H(WE |WA ) = min(eα, (d − r − je)β).

(111)
(112)

For linear codes,
dim(WR ) = rα,
dim(WE ) − dim(WE ∩ WA ) = min(eα, (d − r − je)β).

(113)
(114)

Proof: The result can be derived by proceeding as in Lemma 6 and using the fact that M = f (u1 ) from (109).
Remark 10. in the case of e ∤ k, a set of e are no longer linearly independent. This is expected as eα > dβ. Instead, it can
be seen from Lemma 10 that any set of r nodes are linearly independent.
Lemma 11. For exact-regenerating codes operating at the MBMR point, given sets E, A, R and B such that |E| = e, E and
A are disjoint, R and B are disjoint, |A| = je with j ≤ a − 1, |R| = r and |B| = ae, it holds that
H(WE ) = dβ,

(115)

H(WE |WA ) = (d − je)β,
H(WR |WB ) = (d − ae)β.

(116)
(117)

dim(WE ) = dβ,
dim(WE ) − dim(WE ∩ WA ) = (d − je)β,

(118)
(119)

dim(WR ) − dim(WR ∩ WB ) = (d − ae)β.

(120)

For linear codes,

Proof: The result can be derived by proceeding as in Lemma 6 and using the fact that M = f (u2 ) from (108) and
eα ≥ dβ, rα ≥ (d − ae)β.
It is easy to see that Lemma 7 and Lemma 8 hold true for the case e ∤ k, and for conciseness we do not repeat these lemmas.
The following lemma is used to derive the contradiction.
Lemma 12. let k = ae + r, then at the MBMR point, for any set of r + 1 nodes, it holds that
dim(Wr+1 ∩ W[r] ) = β.

(121)

dβ = dim(W[e] )
e
X
dim(Wi ) − dim(Wi ∩ W[i−1] )
=

(122)

Proof: We have

i=1

(123)

= eα −

e
X

dim(Wi ∩ W[i−1] ),

(124)

i=r+1

where the last equality follows from the fact that the first r nodes are linearly independent. Thus, it follows that
e
X

dim(Wi ∩ W[i−1] ) = eα − dβ = (e − r)(α − aβ).

(125)

i=r+1

Now we write
e
X

(e − r)(α − aβ) =
≥

i=r+1
e
X

dim(Wi ∩ W[i−1] )

(126)

dim(Wi ∩ W[r] )

(127)

i=r+1

= (e − r) dim(Wr+1 ∩ W[r] ),

(128)

where the last equality follows using symmetry. Then, it follows that
dim(Wr+1 ∩ W[r] ) ≤ α − aβ.

(129)

Combining (125) and (129), we obtain
e
X

dim(Wi ∩ W[i−1] ) ≥ (e − r − 1)(α − aβ).

e
X

dim(Wi ∩ W[i−1] ) ≤

(130)

i=r+2

On the other hand, we have
e
X

dim(Wi ∩ WEi )

(131)

i=r+2

i=r+2

= (e − r − 1)β,

(132)

where Ei is a set of e nodes containing the first i − 1 nodes and arbitrary e − i + 1 nodes, excluding node i, and the equality
follows from Lemma 8. Combining (130) and (132), it follows

(e − r − 1)(α − aβ) ≤

e
X

dim(Wi ∩ W[i−1] ) ≤ (e − r − 1)β.

(133)

i=r+2

It follows that α − aβ = d−ae
r β ≤ β. The last inequality holds only when d = k and α − aβ = β. When d > k, we have
α − aβ > β. Therefore, we only consider the case d = k. Hence, it follows from (133) that
e
X

dim(Wi ∩ W[i−1] ) = (e − r − 1)β.

(134)

i=r+2

Using (125), we obtain dim(Wr+1 ∩ W[r] ) = β.
From the proof of the above lemma, we see that exact linear MBMR codes may only be feasible when d = k. The next
theorem states that in fact such codes do not exist.
Theorem 11. Exact linear regenerating MBMR codes do not exist when e < k and e ∤ k.
Proof: Consider repair of the set of nodes E containing nodes 1 through e. Consider helper node i. As dim(Wi ∩ W[r] ) =
dim(Wi ∩ W[e] ) = β, it follows that Wi ∩ W[r] = Wi ∩ W[e] = SiE . Then, each helper node sends vectors in the span of W[r] .
P
P
[e]
Thus, the span of all sub-spaces Si is included in the span of W[r] : SiE ⊆ W[r] . This implies that dim( SiE ) ≤ dim(W[r] ).
i

Namely, we should have dβ ≤ rα: this is a contradiction as dβ > rα.

i

0.26
tradeoff k=7
MBCR k=7
tradeoff k=8
MBCR k=8
tradeoff k=9
MBCR k=9

0.24

Storage per node α

0.22
0.2
0.18
0.16
0.14
0.12
0.1
0.5

0.6

0.7

0.8

0.9

1

Total bandwidth per helper γ

Fig. 4: Optimal repair tradeoffs for fixed e = 3 and different k ∈ {7, 8, 9}. The MBCR point lies on the tradeoff only in case
k = 7.
D. Minimum bandwidth cooperative regenerating codes as centralized multi-node repair codes
In [27], the authors argued that MBCR codes can be used as centralized multi-node repair regenerating codes. We recall
that MBCR codes are characterized with
M2de
M(2d + e − 1)
,γMBCR =
.
(135)
αMBCR =
k(2d − k + e)
k(2d − k + e)
In the case that e | k, it is shown that MBCR codes achieve the MBMR bandwidth, i.e, γMBCR = γMBMR . On the other hand
when e ∤ k, by imposing a certain entropy accumulation property on the entropy of any group of r nodes, [27] showed that the
bandwidth achieved by MBCR codes is optimal. It is important to note here that, from (24), it can be checked that the entropy
constraint condition results in γMBCR > γMBMR . Moreover, in both cases, it is not clear whether the storage size achieved by
MBCR codes is optimal. The next theorem determines the cases in which MBCR codes meet the functional tradeoff.
Theorem 12. Assume 1 < e ≤ k, then, minimum bandwidth cooperative regenerating codes meet the centralized functional
repair tradeoff if and only if k = ae + 1.
M(e−1)
Proof: When e | k, from (22) and (23), it follows that γMBMR = γMBCR and αMBCR = αMBMR + k(2d−k+e)
. Thus,
αMBMR < αMBCR . When e ∤ k, from (19) and (25), one can check that γMBMR < γMBCR < fr (0). Using (18), it follows that
the optimal storage size corresponding to γMBCR and achieving the functional repair tradeoff is given by

M − γMBCR gr (0)
r
M(2d + e − r)
=
k(2d − k + e)
M(r − 1)
.
= αMBCR −
k(2d − k + e)

α∗ (γMBCR ) =

(136)
(137)
(138)

Therefore, α∗ (γMBCR ) ≤ αMBCR with equality if and only if r = 1.
Figure 4 illustrates the functional tradeoff for fixed e = 3, M = 1 and multiple values of k ∈ {7, 8, 9} such that d = k. As
proved in Theorem 12, MBCR codes are optimal centralized repair codes only when r = 1, which corresponds to k = 7 in
Figure 4. When e | k, MBCR codes achieve the same bandwidth as MBMR codes, but have a higher storage cost. In Section V,
we investigate the achievability of MBMR codes under exact repair.
Remark 11. Theorem 12 proves that, when e ∤ k, r = 1, MBCR codes achieve an interior point on the functional tradeoff that
lies near the MBMR point. We note that the existence of this exact-repair interior point does not contradict the non-feasibility
result in Section VI, where we assume e|k.
VI. N ON - FEASIBILITY

OF THE EXACT- REPAIR INTERIOR POINTS

In this section, we study the non-feasibility of the interior points on the optimal functional-repair tradeoff for e | k, e |
d, 2e < k, similarly to [29]. We note that all interior points satisfy (d − k + e)β ≤ eα ≤ dβ. This can be written as

′

(d′ − a + 1)β ≤ α ≤ d′ β, where d =

d
e

and a = ke . This is similar to the single erasure case with reduced parameters.

Parameterization of the interior points. Let α = (d′ − p)β − θ, namely eα = (d − ep)β − eθ with p ∈ {0, 1, . . . , a − 1},
θ ∈ [0, β) such that θ = 0 if p = a − 1. Points at the tradeoff satisfy
M=e

a−1
X

min(α, (d′ − i)β).

i=0

A. Properties of Exact-Repair Codes
We present a set of properties that exact-repair codes, satisfying the optimal functional tradeoff, must satisfy.
Lemma 13. For a set A of arbitrary nodes of size ej, a set L of nodes of size e such that L ∩ A = ∅, we have


j ≤ p,
0
I(WL , WA ) = e((j − p)β − θ)
p<j<a


eα
j ≥ a.

(139)

Proof: First, we note that when j ≥ a, I(WL , WA ) = H(WL ) − H(WL |A) = H(WL ) = eα. In the following, we assume
j < a. We write
I(WL , WA ) = H(WL ) − H(WL |A)
= eα − min(eα, (d − je)β)
= e(α − min(α, (d′ − j)β))

(140)
(141)
(142)

= e(α − (d′ − j)β)+

(143)

= e((j − p)β − θ)+ .

(144)

Here (141) follows from Lemma 6.
Remark 12. Note here that only when e|k does (141) hold, when e ∤ k, H(WL ) < eα. In fact, as pointed out in Remark 11,
the non-feasibility result does not hold for e ∤ k.
Corollary 2. For an arbitrary set L of size e, and a disjoint set A such that |A| = em < k for some integer m, we have
L
H(WL |SA
) = H(WL |WA ) = min(eα, (d − em)β).

Proof: From Lemma 5, we have

L
H(WL |SA
)

(145)

≤ min(eα, (d − em)β). On the other hand, from Lemma 6,

L
H(WL |SA
) ≥ H(WL |WA ) = min(eα, (d − em)β).

(146)

L
Thus, H(WL |SA
) = H(WL |WA ) = min(eα, (d − em)β).

Lemma 14. In the situation where node m is an arbitrary helper node assisting in the repair of a second set of arbitrary nodes
L of size e, we have
L
H(Sm
) = β,

(147)

irrespective of the identity of the other d − 1 helper nodes. Moreover, for set B of size |B| ≤ d − k + e with B ∩ L = ∅, we
have
L
H(SB
) = |B|β.

(148)

Proof: Partition the set of d helpers into A and B such that |A| = k − e and |B| = d − k + e, such that m ∈ B. We have
L
H(WL |SA
) = min(eα, (d − k + e)β) = (d − k + e)β, as eα ≥ (d − k + e)β for all points on the tradeoff. Moreover, exact
L
L
L
L
repair requires H(WL |SA
, SB
) = 0. Thus, H(SB
) ≥ (d − k + e)β. This implies H(SB
) = (d − k + e)β. Moreover, it must
L
L
L
′
hold that H(Sm ) = β in addition to Sm and Sm′ being independent if m 6= m . Moreover, by choosing M ⊆ B, one obtains
L
H(SM
) = eβ.
Helper node pooling. Consider a set F consisting of a collection of f ≤ d + e nodes (f is a multiple of e), and a subset
R of the set F consisting of er′ nodes. A helper node pooling scenario is a scenario where on failure on any e nodes L ⊆ R,
the d helper nodes assisting in its repair include all the f − e remaining nodes in F . The remaining helper nodes are fixed
given L, denoted by V(L). Consider a subset of nodes M ⊆ F \R. Partition the nodes in R into arbitrary but fixed sets
R1 , R2 , . . . , Rr′ ,

(149)

R

R1
R
each of size e. Denote by SM
= (SM
, . . . SMr′ ) the collective transmitted information from helper nodes M to repair
R1 , . . . , Rr′ , respectively.

Lemma 15. In the helper node pooling scenario where min(a, fe ) > p + 2 ≥ r′ , for any set of e arbitrary node M ⊆ F − R,
we have
R
H(SM
) ≤ e(2β − θ).

(150)

Proof: If the statement holds true for some f, r′ , then it also holds true for all f ′ ≥ f and r′′ ≤ r′ . Thus, for the proof,
we only need to consider F = R ∪ M, |F | = f = e(p + 3), |R| = r′ e = (p + 2)e, |M | = e.
Consider repair of an arbitrary set of e nodes L ⊆ R, where the set of helpers include M and the e(p + 1) remaining nodes
in R. Then, we write
L
L
; WR ) = I(SM
; WL , WR−L )
I(SM

=
≥
=

(151)

L
L
I(SM
; WR−L ) + I(SM
; WL |WR−L )
L
I(SM ; WL |WR−L )
L
H(WL |WR−L ) − H(WL |WR−L , SM
)
L
L
H(WL |WR−L ) − H(WL |SR−L , SM )

(152)
(153)
(154)

≥
= min(eα, (d − e(p + 1))β) − min(eα, (d − e(p + 2))β)

(155)
(156)

= (d − e(p + 1))β − (d − e(p + 2))β = eβ.

(157)

Here (156) follows from Lemma 6 and Corollary 2. Then, we obtain
L
L
L
H(SM
|WR ) = H(SM
) − I(SM
; WR ) ≤ eβ − eβ = 0.

(158)

L
R
Hence, H(SM
|WR ) = 0. Since L is arbitrary, it follows that H(SM
|WR ) = 0.
It follows from Lemma 13 that
R
R
H(SM
) = I(SM
; WR ) ≤ I(WM ; WR ) = e(2β − θ).

Lemma 16. In the helper node scenario where min{a, fe } > p + 1 ≥ r′ , for an arbitrary set of e nodes M ⊆ F − R, and an
arbitrary pair of set of e nodes L1 , L2 , it must be that
L1 L2
H(SM
|SM ) ≤ eθ,

(159)

R
H(SM
) ≤ e(β + (r′ − 1)θ).

(160)

and hence

Proof: The set is R assumed to consist of |R| = er′ = e(p + 1) nodes, and the set F is such that F = R ∪ {M }, |M | = e.
Similar to Lemma 15,
L
L
L
I(SM
; WR ) ≥ H(WL |WR−L ) − H(WL |SR−L
, SM
)
′

(161)
′

= min(eα, (d − (r − 1)e)β) − min(eα, (d − r e)β)
= (d − pe)β − eθ − (d − (p + 1)e)β

(162)
(163)

= e(β − θ).

(164)

Then, it must be that
L
L
L
H(SM
|WR ) = H(SM
) − I(SM
; WR ) ≤ eβ − e(β − θ) = eθ.

(165)

Note that the last inequality holds for any set L ⊆ R. Next, consider L1 , L2 ⊆ R. For this, consider
L1
L2
H(SM
, SM
)
L1
L2
L1
L2
= I(WR ; SM
, SM
) + H(SM
, SM
|WR )

≤ I(WR ; WM ) +
= I(WR ; WM ) +

L1
L2
H(SM
, SM
|WR )
L1
L2
L1
H(SM |WR ) + H(SM
|WR , SM
)

(166)
(167)
(168)

≤ e(β − θ) + eθ + eθ = e(β + θ),

(169)

where the last inequality follows from Lemma 13 and (165). Then, we have
L1 L2
L1
L2
L2
H(SM
|SM ) = H(SM
, SM
) − H(SM
)
L1
L2
H(SM
, SM
)

=
− eβ
≤ e(β + θ) − eβ = eθ,

(170)
(171)
(172)

where the first equality follows from Lemma 14.
Finally, partitioning the nodes in R into sets R1 , R2 , . . . , Rr′ of size e, it follows
′

R
H(SM
)

≤

R1
H(SM
)

+

r
X

R

Ri
H(SM
|SMi−1 ) ≤ eβ + e(r′ − 1)θ.

(173)

i=2

B. Non-existence proof
For interior points, 1 ≤ p ≤ a−2. First, we consider the interior points that are multiple of β. That is: eα = (d−ep)β, θ = 0.
Theorem 13. Exact-repair codes do not exist for the interior points with θ = 0.
Proof: Consider a sub-network F consisting of d + e nodes. The parameters satisfy the condition in Lemma 16. Note that
by the regeneration property for any set of e nodes L ⊆ F , H(WL |SFL−L ) = 0. Moreover, for distinct M, L1 , L2 ⊆ F , with
L1 L2
θ = 0, we have H(SM
|SM ) = 0. We partition the nodes in F into groups of size e, denoted Li , i = 1, 2, . . . , d′ + 1. Then,
we write
L

d +1
M ≤ H(WF ) ≤ H(SFL1−L1 , . . . , SF −L
)
d′ +1

(174)

F −L ′
H(SLF1−L1 , . . . , SLd′ +1d +1 )

(175)

=

′

′

≤

dX
+1

H(SLFi−Li )

(176)

eβ

(177)

i=1

≤

′
dX
+1

i=1

= (d + e)β,

(178)

where the inequality (177) follows from Lemma 16. On the other hand,
M=

′
dX
−1

min(eα, (d − ie)β)

(179)

min((d − ep)β, (d − ie)β)

(180)

i=0

=

′
dX
−1

i=0

= 2(d − ep)β +

′
dX
−1

min((d − ep)β, (d − ie)β)

(181)

i=2

≥ 2(d − ep)β + (a − 2)eβ

(182)

≥ 2eβ + (d − ep)β + (a − 2)eβ
= (d − 2e)β + (k − 2e − ep)β

(183)
(184)

≥ (d − 2e)β,

(185)

where we assume 1 ≤ p ≤ a − 2 (non-MSMR point). Thus, ep + 2e ≤ k ≤ d. Both bounds are contradictory, thus proving the
impossibility result in the case of θ = 0.
Theorem 14. For any given values of M, exact-repair regenerating codes do not exist for the parameters lying in the interior
of the storage-bandwidth tradeoff when θ 6= 0, except possibly for the case p + 2 = a and θ ≥ d−ep−e
d−ep β.
Proof: See Appendix C.

VII. M ULTI - NODE REPAIR FOR

MINIMUM BANDWIDTH REGENERATING CODES

In Section V, we proved that MBMR codes are not achievable for linear exact repair codes, when 2 < e < k. When e = 1,
exact MBMR codes are MBR codes and their existence is well established in the literature [25]. Adaptive regenerating codes
possess the extra feature that the number of helpers involved in the repair process can be adaptively selected, which provides
the storage system with robustness to the network varying conditions [1], [18]. Adaptive MSR codes have been constructed
in [41]. On the other hand, adaptive MBR codes have been investigated in [22], in which case optimal repair means that the
total repair bandwidth for each number of helpers d is the lowest possible, and is given by α (assuming the storage per node
contains no redundancy). It is shown in [22] that adaptive MBR codes, designed for arbitrary d, dmin ≤ d ≤ dmax , are equivalent
to MBR codes that are designed for the worst-case number of helpers dmin , and they satisfy optimal repair for arbitrary number
of helpers dmin ≤ d ≤ dmax . Namely, adaptive MBR codes satisfy for any dmin ≤ d ≤ dmax ,
dβ = α,
α=

(186)

2dmin M
dmin M
=
,
−k 2 + k + 2kdmin
dmin k − k2

(187)

where the storage size α corresponds to the MBR code with dmin helpers.
A natural question of interest is, given an MBR code, whether we can efficiently recover from varying number of failures
simultaneously. In this section, we investigate the problem of repairing multiple failures in MBR codes under exact repair, for
varying number of helpers d and varying number of failures e, such that dmin ≤ d ≤ dmax , 1 ≤ e ≤ k, e + d ≤ n. First, we
derive a lower bound on the multi-node repair bandwidth for MBR codes.
Theorem 15. Consider an (n, k, d, α, β) MBR regenerating code, the total repair bandwidth γMBR (e) needed to repair any set
of 1 ≤ e ≤ k nodes satisfies
 
e α
γMBR (e) ≥ eα −
.
(188)
2 d
Proof: Assume w.l.o.g that the first e nodes are to be repaired. From [26], at the MBR point, for any set of A nodes of
size m < k and for i ∈
/ A, we have H(Wi |WA ) = mβ. Therefore,
 
e
e
X
X
e
(d − i + 1)β = (ed −
)β.
(189)
H(Hi |W[i−1] ) =
H(W[e] ) =
2
i=1
i=1

Noting that at the MBR, α = dβ, (188) follows.
We now briefly describe a construction of adaptive MBR codes that simultaneously and efficiently repair single node failures,
presented in [22]. Then, we show how to optimally repair multiple failures in this construction.
A. Adaptive MBR construction

The construction is based on product matrix codes [22], [25]. We first review the repair of single failure, and then present
dQ
max
d . Define z = dαmin and construct the (α × α) data matrix M as
our scheme for multiple failures. Let α =
d=dmin



M1
O

M = .
 ..
O

O
M2

···
···
..
.

O
O
..
.

···

O

Mz





,


(190)

where O is a (dmin × dmin ) zero matrix and each of the submatrices Mi is filled with information symbols, and is symmetric
and satisfies the structural properties of a product-matrix MBR code for parameters k and dmin . For instance, Mi is given by


Ni L i
′
,
(191)
Mi =
Lti O
′

where Ni is a symmetric (k × k) matrix, Li is (k × (dmin − k)) matrix, and O is (dmin − k) × (dmin − k) zero matrix. let Ψ
be an (zn × dmin ) Vandermonde matrix, with rows denoted by ψjt , for 1 ≤ j ≤ zn. Then, storage node l is associated with
i
h
h
i
t
t
t
t
M1 , . . . , ψlz
Mz .
, . . . , ψlz
M = ψ(l−1)z+1
wlt = ψ(l−1)z+1

Single node repair. Denote the set of helpers by H such that |H| = d and dmin ≤ d ≤ dmax . Let Ω be an (z × z) matrix such

that Ωt is a Vandermonde matrix. Assume that node f fails. Let Ωd an ( αd × z) containing the first
let Φi be an (α × z) matrix


ψ(i−1)z+1


..
Φi = 
.
.
ψiz

α
d

rows of Ω. Moreover,

Each helper node ij ∈ H transmits stij ,f = witj Φf Ωtd . After simplification, the replacement node obtains


wft Φi1 Ωtd , . . . , Φid Ωtd = wft ΘH

Noting that ΘH is invertible [22], the replacement node can thus recover wft .
B. multi-node repair in adaptive MBR codes
We state our result in the following theorem.

Theorem 16. Adaptive MBR regenerating codes with storage per node α and arbitrary number of helpers dmin ≤ d ≤ dmax ,
presented in [22], can simultaneously and optimally repair e failures with d helpers, for all dmin ≤ d ≤ dmax , 1 ≤ e ≤ k,
e + d ≤ n.
Proof: Assume w.l.o.g that the first e nodes failed and d helpers are used, where dmin ≤ d ≤ dmax , 1 ≤ e ≤ k, e + d ≤ n.
Denote the helpers by the set H = {i1 , . . . , id }. First, the repair of node 1 is done by contacting all the d helpers and
downloading αd symbols from each one of them, using the procedure described for single node repair. Node 2 is then repaired
using only dmin helpers, comprising repaired node 1 and any other dmin − 1 helpers in H, such that each helper provides
α
dmin = z symbols. The same procedure is then applied repeatedly until recovering the last node e by contacting any dmin − e + 1
helpers in H and using contributions from the e − 1 already repaired nodes. The overall repair bandwidth is given by
 
e−1
e α
α X
z(dmin − i) = eα −
,
d +
2 dmin
d i=1
which matches the bound in (188), establishing the optimality of the repair procedure.

Remark 13. Repairing e failures in an (n, k, dmin , α, β) MBR code separately
 requires a bandwidth of size eα. However,
simultaneously repairing e failures using d ≥ dmin reduces the bandwidth by 2e dαmin .
Remark 14. The repair procedure of multiple erasures in Theorem 16 is asymmetric. However, one can always duplicate the
code a sufficient number of times to achieve a symmetric repair strategy (e.g. [11]).
VIII. C ONCLUSION
We studied the problem of centralized repair of multiple erasures in distributed storage systems. We explicitly characterized
the optimal functional tradeoff between the repair bandwidth and the storage size per node. For instance, we obtained the
expressions of the extreme points on the tradeoff, namely the minimum storage multi-node repair (MSMR) and the minimum
bandwidth multi-node repair (MBMR) points. In the case of e ≥ k, we showed that the tradeoff reduces to a single point,
for which we have provided a code construction achieving it. We described a general framework for converting single erasure
minimum storage regenerating codes to MSMR codes. Then we applied the framework to product-matrix codes and interference
alignment codes. Furthermore, we proved that the functional MBMR point is not achievable for linear exact repair codes.
Similarly, we have shown that the functional repair tradeoff is not achievable under exact repair, except for maybe a small
portion near the MSMR point. Finally, we showed how to adaptively repair multiple failures for MBR codes, with varying
number of helpers and varying number of failures.
Open problems include the generalization of the non-existence proof of linear exact-repair MBMR regenerating codes to
non-linear codes. It is interesting to determine the exact-bound for MBMR regenerating codes under exact-repair. Moreover,
characterization of storage-bandwidth tradeoff for exact repair for the interior points is still not known. Last but not least,
reducing the subpacketization size for high rate exact MSMR codes is an important direction to study for its practical
implications.
A PPENDIX
A. proof of Lemma 4
We first state the following lemma which will be useful in the proof.

30

25

f([1,3,3,3])

f(u)

f([3,1,3,3])
f([3,3,1,3])
20

f([3,3,3,1])

15

10
0

2

4

6

8

10

12

α

Fig. 5: Values of the cut function for different vectors u for k = 9, d = 10, β = 1
Lemma 17. The scenario u = [e, . . . , e, r] achieves the lowest final value of minimum cut:
lim f (u) ≥ lim f ([e, . . . , e, r]), ∀u ∈ P,

α→+∞

(192)

α→+∞

where f (u) and P are defined in (6) and (7), respectively.
Proof: for a specific cut u, we have
lim f (u)

α→+∞
g
X

(d −

=

i−1
X

uj )β

j=1

i=1

= dβg − β

g X
i−1
X

uj = gdβ − β

g−1
X

ui +

i=1

ui (g − i)

i=1

i=1 j=1

= β(dg − g

g−1
X

g−1
X

iui ) = β((d − k)g +

g
X

iui ).

(193)

i=1

i=1

To obtain the smallest minimum cut value, we need to solve the following problem
minimize

(d − k)g +

u,g

g
X

iui

i=1

subject to

1 ≤ ui ≤ e,
g
X
ui = k.

(194)

i=1

It can be seen that the solution to (194) is given by u = [e, . . . , e, r].

We now study the different functions Cj (α) for j = 0, . . . , a. An example of the different functions to be analyzed is given in
Figure 5, with k = 9, d = 10, β = 1. It is observed that u = [1, 3, 3, 3] generates the lowest cut before some threshold α∗ = 5,
after which the lowest cut is generated by u = [3, 3, 3, 1]. In the following, by analyzing Cj (α) for j = 0, . . . , a, we prove
that the above observation holds true in general.
a) j=0: we have
C0 (α) = min(rα, dβ) +
= r min(α,

a−1
X

min(eα, (d − r − ie)β)

i=0
a−1
X

(d − r − ie)β
dβ
e min(α,
)+
).
r
e
i=0

1
0

1

d−r−(a−1)e
e

d−r−(a−2)e
e

1
d−r−je
e

1

1

d−r−(j−1)e
e

∆

1

d−r−(j−2)e
e

d−r−e
e

e−r
e

e−r
e

>1

α
d
r

d−r
e

e−r
e

α
0

d−r−(a−2)e
e

d−r−(a−1)e
e

d−r−je
e

d−je
r

d−(j−1)e
e

d−(j−2)e
e

d−e
e

d
e

Fig. 6: relative positions of the breakpoints (with β = 1)
d
C0 (α) is a piecewise linear function with breakpoints given by { d−r−(a−1)e
β, d−r−(a−2)e
β, . . . , d−r
e
e
e β, r β}. C0 increases
from 0 at a slope of k. Its slope is then reduced by e by the successive breakpoints and then finally by r until it levels off.
b) 1 ≤ j ≤ a: for each j, we have

Cj (α) =

j−1
X

min(eα, (d − ie)β) + min(rα, (d − je)β) +

a−1
X

min(eα, (d − r − ie)β)

i=j

i=0

j−1
X

a−1

X
(d − r − ie)β
(d − je)β
(d − ie)β
e min(α,
) + r min(α,
)+
).
e min(α,
=
e
r
e
i=j
i=0
Cj (α) is also piecewise-linear function with non-increasing successive slopes. Its breakpoints are given by
{

d − r − (a − 1)e
d − r − je d − (j − 1)e
d
d − je
β, . . . ,
β,
β, . . . , β} ∪ {
β}
e
e
e
e
r

. The exact relative position of the breakpoint d−je
r β with respect to the other breakpoints of Cj (α) depends on the system’s
parameters. However, we give a lower bound on d−je
r β.
ed − rd − re + r2 − j(e2 − re)
d − je d − r − (j − 1)e
−
=
r
e
re
(e − r)d − re + r2 − a(e2 − re)
≥
re
(e − r)k − re + r2 − a(e2 − re)
≥
re
= 0,
where the first inequality follows by noticing that the expression is decreasing in j and letting j = a, and the second inequality
follows as the corresponding expression is increasing d.
Figure 6 illustrates the relative positions of all the breakpoints of C0 (α) and Cj (α), j ≥ 1, where for example d−je
∈
r
d−r−(j−1)e d−r−(j−2)e
,
]. We denote by
[
e
e
Cj (∞) = lim Cj (α).
α→+∞

Lemma 18. For 1 ≤ j ≤ a, there exists a point αc (j) ∈ [ de , dr ] such that
C0 (αc (j)) = Cj (αc (j)),
C0 (α) ≤ Cj (α)
C0 (α) ≥ Cj (α)

if α ≤ αc (j),
if α ≥ αc (j),

Cj (α) = Cj (∞)

if α ≥ αc (j).

(195)

Proof: W.l.o.g, assume β = 1. First, we note that
C0 (α) = Cj (α) = kα for α ≤

d − r − (j − 1)e
.
e

Next, we analyze the behavior of each of the functions C0 (α) and Cj (α) over the successive intervals Ii , ( d−r−ie
, d−r−(i−1)e
]
e
e
d−r−ie
and
define
s
(I
)
as
the
slope
of
C
(α)
just
before
α
=
x
.
Consider
a
given
for i ∈ {j − 1, j − 2, . . . , 1}. Let xi =
j i
j
i
e
interval Ii = (xi , xi−1 ], we have

•

C0 (α) has no breakpoint inside Ii . Thus, C0 (α) increases by
C0 (xi−1 ) − C0 (xi ) = s0 (Ii ) − e.

•

Cj (α) has either one or two breakpoints inside Ii .
1) in the case of Cj (α) has a single breakpoint inside Ii (at α =

d−ie
e ),

Cj (α) increases by

r
e−r
Cj (xi−1 ) − Cj (xi ) = sj (Ii ) + (sj (Ii ) − e)
= sj (Ii ) − e + r.
e
e
2) in the case of Cj (α) has two breakpoints inside Ii , namely at α =
Figure 6).
Assuming d−je
≤ d−ie
r
e , then, Cj (α) increases by
Cj (xi−1 ) − Cj (xi ) = (sj (Ii ) − r)(1 − ∆ −
d−je
r

≥

d−je
r

and α =

d−ie
e .

Let ∆ =

d−je
r

−

d−r−ie
e

(c.f.

e−r
e−r
)+
(sj (Ii ) − r − e) + sj (Ii )∆ = sj (Ii ) − e + ∆r.
e
e

d−ie
e ,

then, Cj (α) increases by
r
r
Cj (xi−1 ) − Cj (xi ) = sj (Ii ) + (k − e)(∆ − ) + (sj (Ii ) − r − e)(1 − ∆) = sj (Ii ) − e + ∆r,
e
e
which shows that the increase does not depend on the relative position of the two breakpoints.
Now that we have computed the increase increment of each Cj over Ii , we proceed to compare C0 (α) and Cj (α) for 1 ≤ j ≤ a.
We discuss two cases:
∈ Ij0 for some j0 ∈ [1, j − 1]. j0 may not exist, which will be discussed in the second case. Based
Case 1: Assume d−je
r
on the above discussion, it can be seen that
Assuming

Cj (α) ≥ C0 (α), for α ≤ xj0 .
This can seen by noticing that s0 (Ii ) = sj (Ii ) and that
(Cj (xi−1 ) − Cj (xi )) − (C0 (xi−1 ) − C0 (xi )) = r ≥ 0, ∀i < j0 .
Over Ij0 , Cj also dominates C0 at every point as s0 (Ij0 ) = sj (Ij0 ) and
(Cj (xi−1 ) − Cj (xi )) − (C0 (xi−1 ) − C0 (xi )) = ∆r ≥ 0.
For i > j0 , we have s0 (Ii ) − sj (Ii ) = r. Moreover, over each Ii , i > j0 , we have
(Cj (xi−1 ) − Cj (xi )) − (C0 (xi−1 ) − C0 (xi )) = (sj (Ii ) − e + r) − (s0 (Ii ) − e) = 0.
Combining the last equation and the observation that Cj (xj0 −1 ) ≥ Cj (xj0 −1 ), it follows that Cj continue to dominate C0
over the successive intervals Ii , i > j0 . So far, we have shown that
Cj (α) ≥ C0 (α), for α ≤

d−r
.
e

d
For α ≥ d−r
e , we observe that Cj increases with a slope of e and levels off at e while C0 increases at smaller slope given
d
d
by r and levels off at r > e . Moreover, we know from Lemma 17 that C0 levels off at a higher value than that of Cj . Thus,
there exists αc (j) ∈ [ de , dr ] that satisfies (195).
Case 2: Assume d−r
< d−je
≤ dr , then, using similar arguments as in the first case, it follows that for α ≤ d−r
e
r
e ,
d−r
d−r
d−r
Cj ( e ) ≥ C0 ( e ). At α = e , Cj (α) has a slope of r + e, which is higher than that of C0 , given by r. Thus, the slope
of Cj remains higher than than of C0 until Cj levels off. Combining these observations with the fact that C0 levels off at a
higher value, it follows that both curves will intersect only once. Moreover, the intersection at a point at which Cj has leveled
off i.e., we have αc (j) ≥ max( de , d−je
r ). Therefore, (195) holds also in this case.
Using Lemma 18 and the fact that Ca achieves the smallest final value from Lemma 17, that is Ca (∞) ≤ Cj (∞), j ∈ [0, a−1],
it follows that (15) holds for any j ∈ [0, a]. Moreover, as αc (a) ∈ [ de , dr ], αc (a) satisfies

rαc (a) +

a−1
X

(d − r − ie)β = (a + 1)βd − eβ

i=0

which implies that

rαc (a) + a(d − r −
Simplifying the last equation yields (16).

a2 + a
,
2

a2 + a
ea e
+ )β = (a + 1)βd − eβ
.
2
2
2

B. Storage-bandwidth tradeoff expression
We start with the case k = ae + r. The optimization trade-off is
minimize
α

α

(196)

subject to C(α) ≥ M.
The constraint is a piece-wise linear function C(α) is given by

(a + 1)βd − eβa(a + 1)/2,



a−1

P



rα +
bj ,


j=0

a−1
P
C(α) =
(r + ie)α +
bj ,



j=i







kα,

with αc =

d+ar−ae
β, bi
r
a−1
X

α ≥ αc ,
α ∈ [ be0 , αc ],
α ∈ [ bei ,

(197)

bi−1
],
e

for i = 1, . . . , a − 1,
b
α ≤ a−1
,
e

= (d − r − ie)β and

bj = β(a − i)(d − r −

j=i

e(a − 1 + i)
(a − i)(−2r + e + 2d − ae − ei)
)=γ
, γgr (i),
2
2d

such that
gr (i) =

(a − i)(−2r + e + 2d − ae − ei)
.
2d

The expression C(α) increases from 0 to a maximum
 value given by β((a + 1)d −
C −1 (M) under the condition M ≤ β((a + 1)d − a+1
2 ). Therefore, we obtain,

α∗ =


M

M ∈ [0, kba−1

k ,
e ]


a−1
P


 M− j=i bj
a−1
a−1
P
P

bi


bj , (r + ie) bi−1
bj ]
 r+ie , M ∈ [(r + ie) e +
e +
j=i

j=i


for i = a − 1, . . . 1,



a−1
P


bj
M−

a−1
a−1
P
P

j=0


bj ],
bj , rαc +
, M ∈ [ b0er +

r
j=0

with


). To solve (196), we let α∗ =

a+1
2

(198)

j=0

a−1

X
−a2 e2 + ae2 − 2aer + 2dae − e2 i2 − e2 i − 2eir − 2r2 + 2dr)
rbi
bj =
+ ibi +
γ
e
2de
j=i
−k 2 − r2 + e(k − r) + 2kd − e2 (i2 + i) − 2ier
γ
2ed
M
,
,γ
f (i)
=

such that
fr (i) =

−k 2

−

r2

2edM
.
+ e(k − r) + 2kd − e2 (i2 + i) − 2ier

Therefore, fixing M and varying γ, we write
M
M ∈ [0, kgr (a−1)γ
],

k,
e
M−γgr (i)
γM
γM
,
M
∈
[
,
α∗ =
r+ie
fr (i) fr (i−1) ], for i = a − 1, . . . 1,

 M−γgr (0)
, M ∈ [ fγM
, (gr (0) + d+ar−ae
)γ].
r
d
r (0)

(199)

As a function of γ, after simplifications, we obtain the expression of α∗ as in Theorem 3. We note that there are a piece-wise

linear portions on the curve. Moreover, the minimum bandwidth point γMBMR is given by
γMBMR =

M
dM
=
gr (0) + d+ar−ae
d(a
+
1)
−e
d

.

a+1
2

The expression of αMBMR is given by

M − γMBMR g(0)
d + ar − ea
= γMBMR
.
r
rd
in the case of e | k, we have r = 0. The expression of the tradeoff is obtained from (199) by setting r = 0 and eliminating
the last line. We note that in this case, there are a − 1 piece-wise linear portions on the trade-off curve.
αMBMR =

C. Proof of Theorem 14
Proof: Take a subnetwork F of d+e nodes. Let L, M ⊆ F be two disjoint groups of e nodes. Partition the d−e remaining
nodes into two sets, A of cardinality ep and B of cardinality d − ep − e. Exact repair requires
L
L
L
H(WL |SA
, SB
, SM
) = 0,
M
M
H(WM |SA
, SB
, SLM )

= 0.

(200)
(201)

It follows that
L
M
L
L
M
L
L
M
L
H(WL , WM |WA , SB
, SB
, SM
) =H(WL |WA , SB
, SB
, SM
) + H(WM |WL , WA , SB
, SB
, SM
)

=0.

(202)
(203)

Therefore, we have
L
L
M
, SB
, SM
) ≥ H(WL , WM |WA )
(SB
= H(WL |WA ) + H(WM |WA , WL )

(204)
(205)

= H(WL ) − I(WL ; WA ) + H(WM ) − I(WM ; WA , WL )
= eα − 0 + eα − e(β − θ)

(206)
(207)

= 2eα − eβ + eθ

(208)

= 2((d − ep)β − eθ) − eβ + eθ
= (2d − 2ep − e)β − eθ.

(209)
(210)

Here (207) follows from Lemma 13. We note that the lower bound does not depend on whether d is a multiple of e. Next, we
obtain an an upper bound on the same quantity.
Partition B into sets of size e, denoted by Li . We will use R = L ∪ M, r′ = 2, in the helper node pooling.
case: p + 2 < a: In this case, the parameters satisfy the condition in Lemma 15.
L
M
L
)≤
H(SB
, SB
, SM

X

L
M
L
, SL
) + H(SM
)
H(SL
i
i

(211)

X

e(2β − θ) + eβ

(212)

Li ∈B

≤

Li ∈B

= (d − pe − e)(2β − θ) + eβ
= (2d − 2ep − e)β − (d − ep − e)θ,

(213)
(214)

where the inequality (212) is obtained using Lemma 14 and Lemma 15. Equations (210) and (214) are in contradiction if
d − ep − e > e ⇐⇒ d > e(p + 2), which is true as d ≥ k = ae > (p + 2)e.
L
M
L
case: p + 2 = a: In this case, Lemma 16 is used to derive an upper bound on H(SB
, SB
, SM
). Lemma 16 does not
hold if a = 2. It holds for a > 2 ⇐⇒ k > 2e. Thus, we consider k > 2e. We have
X
L
M
L
L
H(SB
, SB
, SM
)≤
)
(215)
H(SLLi , SLMi ) + H(SM
Li ∈B

≤

X

e(β + θ) + eβ

(216)

= (d − ep)β + (d − ep − e)θ.

(217)

Li ∈B

Equations (210) and (217) are in contradiction when
θ<

d − ep − e
β.
d − ep

(218)

R EFERENCES
[1] V. Aggarwal, C. Tian, V. A. Vaishampayan, and Y.-F. R. Chen, “Distributed data storage systems with opportunistic repair,” in INFOCOM, 2014
Proceedings IEEE. IEEE, 2014, pp. 1833–1841.
[2] R. Ahlswede, N. Cai, S.-Y. Li, and R. W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204–1216, 2000.
[3] N. Alon and M. Tarsi, “Combinatorial nullstellensatz,” Combinatorics Probability and Computing, vol. 8, no. 1, pp. 7–30, 1999.
[4] R. Bhagwan, K. Tati, Y. Cheng, S. Savage, and G. M. Voelker, “Total recall: System support for automated availability management.” in NSDI, vol. 4,
2004, pp. 25–25.
[5] V. R. Cadambe, C. Huang, S. A. Jafar, and J. Li, “Optimal repair of MDS codes in distributed storage via subspace interference alignment,” arXiv
preprint arXiv:1106.1250, 2011.
[6] V. R. Cadambe, S. A. Jafar, H. Maleki, K. Ramchandran, and C. Suh, “Asymptotic interference alignment for optimal repair of MDS codes in distributed
storage,” IEEE Trans. Inf. Theory, vol. 59, no. 5, pp. 2974–2987, 2013.
[7] J. Chen and K. W. Shum, “Repairing multiple failures in the suh-ramchandran regenerating codes,” in 2013 IEEE International Symposium on Information
Theory, July 2013, pp. 1441–1445.
[8] H. Dau, I. Duursma, H. M. Kiah, and O. Milenkovic, “Repairing reed-solomon codes with multiple erasures,” arXiv preprint arXiv:1612.01361, 2016.
[9] ——, “Repairing reed-solomon codes with two erasures,” arXiv preprint arXiv:1701.07118, 2017.
[10] A. G. Dimakis, P. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” IEEE Trans. Inf. Theory,
vol. 56, no. 9, pp. 4539–4551, 2010.
[11] M. Elyasi, S. Mohajer, and R. Tandon, “Linear exact repair rate region of (k + 1, k, k) distributed storage systems: A new approach,” in 2015 IEEE
International Symposium on Information Theory (ISIT), June 2015, pp. 2061–2065.
[12] S. Ghemawat, H. Gobioff, and S.-T. Leung, “The google file system,” in ACM SIGOPS operating systems review, vol. 37, no. 5. ACM, 2003, pp.
29–43.
[13] P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the locality of codeword symbols,” IEEE Trans. Inf. Theory, vol. 58, no. 11, pp. 6925–6934,
Nov 2012.
[14] S. Goparaju, A. Fazeli, and A. Vardy, “Minimum storage regenerating codes for all parameters,” arXiv preprint arXiv:1602.04496, 2016.
[15] V. Guruswami and M. Wootters, “Repairing reed-solomon codes,” arXiv preprint arXiv:1509.04764, 2015.
[16] 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 Trans.
Inf. Theory, vol. 52, no. 10, pp. 4413–4430, 2006.
[17] P. Hu, C. W. Sung, and T. H. Chan, “Broadcast repair for wireless distributed storage systems,” in 2015 10th International Conference on Information,
Communications and Signal Processing (ICICS). IEEE, 2015, pp. 1–5.
[18] A.-M. Kermarrec, N. Le Scouarnec, and G. Straub, “Repairing multiple failures with coordinated and adaptive regenerating codes,” in International
Symposium on Network Coding (NetCod), 2011. IEEE, 2011, pp. 1–6.
[19] D. E. Knuth, The Art of Computer Programming, Volume 1 (3rd Ed.): Fundamental Algorithms. Redwood City, CA, USA: Addison Wesley Longman
Publishing Co., Inc., 1997.
[20] J. Li and B. Li, “Cooperative repair with minimum-storage regenerating codes for distributed storage,” in INFOCOM, 2014 Proceedings IEEE. IEEE,
2014, pp. 316–324.
[21] R. Li, J. Lin, and P. P. Lee, “Enabling concurrent failure recovery for regenerating-coding-based storage systems: From theory to practice,” IEEE Trans.
Comput., vol. 64, no. 7, pp. 1898–1911, 2015.
[22] K. Mahdaviani, A. Khisti, and S. Mohajer, “Bandwidth adaptive & error resilient regenerating codes with minimum repair bandwidth,” in IEEE
International Symposium on Information Theory (ISIT), 2016. IEEE, 2016, pp. 235–239.
[23] D. S. Papailiopoulos, A. G. Dimakis, and V. R. Cadambe, “Repair optimal erasure codes through hadamard designs,” IEEE Trans. Inf. Theory, vol. 59,
no. 5, pp. 3021–3037, 2013.
[24] N. Prakash, V. Lalitha, and P. V. Kumar, “Codes with locality for two erasures,” in IEEE International Symposium on Information Theory 2014, June
2014, pp. 1962–1966.
[25] K. Rashmi, N. Shah, and P. Kumar, “Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix
construction,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5227–5239, Aug 2011.
[26] K. Rashmi, N. B. Shah, P. V. Kumar, and K. Ramchandran, “Explicit construction of optimal exact regenerating codes for distributed storage,” in 47th
Annual Allerton Conference on Communication, Control, and Computing, 2009. Allerton 2009. IEEE, 2009, pp. 1243–1249.
[27] A. S. Rawat, O. O. Koyluoglu, and S. Vishwanath, “Centralized repair of multiple node failures with applications to communication efficient secret
sharing,” arXiv preprint arXiv:1603.04822, 2016.
[28] ——, “Progress on high-rate MSR codes: Enabling arbitrary number of helper nodes,” arXiv preprint arXiv:1601.06362, 2016.
[29] N. B. Shah, K. V. Rashmi, P. V. Kumar, and K. Ramchandran, “Distributed storage codes with repair-by-transfer and nonachievability of interior points
on the storage-bandwidth tradeoff,” IEEE Trans. Inf. Theory, vol. 58, no. 3, pp. 1837–1852, March 2012.
[30] N. B. Shah, K. Rashmi, P. V. Kumar, and K. Ramchandran, “Interference alignment in regenerating codes for distributed storage: Necessity and code
constructions,” IEEE Trans. Inf. Theory, vol. 58, no. 4, pp. 2134–2158, 2012.
[31] K. W. Shum and Y. Hu, “Cooperative regenerating codes,” IEEE Trans. Inf. Theory, vol. 59, no. 11, pp. 7229–7258, Nov 2013.
[32] W. Song and C. Yuen, “Locally repairable codes with functional repair and multiple erasure tolerance,” arXiv preprint arXiv:1507.02796, 2015.
[33] C. Suh and K. Ramchandran, “Exact-repair mds code construction using interference alignment,” IEEE Trans. Inf. Theory, vol. 57, no. 3, pp. 1425–1442,
2011.
[34] I. Tamo and A. Barg, “A family of optimal locally recoverable codes,” IEEE Trans. Inf. Theory, vol. 60, no. 8, pp. 4661–4676, Aug 2014.
[35] I. Tamo, Z. Wang, and J. Bruck, “Zigzag codes: MDS array codes with optimal rebuilding,” IEEE Trans. Inf. Theory, vol. 59, no. 3, pp. 1597–1616,
March 2013.
[36] A. Wang and Z. Zhang, “Exact cooperative regenerating codes with minimum-repair-bandwidth for distributed storage,” in INFOCOM, 2013 Proceedings
IEEE. IEEE, 2013, pp. 400–404.
[37] Z. Wang, I. Tamo, and J. Bruck, “Explicit MDS codes for optimal repair bandwidth,” arXiv preprint arXiv:1411.6328, 2014.
[38] ——, “Optimal rebuilding of multiple erasures in mds codes,” IEEE Trans. Inf. Theory, vol. 63, no. 2, pp. 1084–1101, 2017.
[39] Y. Wu and A. G. Dimakis, “Reducing repair traffic for erasure coding-based storage via interference alignment,” in 2009 IEEE International Symposium
on Information Theory. IEEE, 2009, pp. 2276–2280.
[40] Y. Wu, A. G. Dimakis, and K. Ramchandran, “Deterministic regenerating codes for distributed storage,” in Allerton Conference on Control, Computing,
and Communication. Citeseer, 2007, pp. 1–5.
[41] M. Ye and A. Barg, “Explicit constructions of high-rate MDS array codes with optimal repair bandwidth,” arXiv preprint arXiv:1604.00454, 2016.
[42] ——, “Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization,” CoRR, vol. abs/1605.08630, 2016. [Online].
Available: http://arxiv.org/abs/1605.08630

[43] M. Zorgui and Z. Wang, “Centralized multi-node repair in distributed storage,” in 2016 54th Annual Allerton Conference on Communication, Control,
and Computing (Allerton), Sept 2016, pp. 617–624.
[44] ——, “Centralized multi-node repair for minimum storage regenerating codes,” in IEEE International Symposium on Information Theory, 2017.
[Online]. Available: http://faculty.sites.uci.edu/zhiying/publications/

