PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Locally Repairable Linear Codes

Wentu Song, Son Hoang Dau, Chau Yuen, Tiffany Jing Li

arXiv:1307.1961v1cs.ITmath.IT

TL;DR

MDS erasure codes can make repair costly because recovery may require accessing k fragments. This paper studies optimal all-symbol locally repairable codes through structural results and parameter-specific existence proofs and deterministic constructions. It reports that only two small parameter subcases remain unresolved.

  • Problem

    MDS repair generally requires accessing k encoded fragments, creating considerable I/O bandwidth, while simple MDS codes are difficult to construct.

    Source: §I · p. 1

  • Method

    The paper derives structural properties and analyzes parameter cases to prove nonexistence or provide deterministic constructions for optimal all-symbol locally repairable codes.

    Source: B. Main Results · p. 2, §VII · p. 14

  • Results

    The authors identify two parameter sets with no optimal codes and four with existence and construction results, with smaller field-size requirements than prior work in some previously studied cases.

    Source: §VII · p. 14

  • Takeaways & Limitations

    For some cases already covered by prior existence results, the new constructions require considerably smaller fields.

    Source: §VII · p. 14

    Existence remains unknown for two small parameter subcases.

    Source: §VII · p. 14

Abstract

from arXiv · show

Linear erasure codes with local repairability are desirable for distributed data storage systems. An [n, k, d] code having all-symbol (r, \delta})-locality, denoted as (r, {\delta})a, is considered optimal if it also meets the minimum Hamming distance bound. The existing results on the existence and the construction of optimal (r, {\delta})a codes are limited to only the special case of {\delta} = 2, and to only two small regions within this special case, namely, m = 0 or m >= (v+{\delta}-1) > ({\delta}-1), where m = n mod (r+{\delta}-1) and v = k mod r. This paper investigates the existence conditions and presents deterministic constructive algorithms for optimal (r, {\delta})a codes with general r and {\delta}. First, a structure theorem is derived for general optimal (r, {\delta})a codes which helps illuminate some of their structure properties. Next, the entire problem space with arbitrary n, k, r and {\delta} is divided into eight different cases (regions) with regard to the specific relations of these parameters. For two cases, it is rigorously proved that no optimal (r, {\delta})a could exist. For four other cases the optimal (r, {\delta})a codes are shown to exist, deterministic constructions are proposed and the lower bound on the required field size for these algorithms to work is provided. Our new constructive algorithms not only cover more cases, but for the same cases where previous algorithms exist, the new constructions require a considerably smaller field, which translates to potentially lower computational complexity. Our findings substantially enriches the knowledge on (r, {\delta})a codes, leaving only two cases in which the existence of optimal codes are yet to be determined.

I. INTRODUCTION

Distributed storage needs redundancy because individual nodes can fail, but conventional erasure-code repair can require substantial data access. Locally repairable codes reduce repair access by recovering failed symbols from nearby nodes, including under multiple erasures.

I. INTRODUCTION

  • Distributed storage uses redundancy to protect files because individual storage devices are unreliable and may fail.Replication is simple but wastes storage space; erasure coding can improve storage efficiency.Source: §I · p. 1
  • MDS codes provide recovery from any k encoded fragments, but repair generally requires accessing k fragments and creates considerable I/O bandwidth.Simple MDS codes are also difficult to construct.Source: §I · p. 1
  • Symbol locality allows a code symbol to be recovered by accessing at most r other symbols; (r, δ) locality extends this to multiple failures.For (r, δ) locality, a symbol can be deduced by reading at most r other unerased symbols when at most δ−1 symbols are erased.Source: §I · p. 2
  • Locally repairable codes can reduce repair access: in the (2, 3)a example, two nodes repair a failure, compared with five for a [12, 5] MDS code.The example groups nodes so repair can use nodes in the same group.Source: Figure 1 · p. 1, §I · p. 2

A. Related Work

Prior work established distance bounds and constructions for locally repairable codes, but optimal all-symbol codes remained unresolved for most parameter choices. The paper situates its study within these bounds and open construction questions.

A. Related Work

  • The (r, δ) information-locality distance bound also applies to all-symbol codes, since every (r, δ)a code is an (r, δ)i code.Pyramid codes were shown to achieve the cited bound.Source: A. Related Work · p. 2
  • Codes attaining the minimum-distance bound are called optimal; the bound literature also includes results for general linear and nonlinear codes.Source: A. Related Work · p. 2
  • For lengths divisible by r + δ − 1, prior work established existence results; for δ = 2, explicit constructions covered particular parameter regimes.The cited prior results include linear and vector-code constructions.Source: A. Related Work · p. 2
  • Optimal LRC construction remained open for most n, k, r, and δ, alongside the question of designing such codes over smaller fields.Some existence and construction results were known for divisible lengths and for special δ = 2 cases.Source: A. Related Work · p. 2

