Title :
Repair Locality With Multiple Erasure Tolerance
Author :
Anyu Wang ; Zhifang Zhang
Author_Institution :
Key Lab. of Math. Mechanization, AMSS, Beijing, China
Abstract :
In distributed storage systems, erasure codes with locality r are preferred because a coordinate can be locally repaired 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 not be performed when some of the r coordinates are also erased. To overcome this problem, we propose the (r, δ)c-locality providing δ-1 nonoverlapping local repair groups of size no more than r for a coordinate. Consequently, the repair locality r can tolerate δ -1 erasures in total. We derive an upper bound on the minimum distance for any linear [n, k] code with information (r, δ)c-locality. Then, we prove existence of the codes that attain this bound when n ≥ k(r(δ - 1) + 1). 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 attaining the bound 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 Q(√r) and the information rate is close to 1.
Keywords :
error correction codes; linear codes; δ-1 nonoverlapping local repair groups; disk I/O complexity; distributed storage systems; erasure codes; information (r, δ)c-locality; information rate; linear code; local repair tolerance; minimum distance; multiple erasure tolerance; upper bound; Complexity theory; Generators; Information rates; Linear codes; Maintenance engineering; Measurement; Vectors; Distributed storage; erasure codes; hot data; repair locality;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2014.2351404