arXiv:1802.00872v1 [cs.IT] 2 Feb 2018

Load-Balanced Fractional Repetition Codes
Alexandra Porter

Shashwat Silas

Mary Wootters

Department of Computer Science
Stanford University
Stanford, CA
amporter@stanford.edu

Department of Computer Science
Stanford University
Stanford, CA
silas@stanford.edu

Departments of Computer Science
and Electrical Engineering
Stanford University
Stanford, CA
marykw@stanford.edu

Abstract—We introduce load-balanced fractional repetition
(LBFR) codes, which are a strengthening of fractional repetition
(FR) codes. LBFR codes have the additional property that multiple node failures can be sequentially repaired by downloading no
more than one block from any other node. This allows for better
use of the network, and can additionally reduce the number of
disk reads necessary to repair multiple nodes. We characterize
LBFR codes in terms of their adjacency graphs, and use this
characterization to present explicit constructions LBFR codes
with storage capacity comparable existing FR codes. Surprisingly,
in some parameter regimes, our constructions of LBFR codes
match the parameters of the best constructions of FR codes.
Index Terms—Fractional repetition codes; distributed storage;
repair-by-transfer

I. I NTRODUCTION
In distributed storage, we would like to store a file across
n storage nodes, so that the system can be efficiently repaired
from node failures without data loss. In this paper, we focus
on two notions of “efficient:” network bandwidth and disk
access. That is, when a node (or a collection of nodes) fails,
we would like to minimize the amount of data that is read
and sent by surviving nodes in order to repair the system.
We would also like to maintain the MDS property, which
is that any k out of n nodes in the system are sufficient to
recover the entire file. In this work, we present load-balanced
fractional repetition (LBFR) codes, which are a strengthening
of fractional repetition (FR) codes. FR codes are repetitionbased schemes which admit minimal bandwidth and disk
access, and which have been well-studied since they were
introduced in 2010; see [4], [9], [11]–[15].
LBFR codes have all of the same benefits of FR codes
for a single repair—in particular, minimal bandwidth and
disk access—but have additional benefits when multiple nodes
fail. As the name implies, LBFR codes achieve better loadbalancing between helper nodes in the case of multiple failures. This makes better use of the network during a repair, and
importantly can improve the number of disk accesses required
during the repair of multiple nodes.
A. Fractional repetition codes
Fractional repetition codes were introduced in [4] as a generalization of the codes in [10]. FR codes work by replicating
AP is partially supported by the National Science Foundation Graduate
Research Fellowship under Grant No. DGE-1656518. SS is partially supported
by a Google Graduate Fellowship in Computer Science. SS, AP and MW are
all partially supported by NSF Grant CCF-1657049.

data. A single data block B is replicated ρ times and each
copy is stored on a different node; each node stores α blocks.
When a node fails it is repaired using copies of each of its α
blocks stored elsewhere on the system. Formally, an FR code
is defined as follows:
Definition 1 ( [4]). A (n, α, ρ) fractional repetition code is a
collection of n subsets N1 , ..., Nn of [θ] := {1, 2, ..., θ} with
nα = ρθ such that:
1) |Ni | = α for i = 1, ..., n;
2) For each b ∈ [θ], |{Ni : b ∈ Ni }| = ρ; ρ is called the
repetition degree.
Because each block is replicated ρ times, a (n, α, ρ) FR
code can tolerate up to ρ − 1 node failures. Additionally, most
constructions of FR codes naturally have a load-balancing
property which ensures that a single failed node can be
repaired by downloading a single block from each of α
surviving nodes (as opposed to α blocks from a single node).
In this work, we’ll extend this latter property to ρ − 1 failures.
FR codes can be used as a building block to obtain codes—
called DRESS codes [4]—with the MDS property, and with
optimal disk access and network bandwidth. This is shown in
Figure 1: an FR code is concatenated with an outer maximum
distance separable (MDS) code. Suppose that any k nodes in
the FR code contain at least M distinct blocks between them.
Then we choose an outer MDS code which encodes M data
blocks x1 , . . . , xM as θ encoded blocks B1 , . . . , Bθ , so that
the concatenated code can recover the whole file ~x from any k
nodes. For an FR code C, let MC (k) is the minimum number
of unique data blocks contained in any set of k ≤ α nodes.
In light of the above discussion, MC (k) is called the storage
capacity of C.
The goal is to store as much information as possible: that
is to make M as large as possible given k, α, and ρ. This
parameter M is called the storage capacity of the system. The
fundamental trade-offs here are well-studied. In the case where
any α nodes should be able to repair a single failed node, this
is a special case of regenerating codes at the MBR point, and
the cut-set bound [3] gives an upper bound on M . FR codes
which meet this bound—or exceed it—are termed universally
good in [4]. We will discuss the quantitative definition of
universal goodness more in Section II.

