Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields

Authors Venkatesan Guruswami, Lingfei Jin , Chaoping Xing



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.68.pdf
  • Filesize: 469 kB
  • 14 pages

Document Identifiers

Author Details

Venkatesan Guruswami
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
Lingfei Jin
  • Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai, China
  • Shanghai Institute of Intelligent Electronics & Systems, Shanghai, China
  • Shanghai Bolckchain Engineering Research Center, Fudan University, Shanghai 200433, China
Chaoping Xing
  • School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

Cite AsGet BibTex

Venkatesan Guruswami, Lingfei Jin, and Chaoping Xing. Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.68

Abstract

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 << epsilon log n and large h >=slant Omega(n^{1-epsilon}), we improve the field size from roughly n^h to n^{epsilon h}. For the case of a=1 (one local parity check), we improve the field size quadratically from r^{h(h+1)} to r^{h floor[(h+1)/2]} for some range of r. The improvements are modest, but more importantly are obtained in a unified manner via a promising new idea.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Coding theory
Keywords
  • Erasure codes
  • Algebraic constructions
  • Linear algebra
  • Locally Repairable Codes
  • Explicit constructions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Mario Blaum. Construction of PMDS and SD Codes extending RAID 5. arXiv preprint arXiv:1305.0032, 2013. URL: http://arxiv.org/abs/1305.0032.
  2. Mario Blaum, James Lee Hafner, and Steven Hetzler. Partial-MDS codes and their application to RAID type of architectures. IEEE Transactions on Information Theory, 59(7):4510-4519, 2013. Google Scholar
  3. Mario Blaum, James S Plank, Moshe Schwartz, and Eitan Yaakobi. Construction of partial MDS and sector-disk codes with two global parity symbols. IEEE Transactions on Information Theory, 62(5):2673-2681, 2016. Google Scholar
  4. Gokhan Calis and O Ozan Koyluoglu. A general construction for PMDS codes. IEEE Communications Letters, 21(3):452-455, 2017. Google Scholar
  5. Ryan Gabrys, Eitan Yaakobi, Mario Blaum, and Paul H Siegel. Constructions of partial MDS codes over small fields. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 1-5. IEEE, 2017. Google Scholar
  6. Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang, and Sergey Yekhanin. Maximally recoverable codes for grid-like topologies. In 28th Annual Symposium on Discrete Algorithms (SODA), pages 2092-2108. Society for Industrial and Applied Mathematics, 2017. Google Scholar
  7. Parikshit Gopalan, Cheng Huang, Bob Jenkins, and Sergey Yekhanin. Explicit maximally recoverable codes with locality. IEEE Transactions on Information Theory, 60(9):5245-5256, 2014. Google Scholar
  8. Parikshit Gopalan, Cheng Huang, Huseyin Simitci, and Sergey Yekhanin. On the locality of codeword symbols. IEEE Transactions on Information Theory, 58(11):6925-6934, 2012. Google Scholar
  9. Sivakanth Gopi, Venkatesan Guruswami, and Sergey Yekhanin. On maximally recoverable local reconstruction codes. arXiv preprint arXiv:1710.10322, 2017. Google Scholar
  10. Venkatesan Guruswami, Chaoping Xing, and Chen Yuan. How long can optimal locally repairable codes be? In Proceedings of RANDOM 2018, pages 41:1-41:11, 2018. Google Scholar
  11. Guangda Hu and Sergey Yekhanin. New constructions of SD and MR codes over small finite fields. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 1591-1595. IEEE, 2016. Google Scholar
  12. Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin. Erasure coding in windows azure storage. In USENIX Annual Technical Conference (ATC), pages 15-26, 2012. Google Scholar
  13. Daniel Kane, Shachar Lovett, and Sankeerth Rao. The independence number of the birkhoff polytope graph, and applications to maximally recoverable codes. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 252-259. IEEE, 2017. Google Scholar
  14. Rudolf Lidl and Harald Niederreiter. Finite fields, volume 20. Cambridge university press, 2003. Google Scholar
  15. Alessandro Neri and Anna-Lena Horlemann-Trautmann. Random Construction of Partial MDS Codes. arXiv preprint arXiv:1801.05848, 2018. Google Scholar
  16. Dimitris S Papailiopoulos and Alexandros G Dimakis. Locally repairable codes. IEEE Transactions on Information Theory, 60(10):5843-5855, 2014. Google Scholar
  17. Itzhak Tamo and Alexander Barg. A family of optimal locally recoverable codes. IEEE Transactions on Information Theory, 60(8):4661-4676, 2014. Google Scholar
  18. Itzhak Tamo, Dimitris S Papailiopoulos, and Alexandros G Dimakis. Optimal locally repairable codes and connections to matroid theory. IEEE Transactions on Information Theory, 62(12):6661-6671, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail