1

Bounds on Fractional Repetition Codes using
Hypergraphs

arXiv:1711.07631v1 [cs.IT] 21 Nov 2017

Krishna Gopal Benerjee, and Manish K Gupta, Senior Member, IEEE

Abstract—In the Distributed Storage Systems (DSSs), encoded
fraction of information is stored in the distributed fashion on
different chunk servers. Recently a new paradigm of Fractional
Repetition (FR) codes have been introduced, in which, encoded
data information is stored on distributed servers, where encoding
is done using a Maximum Distance Separable (MDS) code and a
repetition code. In this work, we have shown that an FR code
is equivalent to a hypergraph. Using the correspondence, the
properties and the bounds of a hypergraph are directly mapped
to the associated FR code. Some of the bounds are not satisfied
by any FR codes in the literature with equality. In general, the
necessary and sufficient conditions for the existence of an FR code
is obtained by using the correspondence. It is also shown that
any FR code associated with a linear hypergraph is universally
good.
Index Terms—Distributed Storage Systems, Fractional Repetition Code, Coding for Distributed Storage.

I. I NTRODUCTION
The distributed storage is a well studied area, which deals
with storing the data on distributed nodes in such a manner
so that it allows data accessibility at anytime and anywhere.
Many companies such as Microsoft and Google etc. provide
such storage services by using distributed data centers. In the
storage systems like Google file system [1], multiple copies of
data fragments are stored. Thus, the system becomes reliable
and the file can be retrieved from the system. At the same level
of redundancy, coding techniques can improve the reliability
for the storage system [2].
In [3], Dimakis et al. proposed a coding scheme called
regenerating codes which reduces the repair bandwidth, where
repair bandwidth is total number of communicated packets
to repair a failed node. In the distributed storage system
(DSS), encoded data packets are distributed among n nodes
such that any data collector can get the complete file by
collecting packets from any k (≤ n) nodes. Also, a failed
node can be repaired by replacing it with a new node having
at-least same amount of the data information. The newcomer
node is constructed by downloading packets from any d
(≤ n) active nodes in the DSS. The Minimum Bandwidth
Regenerating (MBR) codes are optimal with respect to the
repair bandwidth but not with respect to the computational
complexity. Motivated by this, in [4], Rashmi et al. proposed
a simple construction of Minimum Bandwidth Regenerating
codes, where a survivor node is only required to read and
transfer the exact amount of data to the replacement node
Krishna Gopal Benerjee and Manish K Gupta are with Laboratory of
Natural Information Processing, Dhirubhai Ambani Institute of Information
and Communication Technology Gandhinagar, Gujarat, 382007, India, e-mail:
(krishna gopal@daiict.ac.in and mankg@computer.org.).

without extra computation. The construction is extended to
new storage code called Fractional Repetition (FR) code [5],
[6]. A typical FR code is a two layer code with an outer MDS
code and an inner repetition code, where a linear [n, k, d]
code is called a Maximum Distance Separable (MDS) code
if k = n − d + 1. Initially, the FR code is defined on
homogeneous DSS (DSS with symmetric parameters). In such
systems, each node has same amount of encoded packets and
the same number of copies of each packets [5]. In many
cases, heterogeneous systems are preferred, in which the node
storage capacity and the packet replication factor need not
be uniform. In the literature, FR codes are constructed with
asymmetric replication factor [7], [8] and asymmetric node
storage capacity [9]–[12]. In [13], an FR codes with nonuniform node storage capacity are constructed using uniform
hypergraphs. A bound on the maximum file size is calculated
for a Locally Repairable Fractional Repetitions (Locally Repairable FR) code in [14], where a Locally Repairable FR code
is an FR code in which the repair degree of a node is less
than the node storage capacity. In [15], the minimum distance
on an FR code is defined as the minimum number of nodes
such that if the nodes fail simultaneously then the system
can not recover the complete file. FR codes with asymmetric
parameters, are also constructed using sequences [16], graphs
[17], [18] and combinatorial designs [19], [20].
For the FR code, the asymmetric node storage capacity
helps to reduce the total storage cost and the asymmetry on
replication factor helps for availability of favorable packets,
where favorable packets are the packets which are downloaded
with more frequency. The asymmetric repair degree and repair
bandwidth help to reduce the repair cost of a node in the FR
code.
In this work, an FR code with asymmetric parameters (node
storage capacity, packet replication factor, repair degree and
repair bandwidth) are considered. In general, it is shown that
any FR code is equivalent to a hypergraph. The equivalence
between a hypergraph and an FR code leads to the several
interesting properties of the FR code. In general, we provide
the existence condition for FR codes using the correspondence.
Bounds on the node storage capacity and the packet replication
factor, are obtained for various FR codes which are equivalent
to some known classes of hypergraphs. We have obtain a
bound on size of a sub-hypergraph of a linear hypergraph.
A new bound on the replication factor, the number of nodes
and the number of packets are obtained such that all the FR
codes satisfying the bound are the universally good. Using the
correspondence, we have identified some bounds which are
not satisfied by any FR codes with equality in the literature.

2

It is observed that an FR code constructed using a linear
hypergraph is universally good code. We have proved that
the availability of favorable packets can be increased by
permuting packets in FR code with asymmetric parameters,
where the availability of all packets in FR code with symmetric
parameters are constant. It is also shown that the asymmetric
parameters of an FR code helps to reduce the total cost
associated with node storage capacity.
The paper is organized as follows. In Section II, we collect
some preliminaries on FR codes and hypergraphs with their
parameters and properties. In Section III, the relation of a
hypergraph and an FR code is studied in detail. Using the
relation, we obtain various bounds on the parameters of FR
codes in Section IV. At the end of the Section, the comparison
graph is plotted between the reconstruction degree and file size
for the FR codes. Section V concludes the paper with some
general remarks.
II. P RELIMINARIES
In this section, background on FR codes and hypergraphs
are given.
A. Background on Fractional Repetition Codes
Let a file be divided into B distinct information packets,
where information packet symbols are associated with a finite
field Fq . By using (θ, B) MDS code on the information
packets, the B information packets are encoded into θ distinct
packets P1 , P2 , . . ., Pθ . Because of the property of MDS
code, the complete file information can be extract from any B
packets. Each packet Pj (1 ≤ j ≤ θ) is replicated ρj times in
the system. All the packets are distributed on n distinct nodes
U1 , U2 , . . ., Un such that a node Ui (i = 1, 2, . . . , n) contains
αi packets. For the FR code, the maximum node storage
capacity and the maximum replication factor are given by α =
max{αi : i = 1, 2, . . . , n} and ρ = max{ρj : j = 1, 2, . . . , θ}
respectively. The FR code is denoted by C : (n, θ, α, ρ).
Example 1. Let a file be splitted into 5 (= B) information
packets and encoded into 6 (= θ) distinct packets P1 , P2 , P3 ,
P4 , P5 and P6 using a (6, 5) MDS code. The 13 replicas of
the 6 (= θ) distinct packets are stored in the 5 distinct nodes
U1 , U2 , U3 , U4 and U5 such that U1 = {P1 , P2 , P3 , P4 }, U2
= {P1 , P5 , P6 }, U3 = {P2 , P5 }, U4 = {P3 , P6 } and U5 =
{P4 , P6 }. The node packet distribution of the FR code C :
(n = 5, θ = 6, α = 4, ρ = 3) is illustrated in Table I. Hence,
α1 = |U1 | = 4, α2 = |U2 | = 3, αi = |Ui | = 2 (i = 3, 4, 5) and
replication vector ρ
~ := (ρ1 ρ2 ρ3 ρ4 ρ5 ρ6 ) = (2 2 2 2 2 3).
In the FR code, ρ = max{ρj : j = 1, 2, . . . , 6} = 3 and
α = max{αi : i = 1, 2, . . . , 5} = 4. Hence, the FR code is
denoted by C : (n = 5, θ = 6, α = 4, ρ = 3). Note that in this
example file size B and number of nodes n are same and this
is not always true.
For an FR code, if a data collector connects any k nodes and
downloads B distinct packets then the file can be retrieved by
using the MDS property. The parameter k is called the reconstruction degree of the FR code. Note that the reconstruction
degree of the FR code C : (5, 6, 4, 3) (Example 1) is k = 3.

TABLE I
D ISTRIBUTION OF REPLICATED PACKETS ON NODES FOR THE FR CODE
C : (5, 6, 4, 3).
U1
U2
U3
U4
U5

P1 , P2 , P3 , P4
P1 , P5 , P6
P2 , P5
P3 , P6
P4 , P6

In an FR code, a failed node Ui can be repair by replacing
a new node Ui0 , where both the nodes Ui and Ui0 carry the
same information. For the new node, the information packets
are downloaded from some active nodes called helper nodes.
The repair degree of a failed node Ui is the cardinality of
the set of the helper nodes. For a node Ui in an FR code
C : (n, θ, α, ρ), more then one such helper node sets exist
with different repair degree. For the node Ui , the maximum
repair degree is di and d = max{di : i = 1, 2, . . . , n}. In the
FR code C : (5, 6, 4, 3) (Example 1), if node U2 fails then
the new node U20 can be created by downloading packets from
nodes of set {U1 , U3 , U4 } or set {U1 , U3 , U5 }. Hence, d2 = 3
and d = max{di : i = 1, 2, 3, 4, 5} = 4. Now, one can define
an FR code formally as follows.
Definition 2. (Fractional Repetition Code): On a Distributed
Storage System with n nodes denoted by Ui (i = 1, 2, . . . , n)
and θ packets denoted by Pj (j = 1, 2, . . . , θ), one can define
an FR code C (n, θ, α, ρ) as a collection C of n subsets Ui
(i = 1, 2, . . . , n) of a set {Pj : j = 1, 2, . . . , θ}, such that
an arbitrary packet Pj is distributed on ρj (∈ N) distinct
subsets in the collection C , where |Ui | = αi denotes the
number of packets stores on the node Ui , ρ = max{ρj :
j = 1, 2, . . . , θ} is the maximum replication among all packets
and the maximum number of packets on any node is given by
α = max{αi : i = 1, 2, . . . , n}.
In an FR code C : (n, θ, α, ρ), if DC (k) (called Code
Dimension) is the maximum number of distinct packets that
guarantee to deliver to any user connected with any k nodes
of the FR code then DC (k) := min {|∪i∈I Ui | : |I| = k, I ⊂
{1, 2, . . . , n}}. Note that B ≤ DC (k). For the FR code
C : (5, 6, 4, 3) as given in Example 1, one can find that
DC (3) = 5.
An FR code C (n, θ, α, ρ) with an asymmetric parameter
is called universally good if the codeP
dimension DC (k) is
k
guaranteed to be more than or equal to i=1 di − k2 for any
k < n, where d1 ≤ d2 ≤ . . . ≤ dn . An FR code C (n, θ, α, ρ)
with d1 ≤ d2 ≤ . . . ≤ dn and |Ui ∩ Uj | ≤ 1 (i, j = 1, 2, . . . , n
Pk
and i 6= n) satisfies the inequality DC (k) ≥ i=1 di − k2
[9].
B. Background on Hypergraphs
For a finite set V = {v1 , v2 , . . . , vn }, the pair H = (V ; E)
is called a hypergraph with hypervertex set V and hyperedge
set E, where E = {E : E ⊆ V } is a family of some subset
of V [21], [22]. For a hypergraph H = (V ; E), |E| is called
the size of the hyperedge E ∈ E and |E(v)| is the degree
of the hypervertex v ∈ V , where E(v) = {E : v ∈ E}.

3

An example of such hypergraph is shown in Figure 1. In this
hypergraph H = (V ; E), hypervertices are shown by simply
bold dots and the hyperedges are represented by the covered
area which contains some hypervertices. In the particular
example, there are 7 hypervertices and 4 hyperedges such that
E(v1 ) = {E1 }, E(v2 ) = φ, E(v3 ) = {E3 }, E(v4 ) = {E1 , E2 },
E(v5 ) = {E1 , E2 , E3 }, E(v6 ) = {E3 } and E(v7 ) = {E4 }.
In a hypergraph H = (V ; E), a hypervertex v ∈ V is called
isolated hypervertex if E(v) = φ. A hypergraph HS = (V ; E)
does not have any isolated hypervertex if V =
E. In a
E∈E

hypergraph H = (V ; E), a loop is a hyperedge E ∈ E with
|E| = 1. If two distinct hyperedges share same hypervertices
then those hyperedges are called parallel hyperedges for the
hypergraph. Similarly, if two distinct hypervertices are shared
by same hyperedges then those hypervertices are called parallel hypervertices.
v1

v4
E1
v2

v7 E4

v5
E2
v3 E
3

v6

Fig. 1. A hypergraph H = (V ; E) is shown, where V = {vi : i ∈ [7]}
and E = {E1 = {v1 , v4 , v5 }, E2 = {v4 , v5 }, E3 = {v3 , v5 , v6 }, E4 =
{v7 }}.

