PaperlayerView exact revision on arXiv

Source-linked AI summary

Bounds on the Parameters of Locally Recoverable Codes

Itzhak Tamo, Alexander Barg, Alexey Frolov

arXiv:1506.07196v2cs.IT

TL;DR

The paper addresses how locality and multiple recovering sets constrain the rate and distance of locally recoverable codes. It derives GV-type, expander-based, and finite-length bounds, showing threshold results for one and two recovering sets and asymptotically good constructions over sufficiently large alphabets.

  • Problem

    The paper studies bounds on the rate and distance of LRC codes with one or multiple disjoint recovering sets.

  • Method

    It uses Gilbert–Varshamov arguments, bipartite and LDPC ideas, expander graphs, and finite-length bound techniques.

  • Results

    The paper derives GV-type bounds for one and two recovering sets, expander-based existence results for arbitrary t and r over sufficiently large alphabets, and finite-length rate and distance bounds.

  • Takeaways & Limitations

    Asymptotically good binary 2-LRC codes require relative distance δ<δ0, while asymptotically good q-ary t-LRC codes exist for sufficiently large q.

  • Takeaways & Limitations

    For finite parameters, the authors identify the shortening bound as the only meaningful known bound that accounts for alphabet size in the single-recovering-set case, while stronger upper bounds remain open.

Abstract

from arXiv · show

A locally recoverable code (LRC code) is a code over a finite alphabet such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. In this paper we derive new finite-length and asymptotic bounds on the parameters of LRC codes. For LRC codes with a single recovering set for every coordinate, we derive an asymptotic Gilbert-Varshamov type bound for LRC codes and find the maximum attainable relative distance of asymptotically good LRC codes. Similar results are established for LRC codes with two disjoint recovering sets for every coordinate. For the case of multiple recovering sets we derive a lower bound on the parameters using expander graph arguments. Finally, we also derive finite-length upper bounds on the rate and distance of LRC codes with multiple recovering sets.

I. INTRODUCTION

The paper studies finite-length and asymptotic bounds for locally recoverable codes, including codes with one or multiple disjoint recovering sets. It introduces Gilbert–Varshamov-type and graph-based results alongside upper bounds on rate and distance.

  • I. INTRODUCTION: LRC codes let each coordinate be recovered from a small recovering set, with multiple disjoint sets improving data availability.The paper focuses on all-symbol locality and, for compactness, equal recovering-set size r.
  • I. INTRODUCTION: The paper derives a Gilbert–Varshamov-type bound for one recovering set, recovering the asymptotic threshold δ0=(q−1)/q for positive-rate code sequences.This addresses a gap in previously available lower bounds for the classic single-recovering-set case.
  • I. INTRODUCTION: For two disjoint recovering sets, the paper obtains asymptotic GV-type bounds and concludes that asymptotically good binary codes require relative distance δ<δ0.The paper also notes a connection to LDPC graphs without 4-cycles, while direct LDPC bounds are insufficient for the LRC problem.
  • I. INTRODUCTION: For arbitrary numbers of recovering sets, expander constructions establish asymptotically good q-ary codes for any t and r when the alphabet is sufficiently large.The approach connects local recovery with expansion properties of a graph associated with the code.

B. Known results, Multiple recovering sets

For multiple recovering sets, the paper develops upper bounds on rate and distance and lower bounds using multilevel constructions and expander graphs. It also compares these bounds with existing constructions and identifies unresolved gaps.

  • Upper bounds: The rate of t-LRC codes is bounded above by a function of r and t, while their minimum distance also has a finite-length upper bound.The paper presents these results as extensions of single-recovering-set bounds to multiple recovering sets.
  • Comparison with prior bounds: The bound (18) is tighter than the asymptotic version of an earlier upper bound for all rates, while the t ≥ 2 rate bounds are not known to be tight.The paper notes that it remains unclear which of the relevant lower and upper bounds is loose.
  • Expander-based lower bounds: Theorem C establishes asymptotically good t-LRC codes for sufficiently large alphabets using expander graphs, with locality r ≥ t and rates up to 1 − t/(r + 1).The relative distance is determined by two equations involving δ and γ.
  • Expander-based lower bounds: For small relative distance, the expander equations may have no solution, so the construction only guarantees rate R = 1 − t/(r + 1).This produces a horizontal extension of the lower bound rather than a distance-specific construction in that regime.
  • The case of t = 2: For two recovering sets, Theorem C yields sequences with higher minimum distance than a prior construction for large alphabets.The comparison is stated for a fixed rate and relies on the intersection behavior of the equations defining the expander construction.

