Binary Cyclic Codes that are Locally Repairable

Abstract

Codes for storage systems aim to minimize the repair locality, which is the number of disks (or nodes) that participate in the repair of a single failed disk. Simultaneously, the code must sustain a high rate, operate on a small finite field to be practically significant and be tolerant to a large number of erasures. To this end, we construct new families of binary linear codes that have an optimal dimension (rate) for a given minimum distance and locality. Specifically, we construct cyclic codes that are locally repairable for locality 2 and distances 2, 6 and 10. In doing so, we discover new upper bounds on the code dimension, and prove the optimality of enabling local repair by provisioning disjoint groups of disks. Finally, we extend our construction to build codes that have multiple repair sets for each disk.

This 5 page paper appeared in the proceedings of the IEEE International Symposium on Information Theory (ISIT), 2014

References in corpus (4)

• A family of optimal locally recoverable codes
• Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction
• Locally Repairable Codes with Multiple Repair Alternatives
• An Upper Bound On the Size of Locally Recoverable Codes

Cited by in corpus (29)

• Cyclic LRC Codes, binary LRC codes, and upper bounds on the distance of cyclic codes
• Optimal Linear and Cyclic Locally Repairable Codes over Small Fields
• Constructions and Properties of Linear Locally Repairable Codes
• Bounds and Constructions of Locally Repairable Codes: Parity-check Matrix Approach
• Locally Repairable Codes with Unequal Local Erasure Correction
• Optimal Binary Locally Repairable Codes via Anticodes
• Alphabet-Dependent Bounds for Linear Locally Repairable Codes Based on Residual Codes
• Achieving Arbitrary Locality and Availability in Binary Codes
• Optimal binary linear locally repairable codes with disjoint repair groups
• Binary Linear Locally Repairable Codes
• Codes With Hierarchical Locality
• On minimum distance of locally repairable codes
• Erasure Coding for Distributed Storage: An Overview
• Locally recoverable $J$-affine variety codes
• Optimal $(r,\delta )$-LRCs from monomial-Cartesian codes and their subfield-subcodes
• Locally rewritable codes for resistive memories
• Constructions of Optimal Cyclic $(r,\delta )$ Locally Repairable Codes
• Bounds and Constructions for Linear Locally Repairable Codes over Binary Fields
• Long Optimal or Small-Defect LRC Codes with Unbounded Minimum Distances
• Optimal Locally Repairable Codes with Improved Update Complexity
• On the Average Locality of Locally Repairable Codes
• New Bounds on the Field Size for Maximally Recoverable Codes Instantiating Grid-like Topologies
• Introduction of Improved Repairing Locality into Secret Sharing Schemes with Perfect Security
• Three New Infinite Families of Optimal Locally Repairable Codes from Matrix-Product Codes
• New Constructions of Optimal Cyclic (r,δ) Locally Repairable Codes from Their Zeros
• Erasure Codes for Distributed Storage: Tight Bounds and Matching Constructions
• Codes with Unequal Disjoint Local Erasure Correction Constraints
• Locality and Availability of Array Codes Constructed from Subspaces
• Multi-Erasure Locally Recoverable Codes Over Small Fields For Flash Memory Array