For a hypergraph H = (V ; E), a subset of V is called a
hypervertex cover if each hyperedge is incident to at least one
hypervertex of the subset. For an example, the set {v4 , v6 , v7 }
is a hypervertex cover of the hypergraph given in Figure 1.
Note that the hypervertex cover of any hypergraph exists but
it is not unique for some hypergraph.
A hypergraph H 0 = (V 0 ; E 0 ) is called a sub-hypergraph
of a hypergraph H = (V ; E) if V 0 ⊆ V and E 0 ⊆
{E 0 6= φ : E 0 ⊆ E ∩ V 0 , E ∈ E}. For an example, a
hypergraph H 0 = (V 0 ; E 0 ) with V 0 = {v1 , v3 , v4 , v5 , v6 } and
E 0 = {E10 = {v1 , v4 , v5 }, E20 = {v4 }, E30 = {v3 , v5 }}, is a
sub-hypergraph of the hypergraph H = (V ; E) (as shown in
Figure 1). For a hypergraph H = (V ; E), hypergraph H 0 =
(V 0 ; E 0 ) is called sub-hypergraph induced by the set V 0 ⊂ V
if E 0 = {E 0 6= φ : E 0 = E ∩ V 0 , E ∈ E}. A hypergraph is
called connected hypergraph if there exists a sub-hypergraph
with the same hypervertex set such that the sub-hypergraph
is isomorphic to a connected graph. The hypergraph H =
(V ; E) ( Figure 1) is not a connected hypergraph since there
is an isolated hypervertex.
Consider a hypergraph H = (V ; E) without isolated hyper∗
}, a hypergraph
vertices. For a finite set V ∗ = {v1∗ , v2∗ , . . . , v|E|
∗
∗
∗
H = (V ; E ) is called the dual of the hypergraph H
= (V ; E) if their exist a bijection g : E → V ∗ such that
Ej = {g(Ei ) = vi∗ : vj ∈ Ei }, where j = 1, 2, . . . , |V |.
For an example, a hypergraph H ∗ = (V ∗ ; E ∗ ) with V ∗ =
{v1∗ , v2∗ , v3∗ , v4∗ } and E ∗ = {E1∗ = {v1∗ }, E2∗ = {v3∗ }, E3∗ =
{v1∗ , v2∗ }, E4∗ = {v1∗ , v2∗ , v3∗ }, E5∗ = {v4∗ }}, is the dual of a
hypergraph H = (V ; E) with V = {v1 , v2 , v3 , v4 , v5 } and

E = {E1 = {v1 , v3 , v4 }, E2 = {v3 , v4 }, E3 = {v2 , v4 }, E4 =
{v5 }}, where g(Ej ) = vj∗ and i = 1, 2, . . . , 5.
In a hypergraph, if two hyperedges shares one node maximum then the hypergraph is called linear hypergraph. For such
hypergraph, one can find bound on the size of the hypergraph
as given in the following Lemma.
Lemma 3. For a linear hypergraph H = (V ; E),
 
X
|V |
|E| ≥
|E(v)| −
.
2

(1)

v∈V

Proof:

|V |
In a linear hypergraph H = (V ; E), at most
P 2 hyperedges are repeated in the hyperedge count v∈V |E(v)|.
So,
 of hyperedges of H is bounded by
P the total number
|V |
v∈V |E(v)| − 2 .
A sub-hypergraph of a linear hypergraph is also a linear
hypergraph. For a positive integer k (not more than the size
of the hypergraph), one can find a bound on the size of subhypergraph induced by any k-element subset. Formally, the
bound is discussed in the following Lemma with a proof in
the Appendix.
Lemma 4. For V = {vi : i = 1, 2, . . . , n}, consider a linear
hypergraph H = (V ; E) with |E(vi )| ≤ |E(vj )|, for i < j and
i, j = 1, 2, . . . , n. For a given positive integer k < n, let H 0 =
(V 0 ⊂ V ; E 0 ) be a induced sub-hypergraph of the hypergraph
H = (V ; E) with E 0 = {E 0 6= φ : E 0 = E ∩ V 0 , E ∈ E} and
|V 0 | = k. Then
 
k
X
k
0
0
0
0
0
min{|E | : H = (V ⊂ V ; E ), |V | = k} ≥
|E(vi )|−
.
2
i=1
(2)

III. H YPERGRAPHS AND F RACTIONAL R EPETITION C ODES
In this Section, A bijection (called Hyper-FR mapping)
between a hypergraph and an FR code is established. Using
the Hyper-FR mapping, the relation between the parameters
of FR codes and hypergraphs are studied at the end of the
Section.
In an FR code, the distribution of nodes and packets are
similar to the incidence of hypervertices and hyperedges in a
hypergraph.
Example 5. As shown in Figure 2, consider a hypergraph
H = (V ; E) with V = {vi : i = 1, 2, 3, 4} and E = {Ej :
j = 1, 2, 3, 4, 5, 6}, where E1 = {v1 , v2 }, E2 = {v1 , v3 }, E3 =
{v1 , v4 }, E4 = {v2 , v3 }, E5 = {v2 , v4 } and E6 = {v3 , v4 }. For
the hypergraph, E(v1 ) = {E1 , E2 , E3 }, E(v2 ) = {E1 , E4 , E5 },
E(v3 ) = {E2 , E4 , E6 } and E(v4 ) = {E3 , E5 , E6 }. As given
in Figure 2, consider an FR code C : (4, 6, 3, 2) with 4 nodes
and 6 such that U1 = {P1 , P2 , P3 }, U2 = {P1 , P4 , P5 }, U3
= {P2 , P4 , P6 } and U4 = {P3 , P5 , P6 }. Note that there exist
the bijection ϕ : E → {Pj : j = 1, 2, . . . , 6} such that
ϕ(Ej ) = Pj for each j = 1, 2, . . . , |E|. Hence, ϕ(E(vi )) =
{Pj = ϕ(Ej ) : Ej ∈ E, vi ∈ Ej }.

4

v1

v2
E1

U1 P1 , P2 , P3

E3
E2

E5

v3 E4

v4
E6

Hypergraph H (V, E)

⇐⇒

U2 P1 , P4 , P5

In this paper, a hypergraph H = (V 6= φ; E) with |E(v)| >
0 ( ∀ v ∈ V ) and |E| > 0 ( ∀ E ∈ E) is called conditional
hypergraph H = (V ; E).

U3 P2 , P4 , P6

IV. F RACTIONAL R EPETITION C ODES USING
H YPERGRAPHS

U4 P3 , P5 , P6
FR code C : (n, θ, α, ρ)

Fig. 2. Relation between hypergraph H (V, E) and FR code C : (n =
4, θ = 6, α = 3, ρ = 2) is illustrated, where V={v1 , v2 , v3 , v4 } and E =
{{v1 , v3 }, {v1 , v4 }, {v2 , v3 }, {v2 , v4 }, {v3 , v4 }}.

Formally, the relation between FR code and hypergraph is
defined as follows.
Definition 6. (Hyper-FR Mapping): For θ ∈ N and |E| = θ,
an FR code C : (n, θ, α, ρ) is equivalent to a hypergraph H
= (V ; E) if a bijection ϕ : E → {Pj : j = 1, 2, . . . , θ} exists
such that ∀ vi ∈ V, E(vi ) = {E : vi ∈ E, E ∈ E} ⇔ Ui =
ϕ(E(vi )) = {Pj = ϕ(E) : vi ∈ E, E ∈ E}. The bijection is
called Hyper-FR mapping.
For θ ∈ N and |E| = θ, let C : (n, θ, α, ρ) be an FR code
which is equivalent to a hypergraph H = (V ; E). Hence, a
bijection ϕ : E → {Pj : j = 1, 2, . . . , θ} exists such that
∀ vi ∈ V, E(vi ) = {E : vi ∈ E, E ∈ E} ⇔ Ui = ϕ(E(vi )) =
{Pj = ϕ(E) : vi ∈ E, E ∈ E}. Because of the bijection, one
can immediate see that the number of nodes and the number
of hypervertices are same i.e. n = |V |, the number of distinct
packets and the number of hyperedges are same i.e θ = |E|,
the node storage capacity of a node is the same as the hypervertex degree of the respective hypervertex i.e. αi = |E(vi )|
(i = 1, 2, . . . , n) and the replication factor of a packet is equal
to the cardinality of the respective hyperedge i.e. ρj = |Ej |
(j = 1, 2, . . . , θ). Hence, the maximum node storage capacity
α = max{|E(v)| : v ∈ V } and the maximum replication
factor ρ = max{|E| : E ∈ E}. A reconstruction set of the
equivalent FR code is associated with a hypervertex cover of
a sub-hypergraph H 0 = (V 0 , E 0 ) induced by V 0 = ∪E∈E(v) E,
and |E 0 | ≥ B. Consider a hypervertex cover V of a subhypergraph H 0 = (V 0 ; E 0 ) of the hypergraph H = (V ; E),
where V 0 = ∪E∈E(v) E and E 0 = E(v). In the equivalent FR
code C , for a node failure Ui , a surviving set is associated
with the set V \{vi }, where i = 1, 2, . . . , |V |. In the FR code,
the repair bandwidth for a node is equal to the hypervertex
degree of respective hypervertex and tolerance factor is equal
to the hypergraph size. For the given positive integer k < n,
Let H 0 = (V 0 ; E 0 ) be a sub-hypergraph induced by V 0 ⊂ V .
The code dimension DC (k) of the equivalent FR code is
DC (k) = min{|E 0 | : V 0 ⊂ V, |V 0 | = k}.
The necessary and sufficient condition for a hypergraph to
represent an FR code is discussed in the following straightforward Lemma.
Lemma 7. For a hypergraph H = (V 6= φ; E), an FR code
C : (n, θ, α, ρ) exists if and only if |E(v)| > 0 ( ∀ v ∈ V ) and
|E| > 0 ( ∀ E ∈ E).

In this Section, bounds on specific hypergraphs are mapped
to the equivalent FR code using a Hyper-FR mapping. For an
FR code, existence condition is calculated in the Section.
A. Bounds on Fractional Repetition Codes using Hypergraphs
The necessary and sufficient condition for the existence of
an FR code is given in the following Theorem.
Theorem 8. (Existence Condition) Consider two vectors
(ρ1 ρ2 . . . ρθ ) and (α1 α2 . . . αn ) on integers such that α =
α1 ≥ α2 ≥ . . . ≥ αn for j = 1, 2, . . . , θ and i = 1, 2, . . . , n.
An FR code C : (n, θ, α, ρ) exists with |Ui | = αi for
i = 1, 2, . . . , n and replication factor of packet Pj is ρj for
j = 1, 2, . . . , θ if
θ
n
P
P
1)
ρj =
αi and
2)