III. AN UPPER BOUND ON THE RATE OF LRC CODES

This section proves the rate upper bound for LRC codes with multiple recovering sets.

  • The rate upper bound is proved in this section as estimate (13) from Theorem A.

A. The recovery graph

The recovery graph represents coordinates as vertices and their recovering-set memberships as colored directed edges. A permutation-based coloring argument yields a large subset whose induced subgraphs miss a color, supporting recovery and rate bounds.

  • A. The recovery graph: The recovery graph has one vertex per coordinate, with edges to recovering-set coordinates and colors distinguishing the t recovering sets.Each coordinate has tr outgoing edges when every recovering set has size r.
  • A. The recovery graph: A permutation-based construction produces a vertex subset whose every induced subgraph contains a vertex missing at least one outgoing edge color.The construction assigns colors according to a random permutation and uses inclusion–exclusion to analyze the resulting events.
  • A. The recovery graph: The missing-color property enables iterative recovery of all coordinates outside the constructed subset from coordinates inside it.At each step, a vertex with a missing recovering-set color can be recovered from already known coordinates.
  • A. The recovery graph: Figure 1 compares GV-type and upper bounds across binary codes with one or two recovering sets and larger-alphabet codes with three recovering sets.Panel (a) uses r = 3 binary codes; panel (b) compares t = 1 and t = 2; panel (c) uses r = 6 and t = 3.

B. Proof of the bound on the rate (13)

The rate-bound proof converts the recovery-graph structure into an iterative recovery argument. It then estimates the resulting product expression to obtain the stated bound on the rate.

  • B. Proof of the bound on the rate (13): The proof iteratively removes recoverable coordinates from the complement of a specially chosen vertex subset.The induced-subgraph property guarantees a vertex whose recovering set is contained in already known coordinates.
  • B. Proof of the bound on the rate (13): The argument reduces the rate estimate to analyzing the product appearing in bound (13).The text introduces an approximation for this product before deriving the target bound (17).
  • B. Proof of the bound on the rate (13): Inequalities (30) are substituted into (31) to complete the rate-bound estimate.The supplied passages identify this substitution as the final algebraic step.

IV. UPPER BOUNDS ON THE MINIMUM DISTANCE OF LRC CODES

The distance upper bound constructs a small coordinate set whose closure is large, then applies a restriction-based distance inequality. Expansion of the recovery graph controls how many coordinates the closure contains.

  • IV. UPPER BOUNDS ON THE MINIMUM DISTANCE OF LRC CODES: The proof seeks k − 1 coordinates whose values determine a large additional coordinate set, allowing a distance bound from the restricted code.Because the combined restriction has at most q^(k−1) possible values, the general restriction inequality applies.
  • IV. UPPER BOUNDS ON THE MINIMUM DISTANCE OF LRC CODES: The coloring process is an influence-propagation model on the recovery graph.The paper relates this process to prior work on closure under threshold decision rules in expanders.
  • IV. UPPER BOUNDS ON THE MINIMUM DISTANCE OF LRC CODES: For every vertex, Lemma 4.1 supplies a seed set of size at most rt with a guaranteed expansion ratio.The lemma is proved inductively on the number of recovering sets.
  • IV. UPPER BOUNDS ON THE MINIMUM DISTANCE OF LRC CODES: Repeatedly applying the lemma to uncolored induced subgraphs builds a set S of k − 1 vertices with controlled expansion.The procedure chooses the largest admissible seed under the remaining coloring budget and combines the resulting sets.
  • IV. UPPER BOUNDS ON THE MINIMUM DISTANCE OF LRC CODES: The closure of S determines enough coordinates that its restriction has at most q^(k−1) codewords, yielding the upper bound on minimum distance.The final step takes the closure as the coordinate set in the restriction inequality.

V. LOWER GV-TYPE BOUNDS FOR LRC CODES

The paper derives lower asymptotic bounds for LRC codes with one and two recovering sets by studying random linear-code ensembles with locality constraints.

  • V. LOWER GV-TYPE BOUNDS FOR LRC CODES: Lower asymptotic bounds for one- and two-recovering-set LRC codes are obtained from random linear-code ensembles with locality properties.The analysis relies on a variation of Gallager’s method previously used for LDPC and bipartite-graph codes.

A. One recovering set, any alphabet

