PaperlayerView exact revision on arXiv

Source-linked AI summary

Locally Repairable Codes with Multiple Repair Alternatives

Lluis Pamies-Juarez, Henk D. L. Hollmann, Frédérique Oggier

arXiv:1302.5518v2cs.ITcs.DCmath.IT

TL;DR

Locally repairable codes can limit repair traffic, but often provide only one repair subset for each lost symbol. This paper develops a framework and partial-geometry constructions for trading repair locality against multiple alternatives. The resulting pg-BLRCs satisfy bounds on repair degree and alternativity, with Generalized Quadrangles attaining the maximum rate.

  • Problem

    Locally repairable codes often provide only one repair subset per lost symbol, while the design trade-off between repair locality and multiple alternatives has not been the focus of analysis.

    Source: §I · p. 1

  • Method

    The paper defines local repair tolerance and constructs pg-BLRCs from partial geometries to study trade-offs among repair degree, repair alternatives, and rate.

    Source: §I · pp. 1–2, §V · p. 3

  • Results

    For pg-BLRCs, r ≤ s and a ≥ t + 1, and the maximum rate is achieved by generalized quadrangles.

    Source: B. Codes from Partial Geometries · p. 4, C. Rate Bounds of pg-BLRC Codes · p. 5

  • Takeaways & Limitations

    Multiple repair alternatives can increase the probability of locally repairing lost data when nodes are unavailable, especially when alternatives share few nodes.

    Source: §IV · p. 3

Abstract

from arXiv · show

Distributed storage systems need to store data redundantly in order to provide some fault-tolerance and guarantee system reliability. Different coding techniques have been proposed to provide the required redundancy more efficiently than traditional replication schemes. However, compared to replication, coding techniques are less efficient for repairing lost redundancy, as they require retrieval of larger amounts of data from larger subsets of storage nodes. To mitigate these problems, several recent works have presented locally repairable codes designed to minimize the repair traffic and the number of nodes involved per repair. Unfortunately, existing methods often lead to codes where there is only one subset of nodes able to repair a piece of lost data, limiting the local repairability to the availability of the nodes in this subset. In this paper, we present a new family of locally repairable codes that allows different trade-offs between the number of contacted nodes per repair, and the number of different subsets of nodes that enable this repair. We show that slightly increasing the number of contacted nodes per repair allows to have repair alternatives, which in turn increases the probability of being able to perform efficient repairs. Finally, we present pg-BLRC, an explicit construction of locally repairable codes with multiple repair alternatives, constructed from partial geometries, in particular from Generalized Quadrangles. We show how these codes can achieve practical lengths and high rates, while requiring a small number of nodes per repair, and providing multiple repair alternatives.

I. INTRODUCTION

Locally repairable codes reduce the number of nodes contacted during repair, but usually offer only one repair subset per lost symbol. This paper studies trade-offs between repair locality and the number of repair alternatives, and introduces local repair tolerance as a measure of repairability under node unavailability.

I. INTRODUCTION

  • Coding reduces storage footprint relative to three-replica storage, but repairing lost encoded data can require substantial data retrieval, network traffic, and I/O.The cited examples use 1.3–1.5 times the original object's size, a 50% footprint reduction compared with three replicas.Source: §I · p. 1
  • Existing locally repairable codes typically have only one repair subset per symbol, while earlier alternatives may require larger subsets as more nodes become unavailable.The paper frames the design goal as balancing small repair sets with multiple alternatives.Source: §I · p. 1
  • The paper presents a framework for trading off repair locality and the number of repair alternatives per failure.The introduction defines local repair tolerance as the maximum number of unavailable nodes compatible with locally repairing all stored data.Source: §I · pp. 1–2
  • The proposed pg-BLRC construction uses partial geometries, with Generalized Quadrangles attaining the stated rate bounds.The paper identifies repair locality, number of alternatives, and storage footprint as jointly competing design goals.Source: §I · p. 2

II. LINEAR CODES FOR DISTRIBUTED STORAGE

The section describes how linear codes represent and store data across nodes. It relates code rate and storage footprint to redundancy, and explains reconstruction from a suitable set of stored symbols.

II. LINEAR CODES FOR DISTRIBUTED STORAGE

  • A q-ary linear code is a k-dimensional subspace of Fq^n and can be represented by a full-rank k × n generator matrix.Its vectors are codewords, and it can also be represented using a full-rank parity-check matrix H satisfying GH⊤ = 0.Source: §II · p. 2
  • Storage encodes a k-symbol object into an n-symbol codeword and places its symbols on n nodes, using capacity beyond the original object.The code rate is k/n; storage footprint n/k is the capacity used per data object relative to its original size.Source: §II · p. 2
  • The original object can be reconstructed from k stored symbols when the corresponding generator-matrix submatrix is invertible.A code is MDS when this submatrix is invertible for every k-symbol subset.Source: §II · p. 2

