Locally Repairable Codes with Availability via Elliptic Function Fields

Sintesi Tecnica: Codici Localmente Riparabili con Disponibilità tramite Campi di Funzioni Ellittiche

Enunciato del Problema
I codici localmente riparabili (LRC) con disponibilità sono fondamentali per i moderni sistemi di archiviazione cloud distribuiti, consentendo il recupero di dati persi da un piccolo sottoinsieme di nodi (località) anche quando alcuni nodi di tale sottoinsieme non sono disponibili (disponibilità). Sebbene gli LRC ottimali con un singolo insieme di recupero ($t=1$) siano stati ampiamente studiati, la costruzione di LRC con più insiemi di recupero ($t \ge 2$) che raggiungano parametri ottimali e località flessibile rimane una sfida. Le costruzioni precedenti si basavano spesso su curve ellittiche supersingolari massimali o su campi di funzioni razionali, il che limitava la gamma di campi finiti applicabili e i parametri di località. Nello specifico, i metodi esistenti faticavano a fornire LRC ottimali su campi finiti con caratteristiche $p \equiv 1 \pmod{3}$ o $p \equiv 1 \pmod{4}$, e la costruzione di LRC con due insiemi di recupero utilizzando campi di funzioni ellittiche spesso risultava in parametri rigidi o richiedeva tecniche modificate di codici geometrici algebrici per compensare la mancanza di posti che si spezzano completamente.

Metodologia
Gli autori impiegano codici geometrici algebrici derivati da campi di funzioni ellittiche e dai loro gruppi di automorfismi. La metodologia è divisa in due percorsi principali:

1. LRC Classici Ottimali ($t=1$): Il paper introduce l'uso di curve ellittiche ordinarie con un alto numero di punti razionali, in particolare quelle che si avvicinano al limite di Hasse-Weil ma non sono necessariamente massimali. Gli autori analizzano due famiglie specifiche di curve ellittiche ordinarie definite su $\mathbb{F}_{p^2}$:

   • Curve definite da $y^2 = x^3 + b$ dove $p = 3u^2 + 3u + 1$.
   • Curve definite da $y^2 = x^3 + ax$ dove $p = v^2 + 1$ e $p \equiv 1 \pmod 4$.
     Sfruttando i gruppi di automorfismi di queste curve (in particolare il gruppo di traslazione e i sottogruppi stabilizzatori), gli autori costruiscono sottogruppi del gruppo di automorfismi completo per definire sottocampi fissi. Un aspetto innovativo del loro approccio è un metodo alternativo per determinare le funzioni $e_i$ utilizzate nella costruzione del codice. A differenza di lavori precedenti che si basavano su insiemi di posti che si spezzano completamente e su tecniche modificate di codici geometrici algebrici, questo metodo sfrutta appieno le proprietà dei sottogruppi per garantire che le funzioni soddisfino le necessarie condizioni di indipendenza lineare e invertibilità per il recupero locale.

