Locally Repairable Codes with Availability via Elliptic Function Fields

Résumé Technique : Codes Localement Réparables avec Disponibilité via des Corps de Fonctions Elliptiques

Énoncé du Problème
Les codes localement réparables (LRC) avec disponibilité sont essentiels pour les systèmes modernes de stockage cloud distribué, permettant la récupération de données perdues à partir d'un petit sous-ensemble de nœuds (localité) même lorsque certains nœuds de ce sous-ensemble sont indisponibles (disponibilité). Bien que les LRC optimaux avec un seul ensemble de récupération ($t=1$) aient fait l'objet d'études approfondies, la construction de LRC avec plusieurs ensembles de récupération ($t \ge 2$) atteignant des paramètres optimaux et une localité flexible demeure un défi. Les constructions antérieures reposaient souvent sur des courbes elliptiques supersingulières maximales ou des corps de fonctions rationnels, ce qui limitait la gamme des corps finis applicables et des paramètres de localité. Plus précisément, les méthodes existantes peinaient à fournir des LRC optimaux sur des corps finis de caractéristiques $p \equiv 1 \pmod{3}$ ou $p \equiv 1 \pmod{4}$, et la construction de LRC avec deux ensembles de récupération utilisant des corps de fonctions elliptiques aboutissait souvent à des paramètres rigides ou nécessitait des techniques modifiées de codes géométriques algébriques pour compenser l'absence de places totalement décomposées.

Méthodologie
Les auteurs emploient des codes géométriques algébriques dérivés de corps de fonctions elliptiques et de leurs groupes d'automorphismes. La méthodologie est divisée en deux axes principaux :

1. LRC Classiques Optimaux ($t=1$) : L'article introduit l'utilisation de courbes elliptiques ordinaires possédant un grand nombre de points rationnels, spécifiquement celles s'approchant de la borne de Hasse-Weil mais pas nécessairement maximales. Les auteurs analysent deux familles spécifiques de courbes elliptiques ordinaires définies sur $\mathbb{F}_{p^2}$ :

   • Courbes définies par $y^2 = x^3 + b$ où $p = 3u^2 + 3u + 1$.
   • Courbes définies par $y^2 = x^3 + ax$ où $p = v^2 + 1$ et $p \equiv 1 \pmod 4$.
     En exploitant les groupes d'automorphismes de ces courbes (spécifiquement le groupe de translation et les sous-groupes stabilisateurs), les auteurs construisent des sous-groupes du groupe d'automorphismes complet pour définir des sous-corps fixes. Un aspect novateur de leur approche est une méthode alternative pour déterminer les fonctions $e_i$ utilisées dans la construction du code. Contrairement aux travaux antérieurs qui reposaient sur des ensembles de places totalement décomposées et des techniques modifiées de codes géométriques algébriques, cette méthode exploite pleinement les propriétés des sous-groupes pour garantir que les fonctions satisfont les conditions nécessaires d'indépendance linéaire et d'inversibilité pour la récupération locale.

2. LRC avec Deux Ensembles de Récupération ($t=2$) : Les auteurs proposent un cadre général pour construire des LRC avec deux ensembles de récupération en utilisant les groupes d'automorphismes des corps de fonctions elliptiques. Pour surmonter les limitations des cadres précédents (où l'intersection des espaces de fonctions était trop petite), ils conçoivent une construction novatrice pour les fonctions $e_i$. Cela garantit que les espaces de fonctions correspondant aux deux ensembles de récupération distincts se situent dans un même espace de Riemann-Roch, assurant une intersection suffisamment grande. Le cadre utilise des sous-groupes $G = T_H A_1 A_2$ (où $T_H$ est un sous-groupe de translation et $A_1, A_2$ sont des sous-groupes stabilisateurs) pour définir les paramètres du code. La construction est appliquée à la fois aux corps de fonctions elliptiques maximaux et aux courbes ordinaires spécifiques introduites dans la première partie de l'article.