The paper constructs random linear LRC ensembles with one recovering set and derives Gilbert–Varshamov-type finite-length and asymptotic distance bounds. The asymptotic rate reaches r/(r+1) at zero relative distance and becomes zero exactly at relative distance (q−1)/q.

  • A block-diagonal single-parity-check matrix supplies locality, while a uniformly random lower matrix enables the distance analysis.The construction uses H_U with parity-check blocks and chooses H_L independently and uniformly over F_q.
  • Theorem 5.1 establishes a Gilbert–Varshamov bound for LRC codes with one recovering set.
  • For sufficiently large length, the ensemble contains codes with relative distance at least δ when the union-bound expression is below one.
  • The optimization over s>0 has a unique minimum attained for 0<s≤1, so restricting the proof to that interval loses nothing.
  • A finite-length proposition guarantees a q-ary linear LRC code with distance d whenever its stated inequality holds.
  • The asymptotic rate satisfies R_q(r,0)=r/(r+1), while R_q(r,δ)=0 exactly when δ≥(q−1)/q.

B. Two recovering sets

For two disjoint recovering sets, the paper builds parity-check ensembles from complete-graph incidence matrices and derives a Gilbert–Varshamov-type bound. The graph structure directly supplies two disjoint recovery groups for each coordinate.

  • The construction uses a block-diagonal matrix whose local block is a complete-graph incidence matrix with one row deleted.The remaining matrix rows are chosen independently and uniformly over F_q.
  • The local block’s weight enumerator is computed through binary and arbitrary-q analyses, followed by the MacWilliams theorem.
  • Theorem 5.6 derives a Gilbert–Varshamov bound for 2-LRC codes from the expected distance of a random parity-check ensemble.
  • Each edge coordinate has two disjoint recovering sets because its endpoint incidence rows intersect only on that edge.

C. Multiple recovering sets, Large alphabets. Proof of Theorem C

For multiple recovering sets over sufficiently large fields, the paper uses biregular expander graphs and Hall’s condition to construct codes with prescribed rate and relative distance. The resulting parity-check matrix simultaneously enforces locality and distance.

  • Hall’s condition lets sufficiently large fields produce linearly independent vectors, yielding a parity-check matrix whose code has minimum distance at least δn.
  • An expander graph supplies neighborhood growth, and the associated subset family satisfies Hall’s condition for all families of size at most δn.
  • Random regular bipartite graphs have the required expansion with probability at least 1−O(n^-β), asymptotically.
  • The first p parity-check rows have weight r+1 and provide the locality property for the code symbols.
  • The construction obtains disjoint recovering sets when the graph has no 4-cycles, while its expansion property holds with probability approaching one.

VI. CONCLUDING REMARKS

The concluding remarks identify unresolved issues in bounding LRC code cardinality and improving bounds, especially for multiple recovering sets. They point to algebraic-curve constructions, stronger upper bounds, tightness questions, and derandomization.

  • For a single recovering set, the asymptotic problem remains difficult, while the authors regard their random-code GV-type bound as close to final form.
  • Upper bounds remain open, and straightforward techniques adapted from LDPC codes do not improve the LRC case.
  • For multiple recovering sets, limited control over recovering-set structure makes both lower and upper bounds difficult to derive.
  • Potential directions include algebraic-curve constructions for t≥2, testing Singleton-like-bound tightness, and derandomizing the expander-based lower bound.

APPENDIX

The appendix proves a lemma by showing that F(s) has a unique minimizer in the relevant interval, using monotonicity and Cauchy–Schwarz. It then establishes positivity of the resulting bound for δ in the stated range.

  • Proof of Lemma 5.2: The proof reduces the lemma to showing that F(s) has a unique minimum attained for 0 < s ≤ 1 when δ ∈ (0, (q −1)/q].F(s) is defined as a combination of ln b(s) and ln s, and the stationary-point equation determines the minimizer.
  • Proof of Lemma 5.2: Strict monotonicity of f(s) makes its inverse unique and places the minimizing value in (0, 1) for 0 < δ < (q −1)/q.The endpoint solutions are (s = 0, δ = 0) and (s = 1, δ = (q −1)/q).
  • Proof of Lemma 5.2: The proof establishes that f(s) is strictly increasing by expressing b(s) as a degree-r + 1 polynomial and reducing positivity to Cauchy–Schwarz.The argument concludes after verifying positivity of the relevant expression for s > 0.
  • Proof of Lemma 5.2: Because the minimizing value s0 is below 1 for δ < (q −1)/q, the minimum in (19) is positive throughout δ ∈ (0, (q −1)/q).The minimum increases from 0 to r/(r + 1) as s0 ranges from 0 to 1.
Loading 1506.07196v2…