Draft:Locally Recoverable Codes - Wikipedia

Review waiting, please be patient. This may take 2 months or more, since drafts are reviewed in no specific order. There are 1,300 pending submissions waiting for review. If the submission is accepted, then this page will be moved into the article space. If the submission is declined, then the reason will be posted here. In the meantime, you can continue to improve this submission by editing normally.

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 LRC is an linear code such that there is a function that takes as input and a set of other coordinates of a codeword different from , and outputs .

Let   be a   linear code. For  , let us denote by   the minimum number of other coordinates we have to look at to recover an erasure in coordinate  . The number   is said to be the locality of the  -th coordinate of the code. The locality of the code is defined as

An   locally recoverable code (LRC) is an   linear code   with locality  .

Let   be an  -locally recoverable code. Then an erased component can be recovered linearly^[6], i.e. for every  , the space of linear equations of the code contains elements of the form  , where  .

Theorem^[7] Let   and let   be an  -locally recoverable code having   disjoint locality sets of size  . Then

An  -LRC   is said to be optimal if the minimum distance of   satisfies

Let   ∈   be a polynomial and let   be a positive integer. Then   is said to be ( ,  )-good if

•   has degree  ,

• there exist   , . . .,   distinct subsets of   such that

– for any  ,   (  ) = { } for some   ∈   , i.e. f is constant on  ,

– #  =  ,

–   ∩   = ∅ for any   ≠  .

We say that { } is a splitting covering for  ^[8].

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

• Suppose that a  -good polynomial   over   is given with splitting covering  .

• Let   ≤   be a positive integer.

• Consider the following   -vector space of polynomials

• Let   =  

• The code   is an   optimal locally coverable code, where   denotes evaluation of g at all points in the set  .

• Length. The length is the number of evaluation points. Because the sets   are disjoint for  , the length of the code is  .

• Dimension. The dimension of the code is  , for   ≤  , as each   has degree at most  , covering a vector space of dimension  , and by the construction of  , there are   distinct  .

• Distance. The distance is given by the fact that  , where  , and the obtained code is the Reed-Solomon code of degree at most  , so the minimum distance equals  .

• Locality. After the erasure of the single component, the evaluation at  , where  , is unknown, but the evaluations for all other   are known, so at most   evaluations are needed to uniquely determine the erased component, which gives us the locality of  .

To see this,   restricted to   can be described by a polynomial   of degree at most   thanks to the form of the elements in   (i.e. thanks to the fact that   is constant on  , and the  's have degree at most  ). On the other hand  , and   evaluations uniquely determine a polynomial of degree  . Therefore   can be constructed and evaluated at   to recover  .

We will use   to construct  -LRC. Notice that the degree of this polynomial is 5, and it is constant on   for  , where  ,  ,  ,  ,  ,  ,  , and  :  ,  ,  ,  ,  ,  ,  ,  . Hence,   is a  -good polynomial over   by the definition. Now, we will use this polynomial to construct a code of dimension   and length   over  . The locality of this code is 4, which will allow us to recover a single server failure by looking at the infromation contained in at most 4 other servers.

Next, let's define the encoding polynomial:  , where  . So,                  .

Thus, we can use the obtained encoding polynomial if we take our data to encode as the row vector    . Encoding the vector   to a length 15 message vector   by multiplying   by the generator matrix

For example, the encoding of information vector   gives the codeword  .

Observe that we constructed an optimal LRC; therefore, using the Singleton bound, we have that the distance of this code is  . Thus, we can recover any 6 erasures from our codeword by looking at no more than 8 other components.

Definition^[10] A code   has all-symbol locality   and availability   if every code symbol can be recovered from   disjoint repair sets of other symbols, each set of size at most   symbols. Such codes are called  -LRC.

Theorem^[11] The minimum distance of  -LRC having locality   and availability   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   and availability  , and is called  -LRC.

Theorem^[12] The minimum distance d of an   linear  -LRC satisfies the upper bound

.