B. Main Results

The paper characterizes structure and existence for optimal all-symbol (r, δ)a linear codes, and gives deterministic constructions in several parameter regions. The remaining undetermined cases are limited to regions (I.8) and (I.9).

Structure theorem

  • When r|k and r<k, every optimal code has disjoint repair sets of size r+δ−1, each puncturing an [r+δ−1, r, δ] MDS code.In particular, r+δ−1 divides n.Source: B. Main Results · p. 2

Nonexistence

  • The authors prove that no optimal (r, δ)a linear codes exist under the conditions m < v + δ − 1 and u ≥ 2(r − v) + 1.Source: B. Main Results · p. 2

Constructions

  • The authors propose a deterministic algorithm for constructing optimal (r, δ)a linear codes, with n = w(r + δ − 1) + m and k = ur + v, where 0 < v < r and 0 < m < r + δ − 1.Source: B. Main Results · p. 2
  • A further deterministic algorithm constructs optimal (r, δ)a linear codes for n = w(r + δ − 1) + m and k = ur + v (Theorems 15 and 16), with condition (I.7) requiring w + 1 ≥ 2(r + δ − 1 − m) and min{2(r − v), w} ≥ u.Source: B. Main Results · p. 3

Open cases

  • If none of conditions (I.2)–(I.7) applies, only parameter regions (I.8) and (I.9) remain with existence undetermined.The text identifies these as the limited scope still unresolved by the existence proofs and constructions.Source: B. Main Results · p. 3

II. LOCALITY OF LINEAR CODES

The section defines all-symbol locality through small coordinate sets whose punctured codes permit local recovery, then records useful consequences and notation for analyzing such codes.

Notation

  • The notation C|S denotes puncturing to coordinates in S, while [t1, t2] denotes the inclusive integer interval and [t2] denotes {1, …, t2}.An r-subset is a subset of size r.Source: §II · p. 3

Locality definition

  • A symbol has locality (r, δ) when it belongs to a coordinate set of size at most r + δ −1 whose punctured code has the required minimum distance.The rank formulation in Remark 3 gives an equivalent characterization using columns of a generating matrix.Source: §II · pp. 3–4

Local repair

  • For any symbol in a locality set, any |S_i| −δ + 1 other symbols in that set suffice to reconstruct it.This follows from the rank condition for the corresponding generating-matrix columns.Source: §II · p. 4

Locality and optimality

  • An (r, δ)a code is optimal when its minimum distance achieves the stated bound, and every such code has minimum distance at least δ.The latter follows because every nonzero codeword has at least δ nonzero symbols in a covering locality set.Source: §II · p. 4

Cover sets

  • An (r, δ)-cover set consists of sets S_i covering all coordinates, each with size at most r + δ −1 and the specified rank property.The cover is minimal in the sense that removing any one set no longer covers all coordinates.Source: §II · p. 4

III. STRUCTURE OF OPTIMAL (r, δ)a CODE WHEN r|k

Under r|k, the section proves a strong structural theorem for optimal all-symbol codes: their repair sets partition the coordinates into full-size sets whose puncturings are MDS codes.

Structure theorem

  • If r|k and r<k, the repair sets are mutually disjoint, each has size r + δ −1, and each punctured code is an [r + δ −1, r, δ] MDS code.Consequently, r + δ −1 divides n.Source: §III · p. 6

Comparison with information locality

  • The theorem's structure is simpler than that of general optimal (r, δ)i codes, for which only a suitably selected collection of sets has the same properties.The comparison is stated for optimal (r, δ)i codes in.Source: §III · p. 6

IV. NON-EXISTENCE CONDITIONS OF OPTIMAL (r, δ)a LINEAR CODES

The section establishes two parameter regions where optimal (r, δ)a linear codes cannot exist: one with r|k and nondivisible n, and another with a small remainder m and sufficiently large u.

Theorem 10

  • No optimal codes exist when (r + δ −1) ∤n and r|k.Source: §IV · p. 6

Theorem 11

  • No optimal codes exist when 0 < m < v + δ −1 and u ≥2(r −v) + 1, for 0 < v < r and 0 < m < r + δ −1.Here n = w(r+δ−1)+m and k = ur+v.Source: §IV · p. 6

Corollary

  • For k > 2r^2 + r, the Theorem 11 nonexistence condition holds whenever 0 < n mod (r + δ −1) < (k mod r) + δ −1.Source: §IV · p. 7

V. CONSTRUCTION OF OPTIMAL (r, δ)a CODES:

The section gives a deterministic construction for optimal (r, δ)a codes and proves existence in specified parameter regions. Its method extends an MDS code, and the authors report a smaller field requirement than an earlier construction in an overlapping case.

