Construction of asymptotically good locally repairable codes via automorphism groups of function fields

Xudong Li, Liming Ma, Chaoping Xing

Abstract

Locally repairable codes (LRCs) are critical for distributed storage systems, yet their asymptotic behavior remains under-explored. This paper presents a novel construction of asymptotically good LRCs by leveraging the automorphism groups of function field towers, specifically the Garcia-Stichtenoth tower. This approach provides greater flexibility in locality parameters and demonstrates that these algebraic geometry (AG) codes can exceed the Gilbert-Varshamov (GV) bound for sufficiently large alphabet sizes.

Introduction: The Challenge of Asymptotic Locality

In modern cloud storage, data is distributed across multiple nodes. To ensure reliability while minimizing the "repair bandwidth"—the amount of data transferred to recover a single failed node—Locally Repairable Codes (LRCs) are employed. A code has locality $r$ if any single symbol can be recovered by accessing at most $r$ other symbols.

While many constructions exist for finite-length LRCs, understanding their performance as the code length $n$ approaches infinity (asymptotic behavior) is a significant theoretical challenge. Previous constructive bounds were often constrained by rigid mathematical requirements on the locality $r$. This research addresses this gap by providing a more versatile construction method.

Methodology: Leveraging Function Field Towers

The authors utilize Algebraic Geometry (AG) codes derived from the Garcia-Stichtenoth function field tower, which is known for its asymptotic optimality (reaching the Drinfeld-Vlăduţ bound). The core innovation lies in the use of automorphism groups of these function fields.

By analyzing the subgroup structure of the tower's decomposition group, the authors can define coordinate subsets that satisfy the locality requirement. This technique decouples the locality $r$ from the strict constraints seen in earlier models, allowing for a wider range of localities, such as $r+1$ dividing $\sqrt{q}$ or $\sqrt{q}-1$.

Key Results: Surpassing the GV Bound

The primary contribution is a concrete lower bound for the rate $R$ of these constructed LRCs (Theorem 1.1). Numerical analysis using SageMath confirms that these AG codes outperform the Gilbert-Varshamov (GV) type bound for LRCs—a standard benchmark for random codes—across various parameters.

Comparison of the proposed LRC AG codes vs. the LRC GV bound for $q=3^6$ and $r=2$.

As shown in Figure 1, for $q = 3^6$ and $r = 2$, the AG codes (green line) maintain a higher rate than the GV bound (red dotted line) for most relative distances $\delta$. This advantage becomes even more pronounced as the alphabet size and locality increase.

Comparison for $q=2^{12}$ and $r=6$, showing the AG codes significantly outperforming the GV bound.

In Figure 2 ($q = 2^{12}, r = 6$), the gap between the AG construction and the GV bound is substantial. Furthermore, the authors prove (Proposition 1.3) that if the locality $r$ falls within a certain logarithmic range relative to $q$, the AG bound will consistently exceed the GV bound for all sufficiently large $q$.

Limitations and Future Outlook

Despite its strengths, the construction has specific requirements:

  • Alphabet Constraints: The field size $q$ must be a square (e.g., $q = \ell^2$), a common constraint in AG code theory.
  • Small Locality Thresholds: For very small localities (e.g., $r=2, 3$), the AG bound may not surpass the GV bound for all field sizes.
  • Implementation Complexity: While theoretically explicit, implementing AG codes from high-level towers is computationally more demanding than standard Reed-Solomon codes.

Future research may focus on optimizing decoding algorithms for these specific structures to make them more practical for real-world distributed storage applications.

Summary updated

Abstract

Locally repairable codes have been investigated extensively in recent years due to practical application in distributed storage as well as theoretical interest. However, not much work on asymptotical behavior of locally repairable codes has been done until now. In particular, there is a little result on constructive lower bound on asymptotical behavior of locally repairable codes. In this paper, we extend the construction given in \cite{BTV17} via automorphism groups of function field towers. The main advantage of our construction is to allow more flexibility of locality. Furthermore, we show that the Gilbert-Varshamov type bound on locally repairable codes can be improved for all sufficiently large alphabet size $q$.
BibTeX
@article{li2019construction,
  author = {Xudong Li and Liming Ma and Chaoping Xing},
  title = {{Construction of asymptotically good locally repairable codes via automorphism groups of function fields}},
  journal = {IEEE Transactions on Information Theory},
  year = {2019},
  doi = {10.1109/tit.2019.2923609},
}
Figure