B1
B2
x1
x2

FR code
B1
Each block B1
is replicated
on ρ nodes

MDS code

n nodes,
each storing α
blocks

xM
Bθ

Fig. 1. A DRESS code is obtained by concatenating an outer MDS code with
an FR code. The FR code replicates each block Bi ρ times, and stores each
copy on a separate storage node; each node holds α blocks.
N1 N2 N3 N4 N5 N6 N7 N8 N9
1 1 1 2 2 3 3 4 4
2 4 6 3 6 4 5 5 6
1

6

2

1
2
N10

4
4
6

(a)

N90

N1 N2 N3 N4 N5 N6
1 1 1 2 2 3
2 4 6 3 5 4
1
1
2
2
2
N10
2
5
(b)
N50

N7 N8 N9
3 4 5
6 5 6
5

Fig. 2. (a) A (9,2,3)-FR code repairs N1 and N9 . (b) A (9,2,3)-LBFR code
repairs N1 and N5 . Both satisfy |Ni ∩ Nj | ≤ 1 for all i 6= j and hence are
universally good.

B. Motivation
Before defining LBFR codes, we first explain the problem
with FR codes that they are solving. In this paper, we focus
on the repair of multiple failed nodes, and we focus on greedy
repair methods for these nodes. That is, if a node Ni fails, we
would like to repair it by greedily searching the system for any
existing copies of the blocks that Ni needs, without taking into
account the full set F of failed nodes. In this model, standard
FR codes have some drawbacks. To see these, we consider the
example shown in Figure 2(a).
Figure 2(a) shows a universally good (9, 2, 3)-FR code with
9 nodes and 6 data blocks. If a single node (say, N1 ) fails,
then it can be repaired by downloading one block from each
of two different nodes. However, suppose that both N1 and
N9 fail simultaneously, and that N1 is greedily repaired first
using N3 and N5 . Then there are no remaining copies of block
B6 in unused nodes, and one of N3 and N5 (in the figure, it
is N5 ) must send a second block to N90 to repair N9 .
Is it possible to come up with a code which allows for the
repair of ρ − 1 failures, downloading just one symbol from
each surviving block? It is not hard to see that, in this model,
the answer is no: suppose that the ρ − 1 failed nodes were all
holding block B1 . Then all of these ρ−1 would need to contact
the same surviving node to obtain B1 . However, if the repair
is allowed to be sequential—meaning that previously repaired
nodes are allowed to be used as helper nodes themselves—
then in fact this stronger load-balancing property is possible,
even with greedy repair.

