Alternative names: Locally repairable code.
Description
A block code for which one can recover any coordinate of a codeword from at most \(r\) other coordinates of the codeword [1; Def. 15.9.3].
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; the corresponding availability is the minimum number of recovery sets per coordinate [1; Def. 15.9.20].
Protection
A Singleton-like bound is \begin{align} d \leq n-k-\left\lceil\frac{k}{r}\right\rceil+2 \tag*{(1)}\end{align} for an \((n,k,r)\) LRC [1; Thm. 15.9.8]. A study on the parameters of \(t\)-LRCs, together with known bounds, can be found in Ref. [2]. See Ref. [3] 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*{(2)}\end{align} Various asymptotic lower [4,5] and upper bounds [6] exist.Realizations
An \((18,14,7)\) LRC has been used in the Windows Azure cloud storage system [7]; see also [8; 31.3.1.2].Facebook f4 BLOB cloud storage system [9]Notes
See Ref. [10].Cousins
- Linear \(q\)-ary code— A \(q\)-ary linear code is an LRC of locality \(r\) if each coordinate participates in at least one parity check of weight \(\leq r\) [11][8; Sec. 31.3.4.5].
- Regenerating code (RGC)— RGCs and LRCs are related via the group repair with optimal access problem [12].
- Linearized RS code— Linearized RS codes can be used to construct locally recoverable codes [13].
- 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\) [14,15].
- Private information retrieval (PIR) code— LRCs and PIR codes are related [16,17]: LRCs are designed to recover a codeword coordinate from a small set of other codeword coordinates, while PIR codes are designed to recover from many disjoint sets of arbitrary size [16].
- Availability code— Availability is the number of recovery sets available for each coordinate of an LRC [1; Def. 15.9.20].
- Quantum locally recoverable code (QLRC)— QLRCs are quantum analogues of LRCs.
Primary Hierarchy
Parents
An LRC of locality \(r\) is a code with \((r,2)\) locality [8; Sec. 31.3.4.5].
Locally recoverable code (LRC)
Children
The Hadamard code is an LRC with \(r=3\) [11].
LRCs recover a coordinate from a small number of other coordinates of an uncorrupted codeword, while LCCs allow recovery from a corrupted received word within the decoding radius. Since an uncorrupted codeword is a special case of a received word, any LCC is also an LRC.
Barg-Tamo-Vladut codes form a family of locally recoverable codes obtained from algebraic curves [1; Thm. 15.9.14].
The \(q\)-ary repetition code is an LRC with \(r=2\) [11].
LDPC codes are linear LRCs whose locality is the maximum number of nonzero entries in a row of the parity-check matrix [11].
References
- [1]
- A. Couvreur, H. Randriambololona, “Algebraic Geometry Codes and Some Applications.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [2]
- I. Tamo, A. Barg, and A. Frolov, “Bounds on the Parameters of Locally Recoverable Codes”, IEEE Transactions on Information Theory 62, 3070 (2016) DOI
- [3]
- A. Mazumdar, “Storage Capacity of Repairable Networks”, IEEE Transactions on Information Theory 61, 5810 (2015) arXiv:1408.4862 DOI
- [4]
- A. Barg, I. Tamo, and S. Vlăduţ, “Locally recoverable codes on algebraic curves”, 2015 IEEE International Symposium on Information Theory (ISIT) 1252 (2015) arXiv:1603.08876 DOI
- [5]
- V. R. Cadambe and A. Mazumdar, “Bounds on the Size of Locally Recoverable Codes”, IEEE Transactions on Information Theory 61, 5787 (2015) DOI
- [6]
- A. Agarwal, A. Barg, S. Hu, A. Mazumdar, and I. Tamo, “Combinatorial Alphabet-Dependent Bounds for Locally Recoverable Codes”, IEEE Transactions on Information Theory 64, 3481 (2018) arXiv:1702.02685 DOI
- [7]
- 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
- [8]
- V. Ramkumar, M. Vajha, S. B. Balaji, M. N. Krishnan, B. Sasidharan, P. Vijay Kumar, “Codes for Distributed Storage.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [9]
- S. Muralidhar, W. Lloyd, S. Roy, C. Hill, E. Lin, W. Liu, S. Pan, S. Shankar, V. Sivakumar, L. Tang, and S. Kumar, 2014. “f4: Facebook’s warm BLOB storage system”. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14) (pp. 383-398)
- [10]
- I. F. Blake, Essays on Coding Theory (Cambridge University Press, 2024) DOI
- [11]
- L. Golowich and V. Guruswami, “Quantum Locally Recoverable Codes”, (2023) arXiv:2311.08653
- [12]
- M. Ye and A. Barg, “Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization”, (2017) arXiv:1605.08630
- [13]
- 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
- [14]
- V. Skachek, “Batch and PIR Codes and Their Connections to Locally Repairable Codes”, Signals and Communication Technology 427 (2018) DOI
- [15]
- 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
- [16]
- A. Fazeli, A. Vardy, and E. Yaakobi, “PIR with Low Storage Overhead: Coding instead of Replication”, (2015) arXiv:1505.06241
- [17]
- V. Skachek, “Batch and PIR Codes and Their Connections to Locally Repairable Codes”, (2017) arXiv:1611.09914
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