j=1
θ
P

i=1

min{ρj , m} ≥

j=1

m
P

αi ( for m < n, m ∈ Z).

i=1

Proof: The proof is obvious.
Note that if the parameters of an FR code do not satisfy one
of the constraint in the Theorem 8 or the Theorem 22, then
the FR code does not exist.
Lemma 9. For each j = 1, 2, . . . , θ, an FR code C :
(n, θ, α, ρ) with ρj = ρ (j = 1, 2, . . . , θ) connected conditional hypergraph, satisfies the following conditions.
n
P
1)
αi is multiple of ρ,
2)

i=1
n
P

αi ≥

i=1

3) α ≤

1
ρ

ρ(n−1)
ρ−1 ,

n
P

αi .

i=1

Proof: The proof follows from [21, Chapter 1, Proposition
2].
For an FR code, let the node set be a disjoint union of two
subsets such that any node from one subset does not share
packets with any node from another subset. A bound on the
FR code is calculated in the following Theorem.
Lemma 10. Let C : (n, θ = 2m, α, ρ) be an FR code with
message packets P1 , P2 ,. . ., Pm , P10 , P20 ,. . ., Pm such that
m
P
|Fj |+|Fj0 |−1
Fi ∩ Fj0 =φ if and only if i = j. Then
≤ 1,
|F |
where Fj = {Ui : Pj ∈ Ui } and

Fj0

j=1

= {Ui :

j

Pj0

∈ Ui }.

Proof: The proof follows from the Theorem 6 in [21,
Chapter 1].
For V = {vi : i = 1, 2, . . . , n}, consider a hypergraph H =
(V ; E) with |E(vi )| ≤ |E(vj )|, for i < j and i, j = 1, 2, . . . , n.
For a given positive integer k < n, let H 0 = (V 0 ⊂ V ; E 0 )
be a induced sub-hypergraph of the hypergraph H = (V ; E)

5

with E 0 = {E 0 6= φ : E 0 = E ∩ V 0 , E ∈ E} and |V 0 | = k. For
the equivalent FR code, the code dimension
DC (k) = min{|E 0 | : H 0 = (V 0 ⊂ V ; E 0 ), |V 0 | = k}.

(3)

An FR code C (n, θ, α, ρ) is universally good

Pk if the code
k
dimension DC (k) is more than or equal to
i=1 di − 2
for any k < n, where d1 ≤ d2 ≤ . . . ≤ dn . The following
Theorem gives the necessary and sufficient condition for a
universally good FR code on hypergraph.

Remark 15. Note that a sub-hypergraph of a linear hypergraph is again a linear hypergraph and each linear hypergraph satisfies the Lemme 3. Hence, all the FR codes which
are equivalent to linear hypergraph satisfy the Theorem 14 for
each k ≤ n − 1. So, each FR code which is equivalent to a
linear conditional hypergraph is universally good.
Remark 16. An FR code illustrated in [23], is equivalent to a
linear conditional hypergraph. The bound on code dimension
(Theorem 14) is also discussed in [23, Inequality 2].

Theorem 11. For V = {vi : i = 1, 2, . . . , n}, consider a
hypergraph H = (V ; E) with |E(vi )| ≤ |E(vj )|, for i < j and C. Fractional Repetition Codes using Simple Hypergraph
i, j = 1, 2, . . . , n. For a given positive integer k < n, let H 0 =
A hypergraph H = (V ; E) is called a simple hypergraph
(V 0 ⊂ V ; E 0 ) be a induced sub-hypergraph of the hypergraph only if Ei ⊆ Ej then i = j, for any Ei , Ej ∈ E. If a simple
H = (V ; E) with E 0 = {E 0 6= φ : E 0 = E ∩ V 0 , E ∈ E} hypergraph is a conditional hypergraph then the hypergraph
and |V 0 | = k. For each k = 1, 2, . . . n − 1, the FR code is can be called as a conditional simple hypergraph.
universally good if and only if
If an FR code is equivalent to a conditional simple hypergraph then all the nodes which share a packet will not contain


k
X
k an another common packet in the FR code. Any FR code
|E(vi )|−
min{|E 0 | : H 0 = (V 0 ⊂ V ; E 0 ), |V 0 | = k} ≥
.
2 equivalent to a conditional simple hypergraph will satisfy the
i=1
(4) following two Lemmas.
Proof: The proof follows the Equation 3 and [9, Theorem
4].

Lemma 17. An FR code C : (n, θ, α, ρ) with {U : Pi ∈ U } *
{U : Pj ∈ U } for each i 6= j and i, j = 1, 2, . . . , n, satisfies
θ


P
n −1
n
≤ 1 and θ ≤ bn/2c
.
ρj

j=1

