Locally recoverable code (LRC)

Description

Any code for which, given a codeword \(x\) and coordinate \(i\), \(x_i\) can be recovered from (at most \(r\)) other coordinates of \(x\). An \(r\)-locally recoverable code of length \(n\) and dimension \(k\) is denoted as an \((n,k,r)\) LRC code.

More technically, a \(q\)-ary code \(C\) with length \(n\) is \(r\)-locally recoverable, or has locality \(r\), if \(\forall i \in [n]\), there exists \(I_i \subset [n]\setminus i\) such that \(|I_i|\leq r\), and the projection of the set \(\mathcal{C}(i,a)=\{x\in C : x_i=a\}\) on to the coordinates in \(I_i\), i.e., \(\mathcal{C}_{I_i}(i,a)\) is disjoint from \(\mathcal{C}_{I_i}(i,a^\prime)\) where \(a\neq a^\prime\).

The definition can be generalized to \(t\)-LRC code, if every coordinate is recoverable from \(t\) disjoint subsets of coordinates. A study on the parameters of \(t\)-LRC codes, together with known bounds, can be found in Ref. [1].

Protection

The distance, \(d\), of an \((n,k,r)\) LRC code satisfies \begin{align} d\leq n-k-\left \lceil\frac{k}{r}\right \rceil+2~,\label{gen-singleton} \end{align} where \(r\leq k\). When \(k=r\), the bound on the distance gives the Singleton bound. The generalized Singleton bound \eqref{gen-singleton} does not account for \(q\)-ary alphabet size. A more generalized bound (including the non-linear case) is given in Ref. [2].

Rate

The rate \(r\) of an \((n,k,r)\) LRC code satisfies \begin{align} \frac{k}{n}\leq\frac{r}{r+1}~. \end{align}

Realizations

An \((18,14,7)\) LRC code has beed used in the Windows Azure cloud storage system [3]; see also Sec. 31.3.1.2 in Ref. [4].

Parent

Children

Zoo code information

Internal code ID: locally_recoverable

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: locally_recoverable

Cite as:
“Locally recoverable code (LRC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/locally_recoverable
BibTeX:
@incollection{eczoo_locally_recoverable, title={Locally recoverable code (LRC)}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/locally_recoverable} }
Permanent link:
https://errorcorrectionzoo.org/c/locally_recoverable

References

[1]
I. Tamo, A. Barg, and A. Frolov, “Bounds on the Parameters of Locally Recoverable Codes”, IEEE Transactions on Information Theory 62, 3070 (2016). DOI
[2]
V. R. Cadambe and A. Mazumdar, “Bounds on the Size of Locally Recoverable Codes”, IEEE Transactions on Information Theory 61, 5787 (2015). DOI
[3]
C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, and S. Yekhanin. Erasure coding in Windows Azure Storage. In Proc. USENIX Annual Technical Conference (ATC), pgs. 15-26, Boston, Massachusetts, June 2012.
[4]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021). DOI

Cite as:

“Locally recoverable code (LRC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/locally_recoverable

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/properties/distributed_storage/locally_recoverable.yml.