Locally Repairable Codes with Availability via Elliptic Function Fields

Resumen Técnico: Códigos Localmente Reparables con Disponibilidad mediante Campos de Funciones Elípticas

Enunciado del Problema
Los códigos localmente reparables (LRCs) con disponibilidad son críticos para los sistemas modernos de almacenamiento en la nube distribuida, permitiendo la recuperación de datos perdidos a partir de un pequeño subconjunto de nodos (localidad) incluso cuando algunos nodos de ese subconjunto no están disponibles (disponibilidad). Aunque los LRCs óptimos con un único conjunto de recuperación ($t=1$) han sido estudiados extensamente, la construcción de LRCs con múltiples conjuntos de recuperación ($t \ge 2$) que logren parámetros óptimos y localidad flexible sigue siendo un desafío. Las construcciones anteriores a menudo dependían de curvas elípticas supersingulares maximales o de campos de funciones racionales, lo que limitaba el rango de campos finitos aplicables y los parámetros de localidad. Específicamente, los métodos existentes tenían dificultades para proporcionar LRCs óptimos sobre campos finitos con características $p \equiv 1 \pmod{3}$ o $p \equiv 1 \pmod{4}$, y la construcción de LRCs con dos conjuntos de recuperación utilizando campos de funciones elípticas a menudo resultaba en parámetros rígidos o requería técnicas modificadas de códigos de geometría algebraica para compensar la falta de lugares completamente descompuestos.

Metodología
Los autores emplean códigos de geometría algebraica derivados de campos de funciones elípticas y sus grupos de automorfismos. La metodología se divide en dos vías principales:

1. LRCs Clásicos Óptimos ($t=1$): El artículo introduce el uso de curvas elípticas ordinarias con un alto número de puntos racionales, específicamente aquellas que se acercan al límite de Hasse-Weil pero no son necesariamente maximales. Los autores analizan dos familias específicas de curvas elípticas ordinarias definidas sobre $\mathbb{F}_{p^2}$:

   • Curvas definidas por $y^2 = x^3 + b$ donde $p = 3u^2 + 3u + 1$.
   • Curvas definidas por $y^2 = x^3 + ax$ donde $p = v^2 + 1$ y $p \equiv 1 \pmod 4$.
     Al utilizar los grupos de automorfismos de estas curvas (específicamente el grupo de traslación y los subgrupos estabilizadores), los autores construyen subgrupos del grupo completo de automorfismos para definir subcampos fijos. Un aspecto novedoso de su enfoque es un método alternativo para determinar las funciones $e_i$ utilizadas en la construcción del código. A diferencia de trabajos anteriores que dependían de conjuntos de lugares completamente descompuestos y técnicas modificadas de geometría algebraica, este método explota plenamente las propiedades de los subgrupos para asegurar que las funciones satisfagan las condiciones necesarias de independencia lineal e invertibilidad para la recuperación local.

2. LRCs con Dos Conjuntos de Recuperación ($t=2$): Los autores proponen un marco general para construir LRCs con dos conjuntos de recuperación utilizando los grupos de automorfismos de campos de funciones elípticas. Para superar las limitaciones en marcos anteriores (donde la intersección de espacios de funciones era demasiado pequeña), diseñan una construcción novedosa para las funciones $e_i$. Esto asegura que los espacios de funciones correspondientes a los dos conjuntos de recuperación distintos residan dentro de un espacio de Riemann-Roch común, garantizando una intersección suficientemente grande. El marco utiliza subgrupos $G = T_H A_1 A_2$ (donde $T_H$ es un subgrupo de traslación y $A_1, A_2$ son subgrupos estabilizadores) para definir los parámetros del código. La construcción se aplica tanto a campos de funciones elípticas maximales como a las curvas ordinarias específicas introducidas en la primera parte del artículo.

Contribuciones y Resultados Clave

• Nuevas Familias de LRCs Clásicos Óptimos: El artículo construye varias nuevas familias de LRCs óptimos $q$-arios con longitud $O(q + 2\sqrt{q})$ y localidad flexible.

  • Teoremas 1 y 2: Estos teoremas establecen la existencia de LRCs óptimos $p^2$-arios con localidad $r = h|A| - 1$ o $r = 2h - 1$. Crucialmente, estas construcciones son válidas para campos finitos con característica $p$ que satisfacen $p \equiv 1 \pmod{12}$ (específicamente $p = 3u^2 + 3u + 1$ o $p = v^2 + 1$), un caso para el cual no existían previamente LRCs óptimos disponibles mediante grupos de automorfismos de curvas elípticas.
  • Comparación: Como se detalla en la Tabla I, estos resultados complementan el trabajo existente (por ejemplo, Li et al., Ma y Xing) expandiendo el rango de características y ofreciendo diferentes parámetros de localidad sobre los mismos campos finitos.

• Marco General para Disponibilidad $t=2$:

  • Proposición 3: Proporciona un marco general para construir LRCs con dos conjuntos de recuperación utilizando campos de funciones elípticas. Establece cotas inferiores para la dimensión $k$ y la distancia mínima $d$ basadas en los tamaños de los subgrupos $A_1$ y $A_2$.
  • Teoremas 3 y 4: Aplican el marco a campos de funciones elípticas maximales y a las curvas ordinarias específicas de la Proposición 1, respectivamente. Estos teoremas generan familias de LRCs con dos conjuntos de recuperación y longitud $O(q + 2\sqrt{q})$ (o $O(q^2 + 2q)$ para el caso $q^2$-ario).
  • Teorema 7: Presenta una construcción especializada sobre campos finitos de característica 2 (específicamente $q = 4^{2a+1}$), generando LRCs con pares de localidad $(5, 6)$ y $(8, 3)$.

• Métricas de Rendimiento:

  • Los códigos construidos alcanzan longitudes de $O(q + 2\sqrt{q})$ para LRCs clásicos y $O(q^2 + 2q)$ para LRCs con dos conjuntos de recuperación.
  • Para los LRCs $q^2$-arios con dos conjuntos de recuperación, se muestra que el defecto de Singleton es $O\left(\frac{2\ell}{q^2 + 2q - 8\ell}\right)$, lo cual tiende a cero a medida que $q$ aumenta, indicando optimalidad asintótica.
  • Los ejemplos numéricos (por ejemplo, sobre $\mathbb{F}_{5^6}$) demuestran que los códigos construidos pueden alcanzar parámetros no alcanzables por métodos anteriores (como los basados en campos de funciones racionales).

Significado y Afirmaciones
El artículo afirma ampliar la selección de curvas disponibles para construir códigos localmente reparables óptimos. Al desplazar el enfoque de las curvas supersingulares maximales a curvas ordinarias con muchos puntos racionales, los autores llenan un vacío en la literatura respecto a campos finitos con características $p \equiv 1 \pmod 3$ y $p \equiv 1 \pmod 4$. Además, el marco propuesto para LRCs con dos conjuntos de recuperación ofrece un enfoque más flexible que los métodos anteriores, evitando la necesidad de técnicas modificadas de códigos de geometría algebraica y permitiendo una mayor variedad de parámetros de localidad. Los autores señalan que, aunque sus cotas de dimensión son conservadoras (como lo demuestran los ejemplos numéricos donde las dimensiones reales superan las cotas inferiores teóricas), el marco genera con éxito nuevas familias de códigos con dos conjuntos de recuperación que antes eran inalcanzables. El trabajo también destaca el potencial para construir LRCs con más de dos conjuntos de recuperación como una dirección para futuras investigaciones.