B. Fractional Repetition Codes using Linear Hypergraphs
A hypergraph is called linear hypergraph if any two hyperedges share at most one hypervertex. Note that in a
hypergraph, any two hyperedges share at most one hypervertex
if and only if any two hypervertices are shared by at most one
hyperedge. If a linear hypergraph is a conditional hypergraph
then the hypergraph is called conditional linear hypergraph.
Any two nodes in an FR code equivalent to a conditional
linear hypergraph do not share more than one packets. An
FR code on conditional linear hypergraph will satisfy the
following Lemmas.
Lemma 12. An FR code C : (n, θ, α, ρ) with |Ui ∩Uj | ≤ 1 (for
θ


P
ρj
n
each i 6= j and i, j = 1, 2, . . . , n), satisfies
2 ≤ 2 .
j=1

Proof: The Lemma followers from [21, Chapter 1, Theorem 3].
Lemma 13. An FR code C : (n, θ, α, ρ) with |Ui ∩ Uj | ≤ 1
n


P
αi
θ
(for each i 6= j and i, j = 1, 2, . . . , n), satisfies
2 ≤ 2 .
i=1

Proof: The Theorem follows from the duality (with
respect to hypergraph) on Lemma 12.
The bound on the code dimension of FR code associated
with linear hypergraph is discussed in the following Theorems.
Theorem 14. An FR code C : (n,
 θ, α, ρ) with |Ui ∩ Uj | ≤ 1
Pk
k
satisfies DC (k) ≥ i=1 αi − 2 , where αi ≤ αj (1 ≤ i <
j ≤ n).
Proof: The proof follows from the Lemma 3 and Lemma
4.

Proof: The Lemma follows from [21, Chapter 1, Theorem
2].
Lemma 18. An FR code C : (n, θ, α, ρ) with Ui * Uj for
n

P
θ −1
≤ 1 and
each i 6= j and i, j = 1, 2, . . . , n, satisfies
αj
i=1

θ
n ≤ bθ/2c
.
Proof: The proof follows the duality (with respect to
hypergraph) on Lemma 17.
Remark 19. In the FR code as considered in [5], [15], [17],
[24], [25], if parallel nodes do not exist then the FR code will
satisfy the Lemma 17 and Lemma 18.
Remark 20. Each FR code studied in the literature is associated with a specific hypergraph. The various FR codes
and equivalent hypergraphs are listed in the Table II (see
the Appendix). FR code as the Hyper-FR image of the listed
hypergraph (Table II), satisfies the constraints given in the
definition of an FR code in respective article.
In [5], [26], FR codes with symmetric parameters satisfies
the bounds in Lemma 12, 13, 17 and 18 with equality. In
[7], [9], [23], FR codes with asymmetric parameters satisfies
the bounds in Lemma 12 and 13 with equality. It would be
an interesting task to find more FR codes with asymmetric
parameters which satisfies Lemma 9, 10, 17 and 18 with
equality.
V. C ONCLUSION
In this work, we have sketched the surface of the very
interesting topic by establishing a relation between FR code
and hypergraph. It is shown that each FR code studied in

6

the literature is associated with some conditional hypergraph,
where the minimum rank and the minimum degree of the
hypergraph are non-zero positive integer. We have compared
our method with other known constructions of FR codes. The
properties of the hypergraphs are mapped to FR codes by using
Hyper-FR mapping. Some new bounds on FR codes have been
derived. It would be an interesting work in the future to find the
FR codes which satisfy those bounds with equality. Analysis
of FR codes on generalized hypergraph could be an another
interesting problem.
R EFERENCES
[1] S. Ghemawat, H. Gobioff, and S.-T. Leung, “The google file system,”
in Proceedings of the nineteenth ACM symposium on Operating systems
principles, ser. SOSP ’03. New York, NY, USA: ACM, 2003, pp.
29–43. [Online]. Available: http://doi.acm.org/10.1145/945445.945450
[2] H. Weatherspoon and J. D. Kubiatowicz, “Erasure coding vs. replication: A quantitative comparison,” in Proceedings of the International
Workshop on Peer-to-Peer Systems, 2002, pp. 328–337.
[3] A. Dimakis, P. Godfrey, Y. Wu, M. Wainwright, and K. Ramchandran,
“Network coding for distributed storage systems,” Information Theory,
IEEE Transactions on, vol. 56, no. 9, pp. 4539–4551, Sept 2010.
[4] K. Rashmi, N. Shah, P. Kumar, and K. Ramchandran, “Explicit construction of optimal exact regenerating codes for distributed storage,”
in Communication, Control, and Computing, 2009. Allerton 2009. 47th
Annual Allerton Conference on, 30 2009-oct. 2 2009, pp. 1243 –1249.
[5] S. El Rouayheb and K. Ramchandran, “Fractional repetition codes for
repair in distributed storage systems,” in Communication, Control, and
Computing (Allerton), 2010 48th Annual Allerton Conference on, Oct.
2010, pp. 1510 –1517.
[6] S. Pawar, N. Noorshams, S. El Rouayheb, and K. Ramchandran,
“DRESS codes for the storage cloud: Simple randomized constructions,”
in Information Theory Proceedings (ISIT), 2011 IEEE International
Symposium on, 31 2011-aug. 5 2011, pp. 2338 –2342.
[7] B. Zhu, H. Li, K. W. Shum, and S.-Y. R. Li, “HFR code: a flexible
replication scheme for cloud storage systems,” IET Communications,
October 2015. [Online]. Available: http://digital-library.theiet.org/
content/journals/10.1049/iet-com.2014.1225
[8] B. Zhu, H. Li, H. Hou, and K. W. Shum, “Replication-based distributed
storage systems with variable repetition degrees,” in 2014 Twentieth
National Conference on Communications (NCC), Feb 2014, pp. 1–5.
[9] B. Zhu, K. Shum, H. Li, and H. Hou, “General fractional repetition
codes for distributed storage systems,” Communications Letters, IEEE,
vol. 18, no. 4, pp. 660–663, April 2014.
[10] M. K. Gupta, A. Agrawal, and D. Yadav, “On weak dress codes for
cloud storage,” CoRR, vol. abs/1302.3681, 2013. [Online]. Available:
http://arxiv.org/abs/1302.3681
[11] H. Park and Y.-S. Kim, “Construction of fractional repetition codes with
variable parameters for distributed storage systems,” Entropy, vol. 18,
no. 12, 2016. [Online]. Available: http://www.mdpi.com/1099-4300/18/
12/441
[12] S. A. Prajapati and M. K. Gupta, “On some universally good fractional
repetition codes,” CoRR, vol. abs/1609.03106, 2016. [Online]. Available:
http://arxiv.org/abs/1609.03106
[13] Q. Yu, C. W. Sung, and T. Chan, “Irregular fractional repetition
code optimization for heterogeneous cloud storage,” Selected Areas in
Communications, IEEE Journal on, vol. 32, no. 5, pp. 1048–1060, May
2014.
[14] M. Y. Nam, J. H. Kim, and H. Y. Song, “Locally repairable fractional
repetition codes,” in 2015 Seventh International Workshop on Signal
Design and its Applications in Communications (IWSDA), Sept 2015,
pp. 128–132.
[15] B. Zhu, “Rethinking fractional repetition codes: New construction and
code distance,” IEEE Communications Letters, vol. 20, no. 2, pp. 220–
223, Feb 2016.
[16] K. G. Benerjee and M. K. Gupta, “On dress codes with flowers,” in 2015
Seventh International Workshop on Signal Design and its Applications
in Communications (IWSDA), Sept 2015, pp. 108–112.
[17] S. Anil, M. K. Gupta, and T. A. Gulliver, “Enumerating some fractional
repetition codes,” CoRR, vol. abs/1303.6801, 2013.

