{'fraction_non_alphanumeric': 0.05375220070422535, 'fraction_numerical': 0.01837588028169014, 'mean_word_length': 3.7671125098347757, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Binary Cyclic Codes that are Locally Repairable

Codes for storage systems aim to minimize the repair locality, which is the number of disks (or nodes) that participate in the repair of a single failed disk. Simultaneously, the code must sustain a high rate, operate on a small finite field to be practically significant and be tolerant to a large number of erasures. To this end, we construct new families of binary linear codes that have an optimal dimension (rate) for a given minimum distance and locality. Specifically, we construct cyclic codes that are locally repairable for locality 2 and distances 2, 6 and 10. In doing so, we discover new upper bounds on the code dimension, and prove the optimality of enabling local repair by provisioning disjoint groups of disks. Finally, we extend our construction to build codes that have multiple repair sets for each disk.


I. INTRODUCTION
Triple replication (or triplication) has been the default storage policy in cloud file systems (notably, Google File system [1] and Hadoop [2]), and though storage-inefficient, performs extremely well in the face of single disk failures. However, the storage capacity today continues to scale beyond petabytes at a rate steadily incompatible with the adage 'storage is cheap'. Whereas erasure codes such as Reed-Solomon codes are storage-efficient, they make the time to repair a disk failure much longer. The conflicting goals have led the search for new storage codes towards optimizing different repair metrics. A large literature studies regenerating codes, which minimize the total number of symbols (or bits) communicated in repairing a failed disk, e.g. [3], [4], [5], [6], [7], and [8]. Another metric of importance, and the one we focus on here, is the number of disks (or nodes) which participate in the repair process, referred to as locality; see among others, [9], [10], [11], [12], [13], [14], [15], and [16].

A. Locally Repairable Codes
A locally repairable (or recoverable) code (LRC) is a code of length n over a finite field F such that a symbol in any coordinate 1 of a codeword can be recovered by accessing the symbols in at most r other coordinates. Most of the literature has been devoted to calculating the maximum possible minimum Hamming distance (or just, distance) d achievable for a given code dimension k (or cardinality A) and locality r. An upper bound on d, analogous to the Singleton bound for The work of Sreechakra Goparaju and Robert Calderbank was supported in part by Air Force Office of Scientific Research grant FA 9550-13-01-0076 under the Complex Networks Program. 1 Each coordinate of a codeword corresponds to a disk or a node in the distributed storage system over n nodes. classical codes, is given by which has been proved using multiple approaches in [12], [13], [14] and [15]. LRCs which achieve this distance (constructed, for example, in [16] and [17]), are called optimal, and Singleton-optimal in this paper. Singleton-optimal LRCs were recently constructed [15] over a finite field of any size that exceeds the code length n using polynomial evaluations, thereby generalizing Reed-Solomon codes.
In practice, small finite fields, especially Galois fields of the form F 2 m , are preferred for their fast arithmetic [18] and backward compatibility with existing hardware. For instance, the recently developed LRC for Microsoft's Windows Azure storage [19] and that implemented on a Facebook analytics cluster [20] are both codes over binary extension fields. However, little has been said on explicit LRCs on a given finite field. An upper bound on the distance of an LRC with a given locality r and field size was given in [21], and the family of simplex codes was shown to achieve the bound, thus proving them to be optimal over the binary field, F 2 .

B. Contribution
In this paper, we focus on linear cyclic codes to construct new binary LRCs (that is, LRCs over F 2 ). Cyclic codes [22] have an inherent structure which enables highly efficient encoder and decoder implementations; they are widely used in data communications and data storage, and several of the well-known classical codes (such as Golay codes, BCH codes and Reed-Solomon codes) are cyclic.
We begin with constructing a family of locally repairable cyclic codes (or, cyclic LRCs) in Section II which turns out to be Singleton-optimal, and acts as a base for the subsequent code constructions. In Section III, we construct codes having distances d = 6 and d = 10 and locality r = 2. For each of these families, we analyze (and in most cases, prove) their optimality in terms of their dimension.
The structure of cyclic codes seamlessly leads to a division of codeword coordinates into disjoint repair groups, such that the coordinates in each repair group aid in the repair of each other (and do not need other coordinates). This structural assumption is either part of the repair model or proved to be optimal in several cases, e.g. [14], [12], and is useful in constructing LRCs over small finite fields. In particular, it has been proved [15] to be optimal when r + 1 divides n and the field size |F| ≥ n. We prove that the optimality of this assumption continues to hold for a family of codes constructed in Section III.
The structural assumption also leads to the tensor-product style of construction that we use and has been alluded to in [15] and [21]. In Section IV, we extend this tensorproduct construction to obtain codes with multiple availability, wherein every symbol can be simultaneously repaired by more than one repair set of size r. Availability is a useful property in systems storing frequently-accessed data; see [23], [15], and [24] for some distance optimality results and multi-available LRC constructions. Finally, we conclude in Section V.

II. A SINGLETON-OPTIMAL FAMILY
We first redefine an LRC in terms of binary linear codes. For simplicity we focus on construction of locally repairable cyclic codes over F 2 of length n = 2 m − 1, and locality r that is even. Furthermore, as mentioned earlier, we assume that r + 1 | n. It follows that m is even when r = 2.

A. Motivation
Consider the linear code dual to the LRC we intend to construct. The smallest cyclic code containing codewords of (Hamming) weight r + 1 is that which consists of the cyclic shifts of the codeword with ones in positions 0, n/(r + 1), 2n/(r + 1), and rn/(r + 1). This code exists. If α is a primitive element 2 (representable as a binary m-vector), then we have α as a zero of where the polynomial h(x) generates the dual code. Notice that if g(x) and h(x) are the generator polynomials of the LRC and its dual, respectively, then and every non-zero field element α j ∈ F 2 m , where j ∈ {0, 1, . . . , n − 2}, is a root of either h(x) or g(x). It can be verified then that h(x) is a factor of x n − 1 and that the other zeroes 3 of h(x) are α j , such that j is not divisible by r + 1. We therefore have the following family of cyclic LRCs.

Construction 1.
Let n = 2 m − 1, r + 1 be a factor of n and α be a primitive element of F 2 m . Let C be a cyclic code with the generator polynomial g(x) having zeroes α j(r+1) , where j ranges from 0 to (n/(r + 1)) − 1. Then C is an LRC with locality r, and dimension k := rn/(r + 1). 2 Throughout the paper, α will represent a primitive element of F 2 m . 3 It is here that we use that r is even. We do not want h(α 0 ) = 0.
and an LRC of dimension k = 10.
Using the LRC Singleton bound from (1), we have, This upper bound on d is achievable for the code defined in Construction 1 (a codeword of Hamming weight 2 can be found -for example, ones at positions 0 and n/(r + 1)), and therefore Construction 1 gives a family of Singleton-optimal codes 4 . As in classical cyclic codes, this minimum distance can be increased by adding more zeroes to the generator polynomial. We look at the optimality of some such codes in the next section.

A. Disjoint Repair Groups
We first construct and analyze some codes which have disjoint repair groups. Consider the following code with minimum distance d = 6.
Example 2. For n = 15 and locality r = 2, if we have the zeroes of g(x) as 1 and all cyclotomic cosets of α and α 3 , then k = 6 and d = 6. This is not optimal with respect to the LRC Singleton bound (1), which gives d ≤ 8. In general, we have the following family of codes.

Construction 2.
Let n = 2 m −1 with m even, and locality r = 2. Let C be a cyclic code with the generator polynomial g(x) having zeroes as in Construction 1, along with the cyclotomic coset of α. Then C is an LRC of dimension and a distance d ≥ 6.
The lower bound on d follows from the BCH distance bound (e.g., [22]). From the LRC Singleton bound (1), we have However, we show in the next theorem that this family of codes is indeed distance-optimal among the set of linear codes which have disjoint locality parity checks. Theorem 1. Consider a binary linear code C of length n = 2 m − 1, distance d = 6, and locality r = 2. Let m be an even number greater than 2. Suppose that the set of coordinates [n] can be divided into n/3 groups, {g i } n/3 i=1 , such that the repair of a given coordinate only requires the bits stored in the coordinates in its corresponding group. This implies that the dual code has a codeword (parity-check) of Hamming weight r + 1 = 3 supported by the coordinates in each group g i . Then, Notice that this k corresponds to the dimension of the family of codes in Construction 2.
Proof: Let x = (x 1 , x 2 , . . . , x n ) be a codeword in C , and let g i = {i, i + (n/3), i + (2n/3)} for i = [n/3]. Consider the projection of a codeword x onto the set of coordinates g i . By the locality parity-checks, we know that the only possible projections are {000, 011, 101, 110}. In other words, we can map the binary code C to an additive code C 4 over F 4 of length n/3, minimum distance d/2 and size 2 k . Conversely, any additive code C 4 over F 4 of length n ′ = (2 m − 1)/3 and minimum (Hamming) distance d ′ = 3 maps back to a binary code C which satisfies the theorem's conditions. Thus, we need only prove that the dimension for such an additive code is upper bounded by To this end, consider the given code C 4 and let x ′ = (x ′ 1 , . . . , x ′ n ′ ) be a codeword in C 4 . We will prove that there exists a set M of m/2 coordinates in [n ′ ] such that the support of no non-zero codeword is a subset of M , that is, supp(x ′ ) ⊆ M , for all x ′ ∈ C 4 \{0}. Then, the code C 4 projected onto the rest of the coordinates, has the same dimension as C 4 , that is, the projected code of length n ′ − (m/2) has a minimum (Hamming) distance of at least 1. Thus, from the naïve Singleton bound applied to the projected code, we have which proves (3). Let u be any nonnegative integer 5 such that Now consider the collection of n ′ −u sets of coordinates of the form {i 1 , i 2 , . . . , i u , i u+1 }, where the first u coordinates are fixed and i u+1 ∈ [n ′ ]\{i 1 , . . . , i u }. We claim that there exists at least one set in this collection such that there is no codeword x ′ such that i u+1 ∈ supp(x ′ ) ⊆ {i 1 , . . . , i u+1 }. If this were not true, then there exists a unique codeword corresponding to each of the n ′ − u. From (5), two of these codewords have the same projections on the coordinates {i 1 , . . . , i u } and therefore, 5 We can assume that m ≥ 6 here; for m = 4, any M is sufficient.
are at a distance of 2, a contradiction. We can now use this claim to construct the required M . Without loss of generality, let i 1 = 1 and i 2 = 2. Since 4 2 < n ′ − 2 for any m > 4, there exists a set of coordinates {1, 2, i 3 } such that there is no codeword x ′ which satisfies i 3 ∈ supp(x ′ ) ⊆ {1, 2, i 3 } (in this special case, we just mean that there is no codeword with the support {1, 2, i 3 }). Again, with no loss in generality, let i 3 = 3. We can append i 4 = 4 to the set {1, 2, 3} in the same manner as above if u = 4 satisfies (5). There is then no codeword x ′ such that 4 ∈ supp(x ′ ) ⊆ {1, 2, 3, 4}. Continuing the process, we obtain a set of coordinates {1, . . . , u * , u * + 1} such that there is no codeword x ′ which satisfies any of the following conditions: where u ∈ {2, 3, . . . , u * } and u * is the maximum value of u which satisfies (5). It can be verified that the above construction implies that for all x ′ ∈ C \{0}, supp(x ′ ) ⊆ [u * + 1], and that u * = m/2 − 1 for the given parameters. Thus, M = [u * + 1] has been constructed.
Another Proof: The upper bound in (3) follows directly from the Hamming bound. In fact, it is satisfied with equality by the Hamming codes over F 4 with the parameters In other words, the constructed binary 2-local codes map to the Hamming codes over However, if k is even, then and there exists a family of cyclic codes satisfying this bound with equality.
Proof: The proof follows in a similar way as that of Theorem 1. The binary code C can be mapped to an additive code C 4 over F 4 of length n ′ = n/3, minimum distance d ′ = 5 and size 2 k . By the Hamming bound, we have the maximum size A(n ′ , 5) := A of any code over F 4 of length n ′ and d ′ = 5 upper bounded as and the substitution n = 2 m − 1 leads to for any even m > 2. Moreover, if k is even, we have (6) instead.
Remark: If we assume that the contracted code is linear, then k is always even (so that the dimension of the code C 4 over F 4 is an integer). This gives us the required bound in (6). (6) is achievable by a cyclic code whose generator polynomial g(x) has zeros at α j , where j is a multiple of 3; α 2 i , that is, the cyclotomic cosets of α; and α n−2 i , that is, the cyclotomic cosets of α −1 , where α is a primitive element.

B. Optimality of Disjoint Repair Groups
We now prove that the assumption of disjoint locality parity checks leads to no loss in optimality in Theorem 1. We start with a basic lemma on the locality parity checks.

Lemma 1.
Let C be a binary linear code of length n and locality r. Then there exist linearly independent codewords (parity checks) of weight r + 1 in the dual code C ⊥ , the union of whose supports equals [n].
Proof: Let P be the set of parity checks corresponding to every coordinate in a codeword of C , and let P m be a maximal linearly independent subset of P. If the supports of the parity checks in P m do not cover a coordinate in [n], say i, then any parity check in P corresponding to i lies outside the span of P m , disproving its maximality. Thus, P m satisfies the lemma.
Remark: In the next theorem, we use not P m , but the smallest subset of P m which satisfies the lemma. Proof: Let Q be a set of linearly independent parity checks of weight 3 in C ⊥ that cover [n]. Suppose that its cardinality, |Q| = b, be minimal and be given by where 0 ≤ t ≤ m. Here t ≥ 0 because we need at least n/3 repair parity checks to cover each coordinate. For t ≥ m + 1, we have which satisfies (2), with a strict inequality. Let N be the maximum number of pairwise disjoint weight 3 parity checks in P m . These parity checks cover 3N coordinates, and each of the remaining b − N covers at most 2 additional coordinates (not already covered by the N in the disjoint set), that is, The remaining b − N ≤ 3t ≤ 3m parity checks can overlap with at most 6m of the N pairwise disjoint parity checks (if each overlaps with two different parity checks). We therefore have at least N * pairwise disjoint parity checks that do not intersect with any of the remaining b − N * parity checks in Q, where Notice that the right hand side above is positive for m ≥ 8.
Let N be the set of 3N * coordinates covered by these N * parity checks. Consider the sub-code C N of C , with zeroes in the coordinates [n]\N . The b parity checks in Q do not preclude codewords which have weights 2 and 4 in C N . To impose a distance d = 6 on C N , the codewords in C N of weight less than 3 (that is, of weights 0 and 2) must be in different cosets, that is, whereb is the number of additional parity checks necessary. Note that the right hand side can be viewed as the number of codewords of length N * on F 4 of weight less than 2 (with a mapping similar to that in the proof of Theorem 1). We therefore haveb ≥ m, for m > 8. This, coupled with (9), gives the dimension of C ⊥ as which is the same as (2). Remark: If t = 0, then Theorem 1 applies, and if t > 0, then we have n − k ≥ (n/3) + m + 1, which satisfies (2) with a strict inequality. Theorem 4 (Corollary). Let C be a binary linear code as given in Theorem 3. Then, C is a distance-optimal LRC only if it has disjoint locality parity checks.

IV. MULTIPLE REPAIR SETS
The basic cyclic code construction in sections II and III (Construction 1) can be seen as a linear code with a parity check matrix given by the tensor product where the first matrix, having (r + 1) ones is the parity check matrix for the simplest binary LRC with locality r and I n/(r+1) is an n/(r + 1)-dimensional identity matrix. This construction can similarly be extended to the case of what we call multiply available locally repairable codes or t-availabler-local LRCs. The codes considered in the previous sections were 1-available-r-local LRCs.
Definition 2 (Availability). A binary linear code C of length n is called a t-available-r-local locally repairable code (LRC) if every coordinate i in [n] has at least t parity checks of weight r + 1 which intersect pairwise in (and only in) {i}.
In the interest of space, we present only an example of a 3-available-2-local LRC.

V. CONCLUDING REMARKS
We have presented a method of constructing locally repairable codes that preserves the simplicity of three way replication and essentially doubles the data rate. We have also proved that in some cases the data rate of the new codes is optimal. Our construction is a natural extension of historical methods for constructing algebraic error correcting codes used in disk arrays. It leads to new coding theory questions about optimality of binary codes given a constraint on the weight structure of the dual code.
VI. ACKNOWLEDGEMENT We thank Dimitris Papailiopoulos and Itzhak Tamo for introducing us to this problem, and Itzhak Tamo and Alexander Barg for sharing their preprint [15].