Achieving Arbitrary Locality and Availability in Binary Codes

Abstract

The $i$th coordinate of an $(n,k)$ code is said to have locality $r$ and availability $t$ if there exist $t$ disjoint groups, each containing at most $r$ other coordinates that can together recover the value of the $i$th coordinate. This property is particularly useful for codes for distributed storage systems because it permits local repair and parallel accesses of hot data. In this paper, for any positive integers $r$ and $t$, we construct a binary linear code of length $\left(\genfrac{}{}{0ex}{}{r+t}{t}\right)$ which has locality $r$ and availability $t$ for all coordinates. The information rate of this code attains $\frac{r}{r+t}$, which is always higher than that of the direct product code, the only known construction that can achieve arbitrary locality and availability.

5 pages

References in corpus (5)

• A family of optimal locally recoverable codes
• Repair Locality with Multiple Erasure Tolerance
• Binary Cyclic Codes that are Locally Repairable
• XORing Elephants: Novel Erasure Codes for Big Data
• On the Locality of Codeword Symbols in Non-Linear Codes

Cited by in corpus (5)

• Bounds and Constructions of Locally Repairable Codes: Parity-check Matrix Approach
• Constructions of Optimal Cyclic $(r,\delta )$ Locally Repairable Codes
• Bounds on the Parameters of Locally Recoverable Codes
• Explicit Constructions and Bounds for Batch Codes with Restricted Size of Reconstruction Sets
• Applications of Polymatroid Theory to Distributed Storage Systems