Constructions of maximally recoverable Local Reconstruction Codes via function fields
Local Reconstruction Codes (LRCs) allow for recovery from a small number of erasures in a local manner based on just a few other codeword symbols. They have emerged as the codes of choice for large scale distributed storage systems due to the very efficient repair of failed storage nodes in the typi...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/142955 |
| _version_ | 1811695164921479168 |
|---|---|
| author | Guruswami, Venkatesan Jin, Lingfei Xing, Chaoping |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Guruswami, Venkatesan Jin, Lingfei Xing, Chaoping |
| author_sort | Guruswami, Venkatesan |
| collection | NTU |
| description | Local Reconstruction Codes (LRCs) allow for recovery from a small number of erasures in a local manner based on just a few other codeword symbols. They have emerged as the codes of choice for large scale distributed storage systems due to the very efficient repair of failed storage nodes in the typical scenario of a single or few nodes failing, while also offering fault tolerance against worst-case scenarios with more erasures. A maximally recoverable (MR) LRC offers the best possible blend of such local and global fault tolerance, guaranteeing recovery from all erasure patterns which are information-theoretically correctable given the presence of local recovery groups. In an (n, r, h, a)-LRC, the n codeword symbols are partitioned into r disjoint groups each of which include a local parity checks capable of locally correcting a erasures. The codeword symbols further obey h heavy (global) parity checks. Such a code is maximally recoverable if it can correct all patterns of a erasures per local group plus up to h additional erasures anywhere in the codeword. This property amounts to linear independence of all such subsets of columns of the parity check matrix. MR LRCs have received much attention recently, with many explicit constructions covering different regimes of parameters. Unfortunately, all known constructions require a large field size that is exponential in h or a, and it is of interest to obtain MR LRCs of minimal possible field size. In this work, we develop an approach based on function fields to construct MR LRCs. Our method recovers, and in most parameter regimes improves, the field size of previous approaches. For instance, for the case of small r ε log n and large h > Ω(n1−ε), we improve the field size from roughly nh to nεh. For the case of a = 1 (one local parity check), we improve the field size quadratically from rh(h+1) to rhb(h+1)/2c for some range of r. The improvements are modest, but more importantly are obtained in a unified manner via a promising new idea. |
| first_indexed | 2024-10-01T07:19:07Z |
| format | Journal Article |
| id | ntu-10356/142955 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:19:07Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-10356/1429552023-02-28T19:53:47Z Constructions of maximally recoverable Local Reconstruction Codes via function fields Guruswami, Venkatesan Jin, Lingfei Xing, Chaoping School of Physical and Mathematical Sciences Science::Physics Erasure Codes Algebraic Constructions Local Reconstruction Codes (LRCs) allow for recovery from a small number of erasures in a local manner based on just a few other codeword symbols. They have emerged as the codes of choice for large scale distributed storage systems due to the very efficient repair of failed storage nodes in the typical scenario of a single or few nodes failing, while also offering fault tolerance against worst-case scenarios with more erasures. A maximally recoverable (MR) LRC offers the best possible blend of such local and global fault tolerance, guaranteeing recovery from all erasure patterns which are information-theoretically correctable given the presence of local recovery groups. In an (n, r, h, a)-LRC, the n codeword symbols are partitioned into r disjoint groups each of which include a local parity checks capable of locally correcting a erasures. The codeword symbols further obey h heavy (global) parity checks. Such a code is maximally recoverable if it can correct all patterns of a erasures per local group plus up to h additional erasures anywhere in the codeword. This property amounts to linear independence of all such subsets of columns of the parity check matrix. MR LRCs have received much attention recently, with many explicit constructions covering different regimes of parameters. Unfortunately, all known constructions require a large field size that is exponential in h or a, and it is of interest to obtain MR LRCs of minimal possible field size. In this work, we develop an approach based on function fields to construct MR LRCs. Our method recovers, and in most parameter regimes improves, the field size of previous approaches. For instance, for the case of small r ε log n and large h > Ω(n1−ε), we improve the field size from roughly nh to nεh. For the case of a = 1 (one local parity check), we improve the field size quadratically from rh(h+1) to rhb(h+1)/2c for some range of r. The improvements are modest, but more importantly are obtained in a unified manner via a promising new idea. NRF (Natl Research Foundation, S’pore) MOE (Min. of Education, S’pore) Published version 2020-07-15T07:33:59Z 2020-07-15T07:33:59Z 2019 Journal Article Guruswami, V., Jin, L., & Xing, C. (2019). Constructions of maximally recoverable Local Reconstruction Codes via function fields. Leibniz International Proceedings in Informatics, 132, 68:1-68:14. doi:10.4230/LIPIcs.ICALP.2019.68 9783959771092 1868-8969 https://hdl.handle.net/10356/142955 10.4230/LIPIcs.ICALP.2019.68 2-s2.0-85069212129 132 68:1 68:14 en Leibniz International Proceedings in Informatics © 2019 Graham Cormode, Jacques Dark, and Christian Konrad; licensed under Creative Commons License CC-BY. application/pdf |
| spellingShingle | Science::Physics Erasure Codes Algebraic Constructions Guruswami, Venkatesan Jin, Lingfei Xing, Chaoping Constructions of maximally recoverable Local Reconstruction Codes via function fields |
| title | Constructions of maximally recoverable Local Reconstruction Codes via function fields |
| title_full | Constructions of maximally recoverable Local Reconstruction Codes via function fields |
| title_fullStr | Constructions of maximally recoverable Local Reconstruction Codes via function fields |
| title_full_unstemmed | Constructions of maximally recoverable Local Reconstruction Codes via function fields |
| title_short | Constructions of maximally recoverable Local Reconstruction Codes via function fields |
| title_sort | constructions of maximally recoverable local reconstruction codes via function fields |
| topic | Science::Physics Erasure Codes Algebraic Constructions |
| url | https://hdl.handle.net/10356/142955 |
| work_keys_str_mv | AT guruswamivenkatesan constructionsofmaximallyrecoverablelocalreconstructioncodesviafunctionfields AT jinlingfei constructionsofmaximallyrecoverablelocalreconstructioncodesviafunctionfields AT xingchaoping constructionsofmaximallyrecoverablelocalreconstructioncodesviafunctionfields |