Locally Repairable Codes with Availability via Elliptic Function Fields

Technische Samenvatting: Lokaal Repareerbare Codes met Beschikbaarheid via Elliptische Functielichamen

Probleemstelling
Lokaal repareerbare codes (LRC's) met beschikbaarheid zijn cruciaal voor moderne gedistribueerde cloudopslagsystemen, omdat ze het herstel van verloren data mogelijk maken vanuit een kleine subset van knooppunten (lokaliteit), zelfs wanneer sommige knooppunten in die subset niet beschikbaar zijn (beschikbaarheid). Hoewel optimale LRC's met één herstelset ($t=1$) uitvoerig zijn bestudeerd, blijft het construeren van LRC's met meerdere herstelsets ($t \ge 2$) die optimale parameters en flexibele lokaliteit bereiken, een uitdaging. Eerdere constructies maakten vaak gebruik van maximale supersinguliere elliptische krommen of rationale functielichamen, wat de reeks toepasbare eindige velden en lokaliteitsparameters beperkte. Specifiek hadden bestaande methoden moeite om optimale LRC's te bieden over eindige velden met karakteristieken $p \equiv 1 \pmod{3}$ of $p \equiv 1 \pmod{4}$, en het construeren van LRC's met twee herstelsets met behulp van elliptische functielichamen resulteerde vaak in rigide parameters of vereiste gemodificeerde algebraïsch-geometrische code-technieken om een gebrek aan volledig splitsende plaatsen te compenseren.

Methodologie
De auteurs maken gebruik van algebraïsch-geometrische codes afgeleid van elliptische functielichamen en hun automorfismegroepen. De methodologie is verdeeld in twee hoofdroutes:

1. Optimale Klassieke LRC's ($t=1$): Het artikel introduceert het gebruik van ordinale elliptische krommen met een groot aantal rationale punten, specifiek die welke de Hasse-Weil-grens benaderen maar niet noodzakelijk maximaal zijn. De auteurs analyseren twee specifieke families van ordinale elliptische krommen gedefinieerd over $\mathbb{F}_{p^2}$:

   • Krommen gedefinieerd door $y^2 = x^3 + b$ waarbij $p = 3u^2 + 3u + 1$.
   • Krommen gedefinieerd door $y^2 = x^3 + ax$ waarbij $p = v^2 + 1$ en $p \equiv 1 \pmod 4$.
     Door gebruik te maken van de automorfismegroepen van deze krommen (specifiek de translatiegroep en stabilisator-subgroepen), construeren de auteurs subgroepen van de volledige automorfismegroep om vaste deellichamen te definiëren. Een nieuw aspect van hun aanpak is een alternatieve methode voor het bepalen van de functies $e_i$ die worden gebruikt in de codeconstructie. In tegenstelling tot eerdere werken die leunden op verzamelingen van volledig splitsende plaatsen en gemodificeerde algebraïsch-geometrische technieken, maakt deze methode volledig gebruik van subgroep-eigenschappen om ervoor te zorgen dat de functies voldoen aan de noodzakelijke voorwaarden voor lineaire onafhankelijkheid en omkeerbaarheid voor lokale herstel.

2. LRC's met Twee Herstelsets ($t=2$): De auteurs stellen een algemeen raamwerk voor het construeren van LRC's met twee herstelsets voor, gebruikmakend van de automorfismegroepen van elliptische functielichamen. Om beperkingen in eerdere raamwerken te overwinnen (waarbij de doorsnede van functieruimten te klein was), ontwikkelen ze een nieuwe constructie voor de functies $e_i$. Dit zorgt ervoor dat de functieruimten die corresponderen met de twee verschillende herstelsets binnen een gemeenschappelijke Riemann-Roch-ruimte liggen, waardoor een voldoende grote doorsnede wordt gegarandeerd. Het raamwerk maakt gebruik van subgroepen $G = T_H A_1 A_2$ (waarbij $T_H$ een translatiesubgroep is en $A_1, A_2$ stabilisator-subgroepen) om de codeparameters te definiëren. De constructie wordt toegepast op zowel maximale elliptische functielichamen als de specifieke ordinale krommen die in het eerste deel van het artikel worden geïntroduceerd.

Belangrijkste Bijdragen en Resultaten

• Nieuwe Families van Optimale Klassieke LRC's: Het artikel construeert verschillende nieuwe families van $q$-aire optimale LRC's met lengte $O(q + 2\sqrt{q})$ en flexibele lokaliteit.

  • Stelling 1 & 2: Deze stellingen stellen het bestaan vast van optimale $p^2$-aire LRC's met lokaliteit $r = h|A| - 1$ of $r = 2h - 1$. Cruciaal is dat deze constructies geldig zijn voor eindige velden met karakteristiek $p$ die voldoet aan $p \equiv 1 \pmod{12}$ (specifiek $p = 3u^2 + 3u + 1$ of $p = v^2 + 1$), een geval waarvoor er voorheen geen optimale LRC's beschikbaar waren via automorfismegroepen van elliptische krommen.
  • Vergelijking: Zoals gedetailleerd in Tabel I, vullen deze resultaten bestaand werk aan (bijvoorbeeld Li et al., Ma en Xing) door de reeks karakteristieken uit te breiden en verschillende lokaliteitsparameters over dezelfde eindige velden aan te bieden.

• Algemeen Raamwerk voor Beschikbaarheid $t=2$:

  • Propositie 3: Biedt een algemeen raamwerk voor het construeren van LRC's met twee herstelsets met behulp van elliptische functielichamen. Het stelt ondergrenzen vast voor de dimensie $k$ en de minimale afstand $d$ op basis van de groottes van de subgroepen $A_1$ en $A_2$.
  • Stelling 3 & 4: Pasen het raamwerk toe op maximale elliptische functielichamen respectievelijk de specifieke ordinale krommen uit Propositie 1. Deze stellingen leveren families van LRC's met twee herstelsets en lengte $O(q + 2\sqrt{q})$ (of $O(q^2 + 2q)$ voor de $q^2$-aire case).
  • Stelling 7: Presenteert een gespecialiseerde constructie over eindige velden met karakteristiek 2 (specifiek $q = 4^{2a+1}$), wat LRC's oplevert met lokaliteitsparen $(5, 6)$ en $(8, 3)$.

• Prestatiemetingen:

  • De geconstrueerde codes bereiken lengtes van $O(q + 2\sqrt{q})$ voor klassieke LRC's en $O(q^2 + 2q)$ voor LRC's met twee herstelsets.
  • Voor de $q^2$-aire LRC's met twee herstelsets wordt aangetoond dat de Singleton-defect $O\left(\frac{2\ell}{q^2 + 2q - 8\ell}\right)$ is, wat naar nul neigt naarmate $q$ toeneemt, wat wijst op asymptotische optimaliteit.
  • Numerieke voorbeelden (bijvoorbeeld over $\mathbb{F}_{5^6}$) tonen aan dat de geconstrueerde codes parameters kunnen bereiken die niet haalbaar waren met eerdere methoden (zoals die gebaseerd op rationale functielichamen).

Betekenis en Beweringen
Het artikel beweert de selectie van krommen die beschikbaar zijn voor het construeren van optimale lokaal repareerbare codes te verbreden. Door de focus te verschuiven van maximale supersinguliere krommen naar ordinale krommen met veel rationale punten, vullen de auteurs een gat in de literatuur met betrekking tot eindige velden met karakteristieken $p \equiv 1 \pmod 3$ en $p \equiv 1 \pmod 4$. Bovendien biedt het voorgestelde raamwerk voor LRC's met twee herstelsets een flexibelere aanpak dan eerdere methoden, waarbij de noodzaak voor gemodificeerde algebraïsch-geometrische code-technieken wordt vermeden en een bredere variëteit aan lokaliteitsparameters mogelijk wordt gemaakt. De auteurs merken op dat hoewel hun dimensiegrenzen conservatief zijn (zoals blijkt uit numerieke voorbeelden waarbij de werkelijke dimensies de theoretische ondergrenzen overtreffen), het raamwerk succesvol nieuwe families van codes met twee herstelsets genereert die voorheen onbereikbaar waren. Het werk benadrukt ook het potentieel voor het construeren van LRC's met meer dan twee herstelsets als een richting voor toekomstig onderzoek.