Locally recoverable code

Locally recoverable codes are a family of error correction codes that were introduced first by D. S. Papailiopoulos and A. G. Dimakis^[1] and have been widely studied in information theory due to their applications related to distributive and cloud storage systems.^[2][3][4][5]

An [ n , k , d , r ] q {\displaystyle [n,k,d,r]_{q}} LRC is an [ n , k , d ] q {\displaystyle [n,k,d]_{q}} linear code such that there is a function f i {\displaystyle f_{i}} that takes as input i {\displaystyle i} and a set of r {\displaystyle r} other coordinates of a codeword c = ( c 1 , … , c n ) ∈ C {\displaystyle c=(c_{1},\ldots ,c_{n})\in C} different from c i {\displaystyle c_{i}} , and outputs c i {\displaystyle c_{i}} .

Erasure-correcting codes, or simply erasure codes, for distributed and cloud storage systems, are becoming more and more popular as a result of the present spike in demand for cloud computing and storage services. This has inspired researchers in the fields of information and coding theory to investigate new facets of codes that are specifically suited for use with storage systems.

It is well-known that LRC is a code that needs only a limited set of other symbols to be accessed in order to restore every symbol in a codeword. This idea is very important for distributed and cloud storage systems since the most common error case is when one storage node fails (erasure). The main objective is to recover as much data as possible from the fewest additional storage nodes in order to restore the node. Hence, Locally Recoverable Codes are crucial for such systems.

The following definition of the LRC follows from the description above: an [ n , k , r ] {\displaystyle [n,k,r]} -Locally Recoverable Code (LRC) of length n {\displaystyle n} is a code that produces an n {\displaystyle n} -symbol codeword from k {\displaystyle k} information symbols, and for any symbol of the codeword, there exist at most r {\displaystyle r} other symbols such that the value of the symbol can be recovered from them. The locality parameter satisfies 1 ≤ r ≤ k {\displaystyle 1\leq r\leq k} because the entire codeword can be found by accessing k {\displaystyle k} symbols other than the erased symbol. Furthermore, Locally Recoverable Codes, having the minimum distance d {\displaystyle d} , can recover d − 1 {\displaystyle d-1} erasures.

Let C {\displaystyle C} be a [ n , k , d ] q {\displaystyle [n,k,d]_{q}} linear code. For i ∈ { 1 , … , n } {\displaystyle i\in \{1,\ldots ,n\}} , let us denote by r i {\displaystyle r_{i}} the minimum number of other coordinates we have to look at to recover an erasure in coordinate i {\displaystyle i} . The number r i {\displaystyle r_{i}} is said to be the locality of the i {\displaystyle i} -th coordinate of the code. The locality of the code is defined as

An [ n , k , d , r ] q {\displaystyle [n,k,d,r]_{q}} locally recoverable code (LRC) is an [ n , k , d ] q {\displaystyle [n,k,d]_{q}} linear code C ∈ F q n {\displaystyle C\in \mathbb {F} _{q}^{n}} with locality r {\displaystyle r} .

Let C {\displaystyle C} be an [ n , k , d ] q {\displaystyle [n,k,d]_{q}} -locally recoverable code. Then an erased component can be recovered linearly,^[6] i.e. for every i ∈ { 1 , … , n } {\displaystyle i\in \{1,\ldots ,n\}} , the space of linear equations of the code contains elements of the form x i = f ( x i 1 , … , x i r ) {\displaystyle x_{i}=f(x_{i_{1}},\ldots ,x_{i_{r}})} , where i j ≠ i {\displaystyle i_{j}\neq i} .

Theorem^[7] Let n = ( r + 1 ) s {\displaystyle n=(r+1)s} and let C {\displaystyle C} be an [ n , k , d ] q {\displaystyle [n,k,d]_{q}} -locally recoverable code having s {\displaystyle s} disjoint locality sets of size r + 1 {\displaystyle r+1} . Then

An [ n , k , d , r ] q {\displaystyle [n,k,d,r]_{q}} -LRC C {\displaystyle C} is said to be optimal if the minimum distance of C {\displaystyle C} satisfies

Let f ∈ F q [ x ] {\displaystyle f\in \mathbb {F} _{q}[x]} be a polynomial and let ℓ {\displaystyle \ell } be a positive integer. Then f {\displaystyle f} is said to be ( r {\displaystyle r} , ℓ {\displaystyle \ell } )-good if

