Locally Repairable Codes with Availability via Elliptic Function Fields

Technical Summary: Locally Repairable Codes with Availability via Elliptic Function Fields

Problem Statement
Locally repairable codes (LRCs) with availability are critical for modern distributed cloud storage systems, enabling the recovery of lost data from a small subset of nodes (locality) even when some nodes in that subset are unavailable (availability). While optimal LRCs with a single recovering set ($t=1$) have been extensively studied, constructing LRCs with multiple recovering sets ($t \ge 2$) that achieve optimal parameters and flexible locality remains a challenge. Previous constructions often relied on maximal supersingular elliptic curves or rational function fields, which limited the range of applicable finite fields and locality parameters. Specifically, existing methods struggled to provide optimal LRCs over finite fields with characteristics $p \equiv 1 \pmod{3}$ or $p \equiv 1 \pmod{4}$, and constructing LRCs with two recovering sets using elliptic function fields often resulted in rigid parameters or required modified algebraic geometry code techniques to compensate for a lack of completely splitting places.

Methodology
The authors employ algebraic geometry codes derived from elliptic function fields and their automorphism groups. The methodology is divided into two primary tracks:

1. Optimal Classical LRCs ($t=1$): The paper introduces the use of ordinary elliptic curves with a high number of rational points, specifically those approaching the Hasse-Weil bound but not necessarily maximal. The authors analyze two specific families of ordinary elliptic curves defined over $\mathbb{F}_{p^2}$:

   • Curves defined by $y^2 = x^3 + b$ where $p = 3u^2 + 3u + 1$.
   • Curves defined by $y^2 = x^3 + ax$ where $p = v^2 + 1$ and $p \equiv 1 \pmod 4$.
     By utilizing the automorphism groups of these curves (specifically the translation group and stabilizer subgroups), the authors construct subgroups of the full automorphism group to define fixed subfields. A novel aspect of their approach is an alternative method for determining the functions $e_i$ used in the code construction. Unlike previous works that relied on sets of completely splitting places and modified algebraic geometry techniques, this method fully exploits subgroup properties to ensure the functions satisfy the necessary linear independence and invertibility conditions for local recovery.

2. LRCs with Two Recovering Sets ($t=2$): The authors propose a general framework for constructing LRCs with two recovering sets using the automorphism groups of elliptic function fields. To overcome limitations in previous frameworks (where the intersection of function spaces was too small), they devise a novel construction for the functions $e_i$. This ensures that the function spaces corresponding to the two distinct recovering sets lie within a common Riemann-Roch space, guaranteeing a sufficiently large intersection. The framework utilizes subgroups $G = T_H A_1 A_2$ (where $T_H$ is a translation subgroup and $A_1, A_2$ are stabilizer subgroups) to define the code parameters. The construction is applied to both maximal elliptic function fields and the specific ordinary curves introduced in the first part of the paper.

Key Contributions and Results

• New Families of Optimal Classical LRCs: The paper constructs several new families of $q$-ary optimal LRCs with length $O(q + 2\sqrt{q})$ and flexible locality.

  • Theorem 1 & 2: These theorems establish the existence of optimal $p^2$-ary LRCs with locality $r = h|A| - 1$ or $r = 2h - 1$. Crucially, these constructions are valid for finite fields with characteristic $p$ satisfying $p \equiv 1 \pmod{12}$ (specifically $p = 3u^2 + 3u + 1$ or $p = v^2 + 1$), a case for which no optimal LRCs were previously available via automorphism groups of elliptic curves.
  • Comparison: As detailed in Table I, these results complement existing work (e.g., Li et al., Ma and Xing) by expanding the range of characteristics and offering different locality parameters over the same finite fields.

• General Framework for Availability $t=2$:

  • Proposition 3: Provides a general framework for constructing LRCs with two recovering sets using elliptic function fields. It establishes lower bounds on the dimension $k$ and minimum distance $d$ based on the sizes of the subgroups $A_1$ and $A_2$.
  • Theorem 3 & 4: Apply the framework to maximal elliptic function fields and the specific ordinary curves from Proposition 1, respectively. These theorems yield families of LRCs with two recovering sets and length $O(q + 2\sqrt{q})$ (or $O(q^2 + 2q)$ for the $q^2$-ary case).
  • Theorem 7: Presents a specialized construction over finite fields of characteristic 2 (specifically $q = 4^{2a+1}$), yielding LRCs with locality pairs $(5, 6)$ and $(8, 3)$.

• Performance Metrics:

  • The constructed codes achieve lengths of $O(q + 2\sqrt{q})$ for classical LRCs and $O(q^2 + 2q)$ for LRCs with two recovering sets.
  • For the $q^2$-ary LRCs with two recovering sets, the Singleton-defect is shown to be $O\left(\frac{2\ell}{q^2 + 2q - 8\ell}\right)$, which tends to zero as $q$ increases, indicating asymptotic optimality.
  • Numerical examples (e.g., over $\mathbb{F}_{5^6}$) demonstrate that the constructed codes can achieve parameters not attainable by previous methods (such as those based on rational function fields).

Significance and Claims
The paper claims to broaden the selection of curves available for constructing optimal locally repairable codes. By shifting focus from maximal supersingular curves to ordinary curves with many rational points, the authors fill a gap in the literature regarding finite fields with characteristics $p \equiv 1 \pmod 3$ and $p \equiv 1 \pmod 4$. Furthermore, the proposed framework for LRCs with two recovering sets offers a more flexible approach than previous methods, avoiding the need for modified algebraic geometry code techniques and allowing for a wider variety of locality parameters. The authors note that while their dimension bounds are conservative (as evidenced by numerical examples where actual dimensions exceed the theoretical lower bounds), the framework successfully generates new families of codes with two recovering sets that were previously unattainable. The work also highlights the potential for constructing LRCs with more than two recovering sets as a direction for future research.