Source-linked AI summary
Repair Locality with Multiple Erasure Tolerance
Anyu Wang, Zhifang Zhang
TL;DR
Distributed-storage repair locality can fail when coordinates needed for recovery are erased. The paper introduces combinatorial (r,δ)c-locality, which supplies δ−1 repair options, derives and attains a distance-related bound, and reports improved minimum distance with near-one information rate.
Problem
Ordinary locality can become ineffective after multiple node failures because a coordinate has only one repair option.
Method
The paper defines combinatorial (r,δ)c-locality with δ −1 repair options, derives a codeword-length lower bound, and constructs codes attaining it.
Results
Under the same locality and repair tolerance, (r,δ)c-locality improves minimum distance over locality (r,δ), with a constructed class gaining Ω(√r) and having information rate close to 1.
Takeaways & Limitations
The proposed locality provides multiple-erasure repair tolerance while supporting shorter codewords or larger minimum distance than the compared locality definition.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper addresses the failure of ordinary repair locality under multiple node failures by introducing a code example with multiple repair options and comparing it with related approaches.
- Erasure codes can reduce storage overhead and improve reliability, but traditional codes incur high repair bandwidth and disk-access costs.
- A locality-r code repairs a coordinate by accessing at most r other coordinates, reducing repair disk I/O when r is much smaller than k.
- Multiple failures can disable ordinary local repair because each coordinate has only one repair option; the locality r therefore tolerates only one node failure.
- The binary [7, 3, 4] example has repair locality r = 2, and its repair locality can tolerate up to three erasures.
- Compared with a minimum-bandwidth regenerating code, the example offers lower storage overhead, lower repair locality, and one additional tolerated erasure.
- The example combines binary coding, low repair locality, high local repair tolerance, and shorter codeword length, motivating a new repair-locality definition.
A. Our Results
The paper defines combinatorial (r,δ)c-locality, derives a distance-related bound, and establishes its tightness and advantage over the locality (r,δ) definition.
- The (r,δ)c-locality provides δ −1 repair options, so a coordinate remains locally repairable with at most r other nodes under up to δ −1 total erasures.
- The authors prove a lower bound on codeword length, equivalently an upper bound on minimum distance, for information symbols with (r,δ)c-locality.
- Codes with information (r,δ)c-locality attain the bound for general r, δ, k when n ≥ k(r(δ −1) + 1), establishing general tightness.
- Under the same locality and repair tolerance, (r,δ)c-locality outperforms locality (r,δ) in minimum distance; a constructed class gains Ω(√r) with information rate close to 1.
B. Related Works
The related work includes multiple-erasure local repair, regenerating codes optimized for bandwidth and uncoded repair, and high-tolerance constructions with specialized geometric requirements.
- Existing erasure codes also study tolerating multiple erasures during local repair.
- The locality (r,δ) approach uses inner error-correcting codes, whereas (r,δ)c-locality is combinatorial and improves codeword length and minimum distance.
- The minimum-bandwidth regenerating-code approach emphasizes minimum bandwidth and uncoded repair rather than repair locality.
- High-tolerance pg-BLRC codes provide an information-rate region, but their high-rate constructions depend on generalized quadrangles, of which few instances are known.
C. Organization
The paper defines and bounds the proposed locality, proves general attainability, compares it with locality (r,δ), constructs codes, and concludes with refined bounds.
- Section II defines (r,δ)c-locality and proves a lower bound on codeword length.
- Section III shows that the lower bound can be attained for general parameters and compares it with locality (r,δ).
- Section IV presents code constructions with (r,δ)c-locality, while Section V concludes the paper.
II. DEFINITION AND LOWER BOUND
The paper defines (r,δ)c-locality through multiple disjoint repair sets, giving each information symbol δ−1 repair options and tolerance of δ−1 erasures. It then derives a lower bound on code length, equivalently an upper bound on minimum distance, and identifies optimal codes attaining it.
- Definition: (r,δ)c-locality gives each coordinate δ−1 pairwise disjoint repair sets, each supporting repair from at most r other coordinates.The construction is designed so that any one repair option remains available when up to δ−1 total erasures occur.
- Definition: The locality parameter is defined so the failed node can be repaired by accessing at most r other nodes despite up to δ−1 total erasures.The paper considers r,δ ≥ 2; r = 1 gives repetition and δ = 1 gives no locality.
- Lower bound: Theorem 1 provides a lower bound on codeword length for information (r,δ)c-locality, equivalently an upper bound on minimum distance.The proof constructs a set of at least k−1+µ coordinates having rank below k, where µ = ⌈((k−1)(δ−1)+1)/((r−1)(δ−1)+1)⌉−1.
- Lower-bound proof: The lower-bound proof builds sets S_h by adding repair neighborhoods while tracking their size and rank until the rank reaches k−1.It analyzes separately whether the terminating set is produced before or after the final repair neighborhood is added.
- Optimality: A code is optimal when its codeword length meets the lower bound with equality, and the paper states that Example 1 is optimal in this sense.The paper introduces optimality to identify codes attaining the derived bound.
III. TIGHTNESS OF THE BOUND
The paper constructs optimal codes meeting the (r,δ)c-locality bound for general parameters and sufficiently large fields. Compared with Prakash et al.’s locality, the construction offers better minimum distance, including an Ω(√r) gain for a high-rate class.
- Base construction: At length n = k(r(δ−1)+1), the constructed generator matrix satisfies the locality and rank conditions, so the code attains the bound with equality.The rank condition implies the required minimum-distance lower bound, while Theorem 1 supplies the matching upper bound.
- Base construction: The construction represents coordinates as points grouped into sets of r+1 points whose vectors are linearly dependent.The point-set representation supplies the local dependencies used to establish information-symbol locality.
- Existence of optimal codes: For n ≥ k(r(δ−1)+1) and sufficiently large q, an optimal [n,k,d]q linear code with information (r,δ)c-locality exists.The construction can be extended by adding independent parity columns while preserving the required conditions.
- Comparison: Optimal codes with (r,δ)c-locality have preferable minimum distance to codes with Prakash et al.’s locality (r,δ) under the same locality and repair tolerance.The paper compares the two definitions through their respective minimum-distance bounds.
- Comparison: Ω(√r) is the minimum-distance gain for a constructed all-symbol (r,δ)c-locality class whose information rate is close to 1.This is the paper’s highlighted advantage over locality (r,δ) for a specific high-rate code class.
IV. CONSTRUCTION OF CODES WITH (r, δ)c-LOCALITY
The paper constructs codes with all-symbol (r,δ)c-locality, including square codes based on grid-structured vectors. These constructions achieve the theoretical bound in some parameter ranges and improve minimum distance over locality (r,δ), while maintaining high information rate.
- The constructions establish that the bound for information (r,δ)c-locality also applies to all-symbol locality.
- Square code construction: The square code uses an (r+1)×(r+1) grid whose rows and columns each provide local repair sets of size r.Each grid point represents a coordinate, and the r+1 vectors in every row or column sum to zero.
- Distance performance: For r+1 ≤ k ≤ 2r−1, the square code is optimal with respect to bound (2).
- Distance performance: At r = 5 and n = 36, the square code is compared with bounds (1) and (2), and it can outperform bound (1) even when it does not attain bound (2).The comparison is presented through three curves for the corresponding (k,d) pairs.
- Distance performance: The minimum-distance gap between the square code and bound (1) can be Ω(√r).For n = (r+1)^2, k = r^2−r+1, and δ = 3, the stated construction realizes this asymptotic gap.
- Rate: For k = r^2−r+1, the square code has information rate approaching 1 as r grows.
V. CONCLUSIONS
The paper defines (r,δ)c-locality combinatorially to guarantee δ−1 erasure tolerance, derives a codeword-length bound, and proves general-parameter attainability. Its all-symbol constructions include square codes with information rate approaching 1 and near-optimality, while a refined bound is left for future work.
- (r,δ)c-locality guarantees δ−1 erasure tolerance for local repair through a combinatorial construction.
- The paper derives a lower bound on codeword length and proves that codes with information (r,δ)c-locality attain it for general parameters.
- All-symbol constructions include square codes with information rate approaching 1 and near-optimality relative to the bound.
- A refined codeword-length bound based on the structure of repair sets is identified, with details deferred to another paper.
APPENDIX
The appendix constructs generator matrices using free sets and polynomial evaluation, then establishes rank conditions that yield codes meeting the distance bound.
- The construction defines variable-based generator matrices satisfying the first locality condition and seeks evaluations also satisfying rank conditions.
- A free set F is one whose associated submatrix can range over any k × |F| matrix over Fq.
- For subsets M of size k + µ, deleting selected points produces a free subset containing k points, enabling a rank-k submatrix.
- Schwartz-Zippel evaluation gives a generator matrix whose code has minimum distance at least n − k + 1 − µk.
- For grid subsets T of size k + µk, deleting one point from each relevant column yields a free set T′ with at least k points.
- The resulting evaluation gives a code with minimum distance at least n − k + 1 − µk, and the construction extends to n ≥ k(r(δ − 1) + 1).