Paper detail

Repair Locality with Multiple Erasure Tolerance

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,δ)_c$-locality providing $δ-1$ local repair options for a coordinate. Consequently, the repair locality $r$ can tolerate $δ-1$ erasures in total. We derive an upper bound on the minimum distance $d$ for any linear $[n,k]$ code with information $(r,δ)_c$-locality. For general parameters, we prove existence of the codes that attain this bound when $n\geq k(r(δ-1)+1)$, implying tightness of this bound. Although the locality $(r,δ)$ defined by Prakash et al provides the same level of locality and local repair tolerance as our definition, codes with $(r,δ)_c$-locality are proved to have more advantage in the minimum distance. In particular, we construct a class of codes with all symbol $(r,δ)_c$-locality where the gain in minimum distance is $Ω(\sqrt{r})$ and the information rate is close to 1.