Achieving arbitrary locality and availability in binary codes

The ith 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 ith coordinate. This property is particularly useful for codes for distributed storage systems because it permits local repair of failed nodes and parallel access of hot data. In this paper, for any positive integers r and t, we construct a binary linear code of length equation which has locality r and availability t for all coordinates. Although it only achieves the trivial minimum distance (i.e. t + 1), its information rate attains equation, which is higher than that of the direct product code, the only known construction that can achieve arbitrary locality and availability.