[18] J. Koo and J. Gill, “Scalable constructions of fractional repetition
codes in distributed storage systems,” in Communication, Control, and
Computing (Allerton), 2011 49th Annual Allerton Conference on, Sept
2011, pp. 1366–1373.
[19] N. Silberstein and T. Etzion, “Optimal fractional repetition codes based
on graphs and designs,” Information Theory, IEEE Transactions on,
vol. PP, no. 99, pp. 1–1, 2015.
[20] B. Zhu and H. Li, “Exploring node repair locality in fractional repetition
codes,” IEEE Communications Letters, vol. 20, no. 12, pp. 2350–2353,
Dec 2016.
[21] C. Berge, Hypergraphs, ser. North-Holland Mathematical Library.
North-Holland, 1989, vol. 45, combinatorics of Finite Sets.
[22] A. Bretto, Hypergraph Theory. Springer International Publishing, 2013.
[23] B. Zhu, K. W. Shum, and H. Li, “Heterogeneity-aware codes with
uncoded repair for distributed storage systems,” IEEE Communications
Letters, vol. 19, no. 6, pp. 901–904, June 2015.
[24] N. Silberstein and T. Etzion, “Optimal fractional repetition codes for
distributed storage systems,” in 2014 IEEE 28th Convention of Electrical
Electronics Engineers in Israel (IEEEI), Dec 2014, pp. 1–4.
[25] B. Zhu and H. Li, “Adaptive fractional repetition codes for dynamic
storage systems,” IEEE Communications Letters, vol. 19, no. 12, pp.
2078–2081, Dec 2015.
[26] O. Olmez and A. Ramamoorthy, “Fractional repetition codes with
flexible repair from combinatorial designs,” IEEE Transactions on
Information Theory, vol. 62, no. 4, pp. 1565–1591, April 2016.
[27] T. Ernvall, “The existence of fractional repetition codes,” CoRR, vol.
abs/1201.3547, 2012.
[28] N. Silberstein and T. Etzion, “Optimal fractional repetition codes and
fractional repetition batch codes,” in 2015 IEEE International Symposium on Information Theory (ISIT), June 2015, pp. 2046–2050.
[29] O. Olmez and A. Ramamoorthy, “Repairable replication-based storage
systems using resolvable designs,” in Communication, Control, and
Computing (Allerton), 2012 50th Annual Allerton Conference on, Oct
2012, pp. 1174–1181.
[30] ——, “Constructions of fractional repetition codes from combinatorial
designs,” in Signals, Systems and Computers, 2013 Asilomar Conference
on, Nov 2013, pp. 647–651.

7

VI. A PPENDIX

C. Bounds on Fractional Repetition Codes using Hypergraphs

The Appendix includes the bounds on FR codes correspondence to various classes of hypergraphs such as uniform
hypergrths, regular hypergraphs and intersecting hypergraphs.
The cost comparison analysis is done for various FR codes at
the end of the Appendix.

The alternate condition for the existence of an FR code is
given in the following Theorem.

A. Proof of Lemma 4
Proof: For V = {vi : i = 1, 2, . . . , n}, let H = (V ; E)
be a linear conditional hypergraph with |E(vi )| ≤ |E(vj )|, for
1 ≤ i < j ≤ n. For a given positive integer k < n, let V 0 be an
arbitrary k-element subset of the set V . Consider a hypergraph
H 0 = (V 0 ; E 0 ), where E 0 = {E 0 6= φ : E 0 = E ∩ V 0 , E ∈ E}.
By definition of degree of a hypervertex,
X

k
X

|E(v)| ≥

v∈V 0

⇒

 
 X
k
k
|V 0 |
|E(vi )| −
|E(v)| −
≥
2
2
0
i=1

X
v∈V

|E(vi )|

i=1



A sub-hypergraph of a linear hypergraph is also linear. So,
using Lemma 3, one can conclude that
 
 0 X
k
X
k
|V |
0
|E(vi )| −
.
|E | ≥
|E(v)| −
≥
2
2
0
i=1
v∈V

Theorem 22. (Alternate Existence Condition) Consider two
vectors (ρ1 ρ2 . . . ρθ ) and (α1 α2 . . . αn ) on integers such
that ρ = ρ1 ≥ ρ2 ≥ . . . ≥ ρθ for j = 1, 2, . . . , θ and
i = 1, 2, . . . , n. An FR code C : (n, θ, α, ρ) exists such that
|Ui | = αi for i = 1, 2, . . . , n and replication factor of packet
Pj is ρj for j = 1, 2, . . . , θ if
n
θ
P
P
1)
αi =
ρj and
2)

i=1
n
P
i=1

j=1

min{αi , m} ≥

m
P

ρj ( for m < θ, m ∈ Z).

j=1

Proof: The proof follows from the duality (with respect
to hypergraph) on the Theorem 8.
Note that if parameters of an FR code do not satisfy one of
the constraint in the Theorem 8 or Theorem 22, then the FR
code does not exist.
In an FR code, two packets with same replication factor
are called parallel packets if the two packets are shared by
same nodes. In an FR code, two nodes with same node
storage capacity are called parallel nodes if the two nodes
contain same packets. For an FR code without parallel packets
and parallel nodes, the bound on node storage capacity and
replication factor are given in the following two Lemmas.

The chosen k-element set V 0 is an arbitrary subset of set V , Lemma 23. An FR code C : (n, θ, α, ρ) without parallel
packets, satisfies α ≤ 2n−1 .
so
 
k
X
Proof: The proof follows from the Theorem 4 in [21,
k
0
0
0
0
0
|E(vi )|−
. Chapter 1].
min{|E | : H = (V ⊂ V ; E ), |V | = k} ≥
2
i=1
Hence, the lemma is proved.

Lemma 24. An FR code C : (n, θ, α, ρ) without parallel
nodes, satisfies ρ ≤ 2θ−1 .

B. Algebraic Entropy on Fractional Repetition Code

Proof: The proof follows from the duality (with respect
to the hypergraph) on Lemma 23.

An algebraic entropy of a hypergraph is discussed in [22].
Using a Hyper-FR mapping on a hypergraph, one can find the
algebraic entropy for an FR code in the following Theorem.
Theorem 21. (Algebraic Entropy) Consider an FR code
C : (n, θ, α, ρ) with the node adjacency matrix A(C ) =
[ai,j ]n×n . The algebraic entropy associated with the FR code
C : (n, θ, α, ρ), is given by
I(C ) = −

n
X

λi log2 λi ,

i=1