LBFR codes (defined below) are defined precisely to allow
for greedy sequential repair of multiple failed nodes with
disjoint repair groups. Figure 2(b) shows an LBFR code with
the same parameters as the FR code in Figure 2(a). If nodes
N1 and N9 fail, it can be checked that no matter how N1
is repaired, N9 can still be repaired using a disjoint repair
group (we will explain how to verify this in Section III), and
this holds for any pair of nodes with |Ni ∩ Nj | = 0. The
other case (shown in Figure 2(b)) is when two nodes with
overlapping contents fail—say, N1 and N5 , which share block
B2 . In this case, there is no non-sequential way to repair both
nodes with disjoint repair groups, since only one copy of block
B2 remains. However, if we are allowed to use N10 as a helper
node after it is repaired, then we can repair N5 with disjoint
repair groups, as shown.
Our main result is that good LBFR codes exist and moreover
that there are some parameter regimes where the parameters
of FR codes match those of LBFR codes.
It is worth asking why we might want this. While LBFR
codes do obtain the load-balancing property we were originally
after, it came at the price of sequential repair, and it is not
immediately clear that making this trade-off improves any
of the desiderata that we care about. One reason the LBFR
property is desirable is that it has implications for data read.
In Figure 2(a), N5 must read two blocks, B2 and B6 . However
in Figure 2(b), N5 reads only one block, which is sent to N10 .
Now, N10 does not need to first write and then read this block
before sending it on to N50 ; rather it can send and then write.1
This saves a single disk access in this set-up, and in general
when making ρ − 1 repairs it can save as many as ρ − 2 disk
accesses.
Additionally, we expect that the load-balanced sequential
setting could yield improvements in practice, for example if
the blocks are being sent one packet at a time: this would
allow the node N10 to begin forwarding information before it
is completely repaired.2
Finally, we note that existing constructions of FR codes do
not in general have this LBFR property. For example, it is not
hard to check that the FR codes obtained from Steiner systems
in [4] (for example, shown in Figure 5 in that work) are not
LBFR codes.
C. Outline and contributions
After a brief discussion of related work in Section II, we
formally define LBFR codes in Section III. The main technical
contribution is Theorem 1, which characterizes LBFR codes
precisely in terms of their adjacency graphs. In Theorem 2, we
1 Moreover, the situation depicted in Figure 2(a) can be adapted to the
parallel setting, with the guarantee that N4 reads only one block which it
sends to both N10 and N50 .
2 Of course, this motivation comes with the caveat that if we are going to
sub-divide the blocks, perhaps we should have just used smaller data blocks
to begin with. This caveat makes this application less compelling than the
previous one in theory, but in practice there are plenty of reasons why we
would have a fixed block size. In particular, sub-dividing the blocks further
would increase the number of nodes that each replacement node needs to
contact.

show that LBFR codes are automatically univerally good, if
they exist. Finally, in Section IV, we give explicit constructions
of LBFR codes—based on our characterization—and establish
that optimal LBFR codes exist in the parameter regimes where
we know that optimal FR codes exist.
II. BACKGROUND AND RELATED WORK
Since FR codes were introduced in [4], there have been several constructions in that paper and follow-up works extending
the possible parameter regimes; see [8] and the references
therein. The goal of these works is to create FR codes C in a
variety of parameter regimes which lead to DRESS codes with
the largest possible storage capacity MC (k). To understand
what the limitations on MC (k) are, [4] considered the cut-set
bound of [3], a general lower bound which applies in particular
to Minimum Bandwidth Regenerating (MBR) codes. The cutset bound implies that the storage
 capacity CM BR (n, k, α) for
MBR codes is equal to kα− k2 . [4] defined an FR code C to be
universally good if MC (k) ≥ CM BR (n, k, α). However, it is
possible for MC (k) to be strictly greater than CM BR (n, k, α);
this is because FR codes allow for table-based repair: they
guarantee that there exists a set of α helper nodes which can
repair any failure, while MBR codes guarantee that any set of
α nodes will work.
Given that the storage capacity for FR codes can exceed
CM BR (n, k, α), it is natural to ask what the optimal storage
capacity is. The work of [4] provides two upper bounds. The
tighter of the two is a recursive upper bound, which establishes
that MC (k) ≤ g(k), where g(k) is defined
by
m
l recursively
ρg(k)−kd
. The
g(1) = d and g(k + 1) = g(k) + d −
n−k
work of [11] gave constructions of FR codes matching this
bound, showing that it is tight in some parameter regimes.
Following [11], we say that an FR code C is k-optimal if
MC (k) = g(k), and optimal if this holds for all k ≤ α.
There are many approaches to constructing FR codes for a
wide range of parameter regimes. In [15], universally good FR
codes are constructed from Group Divisible Designs and in [9]
new construction methods are used to achieve more parameters
for FR codes. More recent work, including [13], [12] and [14],
have focused on constructions FR codes for systems with
heterogeneous repetition degree, node storage capacity, and
link costs. There are also many notions in coding theory which
are related to LBFR codes, including batch codes, PIR codes,
and Fractional Repetition Batch codes. We omit the discussion
of these due to space constraints.