2. LRC con Due Insiemi di Recupero ($t=2$): Gli autori propongono un quadro generale per la costruzione di LRC con due insiemi di recupero utilizzando i gruppi di automorfismi dei campi di funzioni ellittiche. Per superare le limitazioni dei quadri precedenti (dove l'intersezione degli spazi di funzioni era troppo piccola), essi ideano una costruzione innovativa per le funzioni $e_i$. Ciò garantisce che gli spazi di funzioni corrispondenti ai due distinti insiemi di recupero risiedano all'interno di uno spazio comune di Riemann-Roch, garantendo un'intersezione sufficientemente ampia. Il quadro utilizza sottogruppi $G = T_H A_1 A_2$ (dove $T_H$ è un sottogruppo di traslazione e $A_1, A_2$ sono sottogruppi stabilizzatori) per definire i parametri del codice. La costruzione è applicata sia ai campi di funzioni ellittici massimali sia alle curve ordinarie specifiche introdotte nella prima parte del paper.

Contributi e Risultati Chiave

• Nuove Famiglie di LRC Classici Ottimali: Il paper costruisce diverse nuove famiglie di LRC ottimali $q$-ari con lunghezza $O(q + 2\sqrt{q})$ e località flessibile.

  • Teorema 1 e 2: Questi teoremi stabiliscono l'esistenza di LRC ottimali $p^2$-ari con località $r = h|A| - 1$ o $r = 2h - 1$. Crucialmente, queste costruzioni sono valide per campi finiti con caratteristica $p$ tale che $p \equiv 1 \pmod{12}$ (specificamente $p = 3u^2 + 3u + 1$ o $p = v^2 + 1$), un caso per il quale non erano precedentemente disponibili LRC ottimali tramite gruppi di automorfismi di curve ellittiche.
  • Confronto: Come dettagliato nella Tabella I, questi risultati completano il lavoro esistente (ad esempio, Li et al., Ma e Xing) ampliando la gamma di caratteristiche e offrendo diversi parametri di località sugli stessi campi finiti.

• Quadro Generale per la Disponibilità $t=2$:

  • Proposizione 3: Fornisce un quadro generale per la costruzione di LRC con due insiemi di recupero utilizzando campi di funzioni ellittiche. Stabilisce limiti inferiori sulla dimensione $k$ e sulla distanza minima $d$ basati sulle dimensioni dei sottogruppi $A_1$ e $A_2$.
  • Teorema 3 e 4: Applicano il quadro ai campi di funzioni ellittici massimali e alle curve ordinarie specifiche della Proposizione 1, rispettivamente. Questi teoremi producono famiglie di LRC con due insiemi di recupero e lunghezza $O(q + 2\sqrt{q})$ (o $O(q^2 + 2q)$ per il caso $q^2$-ario).
  • Teorema 7: Presenta una costruzione specializzata su campi finiti di caratteristica 2 (specificamente $q = 4^{2a+1}$), producendo LRC con coppie di località $(5, 6)$ e $(8, 3)$.

• Metriche di Prestazione:

  • I codici costruiti raggiungono lunghezze di $O(q + 2\sqrt{q})$ per gli LRC classici e $O(q^2 + 2q)$ per gli LRC con due insiemi di recupero.
  • Per gli LRC $q^2$-ari con due insiemi di recupero, il difetto di Singleton è mostrato essere $O\left(\frac{2\ell}{q^2 + 2q - 8\ell}\right)$, che tende a zero all'aumentare di $q$, indicando ottimalità asintotica.
  • Esempi numerici (ad esempio, su $\mathbb{F}_{5^6}$) dimostrano che i codici costruiti possono raggiungere parametri non ottenibili con i metodi precedenti (come quelli basati su campi di funzioni razionali).

Significato e Affermazioni
Il paper afferma di ampliare la selezione di curve disponibili per la costruzione di codici localmente riparabili ottimali. Spostando l'attenzione dalle curve supersingolari massimali alle curve ordinarie con molti punti razionali, gli autori colmano una lacuna nella letteratura riguardante i campi finiti con caratteristiche $p \equiv 1 \pmod 3$ e $p \equiv 1 \pmod 4$. Inoltre, il quadro proposto per gli LRC con due insiemi di recupero offre un approccio più flessibile rispetto ai metodi precedenti, evitando la necessità di tecniche modificate di codici geometrici algebrici e permettendo una più ampia varietà di parametri di località. Gli autori notano che, sebbene i loro limiti di dimensione siano conservativi (come dimostrato dagli esempi numerici in cui le dimensioni effettive superano i limiti inferiori teorici), il quadro genera con successo nuove famiglie di codici con due insiemi di recupero che erano precedentemente irraggiungibili. Il lavoro evidenzia inoltre il potenziale per la costruzione di LRC con più di due insiemi di recupero come direzione per ricerche future.