Locally Repairable Codes with Availability via Elliptic Function Fields

Technische Zusammenfassung: Lokal reparierbare Codes mit Verfügbarkeit durch elliptische Funktionenkörper

Problemstellung
Lokal reparierbare Codes (LRCs) mit Verfügbarkeit sind entscheidend für moderne verteilte Cloud-Speichersysteme und ermöglichen die Wiederherstellung verlorener Daten aus einer kleinen Teilmenge von Knoten (Lokalität), selbst wenn einige Knoten in dieser Teilmenge nicht verfügbar sind (Verfügbarkeit). Während optimale LRCs mit einem einzigen Wiederherstellungssatz ($t=1$) intensiv untersucht wurden, bleibt die Konstruktion von LRCs mit mehreren Wiederherstellungssätzen ($t \ge 2$), die optimale Parameter und flexible Lokalität erreichen, eine Herausforderung. Frühere Konstruktionen stützten sich oft auf maximale supersinguläre elliptische Kurven oder rationale Funktionenkörper, was den Bereich anwendbarer endlicher Körper und Lokalitätsparameter einschränkte. Insbesondere hatten bestehende Methoden Schwierigkeiten, optimale LRCs über endliche Körper mit Charakteristiken $p \equiv 1 \pmod{3}$ oder $p \equiv 1 \pmod{4}$ bereitzustellen, und die Konstruktion von LRCs mit zwei Wiederherstellungssätzen unter Verwendung elliptischer Funktionenkörper führte häufig zu starren Parametern oder erforderte modifizierte Techniken algebraisch-geometrischer Codes, um einen Mangel an vollständig zerfallenden Stellen auszugleichen.

Methodik
Die Autoren verwenden algebraisch-geometrische Codes, die von elliptischen Funktionenkörpern und ihren Automorphismengruppen abgeleitet sind. Die Methodik gliedert sich in zwei Hauptpfade:

1. Optimale klassische LRCs ($t=1$): Der Artikel führt die Verwendung gewöhnlicher elliptischer Kurven mit einer hohen Anzahl rationaler Punkte ein, insbesondere solcher, die die Hasse-Weil-Schranke annähern, aber nicht notwendigerweise maximal sind. Die Autoren analysieren zwei spezifische Familien gewöhnlicher elliptischer Kurven, die über $\mathbb{F}_{p^2}$ definiert sind:

   • Kurven, definiert durch $y^2 = x^3 + b$, wobei $p = 3u^2 + 3u + 1$.
   • Kurven, definiert durch $y^2 = x^3 + ax$, wobei $p = v^2 + 1$ und $p \equiv 1 \pmod 4$.
     Durch die Nutzung der Automorphismengruppen dieser Kurven (insbesondere der Translationsgruppe und der Stabilisator-Untergruppen) konstruieren die Autoren Untergruppen der vollen Automorphismengruppe, um feste Teilkörper zu definieren. Ein neuartiger Aspekt ihres Ansatzes ist eine alternative Methode zur Bestimmung der Funktionen $e_i$, die in der Codekonstruktion verwendet werden. Im Gegensatz zu früheren Arbeiten, die auf Mengen vollständig zerfallender Stellen und modifizierten Techniken algebraisch-geometrischer Codes beruhten, nutzt diese Methode die Untergruppeneigenschaften vollständig aus, um sicherzustellen, dass die Funktionen die notwendigen Bedingungen der linearen Unabhängigkeit und Invertierbarkeit für die lokale Wiederherstellung erfüllen.

2. LRCs mit zwei Wiederherstellungssätzen ($t=2$): Die Autoren schlagen ein allgemeines Rahmenwerk zur Konstruktion von LRCs mit zwei Wiederherstellungssätzen unter Verwendung der Automorphismengruppen elliptischer Funktionenkörper vor. Um Einschränkungen früherer Rahmenwerke zu überwinden (bei denen der Schnitt von Funktionenräumen zu klein war), entwickeln sie eine neuartige Konstruktion für die Funktionen $e_i$. Dies stellt sicher, dass die Funktionenräume, die den beiden verschiedenen Wiederherstellungssätzen entsprechen, innerhalb eines gemeinsamen Riemann-Roch-Raums liegen und somit einen hinreichend großen Schnitt garantieren. Das Rahmenwerk nutzt Untergruppen $G = T_H A_1 A_2$ (wobei $T_H$ eine Translationsuntergruppe und $A_1, A_2$ Stabilisator-Untergruppen sind), um die Codeparameter zu definieren. Die Konstruktion wird sowohl auf maximale elliptische Funktionenkörper als auch auf die spezifischen gewöhnlichen Kurven angewendet, die im ersten Teil des Artikels eingeführt wurden.

