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
Rate
Realizations
Parents
- Galois-field \(q\)-ary code — Locally recoverable codes protect against coordinate erasure.
- Distributed-storage code
Children
- Batch code — A systematic batch code with restricted size of reconstruction sets can recover any query of \(t\) information symbols with recovery sets of size \(r\) [5,6].
- Maximum distance separable (MDS) code — MDS codes are most efficient in terms of minimizing storage overhead for handling erasures. They are locally recoverable with locality \(k\).
- Sequential-recovery code
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]
- 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
- [5]
- V. Skachek, “Batch and PIR Codes and Their Connections to Locally Repairable Codes”, Network Coding and Subspace Designs 427 (2018) DOI
- [6]
- 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
Page edit log
- Victor V. Albert (2022-04-28) — most recent
- Mustafa Doger (2022-04-03)
Cite as:
“Locally recoverable code (LRC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/locally_recoverable