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.
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.
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