• f {\displaystyle f} has degree r + 1 {\displaystyle r+1} ,

• there exist distinct subsets A 1 , … , A ℓ {\displaystyle A_{1},\ldots ,A_{\ell }} of F q {\displaystyle \mathbb {F} _{q}} such that

– for any i ∈ { 1 , … , ℓ } {\displaystyle i\in \{1,\ldots ,\ell \}} , f ( A i ) = { t i } {\displaystyle f(A_{i})=\{t_{i}\}} for some t i ∈ F q {\displaystyle t_{i}\in \mathbb {F} _{q}} , i.e., f {\displaystyle f} is constant on A i {\displaystyle A_{i}} ,

– # A i = r + 1 {\displaystyle \#A_{i}=r+1} ,

– A i ∩ A j = ∅ {\displaystyle A_{i}\cap A_{j}=\varnothing } for any i ≠ j {\displaystyle i\neq j} .

We say that { A 1 , … , A ℓ {\displaystyle A_{1},\ldots ,A_{\ell }} } is a splitting covering for f {\displaystyle f} .^[8]

The Tamo–Barg construction utilizes good polynomials.^[9]

• Suppose that a ( r , ℓ ) {\displaystyle (r,\ell )} -good polynomial f ( x ) {\displaystyle f(x)} over F q {\displaystyle \mathbb {F} _{q}} is given with splitting covering i ∈ { 1 , … , ℓ } {\displaystyle i\in \{1,\ldots ,\ell \}} .

• Let s ≤ ℓ − 1 {\displaystyle s\leq \ell -1} be a positive integer.

• Consider the following F q {\displaystyle \mathbb {F} _{q}} -vector space of polynomials V = { ∑ i = 0 s g i ( x ) f ( x ) i : deg ⁡ ( g i ( x ) ) ≤ deg ⁡ ( f ( x ) ) − 2 } . {\displaystyle V=\left\{\sum _{i=0}^{s}g_{i}(x)f(x)^{i}:\deg(g_{i}(x))\leq \deg(f(x))-2\right\}.}

• Let T = ⋃ i = 1 ℓ A i {\textstyle T=\bigcup _{i=1}^{\ell }A_{i}} .

• The code { ev T ⁡ ( g ) : g ∈ V } {\displaystyle \{\operatorname {ev} _{T}(g):g\in V\}} is an ( ( r + 1 ) ℓ , ( s + 1 ) r , d , r ) {\displaystyle ((r+1)\ell ,(s+1)r,d,r)} -optimal locally coverable code, where ev T {\displaystyle \operatorname {ev} _{T}} denotes evaluation of g {\displaystyle g} at all points in the set T {\displaystyle T} .

• Length. The length is the number of evaluation points. Because the sets A i {\displaystyle A_{i}} are disjoint for i ∈ { 1 , … , ℓ } {\displaystyle i\in \{1,\ldots ,\ell \}} , the length of the code is | T | = ( r + 1 ) ℓ {\displaystyle |T|=(r+1)\ell } .

• Dimension. The dimension of the code is ( s + 1 ) r {\displaystyle (s+1)r} , for s {\displaystyle s} ≤ ℓ − 1 {\displaystyle \ell -1} , as each g i {\displaystyle g_{i}} has degree at most deg ⁡ ( f ( x ) ) − 2 {\displaystyle \deg(f(x))-2} , covering a vector space of dimension deg ⁡ ( f ( x ) ) − 1 = r {\displaystyle \deg(f(x))-1=r} , and by the construction of V {\displaystyle V} , there are s + 1 {\displaystyle s+1} distinct g i {\displaystyle g_{i}} .

• Distance. The distance is given by the fact that V ⊆ F q [ x ] ≤ k {\displaystyle V\subseteq \mathbb {F} _{q}[x]_{\leq k}} , where k = r + 1 − 2 + s ( r + 1 ) {\displaystyle k=r+1-2+s(r+1)} , and the obtained code is the Reed-Solomon code of degree at most k {\displaystyle k} , so the minimum distance equals ( r + 1 ) ℓ − ( ( r + 1 ) − 2 + s ( r + 1 ) ) {\displaystyle (r+1)\ell -((r+1)-2+s(r+1))} .

• Locality. After the erasure of the single component, the evaluation at a i ∈ A i {\displaystyle a_{i}\in A_{i}} , where | A i | = r + 1 {\displaystyle |A_{i}|=r+1} , is unknown, but the evaluations for all other a ∈ A i {\displaystyle a\in A_{i}} are known, so at most r {\displaystyle r} evaluations are needed to uniquely determine the erased component, which gives us the locality of r {\displaystyle r} .

To see this, g {\displaystyle g} restricted to A j {\displaystyle A_{j}} can be described by a polynomial h {\displaystyle h} of degree at most deg ⁡ ( f ( x ) ) − 2 = r + 1 − 2 = r − 1 {\displaystyle \deg(f(x))-2=r+1-2=r-1} thanks to the form of the elements in V {\displaystyle V} (i.e., thanks to the fact that f {\displaystyle f} is constant on A j {\displaystyle A_{j}} , and the g i {\displaystyle g_{i}} 's have degree at most deg ⁡ ( f ( x ) ) − 2 {\displaystyle \deg(f(x))-2} ). On the other hand | A j ∖ { a j } | = r {\displaystyle |A_{j}\backslash \{a_{j}\}|=r} , and r {\displaystyle r} evaluations uniquely determine a polynomial of degree r − 1 {\displaystyle r-1} . Therefore h {\displaystyle h} can be constructed and evaluated at a j {\displaystyle a_{j}} to recover g ( a j ) {\displaystyle g(a_{j})} .

We will use x 5 ∈ F 41 [ x ] {\displaystyle x^{5}\in \mathbb {F} _{41}[x]} to construct [ 15 , 8 , 6 , 4 ] {\displaystyle [15,8,6,4]} -LRC. Notice that the degree of this polynomial is 5, and it is constant on A i {\displaystyle A_{i}} for i ∈ { 1 , … , 8 } {\displaystyle i\in \{1,\ldots ,8\}} , where A 1 = { 1 , 10 , 16 , 18 , 37 } {\displaystyle A_{1}=\{1,10,16,18,37\}} , A 2 = 2 A 1 {\displaystyle A_{2}=2A_{1}} , A 3 = 3 A 1 {\displaystyle A_{3}=3A_{1}} , A 4 = 4 A 1 {\displaystyle A_{4}=4A_{1}} , A 5 = 5 A 1 {\displaystyle A_{5}=5A_{1}} , A 6 = 6 A 1 {\displaystyle A_{6}=6A_{1}} , A 7 = 11 A 1 {\displaystyle A_{7}=11A_{1}} , and A 8 = 15 A 1 {\displaystyle A_{8}=15A_{1}} : A 1 5 = { 1 } {\displaystyle A_{1}^{5}=\{1\}} , A 2 5 = { 32 } {\displaystyle A_{2}^{5}=\{32\}} , A 3 5 = { 38 } {\displaystyle A_{3}^{5}=\{38\}} , A 4 5 = { 40 } {\displaystyle A_{4}^{5}=\{40\}} , A 5 5 = { 9 } {\displaystyle A_{5}^{5}=\{9\}} , A 6 5 = { 27 } {\displaystyle A_{6}^{5}=\{27\}} , A 7 5 = { 3 } {\displaystyle A_{7}^{5}=\{3\}} , A 8 5 = { 14 } {\displaystyle A_{8}^{5}=\{14\}} . Hence, x 5 {\displaystyle x^{5}} is a ( 4 , 8 ) {\displaystyle (4,8)} -good polynomial over F 41 {\displaystyle \mathbb {F} _{41}} by the definition. Now, we will use this polynomial to construct a code of dimension k = 8 {\displaystyle k=8} and length n = 15 {\displaystyle n=15} over F 41 {\displaystyle \mathbb {F} _{41}} . The locality of this code is 4, which will allow us to recover a single server failure by looking at the information contained in at most 4 other servers.

Next, let us define the encoding polynomial: f a ( x ) = ∑ i = 0 r − 1 f i ( x ) x i {\displaystyle f_{a}(x)=\sum _{i=0}^{r-1}f_{i}(x)x^{i}} , where f i ( x ) = ∑ i = 0 k r − 1 a i , j g ( x ) j {\displaystyle f_{i}(x)=\sum _{i=0}^{{\frac {k}{r}}-1}a_{i,j}g(x)^{j}} . So, f a ( x ) = {\displaystyle f_{a}(x)=} a 0 , 0 + {\displaystyle a_{0,0}+} a 0 , 1 x 5 + {\displaystyle a_{0,1}x^{5}+} a 1 , 0 x + {\displaystyle a_{1,0}x+} a 1 , 1 x 6 + {\displaystyle a_{1,1}x^{6}+} a 2 , 0 x 2 + {\displaystyle a_{2,0}x^{2}+} a 2 , 1 x 7 + {\displaystyle a_{2,1}x^{7}+} a 3 , 0 x 3 + {\displaystyle a_{3,0}x^{3}+} a 3 , 1 x 8 {\displaystyle a_{3,1}x^{8}} .

Thus, we can use the obtained encoding polynomial if we take our data to encode as the row vector a = {\displaystyle a=} ( a 0 , 0 , a 0 , 1 , a 1 , 0 , a 1 , 1 , a 2 , 0 , a 2 , 1 , a 3 , 0 , a 3 , 1 ) {\displaystyle (a_{0,0},a_{0,1},a_{1,0},a_{1,1},a_{2,0},a_{2,1},a_{3,0},a_{3,1})} . Encoding the vector m {\displaystyle m} to a length 15 message vector c {\displaystyle c} by multiplying m {\displaystyle m} by the generator matrix

G = ( 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 32 32 32 32 32 38 38 38 38 38 1 10 16 18 37 2 20 32 33 36 3 7 13 29 30 1 10 16 18 37 23 25 40 31 4 32 20 2 36 33 1 18 10 37 16 4 31 40 23 25 9 8 5 21 39 1 18 10 37 16 5 8 9 39 21 14 17 26 19 6 1 16 37 10 18 8 5 9 21 39 27 15 24 35 22 1 16 37 10 18 10 37 1 16 18 1 37 10 18 16 ) . {\displaystyle G={\begin{pmatrix}1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\1&1&1&1&1&32&32&32&32&32&38&38&38&38&38\\1&10&16&18&37&2&20&32&33&36&3&7&13&29&30\\1&10&16&18&37&23&25&40&31&4&32&20&2&36&33\\1&18&10&37&16&4&31&40&23&25&9&8&5&21&39\\1&18&10&37&16&5&8&9&39&21&14&17&26&19&6\\1&16&37&10&18&8&5&9&21&39&27&15&24&35&22\\1&16&37&10&18&10&37&1&16&18&1&37&10&18&16\end{pmatrix}}.}

For example, the encoding of information vector m = ( 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ) {\displaystyle m=(1,1,1,1,1,1,1,1)} gives the codeword c = m G = ( 8 , 8 , 5 , 9 , 21 , 3 , 36 , 31 , 32 , 12 , 2 , 20 , 37 , 33 , 21 ) {\displaystyle c=mG=(8,8,5,9,21,3,36,31,32,12,2,20,37,33,21)} .

Observe that we constructed an optimal LRC; therefore, using the Singleton bound, we have that the distance of this code is d = n − k − ⌈ k r ⌉ + 2 = 15 − 8 − 2 + 2 = 7 {\displaystyle d=n-k-\left\lceil {\frac {k}{r}}\right\rceil +2=15-8-2+2=7} . Thus, we can recover any 6 erasures from our codeword by looking at no more than 8 other components.

A code C {\displaystyle C} has all-symbol locality r {\displaystyle r} and availability t {\displaystyle t} if every code symbol can be recovered from t {\displaystyle t} disjoint repair sets of other symbols, each set of size at most r {\displaystyle r} symbols. Such codes are called ( r , t ) a {\displaystyle (r,t)_{a}} -LRC.^[10]

Theorem The minimum distance of [ n , k , d ] q {\displaystyle [n,k,d]_{q}} -LRC having locality r {\displaystyle r} and availability t {\displaystyle t} satisfies the upper bound

If the code is systematic and locality and availability apply only to its information symbols, then the code has information locality r {\displaystyle r} and availability t {\displaystyle t} , and is called ( r , t ) i {\displaystyle (r,t)_{i}} -LRC.^[11]

Theorem^[12] The minimum distance d {\displaystyle d} of an [ n , k , d ] q {\displaystyle [n,k,d]_{q}} linear ( r , t ) i {\displaystyle (r,t)_{i}} -LRC satisfies the upper bound