IEEE Transactions on Information Theory · 2014 · 198 citations · 20 references
ComputingComputer EngineeringComputer ScienceFault ToleranceFault-tolerant ComputingFault-tolerant SystemsCoding TheoryData RedundancyErasure CodingError Control CodingError-correcting CodesFault-tolerant Storage SystemsBounds On CodesDistributed Storage CodesErasure CorrectionI/o ComplexityLocally Repairable CodesMinimum DistanceMinimum Distance BoundsRegenerating Codes
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, δ) <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sub> -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, δ) <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sub> -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, δ) <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sub> -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, δ) <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sub> -locality where the gain in minimum distance is Q(√r) and the information rate is close to 1.
20
Network Coding for Distributed Storage Systems
Alexandros G. Dimakis, P. Brighten Godfrey, Yunnan Wu et al. · IEEE Transactions on Information Theory · 2010 · 2K citations
On the Locality of Codeword Symbols
Parikshit Gopalan, Cheng Huang, Huseyin Simitci et al. · IEEE Transactions on Information Theory · 2012 · 862 citations
Optimal linear codes with a local-error-correction property
N. Prakash, Govinda M. Kamath, V. Lalitha et al. · 2012 · 302 citations