failed node corresponds to a contiguous group of α blocks in
the sequence. We define the repair group for a node in a repair
sequence S as RS (Ni ) = {RS (Bj , Ni ) | Bj ∈ Ni }. A repair
sequence is valid if for any Ni that failed, RS (Bj , Ni ) 6= Nl ∈
F for l > i, meaning the sequence does not require use of a
failed and un-repaired node. We say that a repair sequence
has disjoint repair groups if the sets RS (Ni ) are disjoint for
i 6= j, meaning that no helper node has to send information to
more than one replacement node. With this notation in place,
we define an LBFR code as follows.
Definition 2. A (n, α, ρ) LBFR code C, is a set of subsets
N1 , ..., Nn of the set {B1 , ..., Bθ } such that nα = θρ where
each Ni for i ∈ [n] corresponds to a node and each Bj for
j ∈ [θ] corresponds to a data block. C then has the properties:
1) |Ni | = α for i = 1, ..., n;
2) For each Bj , j ∈ [θ], |{Ni : Bj ∈ Ni }| = ρ;
3) For any multi-set of ρ − 1 failed nodes {N1 , ..., Nρ−1 },
and for all 1 ≤ t < ρ − 1, the following holds: For any
valid repair sequence St = [Bj , RS (Bj , Ndj/αe )]tj=1
such that no node RS (Bj , Ndj/αe ) is repeated, there
exists a node RS (Bt+1 , Nd(t+1)/αe ) not in St to repair
the next block.
The first two properties are identical to those of Definition 1.
The third property guarantees precisely that LBFR codes can
be greedily sequentially repair any sequence of up to ρ −
1 failed nodes using disjoint repair groups, as described in
Section I-B.
A. Adjacency Graph Characterization
We define the adjacency graph for an FR code (and hence
also for an LBFR code) as follows.
Definition 3. For a (n, α, ρ) fractional repetition code C,
the adjacency graph GC is an undirected bipartite graph
(V1 , V2 , E) such that |V1 | = n and |V2 | = θ. Relate GC
to C with the function v such that v(Ni ) ∈ V1 corresponds
to node Ni and v(Bj ) ∈ V2 corresponds to block Bj . Then
(v(Ni ), v(Bj )) ∈ E(GC ) if and only if Bj ∈ Ni .
The adjacency graph GC for FR code C is bi-regular with
d(v(Ni )) = α for all v(Ni ) ∈ V1 and d(v(Bj )) = ρ for all
v(Bj ) ∈ V2 . Above, d(v) denotes the degree of a vertex v in
the graph; we will use Γ(v) to denote the neighborhood of v
in GC .

III. LBFR CODES

Theorem 1. An FR C described by adjacency graph GC is a
LBFR code if and only if GC has no 4- or 6-cycles.

We begin with some notation in order to formally define
LBFR codes. Suppose a set of nodes F = {N1 , N2 , ..., Nρ−1 }
fails. A repair sequence S for F is defined as a sequence
of blocks sent in the process of repairing the nodes in F .
α(ρ−1)
Formally, we write S = [(Bj , RS (Bj , Ni ))]j=1 , where
RS (Bj , Ni ) is the node which sends data block Bj to the
replacement node Ni0 for Ni in the sequence. We assume
that the blocks corresponding to a node Ni ∈ F are grouped
together in S, so Ni = {B(i−1)α+j : 1 ≤ j ≤ α}. Thus, each

Theorem 1 shows how we can check that the code shown in
Figure 2(b) is indeed an LBFR code; indeed, it is straightforward to verify that the associated graph has no 4 or 6 cycles.
We prove the two directions of Theorem 1 in Lemmas 1
and 2 below. Before we prove the theorem, we note that this
may be surprising. Graphs without 4- or 6-cycles have been
useful in constructing batch codes [2]; however, those connections are not a tight characterization. In contrast, Theorem 1
shows that the load-balancing property that we are after—a