Contributions et Résultats Clés

• Nouvelles Familles de LRC Classiques Optimaux : L'article construit plusieurs nouvelles familles de LRC optimaux $q$-aires de longueur $O(q + 2\sqrt{q})$ et de localité flexible.

  • Théorèmes 1 & 2 : Ces théorèmes établissent l'existence de LRC optimaux $p^2$-aires avec une localité $r = h|A| - 1$ ou $r = 2h - 1$. Crucialement, ces constructions sont valables pour des corps finis de caractéristique $p$ satisfaisant $p \equiv 1 \pmod{12}$ (spécifiquement $p = 3u^2 + 3u + 1$ ou $p = v^2 + 1$), un cas pour lequel aucun LRC optimal n'était précédemment disponible via les groupes d'automorphismes de courbes elliptiques.
  • Comparaison : Comme détaillé dans le Tableau I, ces résultats complètent les travaux existants (par exemple, Li et al., Ma et Xing) en élargissant la gamme des caractéristiques et en offrant différents paramètres de localité sur les mêmes corps finis.

• Cadre Général pour la Disponibilité $t=2$ :

  • Proposition 3 : Fournit un cadre général pour construire des LRC avec deux ensembles de récupération en utilisant des corps de fonctions elliptiques. Elle établit des bornes inférieures sur la dimension $k$ et la distance minimale $d$ basées sur les tailles des sous-groupes $A_1$ et $A_2$.
  • Théorèmes 3 & 4 : Appliquent le cadre aux corps de fonctions elliptiques maximaux et aux courbes ordinaires spécifiques de la Proposition 1, respectivement. Ces théorèmes produisent des familles de LRC avec deux ensembles de récupération et de longueur $O(q + 2\sqrt{q})$ (ou $O(q^2 + 2q)$ pour le cas $q^2$-aire).
  • Théorème 7 : Présente une construction spécialisée sur des corps finis de caractéristique 2 (spécifiquement $q = 4^{2a+1}$), produisant des LRC avec des paires de localité $(5, 6)$ et $(8, 3)$.

• Métriques de Performance :

  • Les codes construits atteignent des longueurs de $O(q + 2\sqrt{q})$ pour les LRC classiques et $O(q^2 + 2q)$ pour les LRC avec deux ensembles de récupération.
  • Pour les LRC $q^2$-aires avec deux ensembles de récupération, le défaut de Singleton est montré comme étant $O\left(\frac{2\ell}{q^2 + 2q - 8\ell}\right)$, ce qui tend vers zéro lorsque $q$ augmente, indiquant une optimalité asymptotique.
  • Des exemples numériques (par exemple, sur $\mathbb{F}_{5^6}$) démontrent que les codes construits peuvent atteindre des paramètres inaccessibles par les méthodes précédentes (telles que celles basées sur des corps de fonctions rationnels).

Signification et Revendications
L'article revendique élargir la sélection de courbes disponibles pour construire des codes localement réparables optimaux. En déplaçant le focus des courbes supersingulières maximales vers des courbes ordinaires possédant de nombreux points rationnels, les auteurs comblent une lacune dans la littérature concernant les corps finis de caractéristiques $p \equiv 1 \pmod 3$ et $p \equiv 1 \pmod 4$. De plus, le cadre proposé pour les LRC avec deux ensembles de récupération offre une approche plus flexible que les méthodes antérieures, évitant le besoin de techniques modifiées de codes géométriques algébriques et permettant une plus grande variété de paramètres de localité. Les auteurs notent que bien que leurs bornes de dimension soient conservatrices (comme en témoignent les exemples numériques où les dimensions réelles dépassent les bornes inférieures théoriques), le cadre génère avec succès de nouvelles familles de codes avec deux ensembles de récupération qui étaient précédemment inaccessibles. Le travail met également en évidence le potentiel de construction de LRC avec plus de deux ensembles de récupération comme une direction pour la recherche future.