where λi (for i = 1, 2, . . . , n) is a discrete probability distribution. In particular, λi (i = 1, 2, . . . , n) is the P
eigenvalue of
n
matrix L(C ) = D − A(C ) are real such that i=1 λi = 1
and 0 ≤ λi ≤ 1 (∀i = 1, 2, . . . , n), where


n
n
n
X
X
X
D = diag 
a1j ,
a2j , . . . ,
anj  .
j=1

j=1

j=1

Proof: The proof follows from the algebraic entropy of
the hypergraph [22, Capter 1].

Theorem 25. For an FR code C : (n, θ, α, ρ) with |{U :
Pm ∈ U } ∩ {U : Pj ∈ U }| ≤ 1,
k
X

 
k
DC (k) ≥
αi −
,
2
i=1

(5)

where αi ≤ αj and 1 ≤ m < j ≤ θ.
Proof: The proof follows from the Theorem 14 and |Ui ∩
Uj | ≤ 1 ⇔ |{U : Pm ∈ U } ∩ {U : Pl ∈ U }| ≤ 1 for
1 ≤ m < l ≤ θ and 1 ≤ i < j ≤ n.
D. Fractional Repetition Codes using the Uniform Hypergraphs
For a positive integer r, an r-uniform hypergraph is a
hypergraph H = (V ; E) with |E| = r, for each E ∈ E. If
a conditional hypergraph is an r-uniform hypergraph then the
hypergraph is called an r-uniform conditional hypergraph.
An FR code C : (n, θ, α, ρ) associated with an r-uniform
conditional hypergraph H = (V ; E) will have the same

8

replication factor for each packet i.e. ρ = ρj for each
j = 1, 2, . . . , θ.
For a positive integer r, an r-uniform hypergraph H =
r
(V ; E) is called an r-complete hypergraph denoted by K|V
|
if E = {E : E ⊆ V, |E| = r}. The following Lemma gives a
bound on total number of packets for an FR code.
Lemma 26. For an FR code C : (n, θ, α, ρ) with ρ = ρj (j =
1, 2, . . . , θ), the total number of distinct packets is θ ≤ nρ .
r
Proof: In an r-complete hypergraph K|V
parallel
| with no

hyperedges and isolated hypervertices, |E| = |Vr | . An runiform hypergraph H = (V ; E) is a sub-hypergraph
of the

|V |
r
r-complete hypergraph K|V
.
Hence,
|E|
≤
.
The
number
|
r
of distinct edges in FR code C : (n, θ, α, ρ) equivalent to a
ρ-uniform hypergraph H = (V ; E), is θ ≤ nρ .
Note that the condition given in Lemma 26, is derived in
[27] for FR codes with symmetric parameters. If an r-uniform
hypergraph is a connected hypergraph then the hypergraph is
called a connected r-uniform hypergraph.
An FR code equivalent to a uniform hypergraph will satisfy
the following bound.

Lemma 27. An FR code C : (n, θ, α, ρ) with |Ui ∩Uj | ≤ 1 (for
each i, j = 1, 2, . . . , n) and ρm = ρ (for each m = 1, 2, . . . , θ)
satisfies θ ≤ n(n−1)
ρ(ρ−1) .
Proof: The proof follows from [21, Chapter 1, Theorem
3].
Remark 28. The FR code associated with a ρ-uniform linear
conditional hypergraph is GFR code [9]. For a ρ-uniform
linear conditional hypergraph, the Theorem 14 follows the
bound on code dimension for GFR code [9, Theorem 4].
Remark 29. In [13, Fact 1], it is shown that an IFR code is
equivalent to a ρ-uniform hypergraph.
E. Fractional Repetition Codes using Regular Hypergraphs
An s-regular hypergraph is a hypergraph H = (V ; E) such
that |E(vi )| = s, for each vi ∈ V . An conditional hypergraph
H = (V ; E) is called an s-regular conditional hypergraph if
|E(vi )| = s, for each vi ∈ V .
An FR code C : (n, θ, α, ρ) associated with an s-regular
conditional hypergraph H = (V ; E) will have the same node
storage capacity for each node i.e. α = αi for each i =
1, 2, . . . , n. The following three Lemmas give bound on the
FR codes.
Lemma 30. An FR code C : (n, θ, α, ρ) associated with
connected α-regular conditional hypergraph, satisfies the following conditions.
θ
P
1)
ρj is multiple of α,
2)

j=1
θ
P

ρj ≥

j=1

3) ρ ≤

1
α

α(θ−1)
α−1 ,

θ
P

ρj .

j=1

Proof: The proof follows from the duality (with respect
to hypergraphs) on Lemma 9.

Lemma 31. An FR code C : (n, θ, α, ρ) with |Ui ∩ Uj | ≤ 1
(for each i, j = 1, 2, . . . , n) and αm = α (for each m =
θ(θ−1)
.
1, 2, . . . , n) satisfies n ≤ α(α−1)
A hypervertex of an s-regular hypergraph
 H = (V ; E),
shares s distinct hyperedges so |V | ≤ |E|
s . The following
Lemma ensures the existence of an FR code with the same
number of nodes and packets and same packet replication
factor and node storage capacity.
Lemma 32. For a positive integer r, there exists an FR code
C : (n, n, r, r) such that 2 ≤ r ≤ n − 1 and αi = ρj = r, for
each i = 1, 2, . . . , n.
Proof: The proof follows from the fact that there exists
an r-uniform r-regular hypergraph with n hypervertices for
2 ≤ r ≤ n − 1.
The node packet distribution of the FR code C : (5, 5, r, r)
with 5 nodes and αi = ρj = r (for each i = 1, 2, 3, 4, 5) are
following.
• For r = 2, there exists an FR code C : (5, 5, 2, 2) with
U1 = {P1 , P2 }, U2 = {P2 , P3 }, U3 = {P3 , P4 }, U4 =
{P4 , P5 } and U5 = {P5 , P1 }.
• For r = 3, there exists an FR code C : (5, 5, 3, 3)
with U1 = {P1 , P2 , P3 }, U2 = {P2 , P3 , P4 }, U3 =
{P3 , P4 , P5 }, U4 = {P4 , P5 , P1 } and U5 = {P5 , P1 , P2 }.
• For r = 4, there exists an FR code C : (5, 5, 4, 4)
with U1 = {P1 , P2 , P3 , P4 }, U2 = {P2 , P3 , P4 , P5 },
U3 = {P3 , P4 , P5 , P1 }, U4 = {P4 , P5 , P1 , P2 } and
U5 = {P5 , P1 , P2 , P3 }.
Remark 33. Each FR code C : (n, θ, α, ρ) considered in [5]
is associated with a ρ-uniform α-regular hypergraph H =
(V ; E).
Recall that the storage capacity of nodes in an FR code
is related to the replication factor of packets in the dual FR
code and vise verse. Following two Lemmas are based on the
properties of duality.
Lemma 34. If C : (n, θ, α, ρ) is an FR code with αi = α
(for each i = 1, 2, . . . , n) then the dual FR code C ∗ :
(n∗ , θ∗ , α∗ , ρ∗ ) is an FR code with ρ∗j ∗ = α, for each
j ∗ = 1, 2, . . . , θ∗ .
Proof: The Lemma follows from the fact that the dual of
an r-uniform hypergraph is an r-regular hypergraph.
Lemma 35. If C : (n, θ, α, ρ) is an FR code with ρj = ρ
(for each j = 1, 2, . . . , θ) then the dual FR code C ∗ :
(n∗ , θ∗ , α∗ , ρ∗ ) is an FR code with αi∗∗ = ρ, for each
i∗ = 1, 2, . . . , n∗ .
Proof: The Lemma follows from the fact that the dual of
an s-regular hypergraph is an s-uniform hypergraph.
Remark 36. If C : (n, θ, α, ρ) is an FR code with ρj
and αi = α (for each j = 1, 2, . . . , θ); i = 1, 2, . . . , n)
the dual FR code C ∗ : (n∗ , θ∗ , α∗ , ρ∗ ) is an FR code
αi∗∗ = α∗ and ρ∗j ∗ = ρ∗ , for each i∗ = 1, 2, . . . , n∗
j ∗ = 1, 2, . . . , θ∗ .