III. DATA REPAIRABILITY OF LINEAR CODES

The section evaluates repair of linear-code symbols through parity-check vectors. Their Hamming weights determine the number of other symbols retrieved, and the minimum and maximum repair degrees characterize local repairability.

III. DATA REPAIRABILITY OF LINEAR CODES

  • A parity-check vector with a nonzero entry at the missing symbol enables its recovery by solving the parity-check equation.The equation relates the missing symbol to the other symbols in the vector's support.Source: §III · p. 2
  • Repairing a symbol using a parity-check vector of weight w requires retrieving w − 1 other symbols, so low-weight vectors limit repair traffic.The design objective is to provide, for every symbol, a low-weight parity-check vector with a nonzero entry at that position.Source: §III · p. 2
  • The repair degree r(i) is the minimum w(v) − 1 among vectors in Ω(i), and the code's overall repair degree is the maximum r(i).Ω(i) contains parity-check vectors that repair symbol i.Source: §III · p. 2
  • Locally repairable codes have overall repair degree much smaller than their rank, unlike classic MDS and regenerating codes whose repair degree is at least the rank.For Reed-Solomon codes, repair requires transferring information equal to the original object size; regenerating codes can transfer slightly less but still contact at least k nodes.Source: §III · p. 2

IV. CODES WITH MULTIPLE REPAIR ALTERNATIVES

Multiple repair subsets can preserve local repair when some contacted nodes are unavailable. The section defines repair alternativity and local repair tolerance, then specifies balanced codes through their repair degree, alternatives, and outage tolerance.

IV. CODES WITH MULTIPLE REPAIR ALTERNATIVES

  • Repair alternatives matter when contacted nodes are unavailable, but most existing locally repairable codes have alternativity a = 1.SRC codes can have a > 1, but their alternativity depends on construction, and large a leads to low-rate, impractical codes.Source: §IV · p. 3
  • Repair alternativity a counts the distinct subsets of at most r nodes that can repair a symbol, using the minimum count across symbols.Each eligible parity-check vector corresponds to a possible repair alternative.Source: §IV · p. 3
  • The paper seeks to increase local-repair probability by minimizing the overlap between different repair alternatives for a symbol.It formalizes local repair tolerance δ(i) as the size of the smallest set of other coordinates intersecting every eligible repair support.Source: §IV · p. 3
  • Overall local repair tolerance δ is the minimum symbol-level tolerance, and balanced codes require equal tolerance across all symbols.The framework focuses on balanced codes to avoid designs in which different symbols have unequal local-repair availability.Source: §IV · p. 3
  • An (n, k, r, a, δ)-BLRC has length n and rank k, repairs each symbol from at most r others using at least a subsets, and tolerates up to δ unavailable nodes.These codes are the balanced locally repairable codes considered in the paper.Source: §IV · p. 3

V. BALANCED LOCALLY REPAIRABLE CODES FROM PARTIAL GEOMETRIES

This section introduces explicit BLRC constructions from partial geometries and evaluates them analytically by repair tolerance and code rate.

V. BALANCED LOCALLY REPAIRABLE CODES FROM PARTIAL GEOMETRIES

  • The section presents a method for generating explicit BLRC constructions from partial geometries.These constructions are analyzed in terms of repair tolerance δ and code rate R.Source: §V · p. 3
  • The analysis evaluates the constructed codes in terms of repair tolerance δ.Source: §V · p. 3
  • The analysis also evaluates the constructed codes in terms of code rate R.Source: §V · p. 3

A. Partial Geometries

A partial geometry is an incidence structure of points and lines governed by parameters s, t, and α; generalized quadrangles are identified as especially useful for code rate.

A. Partial Geometries

  • A partial geometry pg(s, t, α) is an incidence structure between point and line sets with specified incidence properties.Each point is on t + 1 lines, each line on s + 1 points, and nonincident point-line pairs have exactly α connecting pairs.Source: A. Partial Geometries · p. 3
  • Partial geometries include Steiner 2-designs, nets or transversal designs, generalized quadrangles, and proper geometries, depending on their parameters.The dual structure interchanges points and lines and swaps s and t.Source: A. Partial Geometries · p. 3
  • Generalized quadrangles are of special interest for designing codes optimal in rate.Source: A. Partial Geometries · p. 3

