Optimal Locally Repairable Codes of Distance 3 and 4 via Cyclic Codes

Yuan Luo, Chaoping Xing, Chen Yuan

TL;DR

This paper introduces a new construction for Locally Repairable Codes (LRCs) that achieve the theoretical maximum efficiency (the Singleton-type bound) for minimum distances of 3 and 4. Unlike previous optimal constructions that were limited by the size of the code's alphabet, these new cyclic codes allow for unbounded code lengths, making them highly practical for massive distributed storage systems.

What Problem Does This Paper Address?

In distributed storage (like cloud databases), data is spread across many nodes. If one node fails, we want to repair it by downloading data from as few other nodes as possible. This "repair cost" is defined as locality ($r$).

There is a fundamental tradeoff between a code's redundancy, its ability to correct errors (minimum distance $d$), and its locality. Codes that hit the absolute best possible tradeoff are called optimal LRCs.

The major bottleneck in existing research was the "alphabet size limit." Most known optimal LRCs were based on Reed-Solomon codes, which require the number of nodes ($n$) to be less than or equal to the alphabet size ($q$). If you want a system with thousands of nodes using small data symbols, these older methods don't scale. This paper tackles the challenge of building optimal codes where the number of nodes $n$ can be much, much larger than $q$.

Methods

The authors use Cyclic Codes to build their LRCs. A cyclic code is a linear code where any cyclic shift of a codeword is also a codeword. These are mathematically elegant because they can be treated as ideals in a polynomial ring.

The key technical steps include:

  1. Generator Polynomial Selection: The authors carefully choose the roots of the generator polynomial $g(x)$. By selecting specific $n$-th roots of unity, they can precisely control the minimum distance of the code.
  2. Dual Distance Control: To ensure a specific locality $r$, the authors prove a general lemma: if a code is "transitive" (which cyclic codes are) and its dual code has a small distance, then the original code has small locality.
  3. Algebraic Construction: They provide specific algebraic conditions (divisibility requirements between $n, q,$ and $r$) that allow the construction of these polynomials such that the resulting code hits the Singleton-type bound exactly.

Datasets

As a theoretical paper in coding theory, no empirical datasets were used. The "evaluation" consists of mathematical proofs demonstrating that the constructed codes satisfy the parameters for optimality.

Key Insights and Ideas

  • Transitivity is a Shortcut: The authors highlight that for transitive codes (like cyclic and Reed-Muller codes), locality is much easier to determine. You only need to find one low-weight codeword in the dual code to prove the locality for the entire code.
  • Breaking the Alphabet Barrier: By moving away from Reed-Solomon-like structures and using the broader properties of cyclic codes, the authors show that "optimality" doesn't have to come at the cost of "short length."
  • Distance 3 and 4 focus: The paper provides a "recipe" for $d=3$ and $d=4$. For $d=3$, they use a generator polynomial $g(x) = (x-1)(x^{n/(r+1)} - \alpha)$. For $d=4$, the construction is slightly more complex, involving an additional linear factor to push the distance higher while maintaining the same locality.

Key Results

The main result is Theorem 1.1, which proves the existence of $q$-ary optimal cyclic LRCs with:

  • Distance 3: Length $n$ is unbounded, provided $gcd(n, q) = 1$ and $gcd(n, q-1) \equiv 0 \pmod{r+1}$.
  • Distance 4: Length $n$ is unbounded, provided $r \ge 3$ and certain $gcd$ conditions are met.
  • Verification: The authors explicitly calculate the parameters ($n, k, d, r$) and show they satisfy the equality $d = n - k - \lceil k/r \rceil + 2$, which is the definition of an optimal LRC.

Limitations and Future Work

  • Fixed Distance: The current construction only works for small, fixed minimum distances ($d=3$ and $d=4$). While these are common in practical storage systems (which often only need to survive 1 or 2 simultaneous failures), they don't cover cases requiring very high error resilience.
  • Open Problems: The authors pose two significant challenges for the community:
  • Can we find optimal codes where the length $n$ is much larger than $q$ (e.g., $n = \Omega(q^2)$) and the distance $d$ grows linearly with $n$?
  • Can we construct optimal LRCs with unbounded length for any constant distance $d$, not just 3 and 4?

Summary updated

Abstract

Like classical block codes, a locally repairable code also obeys the Singleton-type bound (we call a locally repairable code optimal if it achieves the Singleton-type bound). In the breakthrough work of Tamo and Barg, several classes of optimal locally repairable codes were constructed via subcodes of Reed-Solomon codes. Thus, the lengths of the codes given by Tamo and Barg are upper bounded by the code alphabet size q. Recently, it was proved through the extension of construction by Tamo and Barg that the length of q-ary optimal locally repairable codes can be q +1 by Jin et al. Surprisingly, Barg et al. presented a few examples of q-ary optimal locally repairable codes of small distance and locality with code length achieving roughly q <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> . Very recently, it was further shown in the work of Li et al. that there exist q-ary optimal locally repairable codes with the length bigger than q+1 and the distance proportional to n. Thus, it becomes an interesting and challenging problem to construct new families of q-ary optimal locally repairable codes of length bigger than q+1. In this paper, we construct a class of optimal locally repairable codes of distances 3 and 4 with unbounded length (i.e., length of the codes is independent of the code alphabet size). Our technique is through cyclic codes with particular generator and parity-check polynomials that are carefully chosen.
BibTeX
@article{luo2019optimal,
  author = {Yuan Luo and Chaoping Xing and Chen Yuan},
  title = {{Optimal Locally Repairable Codes of Distance 3 and 4 via Cyclic Codes}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=sRstX9VGSWf},
}

Loading related content...

Figure