22 August 2014 in IEEE Transactions on Information Theory
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.
25 January 2019 in IEEE Transactions on Information Theory
For locally repairable codes (LRCs), V. Cadambe and A. Mazumdar derived the first field-dependent parameter bound, known as the C-M bound. However, the C-M bound depends on an undetermined parameter k(q) opt(n; d). In this paper, a sphere-packing approach is developed for upper bounding the parameter k for [n; k; d] linear LRCs with locality r. When restricted to the binary field, three upper bounds (i.e., Bound A, Bound B, and Bound C) are derived in explicit form. More specifically, Bound A holds under the hypothesis that the local repair groups are disjoint and of equal size. Comparing with previous bounds obtained under the same hypothesis, Bound A either covers them as special cases or has an advantage due to its explicit form. Then the hypothesis is removed in Bound B and Bound C. As the price for explicit form, Bound B specially holds for d ≥ 5 and Bound C for r = 2. Through specific comparisons we show that Bound B and Bound C both tend to outperform the C-M bound as n goes large. Moreover, a family of binary linear LRCs with d ≥ 6 attaining Bound B is constructed and later extended to a wider range of parameters by a shortening technique. Lastly, most of the bounds and constructions are extended to q-ary LRCs.