Locally Repairable Codes with Availability via Elliptic Function Fields

Resumo Técnico: Códigos Localmente Reparáveis com Disponibilidade via Campos de Funções Elípticas

Enunciação do Problema
Códigos localmente reparáveis (LRCs) com disponibilidade são críticos para sistemas modernos de armazenamento em nuvem distribuída, permitindo a recuperação de dados perdidos a partir de um pequeno subconjunto de nós (localidade) mesmo quando alguns nós nesse subconjunto estão indisponíveis (disponibilidade). Embora LRCs ótimos com um único conjunto de recuperação ($t=1$) tenham sido extensivamente estudados, a construção de LRCs com múltiplos conjuntos de recuperação ($t \ge 2$) que alcancem parâmetros ótimos e localidade flexível permanece um desafio. Construções anteriores frequentemente dependiam de curvas elípticas supersingulares maximais ou campos de funções racionais, o que limitava a gama de corpos finitos aplicáveis e parâmetros de localidade. Especificamente, os métodos existentes lutavam para fornecer LRCs ótimos sobre corpos finitos com características $p \equiv 1 \pmod{3}$ ou $p \equiv 1 \pmod{4}$, e a construção de LRCs com dois conjuntos de recuperação usando campos de funções elípticas frequentemente resultava em parâmetros rígidos ou exigia técnicas modificadas de códigos de geometria algébrica para compensar a falta de lugares completamente decompostos.

Metodologia
Os autores empregam códigos de geometria algébrica derivados de campos de funções elípticas e seus grupos de automorfismos. A metodologia é dividida em duas trilhas principais:

1. LRCs Clássicos Ótimos ($t=1$): O artigo introduz o uso de curvas elípticas ordinárias com um alto número de pontos racionais, especificamente aquelas que se aproximam do limite de Hasse-Weil, mas não necessariamente maximais. Os autores analisam duas famílias específicas de curvas elípticas ordinárias definidas sobre $\mathbb{F}_{p^2}$:

   • Curvas definidas por $y^2 = x^3 + b$ onde $p = 3u^2 + 3u + 1$.
   • Curvas definidas por $y^2 = x^3 + ax$ onde $p = v^2 + 1$ e $p \equiv 1 \pmod 4$.
     Ao utilizar os grupos de automorfismos dessas curvas (especificamente o grupo de translação e subgrupos estabilizadores), os autores constroem subgrupos do grupo de automorfismo total para definir subcampos fixos. Um aspecto novo de sua abordagem é um método alternativo para determinar as funções $e_i$ usadas na construção do código. Diferentemente de trabalhos anteriores que dependiam de conjuntos de lugares completamente decompostos e técnicas modificadas de geometria algébrica, este método explora plenamente as propriedades dos subgrupos para garantir que as funções satisfaçam as condições necessárias de independência linear e invertibilidade para a recuperação local.

2. LRCs com Dois Conjuntos de Recuperação ($t=2$): Os autores propõem uma estrutura geral para construir LRCs com dois conjuntos de recuperação usando os grupos de automorfismos de campos de funções elípticas. Para superar limitações em estruturas anteriores (onde a interseção de espaços de funções era muito pequena), eles concebem uma construção nova para as funções $e_i$. Isso garante que os espaços de funções correspondentes aos dois conjuntos distintos de recuperação estejam dentro de um espaço de Riemann-Roch comum, garantindo uma interseção suficientemente grande. A estrutura utiliza subgrupos $G = T_H A_1 A_2$ (onde $T_H$ é um subgrupo de translação e $A_1, A_2$ são subgrupos estabilizadores) para definir os parâmetros do código. A construção é aplicada tanto a campos de funções elípticas maximais quanto às curvas ordinárias específicas introduzidas na primeira parte do artigo.

Principais Contribuições e Resultados

• Novas Famílias de LRCs Clássicos Ótimos: O artigo constrói várias novas famílias de LRCs $q$-ários ótimos com comprimento $O(q + 2\sqrt{q})$ e localidade flexível.

  • Teoremas 1 e 2: Estes teoremas estabelecem a existência de LRCs $p^2$-ários ótimos com localidade $r = h|A| - 1$ ou $r = 2h - 1$. Crucialmente, essas construções são válidas para corpos finitos com característica $p$ satisfazendo $p \equiv 1 \pmod{12}$ (especificamente $p = 3u^2 + 3u + 1$ ou $p = v^2 + 1$), um caso para o qual não havia LRCs ótimos disponíveis anteriormente via grupos de automorfismos de curvas elípticas.
  • Comparação: Conforme detalhado na Tabela I, estes resultados complementam trabalhos existentes (por exemplo, Li et al., Ma e Xing) expandindo a gama de características e oferecendo diferentes parâmetros de localidade sobre os mesmos corpos finitos.

• Estrutura Geral para Disponibilidade $t=2$:

  • Proposição 3: Fornece uma estrutura geral para construir LRCs com dois conjuntos de recuperação usando campos de funções elípticas. Estabelece limites inferiores para a dimensão $k$ e distância mínima $d$ com base nos tamanhos dos subgrupos $A_1$ e $A_2$.
  • Teoremas 3 e 4: Aplicam a estrutura a campos de funções elípticas maximais e às curvas ordinárias específicas da Proposição 1, respectivamente. Estes teoremas produzem famílias de LRCs com dois conjuntos de recuperação e comprimento $O(q + 2\sqrt{q})$ (ou $O(q^2 + 2q)$ para o caso $q^2$-ário).
  • Teorema 7: Apresenta uma construção especializada sobre corpos finitos de característica 2 (especificamente $q = 4^{2a+1}$), produzindo LRCs com pares de localidade $(5, 6)$ e $(8, 3)$.

• Métricas de Desempenho:

  • Os códigos construídos alcançam comprimentos de $O(q + 2\sqrt{q})$ para LRCs clássicos e $O(q^2 + 2q)$ para LRCs com dois conjuntos de recuperação.
  • Para os LRCs $q^2$-ários com dois conjuntos de recuperação, o defeito de Singleton é mostrado como $O\left(\frac{2\ell}{q^2 + 2q - 8\ell}\right)$, que tende a zero à medida que $q$ aumenta, indicando optimalidade assintótica.
  • Exemplos numéricos (por exemplo, sobre $\mathbb{F}_{5^6}$) demonstram que os códigos construídos podem alcançar parâmetros não atingíveis por métodos anteriores (como aqueles baseados em campos de funções racionais).

Significância e Alegações
O artigo alega ampliar a seleção de curvas disponíveis para a construção de códigos localmente reparáveis ótimos. Ao deslocar o foco de curvas supersingulares maximais para curvas ordinárias com muitos pontos racionais, os autores preenchem uma lacuna na literatura referente a corpos finitos com características $p \equiv 1 \pmod 3$ e $p \equiv 1 \pmod 4$. Além disso, a estrutura proposta para LRCs com dois conjuntos de recuperação oferece uma abordagem mais flexível do que métodos anteriores, evitando a necessidade de técnicas modificadas de códigos de geometria algébrica e permitindo uma maior variedade de parâmetros de localidade. Os autores observam que, embora seus limites de dimensão sejam conservadores (como evidenciado por exemplos numéricos onde as dimensões reais excedem os limites inferiores teóricos), a estrutura gera com sucesso novas famílias de códigos com dois conjuntos de recuperação que anteriormente eram inatingíveis. O trabalho também destaca o potencial para a construção de LRCs com mais de dois conjuntos de recuperação como uma direção para pesquisa futura.