Achieving Arbitrary Locality And Availability In Binary Codes

Wang Anyu, Zhang Zhifang. Arxiv 2015

[Paper]    
ARXIV

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 $(\genfrac{}{}{0ex}{}{r+t}{t})$ 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.

Similar Work

• Thscalable Distributed Trie Hashing
• Hashencoding Autoencoding With Multiscale Coordinate Hashing
• Distributed Stratified Locality Sensitive Hashing For Critical Event Prediction In The Cloud
• Approximate Nearest Neighbors In Limited Space