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 (1)

• Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction

Cited by in corpus (10)

• Optimal Binary Locally Repairable Codes via Anticodes
• Achieving Arbitrary Locality and Availability in Binary Codes
• Optimal binary linear locally repairable codes with disjoint repair groups
• Codes With Hierarchical Locality
• Constructions of Optimal Cyclic $(r,\delta )$ Locally Repairable Codes
• Bounds and Constructions for Linear Locally Repairable Codes over Binary Fields
• Optimal Locally Repairable Codes with Improved Update Complexity
• Introduction of Improved Repairing Locality into Secret Sharing Schemes with Perfect Security
• On the Average Locality of Locally Repairable Codes
• Multi-Erasure Locally Recoverable Codes Over Small Fields For Flash Memory Array