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.
linear code such that there is a function
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.
-Locally Recoverable Code (LRC) of length
because the entire codeword can be found by accessing
Furthermore, Locally Recoverable Codes, having the minimum distance
locally recoverable code (LRC) is an
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
disjoint locality sets of size
is said to be optimal if the minimum distance of
[8] The Tamo–Barg construction utilizes good polynomials.
Notice that the degree of this polynomial is 5, and it is constant on
Now, we will use this polynomial to construct a code of dimension
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:
Thus, we can use the obtained encoding polynomial if we take our data to encode as the row vector
to a length 15 message vector
by the generator matrix For example, the encoding of information vector
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.
Theorem The minimum distance of
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
Theorem[12] The minimum distance
-LRC satisfies the upper bound