Locally recoverable code (LRC) 

Also known as Locally repairable code.

Description

An LRC is a block code for which one can recover any coordinate of a codeword from at most \(r\) other coordinates of the codeword. In other words, an LRC of locality \(r\) is a block code for which, given a codeword \(c\) and coordinate \(c_i\), \(c_i\) can be recovered from at most \(r\) other coordinates of \(c\). An \(r\)-locally recoverable code of length \(n\) and dimension \(k\) is denoted as an \((n,k,r)\) LRC. The definition can be generalized to \(t\)-LRC, if every coordinate is recoverable from \(t\) disjoint subsets of coordinates.

Protection

A study on the parameters of \(t\)-LRCs, together with known bounds, can be found in Ref. [1]. See Ref. [2] for more bounds on locally recoverable distributed storage codes.

Rate

The rate of an \((n,k,r)\) LRC satisfies \begin{align} \frac{k}{n}\leq\frac{r}{r+1}~. \tag*{(1)}\end{align} Various asymptotic lower [3,4] and upper bounds [5] exist.

Realizations

An \((18,14,7)\) LRC has beed used in the Windows Azure cloud storage system [6]; see also [7; 31.3.1.2].Facebook f4 BLOB cloud storage system [8]

Notes

See Ref. [9].

Parents

Children

  • Locally correctable code (LCC) — LRCs (LCCs) allow one to recover any coordinate of a codeword from at most \(r\) coordinates of a codeword (an error word within the decoding radius). Since a codeword is a trivial error word, any LCC is also an LRC.
  • Optimal LRC
  • Tamo-Barg-Vladut code
  • \(q\)-ary LDPC code — LDPC codes are linear LRCs whose locality is the maximum number of nonzero entries in a row of the parity-check matrix [10].

Cousins

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]
A. Mazumdar, “Storage Capacity of Repairable Networks”, IEEE Transactions on Information Theory 61, 5810 (2015) arXiv:1408.4862 DOI
[3]
A. Barg, I. Tamo, and S. Vladut, “Locally recoverable codes on algebraic curves”, 2015 IEEE International Symposium on Information Theory (ISIT) (2015) arXiv:1603.08876 DOI
[4]
V. R. Cadambe and A. Mazumdar, “Bounds on the Size of Locally Recoverable Codes”, IEEE Transactions on Information Theory 61, 5787 (2015) DOI
[5]
A. Agarwal et al., “Combinatorial Alphabet-Dependent Bounds for Locally Recoverable Codes”, IEEE Transactions on Information Theory 64, 3481 (2018) arXiv:1702.02685 DOI
[6]
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.
[7]
V. Ramkumar, M. Vajha, S. B. Balaji, M. Nikhil Krishnan, B. Sasidharan, P. Vijay Kumar, "Codes for Distributed Storage." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[8]
Muralidhar, S., Lloyd, W., Roy, S., Hill, C., Lin, E., Liu, W., Pan, S., Shankar, S., Sivakumar, V., Tang, L. and Kumar, S., 2014. f4: Facebook's warm BLOB storage system. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14) (pp. 383-398).
[9]
I. F. Blake, Essays on Coding Theory (Cambridge University Press, 2024) DOI
[10]
L. Golowich and V. Guruswami, “Quantum Locally Recoverable Codes”, (2023) arXiv:2311.08653
[11]
M. Ye and A. Barg, “Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization”, (2017) arXiv:1605.08630
[12]
U. Martínez-Peñas and F. R. Kschischang, “Universal and Dynamic Locally Repairable Codes with Maximal Recoverability via Sum-Rank Codes”, (2019) arXiv:1809.11158
[13]
V. Skachek, “Batch and PIR Codes and Their Connections to Locally Repairable Codes”, Network Coding and Subspace Designs 427 (2018) DOI
[14]
A.-E. Riet, V. Skachek, and E. K. Thomas, “Batch Codes for Asynchronous Recovery of Data”, IEEE Transactions on Information Theory 68, 1545 (2022) DOI
[15]
A. Fazeli, A. Vardy, and E. Yaakobi, “PIR with Low Storage Overhead: Coding instead of Replication”, (2015) arXiv:1505.06241
[16]
V. Skachek, “Batch and PIR Codes and Their Connections to Locally Repairable Codes”, (2017) arXiv:1611.09914
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

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} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/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

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