Optimal locally repairable codes of distance 3 and 4 via cyclic codes

Yuan Luo, Chaoping Xing, Chen Yuan

Introduction

In modern distributed storage systems, such as cloud databases and large-scale data centers, data is distributed across multiple nodes to ensure reliability. However, node failures are inevitable. To restore lost data, systems traditionally use erasure codes. A critical metric in this context is locality ($r$), which defines the number of other nodes that must be accessed to repair a single failed node.

Like classical block codes, Locally Repairable Codes (LRCs) are subject to a fundamental performance limit known as the Singleton-type bound. Codes that achieve this bound are termed optimal LRCs. While previous research successfully constructed optimal LRCs, most were based on Reed-Solomon structures, which impose a strict "alphabet size limit": the number of nodes ($n$) cannot exceed the size of the code's alphabet ($q$). This paper presents a breakthrough by constructing optimal LRCs with unbounded code lengths, meaning the number of nodes can be significantly larger than the alphabet size.

The Problem: Breaking the Alphabet Barrier

The primary bottleneck in existing optimal LRC research was scalability. If a system requires thousands of nodes ($n$) but uses relatively small data symbols ($q$), traditional Reed-Solomon-based constructions ($n \le q+1$) are inapplicable. While some recent work suggested the possibility of longer codes, constructing a general family of optimal LRCs where $n$ is independent of $q$ remained a challenging problem. This research addresses this gap specifically for codes with minimum distances ($d$) of 3 and 4.

Methodology: The Power of Cyclic Codes

The authors utilize the algebraic properties of Cyclic Codes to overcome previous length limitations. A cyclic code is a linear code where any cyclic shift of a codeword results in another valid codeword. These codes are mathematically represented as ideals in a polynomial ring, allowing for precise manipulation via generator polynomials.

Key Technical Strategies

  1. Generator Polynomial Selection: The researchers carefully selected the roots of the generator polynomial $g(x)$. By choosing specific $n$-th roots of unity, they could precisely control the code's minimum distance.
  2. Transitivity and Locality: A significant insight of this work is that for transitive codes (such as cyclic codes), determining locality is simplified. The authors proved that if the dual code contains a codeword of small weight, the locality of the original code is automatically constrained. This allowed them to use the dual distance as a proxy for controlling repair costs.
  3. Algebraic Constraints: The construction relies on specific divisibility conditions between the code length $n$, the alphabet size $q$, and the locality $r$. By satisfying these conditions, the authors ensure the resulting code hits the Singleton-type bound exactly.

Key Results

The paper's main contribution is the formal proof (Theorem 1.1) of the existence of $q$-ary optimal cyclic LRCs with the following properties:

  • Distance 3 ($d=3$): The code length $n$ is unbounded, provided that $gcd(n, q) = 1$ and $gcd(n, q-1)$ is a multiple of $r+1$. The generator polynomial used is $g(x) = (x-1)(x^{n/(r+1)} - \alpha)$.
  • Distance 4 ($d=4$): The length $n$ remains unbounded for $r \ge 3$, using a more complex polynomial construction to increase error resilience while maintaining optimal locality.

By calculating the parameters $(n, k, d, r)$ and verifying they satisfy the equality $d = n - k - \lceil k/r \rceil + 2$, the authors demonstrate that these codes are theoretically perfect in terms of the redundancy-locality tradeoff.

Discussion and Future Work

This research proves that optimality in LRCs does not require short code lengths. By moving beyond Reed-Solomon frameworks to cyclic codes, the authors provide a "recipe" for building highly scalable, efficient storage codes.

However, the current construction is limited to small, fixed distances ($d=3$ and $d=4$). While these are the most common configurations in practical storage (protecting against 1 or 2 simultaneous failures), future research is needed to:

  1. Construct optimal LRCs with unbounded length for any constant distance $d$.
  2. Explore scenarios where the distance $d$ grows linearly with the code length $n$ while maintaining $n \gg q$.

Summary updated

Abstract

Like classical block codes, a locally repairable code also obeys the Singleton-type bound (we call a locally repairable code {\it optimal} if it achieves the Singleton-type bound). In the breakthrough work of \cite{TB14}, several classes of optimal locally repairable codes were constructed via subcodes of Reed-Solomon codes. Thus, the lengths of the codes given in \cite{TB14} are upper bounded by the code alphabet size $q$. Recently, it was proved through extension of construction in \cite{TB14} that length of $q$-ary optimal locally repairable codes can be $q+1$ in \cite{JMX17}. Surprisingly, \cite{BHHMV16} presented a few examples of $q$-ary optimal locally repairable codes of small distance and locality with code length achieving roughly $q^2$. Very recently, it was further shown in \cite{LMX17} that there exist $q$-ary optimal locally repairable codes with length bigger than $q+1$ and distance propositional 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 distance $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},
}
Figure