B. Codes from Partial Geometries

The section constructs systematic binary pg-BLRC codes from partial-geometry incidence matrices and establishes bounds on locality, repair alternatives, and tolerance to unavailable nodes.

B. Codes from Partial Geometries

  • The code designs are limited to binary codes, a restriction stated not to affect the obtained code rate.Partial-geometry incidence matrices are used to construct the codes.Source: B. Codes from Partial Geometries · p. 4
  • A pg-BLRC is constructed by taking linearly independent rows of the partial-geometry incidence matrix as a parity-check matrix, then deriving a systematic generator matrix.The incidence matrix records whether each line is incident with each point.Source: B. Codes from Partial Geometries · p. 4
  • The repair and alternativity bounds follow because each point lies on t + 1 lines, each containing s + 1 points.Those incident lines yield repair checks of weight s + 1 for each symbol.Source: B. Codes from Partial Geometries · p. 4
  • The paper excludes replication schemes by requiring s > 1 for its pg-BLRC codes.When s = 1, lost data can be repaired by contacting one node, corresponding to replication.Source: B. Codes from Partial Geometries · p. 4
  • For a pg-BLRC built from pg(s, t, α), repair degree r is at most s, alternativity a is at least t + 1, and repair tolerance δ is at least t + 1.The code guarantees repair by contacting r other nodes using a alternative r-subsets, and can repair when up to δ = a nodes are temporarily unavailable.Source: B. Codes from Partial Geometries · p. 4

C. Rate Bounds of pg-BLRC Codes

The section bounds the rate of pg-BLRC codes and shows that maximizing rate favors generalized quadrangles. Its rate analysis exposes a trade-off: smaller repair degree and more repair alternatives come with lower rate.

C. Rate Bounds of pg-BLRC Codes

  • Theorem 1 provides a lower rate bound and, when r + a − 1 is even, an upper rate bound for pg-BLRC codes.The section derives the bounds from rank bounds on the partial-geometry incidence matrix.Source: C. Rate Bounds of pg-BLRC Codes · p. 4
  • Figure 1 depicts the theoretical minimum and maximum rates for different repair-degree r and repair-alternativity a combinations.The bounds shown apply to pg-BLRC codes with α = 1.Source: Figure 1 · p. 5, C. Rate Bounds of pg-BLRC Codes · p. 5
  • The upper and lower rate bounds for (r, a) pg-BLRC codes are attained at α = 1, corresponding to generalized quadrangles.The upper bound is evaluated by substituting s := r and t := a−1; the lower-bound derivation also evaluates at α = 1.Source: C. Rate Bounds of pg-BLRC Codes · p. 5
  • The rate decreases when repair degree r decreases or repair alternativity a increases, trading efficient repairs for greater storage overhead.The section frames these opposing objectives as an optimization trade-off for storage-system designers.Source: C. Rate Bounds of pg-BLRC Codes · p. 5

D. Explicit pg-BLRC Code Constructions

The construction discussion identifies practical parameter pairs for pg-BLRC codes and notes that generalized quadrangles are not known for all parameter values.

D. Explicit pg-BLRC Code Constructions

  • Generalized quadrangle constructions are known only for a limited set of parameter families, not for all possible s and t values.The passage lists known pairs and families and cites.Source: D. Explicit pg-BLRC Code Constructions · p. 5
  • The practical parameter pairs are identified by filtering the possible (s, t) pairs using the stated rate and length thresholds.The filters are R ≤ 1/3 and n > 100.Source: D. Explicit pg-BLRC Code Constructions · p. 5
  • After excluding cases with R ≤ 1/3 or n > 100, the listed practical parameter pairs are (r, a) ∈ {(r, 2), (2, 3), (4, 3), (3, 4), (5, 4), (4, 5)}.The upper-bound cases are limited to those where r + a − 1 ≡ 1 mod 2.Source: D. Explicit pg-BLRC Code Constructions · p. 5

VI. CONCLUSIONS

The conclusion presents pg-BLRC codes as a way to trade repair locality against the number of repair alternatives, with rate bounds for the resulting codes.

VI. CONCLUSIONS

  • The paper proposes analyzing locally repairable codes through trade-offs between repair locality and the number of repair alternatives per failure.The approach considers more than codes focused only on minimum repair locality and maximum rate.Source: §VI · p. 5
  • The paper presents an explicit construction of locally repairable codes with different repair-locality and repair-alternativity trade-offs.Source: §VI · p. 5
  • The paper provides upper and lower bounds on the attainable rate of these codes.Source: §VI · p. 5
Loading 1302.5518v2…