Repair Locality with Multiple Erasure Tolerance

Abstract

In distributed storage systems, erasure codes with locality $r$ is preferred because a coordinate can be recovered by accessing at most $r$ other coordinates which in turn greatly reduces the disk I/O complexity for small $r$. However, the local repair may be ineffective when some of the $r$ coordinates accessed for recovery are also erased. To overcome this problem, we propose the $(r,\delta {)}_c$-locality providing $\delta -1$ local repair options for a coordinate. Consequently, the repair locality $r$ can tolerate $\delta -1$ erasures in total. We derive an upper bound on the minimum distance $d$ for any linear $[n,k]$ code with information $(r,\delta {)}_c$-locality. For general parameters, we prove existence of the codes that attain this bound when $n\ge k(r(\delta -1)+1)$, implying tightness of this bound. Although the locality $(r,\delta )$ defined by Prakash et al provides the same level of locality and local repair tolerance as our definition, codes with $(r,\delta {)}_c$-locality are proved to have more advantage in the minimum distance. In particular, we construct a class of codes with all symbol $(r,\delta {)}_c$-locality where the gain in minimum distance is $\Omega (\sqrt{r})$ and the information rate is close to 1.

14 pages

References in corpus (3)

• Optimal Locally Repairable and Secure Codes for Distributed Storage Systems
• Locally Repairable Codes with Multiple Repair Alternatives
• Repair Locality From a Combinatorial Perspective

Cited by in corpus (38)

• Cooperative Local Repair in Distributed Storage
• Combinatorial Alphabet-Dependent Bounds for Locally Recoverable Codes
• Locally Repairable Codes with Functional Repair and Multiple Erasure Tolerance
• Bounds and Constructions of Locally Repairable Codes: Parity-check Matrix Approach
• Binary Codes with Locality for Multiple Erasures Having Short Block Length
• Alphabet-Dependent Bounds for Linear Locally Repairable Codes Based on Residual Codes
• Some Improvements on Locally Repairable Codes
• Achieving Arbitrary Locality and Availability in Binary Codes
• A Construction of Maximally Recoverable Codes with Order-Optimal Field Size
• Optimal binary linear locally repairable codes with disjoint repair groups
• Binary Linear Locally Repairable Codes
• PMDS Array Codes With Small Sub-packetization, Small Repair Bandwidth/Rebuilding Access
• Codes With Hierarchical Locality
• Binary Codes with Locality for Four Erasures
• Locally recoverable $J$-affine variety codes
• Latency optimal storage and scheduling of replicated fragments for memory-constrained servers
• Erasure Coding for Distributed Storage: An Overview
• Binary Locally Repairable Codes ---Sequential Repair for Multiple Erasures
• Irregular Recovery and Unequal Locality for Locally Recoverable Codes with Availability
• Constructions of Optimal Cyclic $(r,\delta )$ Locally Repairable Codes
• Bounds on Codes with Locality and Availability
• Bounds on the Parameters of Locally Recoverable Codes
• On Sequential Locally Repairable Codes
• A Study on the Impact of Locality in the Decoding of Binary Cyclic Codes
• New Constructions of Optimal Locally Repairable Codes with Super-Linear Length
• A Tight Rate Bound and Matching Construction for Locally Recoverable Codes with Sequential Recovery From Any Number of Multiple Erasures
• On Optimal Locally Repairable Codes with Super-Linear Length
• Erasure codes with symbol locality and group decodability for distributed storage
• Integrated Interleaved Codes as Locally Recoverable Codes: Properties and Performance
• Optimal Locally Repairable Systematic Codes Based on Packings
• On Finding the Largest Minimum Distance of Locally Recoverable Codes
• New Bounds on the Field Size for Maximally Recoverable Codes Instantiating Grid-like Topologies
• Mathematical LoRE: Local Recovery of Erasures using Polynomials, Curves, Surfaces, and Liftings
• Applications of Polymatroid Theory to Distributed Storage Systems
• On Optimal Locally Repairable Codes and Generalized Sector-Disk Codes
• Cyclic and convolutional codes with locality
• Locally recoverable codes from automorphism groups of function fields of genus $g\ge 1$
• Erasure Codes for Distributed Storage: Tight Bounds and Matching Constructions