= ρ
then
with
and

Remark 37. In [18], the Transpose code of an FR code is

9

Fig. 3. The graph shows the comparative analysis of an FR code with
the symmetric parameters and FR codes with the asymmetric parameters.
In the graph, the points on the vertical axis represents the maximum file
size (code dimension) which is delivered to any data collector. The points
on the horizontal axis represent the reconstruction degree (number of nodes
connected to any data collector to retrieve the file).

the FR code corresponding to dual hypergraph. All the FR
codes in [18], are corresponding to a ρ-uniform α-regular
hypergraph. So, all the Transpose codes are corresponding to
an α-uniform ρ-regular hypergraph.
F. Analysis
In this subsection, the comparison among FR codes on
homogeneous DSSs and heterogeneous DSSs is done by numerical analysis. Consider an FR code with n = 5 and θ = 10.
For an FR code C : (n = 5, θ = 10, α, ρ), let a data collector
connects k (≤ n = 5) nodes and receives DC (k) (≤ θ = 10)
distinct packets. Two plots between the maximum file size
(or code dimension) DC (k) and the reconstruction degree
k are given in Figure 3. The ∗ are the points, for the FR
code Chomo : (n = 5, θ = 10, α = 4, ρ = 2) with
symmetric parameters [5]. The + are the points, for the codes
Chete : (n = 5, θ = 10, α ≤ 6, ρ ≤ 4), where αi ≤ α ≤ 6
(i = 1, 2, 3, 4, 5) and ρj ≤ ρ ≤ 4 (j = 1, 2, . . . , 10). The
+ points are obtained for the FR codes Chete equivalent to
a random hypergraph with 5 nodes and 10 distinct packets.
In the Figure 3, the code dimension of Chomo and Chete are
same for k = 0, 4, 5. For k = 1, 2, 3, the code dimension
DChete (k) = 1 + DChomo (k). The graph shows that the code
dimension of the FR code with symmetric parameters are not
more than the code dimension of the FR code with asymmetric
parameters.
In an FR code, some encoded packets may be favorable for a
data collector because of their functionality and characteristics.
For example, if symmetric (θ, B) MDS code is used in the FR
code then the first B packets will be favourable to any user
because those packets needs no computation since they are
the exact copy of the information packets. One can increase
the availability of those packets in the FR code by increasing
the replication factor of only those packets. Note that the
replication factor of each packet in an FR code with the
symmetric parameters are same, so the availability of every
packets in the FR code remains the same.

For n nodes and θ packets, consider an FR code Chete with
asymmetric parameters. In the FR code Chete , a packet Pj
is available in ρj distinct nodes so, the availability fraction
of the packet Pj is ρj /n. Choosing higher values of the
replication factor ρj , one can increase the availability fraction
of the packet Pj in the system. Note that the availability
fraction of each packet is fixed with ρ/n for an FR code
Chomo : (n, θ, ., ρ) with symmetric parameters.
In an FR code, some nodes may be favorable for a data
collector because of their popularity or storage cost. For
example, a data collector would like to connect to a node
which contains more number of favorable packets and having
less storage cost. By permuting the packets, one can find an
FR code with the same parameters such that the typical node
contains more favorable packets.
For an FR code with asymmetric parameters, the system
allows to store more packets in a node. Hence, one can find
an FR code with the low storage cost sum by replacing packets
between two nodes, where the storage costs of the two packets
are distinct.
Now, consider an FR code with n nodes and θ packets. Let
the ci ∈ R be the cost to store one packet in the node Ui . For
some i, j ∈ {1, 2, . . . , n} and i 6= j, if 2ci ≤ cj then the cost
to store two packets in a node Ui is less then or equal to the
cost to store one packet in node Uj . Hence, for a given FR
code, the following two propositions give the condition of the
existence of FR codes with less storage cost sum.
Proposition 38. For the given n, θ ∈ N, let Chomo :
(n, θ, α, ρ) be an FR code with the symmetric parameters.
Let the ci ∈ R (c1 ≤ c2 ≤ . . . ≤ cn ) be the cost to store one
packet in the node Ui . For some i, j ∈ N, if 2ci ≤ cj then
an FR code Chete : (n, θ, α0 , ρ0 ) with asymmetric parameters
exists such that the total cost sum associated with Chete is less
then the total cost sum associated to Chomo , where the total
sum of node storage capacity of Chomo and Chete are same.
Proposition 39. For given n, θ ∈ N, let C : (n, θ, α, ρ) be an
FR code with asymmetric parameters. Let the ci ∈ R (c1 ≤
c2 ≤ . . . ≤ cn ) be the cost to store one packet in the node
Ui . For some i, j ∈ N, if ci + ci αi ≤ cj αj then an FR code
C 0 : (n, θ, α0 , ρ0 ) exists with asymmetric parameters such that
the total cost sum associated with C 0 is more then the total
cost sum associated to C , where the total sum of node storage
capacity of C and C 0 are the same.

10

TABLE II
FR CODES AND RESPECTIVE HYPERGRAPHS
FR code
C : (n, θ, α, ρ)
FR code [5], [24]
HFR code [7]
IFR code [13]
VFR code [8]
GFR code [9]
WFR code [10]
FR code [11]
Adaptive FR code [25]

FFR code [23]
FR code [12]
FR code [16]
FR code [15], [17]
FR code [19], [26], [28],
[29], [30]
Locally repairable
FR code [14], [20]

Corresponding conditional hypergraph
H = (V ; E)
ρ-uniform and α-regular hypergraph
Linear and α-regular hypergraph
ρ-uniform hypergraph
α-regular hypergraph with
|E| ∈ {ρ1 , ρ2 }, for each E ∈ E
ρ-uniform and linear hypergraph
ρ-uniform hypergraph
ρ-uniform, α-regular and linear hypergraph
ρ-uniform α-regular hypergraph s.t. there
exist a ρ0 -uniform α0 -regular sub-hypergraph,
where ρ0 < ρ and α0 < α, for ρ0 , α0 ∈ N
Linear hypergraph
ρ-uniform hypergraph
Hypergraph
ρ-uniform and α-regular hypergraph
Intersecting, ρ-uniform and
α-regular hypergraph
ρ-uniform, α-regular and
and non-linear hypergraph