Existence conditions

  • The stated existence regions include (r + δ −1)|n and m ≥v + δ −1; Theorem 16 additionally assumes d ≥δ for its m ≥v + δ −1 case.Source: §V · pp. 7, 10

Field size

  • For the divisible-length case, the authors say their method needs a much smaller field than the earlier construction in.Source: §V · pp. 7, 10

Theorem 14

  • Theorem 14 constructs an optimal (r, δ)a code over Fq from a partition satisfying its stated conditions.The theorem’s field-size threshold is stated in the source, but its value is not available in the supplied passage.Source: §V · p. 8

Construction algorithm

  • The deterministic algorithm first builds an [L, k] MDS code and then extends it by selecting generator columns while preserving independence of every (S, r, k)-core.The extension process adds columns from the span of those already selected within each partition block.Source: §V · p. 8

Correctness

  • The construction is proved to yield an (r, δ)a code with minimum distance attaining the upper bound, and the required generator vector can always be found.Source: §V · pp. 8–9

VI. CONSTRUCTION OF OPTIMAL (r, δ)a CODES:

This section develops a construction using (A, Ψ)-frames and cores to establish the existence of optimal (r, δ)a linear codes under parameter conditions. It also gives sufficient existence conditions and discusses a threshold on n for meeting key size requirements.

VI. CONSTRUCTION OF OPTIMAL (r, δ)a CODES:

  • Lemma 20 supplies the core existence properties used in the construction, including a k-sized core within a suitable T and a core containing any specified r-subset of a local set.These properties support the proof that the extended code has the required locality and distance.Source: §VI · p. 11
  • Theorem 25 constructs an optimal (r, δ)a linear code from an (A, Ψ)-frame under its stated hypotheses, attaining d = n − k + 1 − (⌈k/r⌉ − 1)(δ − 1).The proof initializes an [L, k] MDS code and extends it while maintaining linear independence for every core, establishing locality and the claimed minimum distance.Source: §VI · pp. 12–13
  • The construction starts with an [L, k] MDS code and adds columns from local spans so every (S, r, k)-core retains linear independence.Algorithm 2 repeatedly selects a new symbol in a local set and chooses its column from the span of existing columns in that set, subject to the core-independence condition.Source: §VI · pp. 12–13
  • For r = δ = 3, the section gives a new optimal code example with (r + δ − 1) not dividing n.The example applies Algorithm 2 to the frame with k = 7; the field-size bound is not visible in the supplied passage.Source: §VI · p. 13
  • Theorem 26 establishes existence when n = w(r + δ − 1) + m and k = ur + v, with 0 < m < r + δ − 1, 0 < v < r, w ≥ r + δ − 1 − m, and r − v ≥ u, provided q meets its stated threshold.The supplied passage does not expose the field-size threshold.Source: §VI · p. 13
  • Under Theorem 27’s field-size condition, an optimal (r, δ)a linear code exists when 0 < m < r + δ − 1, 0 < v < r, w + 1 ≥ 2(r + δ − 1 − m), and 2(r − v) ≥ u.Here n = w(r + δ − 1) + m and k = ur + v.Source: §VI · p. 13
  • The proof partitions coordinates into paired subsets intersecting in one point, then fills the remaining positions with subsets of size r + δ − 1 to form a frame.The paired subsets are drawn from blocks of size 2(r + δ − 1) − 1.Source: §VI · p. 14
  • For α = max{2(r + δ − 1), ⌈k/r⌉}, the discussion states that the inequalities w + 1 ≥ 2(r + δ − 1 − m) and w ≥ u can be satisfied when n ≥ α(r + δ − 1).This provides a size threshold for applying Theorem 27.Source: §VI · p. 14

VII. CONCLUSIONS

The paper derives a structure theorem for optimal (r, δ)a codes when r|k and identifies parameter sets where such codes do or do not exist. It reports smaller field requirements for some constructions, with only two subcases left unresolved.

VII. CONCLUSIONS

  • A structure theorem is obtained for optimal (r, δ)a codes with r|k.Source: §VII · p. 14
  • Two parameter sets are shown to admit no optimal codes, while four others admit codes over fields meeting stated size thresholds.Source: §VII · p. 14
  • For some existence conditions reported previously, the derived minimum field size is considerably smaller than earlier bounds.Source: §VII · p. 14
  • Except for two small subcases, each parameter tuple is classified as admitting no optimal code or permitting deterministic construction.Source: §VII · p. 14
  • The illustrative table covers n = 60, δ = 5, 2 ≤ r ≤ 11, and 11 ≤ k ≤ 20, marking constructions, nonexistence, and unresolved cases.Source: §VII · p. 14
Loading 1307.1961v1…