very operational definition—is in fact equivalent to this very
combinatorial statement.

N2 and N3 already. Thus the graph is not an LBFR adjacency
graph because LBFR Property 3 does not hold.

Lemma 1. Let GC = (V1 , V2 , E) be a bi-regular bipartite
graph without 4- or 6-cycles, such that |V1 | = n, |V2 | = θ,
with left degree α and right degree ρ. Then GC is the adjacency
graph of a (n, α, ρ) LBFR code C.
Proof. Suppose that GC is as above. Properties 1 and 2 of
LBFR codes follow for C directly from the definition of GC .
We next prove Property 3 for some multi-set F =
{N1 , ..., Nρ−1 } of failed nodes. Suppose that B1 is the first
block needed by the first node N1 ∈ F . Since |Γ(v(B1 ))| = ρ
and at most ρ − 1 of these neighbors are unavailable to
repair N1 , there exists a valid node for RS (B1 , N1 ). Now
we proceed by induction. Suppose the repair sequence St =
[Bj , RS (Bj , Ndj/αe )]tj=1 for some t < α(ρ − 1) is valid and
has disjoint repair groups. Let i = d(t+1)/αe, so the sequence
would be continued by transferring block Bt+1 to repair Ni .
We show that at most ρ − 1 locations of Bt+1 are unavailable
to be RS (Bt+1 , Ni ) (including Ni itself), leaving at least one
node available such that Property 3 holds.
First, we show that if Bt+1 is not the first block of Ni to
appear in the sequence (i.e. t + 1 > α(i − 1) + 1) no node
N such that Bt+1 ∈ N has been used to repair an earlier
block for Ni . Indeed, suppose that there were such a block
Bh that appeared before Bt+1 in Ni ; then the node N also
contains Bt+1 and Bh . But then v(N )v(Bh )v(Ni )v(Bt+1 ) is
a 4-cycle, which is a contradiction.
Now suppose that in fact, each of the ρ − 1 locations of
Bt+1 other than
S Ni is unavailable, so by the previous step each
must be in ( `∈[i−1] RS (N` )) ∪ {Ni+1 , ..., Nρ−1 }. However,
if two nodes corresponding to vertices in Γ(v(Bt+1 )) were in
RS (N` ) for some N` 6= Ni , the adjacency graph would have
a 6-cycle. Then at most i − 1 + ((ρ − 1) − i) = ρ − 2 instances
of Bt+1 are accounted for in nodes other than Ni . Thus there
is some node in Γ(v(Bj )) which is neither already used in St
nor not yet repaired, and this node can be used to transfer Bj
to Ni in repair. This establishes the inductive step and hence
Property 3.

Lemma 2. Let C be a (n, α, ρ) LBFR code. Then the adjacency graph GC contains no 4- or 6-cycles.
Proof. First suppose a 4-cycle exists in the adjacency graph
GC for C. Let B1 and B2 the blocks on the 4-cycle and N1
and N2 be the nodes. Now suppose all nodes containing B2
except for N1 fail, including N2 . Then N2 also needs B1
during repair. Greedily repair N2 first, using N1 for B1 . Then
there is no way to recover B2 and the graph is not an LBFR
adjacency graph because LBFR Property 3 does not hold.
Now suppose a 6-cycle exists in GC , with blocks B1 , B2 ,
and B3 and nodes N1 , N2 and N3 . Suppose the ρ−2 neighbors
of B3 outside the cycle fail, as well as N1 . Repair N1 using
N2 for B1 and N3 for B2 . Then ρ − 2 failed nodes remain
which need B3 , but no unused node has B3 since we used

a.

b.

Fig. 3. Proof of Lemma 2: a. failure of LBFR Property 3 with 4-cycle b.
failure of LBFR Property 3 with 6-cycle

B. Storage Capacity
In this section, we show that any LBFR code is universally
good: that is, the storage capacity exceeds (in fact, strictly
exceeds) that of any MBR code with the same parameters.
We recall that
[
MC (k) := | min
Si |
(1)
I⊂[n],|I|=k

i∈I

denotes the storage capacity of an LBFR code C.
Theorem 2. MC (k) > CM BR (n, k, d).
Proof. Let C be a LBFR code with adjacency graph GC .
Suppose that I = {N1 , . . . , Nk } minimizes the right hand side
of (1). Let
Pr denote the number of block duplications in I: that
is, r = i |Ni | − | ∪i∈I Ni | = kα − RC (k). We will show
k
r<
 2 for any G without 4 or 6 cycles; this will imply that
k
2 > r = kα − MC (k), and thus MC (k) > CM BR (n, k, α).
As a result of Property 3 in the definition of LBFR codes
and Lemma 1, any two nodes in {N1 , . . . , Nk } share at
most one block. Thus
 the maximum number of duplications

k
possible is r ≤ k2 . In fact,
we
must
have
r
<
. To see
2

k
this, assume that r = 2 . Then in fact any two nodes in
N1 , . . . , Nk share exactly one block. Consider N1 , N2 , and
N3 . Then if {B1 } = N1 ∩ N2 , {B2 } = N2 ∩ N3 , and
{B3 } = N3 ∩ N1 , for data blocks B1 , B2 , B3 , the cycle
v(N1 )v(B1 )v(N2 )v(B2 )v(N3 )v(B3 )v(N
1 ) is a 6-cycle. This

k
contradicts
Theorem
1.
Thus
r
<
,
and
so kα − MC (k) <
2

k
2 , as desired.
IV. C ONSTRUCTIONS
Theorem 1 implies that any graph without 4- or 6-cycles
gives rise to a LBFR code. Such graphs are well-studied, and
in this section we review these constructions and work out the
implications for distributed storage.
The main takeaways are that, in a variety of parameter
regimes, there are constructions of LBFR codes which match
the parameters of FR codes; and in many settings where
optimal FR codes are known, we also have constructions of
LBFR codes which are optimal (in that they meet the recursive
bound of [4]). Unfortunately, this is not a very wide range
of parameter regimes—as discussed below, we only know
of provably optimal FR codes when k, α, ρ are small—and

TABLE I
LBFR C ODE C ONSTRUCTION PARAMETERS
Source Graph
Cages [5]

Girth-8 Graphs
from Lazebnik et
al. [7]
Array transversal
design construction [1]
Lifts of Cages [6]

Data Blocks (θ)

Nodes (n)

α

ρ

M (k) (k ≤ d = α)

n

n

d

d

M (1) = d; M (k) ≥ M (k − 1) + d − b k2 c

q 3+s

q 3+t

qs

qt

M (k) ≥ kα −

k
2

+ bt + ρ

b
2

αp

ρp

α

ρ

M (k) ≥ kα −

k
2

+ bt + ρ

b
2

ni

ni

d

d

Constraints

M (1) = d; M (k) ≥ M (k − 1) + d − b k2 c

we still do not know if there exist LBFR codes which are
as good as FR codes in all parameter regimes. However, it
is encouraging that at least for existing constructions, LBFR
codes are competitive with general FR codes.
We discuss a few constructions below; see Table I for the
technical results. We refer the reader to [8] and the references
therein for a more complete discussion of existing FR codes.
Generalized quadrangles have been used in [11] to construct
optimal FR codes in settings where generalized quadrangles
exist. It turns out that in this case the underlying graphs don’t
have any 4- or 6-cycles, and so this construction is also an
LBFR code. These codes are k-optimal whenever k ≤ 3. In
particular, they are optimal (meaning, k-optimal for all α ≤ k)
when α = 3; this requires s ≤ t = 2 (where s and t are as
in Table I), and so there are only a small number of optimal
examples. However, this example does show that LBFR codes
can be optimal.
One may construct girth-8 graphs via cages [5]. For k ≤ d
up to d = 6, these constructions give universally good but not
optimal LBFR codes.
Lazebnik, Ustimenko, and Woldar [7] gave constructions
of girth-eight graphs (also used for constructions of batch
codes in [2]), and hence give constructions of LBFR codes. A
construction with the same storage capacity but slightly more
flexible parameters can also be obtained by using the array
construction for batch codes given in [1]. The storage capacity
M (k) of these codes is the same as the construction of FR
codes via transversal designs in [11]. As shown in [11], this
value of M (k) is optimal when α > α0 (k), for a function
α0 (k) which depends on ρ. Working out the details, this gives
optimal parameters when ρ = 2, or when ρ = 3 and α ≤ 5.
Finally, we note that it is possible to extend the range of
parameters for LBFR codes by taking covering graphs, or lifts,
of graphs for smaller LBFR codes [6]. The parameters in the
last row of Table I are achieved by taking lifts of known cages
of girth at least eight.
R EFERENCES
[1] Hilal Asi and Eitan Yaakobi. Nearly optimal constructions of PIR and
batch codes. arXiv preprint arXiv:1701.07206, 2017.

choose n, d such that a degree d
cage on 2n nodes with girth at least
8 exists
prime power q; t ∈ (0, 2]; s ∈
(0, 1] s.t. q s , q t ∈ Z, k ≤ q s
prime p, ρ ≤

√
p
√
α 2

choose n, d such that a degree d
cage on 2n nodes with girth at least
8 exists; any i ∈ Z+

[2] Alexandros G Dimakis, Anna Gál, Ankit Singh Rawat, and Zhao Song.
Batch codes through dense graphs without short cycles. arXiv preprint
arXiv:1410.2920, 2014.
[3] Alexandros G Dimakis, P Brighten Godfrey, Yunnan Wu, Martin J
Wainwright, and Kannan Ramchandran. Network coding for distributed
storage systems. IEEE Transactions on Information Theory, 56(9):4539–
4551, 2010.
[4] Salim El Rouayheb and Kannan Ramchandran. Fractional repetition
codes for repair in distributed storage systems. In Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference
on, pages 1510–1517. IEEE, 2010.
[5] Geoffrey Exoo and Robert Jajcay. Dynamic cage survey. Electron. J.
Combin, 15(16):4, 2008.
[6] Jonathan L Gross and Thomas W Tucker. Topological graph theory.
Courier Corporation, 1987.
[7] Felix Lazebnik, Vasiliy A Ustimenko, and Andrew J Woldar. New
constructions of bipartite graphs on m, n vertices with many edges
and without small cycles. Journal of Combinatorial Theory, Series B,
61(1):111–117, 1994.
[8] Oktay Olmez and Aditya Ramamoorthy. Fractional repetition codes
with flexible repair from combinatorial designs. IEEE Transactions on
Information Theory, 62(4):1565–1591, 2016.
[9] Hosung Park and Young-Sik Kim. Construction of fractional repetition
codes with variable parameters for distributed storage systems. Entropy,
18(12):441, 2016.
[10] Nihar B Shah, K Vinayak Rashmi, P Vijay Kumar, and Kannan
Ramchandran. Distributed storage codes with repair-by-transfer and
nonachievability of interior points on the storage-bandwidth tradeoff.
IEEE Transactions on Information Theory, 58(3):1837–1852, 2012.
[11] Natalia Silberstein and Tuvi Etzion. Optimal fractional repetition codes
based on graphs and designs. IEEE Transactions on Information Theory,
61(8):4164–4180, 2015.
[12] Quan Yu, Chi Wan Sung, and Terence H Chan. Irregular fractional
repetition code optimization for heterogeneous cloud storage. IEEE
Journal on Selected Areas in Communications, 32(5):1048–1060, 2014.
[13] Bing Zhu, Hui Li, Hanxu Hou, and Kenneth W Shum. Replicationbased distributed storage systems with variable repetition degrees. In
Communications (NCC), 2014 Twentieth National Conference on, pages
1–5. IEEE, 2014.
[14] Bing Zhu, Kenneth W Shum, and Hui Li. Heterogeneity-aware codes
with uncoded repair for distributed storage systems. IEEE Communications Letters, 19(6):901–904, 2015.
[15] Bing Zhu, Kenneth W Shum, Hui Li, and Shuo-Yen Robert Li. On
low repair complexity storage codes via group divisible designs. In
Computers and Communication (ISCC), 2014 IEEE Symposium on,
pages 1–5. IEEE, 2014.