Hauptbeiträge und Ergebnisse

• Neue Familien optimaler klassischer LRCs: Der Artikel konstruiert mehrere neue Familien von $q$-ären optimalen LRCs mit Länge $O(q + 2\sqrt{q})$ und flexibler Lokalität.

  • Satz 1 & 2: Diese Sätze belegen die Existenz optimaler $p^2$-ärer LRCs mit der Lokalität $r = h|A| - 1$ oder $r = 2h - 1$. Entscheidend ist, dass diese Konstruktionen für endliche Körper mit Charakteristik $p$ gültig sind, die $p \equiv 1 \pmod{12}$ erfüllen (insbesondere $p = 3u^2 + 3u + 1$ oder $p = v^2 + 1$), ein Fall, für den bisher keine optimalen LRCs über Automorphismengruppen elliptischer Kurven verfügbar waren.
  • Vergleich: Wie in Tabelle I detailliert beschrieben, ergänzen diese Ergebnisse bestehende Arbeiten (z. B. Li et al., Ma und Xing), indem sie den Bereich der Charakteristiken erweitern und unterschiedliche Lokalitätsparameter über denselben endlichen Körpern anbieten.

• Allgemeines Rahmenwerk für Verfügbarkeit $t=2$:

  • Aussage 3: Bietet ein allgemeines Rahmenwerk zur Konstruktion von LRCs mit zwei Wiederherstellungssätzen unter Verwendung elliptischer Funktionenkörper. Es establishes untere Schranken für die Dimension $k$ und den minimalen Abstand $d$ basierend auf den Größen der Untergruppen $A_1$ und $A_2$.
  • Satz 3 & 4: Wenden das Rahmenwerk auf maximale elliptische Funktionenkörper bzw. die spezifischen gewöhnlichen Kurven aus Aussage 1 an. Diese Sätze liefern Familien von LRCs mit zwei Wiederherstellungssätzen und Länge $O(q + 2\sqrt{q})$ (bzw. $O(q^2 + 2q)$ für den $q^2$-ären Fall).
  • Satz 7: Präsentiert eine spezialisierte Konstruktion über endliche Körper der Charakteristik 2 (insbesondere $q = 4^{2a+1}$) und liefert LRCs mit Lokalitätspaaren $(5, 6)$ und $(8, 3)$.

• Leistungsindikatoren:

  • Die konstruierten Codes erreichen Längen von $O(q + 2\sqrt{q})$ für klassische LRCs und $O(q^2 + 2q)$ für LRCs mit zwei Wiederherstellungssätzen.
  • Für die $q^2$-ären LRCs mit zwei Wiederherstellungssätzen wird gezeigt, dass der Singleton-Defekt $O\left(\frac{2\ell}{q^2 + 2q - 8\ell}\right)$ beträgt, was gegen Null strebt, wenn $q$ zunimmt, was eine asymptotische Optimalität anzeigt.
  • Numerische Beispiele (z. B. über $\mathbb{F}_{5^6}$) zeigen, dass die konstruierten Codes Parameter erreichen können, die mit früheren Methoden (wie denen auf Basis rationaler Funktionenkörper) nicht erreichbar waren.

Bedeutung und Behauptungen
Der Artikel behauptet, die Auswahl an Kurven, die für die Konstruktion optimaler lokal reparierbarer Codes verfügbar sind, zu erweitern. Durch den Wechsel des Fokus von maximalen supersingulären Kurven zu gewöhnlichen Kurven mit vielen rationalen Punkten schließen die Autoren eine Lücke in der Literatur bezüglich endlicher Körper mit den Charakteristiken $p \equiv 1 \pmod 3$ und $p \equiv 1 \pmod 4$. Darüber hinaus bietet das vorgeschlagene Rahmenwerk für LRCs mit zwei Wiederherstellungssätzen einen flexibleren Ansatz als frühere Methoden, vermeidet die Notwendigkeit modifizierter Techniken algebraisch-geometrischer Codes und ermöglicht eine größere Vielfalt an Lokalitätsparametern. Die Autoren stellen fest, dass ihre Dimensionsgrenzen konservativ sind (wie numerische Beispiele belegen, bei denen die tatsächlichen Dimensionen die theoretischen unteren Schranken überschreiten), das Rahmenwerk jedoch erfolgreich neue Familien von Codes mit zwei Wiederherstellungssätzen generiert, die zuvor nicht erreichbar waren. Die Arbeit hebt zudem das Potenzial zur Konstruktion von LRCs mit mehr als zwei Wiederherstellungssätzen als Richtung für zukünftige Forschung hervor.