IEEE Transactions on Information Theory · 2015 · 70 citations · 21 references
ComputingComputer ScienceMathematicsAlgorithmsFault ToleranceFault-tolerant ComputingApproximation AlgorithmsCoding TheoryError Control CodingError-correcting CodesInteger ProgrammingLinear ProgrammingBounds On CodesInteger Programming ModelsInteger Programming RelaxationsLinear CodesLocally Repairable CodesMinimum DistanceMinimum Distance BoundsUpper Bound Computation
The locally repairable code (LRC) studied in this paper is an [n, k] linear code of which the value at each coordinate can be recovered by a linear combination of at most r other coordinates. The central problem in this paper is to determine the largest possible minimum distance for LRCs. First, an integer programming-based upper bound is derived for any LRC. Then, by solving the programming problem under certain conditions, an explicit upper bound is obtained for LRCs with parameters n <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> > n <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> , where n <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> = ⌈(n/r + 1)⌉ and n2 = n <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> (r +1)-n. Finally, an explicit construction for LRCs attaining this upper bound is presented over the finite field F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sub> ,where m ≥ n <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> r. Based on these r ≤ √n - 1 has been definitely determined, which is of great results, the largest possible minimum distance for all LRCs with significance in practical use.
21
On the Locality of Codeword Symbols
Parikshit Gopalan, Cheng Huang, Huseyin Simitci et al. · IEEE Transactions on Information Theory · 2012 · 862 citations
Erasure coding in windows azure storage
Cheng Huang, Huseyin Simitci, Yikang Xu et al. · 2012 · 806 citations
Maheswaran Sathiamoorthy, Megasthenis Asteris, Dimitris Papailiopoulos et al. · Proceedings of the VLDB Endowment · 2013 · 689 citations