Esquema ‘mágico’ de correção de erros provou ser inerentemente ineficiente | Revista Quanta

Se você já enviou uma mensagem de texto, reproduziu um CD ou armazenou um arquivo na nuvem, você se beneficiou da correção de erros. Esta ideia revolucionária remonta à década de 1940, quando os investigadores perceberam pela primeira vez que é possível reescrever qualquer mensagem de uma forma que permita que a corrupção posterior seja facilmente revertida.

Ao longo dos anos, os investigadores desenvolveram muitos esquemas engenhosos, chamados códigos de correção de erros, que codificam dados de diferentes maneiras e utilizam procedimentos diferentes para corrigir erros. Mas para os cientistas da computação teóricos, poucos são tão convincentes quanto os chamados códigos corrigíveis localmente. Esses códigos têm duas propriedades simultâneas que parecem quase contraditórias: qualquer erro pode ser corrigido lendo os dados codificados em apenas alguns lugares, mas nenhum invasor pode frustrar esse procedimento de correção adulterando seletivamente o código. É como se você pudesse recuperar qualquer página arrancada de um livro apenas olhando algumas outras.

“É um fenômeno bastante mágico”, disse Tom Gur, cientista da computação da Universidade de Cambridge. “A priori, não é óbvio que tal objeto matemático possa existir.”

Mas essa magia tem um custo altíssimo. Os únicos exemplos conhecidos de códigos corrigíveis localmente são extremamente ineficientes – codificar qualquer mensagem também a torna exponencialmente mais longa. Livros inteiros codificados dessa maneira seriam muito difíceis de manejar.

Os cientistas da computação há muito se perguntam se são possíveis melhores códigos corrigíveis localmente. Eles se concentraram especialmente em códigos que usam apenas três consultas para corrigir qualquer erro, esperando que essa restrição severa possa tornar esses códigos mais fáceis de entender. Mas mesmo este caso simples tem deixado os investigadores perplexos há mais de 20 anos.

Agora, o cientista da computação Pravesh Kothari da Carnegie Mellon University e seu aluno de pós-graduação Pedro Manohar finalmente provou que é impossível construir um código corrigível localmente de três consultas que evite esse custo exponencial. Pode ser um resultado negativo, mas qualquer coisa que esclareça os limites da correção de erros é estimulante para os pesquisadores, especialmente porque a matemática dos códigos corrigíveis localmente surge em áreas distantes da comunicação.

“Esse resultado é incrível”, disse Shubhangi Saraf, cientista da computação da Universidade de Toronto. “É um grande avanço.”

Força em números

Para entender a correção de erros, imagine os dados que você gostaria de proteger como uma sequência de bits, ou 0s e 1s. Um erro, neste modelo, pode ser qualquer mudança indesejada de 0 em 1 ou vice-versa, seja devido a uma flutuação aleatória ou a uma adulteração deliberada.

Suponha que você queira enviar uma mensagem a um amigo, mas está preocupado com a possibilidade de erros alterarem o significado. Uma estratégia simples é substituir cada 0 da sua mensagem por 000 e cada 1 por 111. Se o seu amigo vir uma parte da mensagem que não contém três bits idênticos seguidos, ele saberá que ocorreu um erro. E se os erros são aleatórios e relativamente raros, então qualquer sequência de 110 tem muito mais probabilidade de ser um 111 corrompido do que um 000 corrompido. Uma votação por maioria simples dentro de cada trigêmeo será suficiente para corrigir a maioria dos erros.

Esse esquema, chamado de código de repetição, tem a virtude da simplicidade, mas nada mais que o recomende. Por um lado, é necessário triplicar o comprimento de cada mensagem apenas para lidar com erros relativamente raros e, se houver uma boa chance de ocorrerem dois erros adjacentes, precisaremos de ainda mais redundância. Pior ainda, rapidamente se torna inútil se os erros não forem aleatórios, como quando os invasores tentam ativamente sabotar o código. No código de repetição, todas as informações necessárias para corrigir um determinado bit são armazenadas em apenas alguns outros bits, deixando-o vulnerável a um ataque direcionado.

Felizmente, muitos códigos de correção de erros têm melhor desempenho. Um exemplo famoso, chamado Código Reed-Solomon, funciona transformando mensagens em polinômios – expressões matemáticas como x² + 3x + 2 que consistem em diferentes termos somados, cada um com uma variável (como x) elevado a uma potência diferente. Codificar uma mensagem usando um código Reed-Solomon envolve construir um polinômio com um termo para cada caractere da mensagem, depois traçar o polinômio como uma curva em um gráfico e armazenar as coordenadas dos pontos que estão na curva (pegando pelo menos mais um). ponto do que o número de caracteres). Os erros podem empurrar alguns desses pontos para fora da curva, mas se não houver muitos erros, apenas uma curva polinomial passará pela maioria dos pontos. Essa curva quase certamente corresponde à verdadeira mensagem.

Os códigos Reed-Solomon são hipereficientes – você só precisa armazenar alguns pontos extras para corrigir erros, de modo que qualquer mensagem codificada é apenas um pouco mais longa que a original. Eles também são menos vulneráveis ​​ao tipo de interrupção direcionada que significaria um desastre para o código de repetição, porque as informações usadas para corrigir um erro em qualquer lugar são distribuídas por toda a mensagem codificada.

Pensar globalmente agir localmente

A força do código Reed-Solomon decorre da interconectividade. Mas precisamente por causa dessa interconectividade, não há como corrigir um único erro em uma mensagem codificada sem ler tudo. Isso pode não parecer um problema no contexto da comunicação: se você estiver enviando uma mensagem, provavelmente deseja que o destinatário a leia inteira. Mas pode ser um problema no armazenamento de dados – outra aplicação importante da correção de erros.

Considere uma empresa que armazena e-mails de usuários na nuvem — ou seja, em uma vasta gama de servidores. Você pode pensar em toda a coleção de e-mails como uma mensagem longa. Agora suponha que um servidor trave. Com um código Reed-Solomon, você precisaria realizar um cálculo massivo envolvendo todos os dados codificados para recuperar seus e-mails daquele servidor perdido. “Você teria que olhar para tudo”, disse Zeev Dvir, cientista da computação da Universidade de Princeton. “Isso pode significar bilhões e bilhões de e-mails – pode levar muito tempo.”

Os pesquisadores usam o termo “local” para descrever códigos que usam apenas uma fração da mensagem codificada para erros pontuais ou corrigi-los. O código de repetição simples tem algo desse caráter local, mas é exatamente isso que o torna tão vulnerável à adulteração. Um código corrigível localmente, por outro lado, obtém o melhor dos dois mundos – ele pode corrigir qualquer erro com apenas algumas consultas, tudo sem perder a interconexão que torna os códigos Reed-Solomon tão resilientes.

“Esta é uma noção realmente rigorosa”, disse Kothari.

Os exemplos mais famosos de códigos corrigíveis localmente são versões de um venerável código de correção de erros inventado em 1954 pelos matemáticos David Müller e Irving Reed (que também ajudou a desenvolver os códigos Reed-Solomon). Assim como os códigos Reed-Solomon, os códigos Reed-Muller usam polinômios com muitos termos somados para codificar mensagens longas.

Os polinômios usados ​​nos códigos Reed-Solomon envolvem uma única variável, x, então a única maneira de adicionar mais termos é usar poderes superiores de x. Isso resulta em uma curva com muitas oscilações que só podem ser definidas observando-se muitos pontos. Em vez disso, os códigos Reed-Muller usam polinômios nos quais cada termo pode conter múltiplas variáveis ​​​​multiplicadas. Mais variáveis ​​significam mais maneiras de combiná-las, o que por sua vez oferece uma maneira de aumentar o número de termos polinomiais sem elevar qualquer variável individual a potências tão altas.

Os códigos Reed-Muller são muito flexíveis. Você pode codificar mensagens mais longas aumentando a potência mais alta que aparece no polinômio, aumentando o número de variáveis ​​ou ambos. Para tornar um código Reed-Muller corrigível localmente, basta limitar a potência máxima de cada variável a um pequeno valor constante e lidar com mensagens mais longas aumentando apenas o número de variáveis.

Especificamente para um código corrigível localmente de três consultas, esse poder máximo é definido como 2. Então, no que diz respeito a cada variável individual, o polinômio que codifica a mensagem traça uma parábola simples. Para determinar a forma exata dessa parábola, basta examinar a curva em três pontos. Além do mais, com muitas variáveis ​​existem muitas parábolas, qualquer uma das quais pode ser usada para corrigir erros. É isso que torna os códigos Reed-Muller tão resilientes.

Infelizmente, o código Reed-Muller tem uma séria desvantagem: o número de bits necessários para codificar uma mensagem aumenta exponencialmente com o número de variáveis. Se você deseja um código altamente local que corrija erros com apenas algumas consultas, precisará de muitas variáveis ​​para mensagens longas, e o código Reed-Muller rapidamente se tornará inútil na prática.

“Exonencial neste caso é muito ruim”, disse Dvir. Mas é inevitável?

Corrigível ou Decodificável?

À medida que os cientistas da computação tentavam e não conseguiam encontrar códigos mais eficientes e corrigíveis localmente, eles começaram a suspeitar que tais códigos não eram de todo possíveis. Em 2003, dois pesquisadores provou que não há como superar o código Reed-Muller usando apenas duas consultas. Mas isso foi tudo que alguém conseguiu.

“Quando chegamos ao nível três, nosso conhecimento se torna muito vago”, disse Kothari.

A próxima descoberta apenas complicou ainda mais as coisas. Em dois artigos publicados em 2008 e 2009, os cientistas da computação Sergey Yekhanin e Klim Efremenko mostraram como construir códigos de três consultas que eram mais eficientes do que os códigos Reed-Muller, mas esses códigos não eram totalmente corrigíveis localmente. Em vez disso, eles tinham uma propriedade sutilmente diferente chamada decodificabilidade local.

Para entender a diferença, vamos imaginar novamente um provedor de armazenamento em nuvem que combina os dados dos usuários em uma longa mensagem e os protege usando um código de correção de erros. Tanto os códigos corrigíveis localmente quanto os códigos decodificáveis ​​localmente podem corrigir um erro em qualquer parte da mensagem original com apenas algumas consultas.

Mas todo código de correção de erros também requer bits extras que não estavam na mensagem original – é por isso que codificar uma mensagem a torna mais longa. Os dois tipos de códigos diferem na forma como tratam esses bits adicionais. Os códigos localmente decodificáveis ​​não fazem promessas sobre o número de consultas necessárias para corrigir erros nesses bits. Mas em um código corrigível localmente, um erro em qualquer um dos bits extras pode ser corrigido exatamente da mesma maneira que um erro em qualquer bit da mensagem original.

“Tudo o que você armazena, sejam os dados originais dos usuários ou a redundância e as informações do cheque – tudo isso pode ser corrigido localmente”, disse Madhu Sudão, cientista da computação da Universidade de Harvard.

Embora diferentes em princípio, a corrigibilidade local e a decodificação local sempre pareceram intercambiáveis ​​na prática antes de 2008 – todo código localmente decodificável conhecido também era corrigível localmente. A descoberta de Yekhanin e Efremenko levantou a possibilidade de uma diferença fundamental entre as duas condições. Ou talvez fosse possível modificar os códigos de Yekhanin e Efremenko para torná-los corrigíveis localmente. Isso colocaria as duas condições em pé de igualdade mais uma vez, mas também significaria que os pesquisadores estavam enganados sobre a eficiência dos códigos corrigíveis localmente com três consultas. De qualquer forma, a sabedoria convencional teria de mudar.

Lógica de empréstimo

Kothari e Manohar finalmente resolveram essa tensão adaptando uma técnica de uma área diferente da ciência da computação: o estudo dos chamados problemas de satisfação de restrições. Tentar coordenar os planos de jantar com um grupo de amigos é uma espécie de problema de satisfação de restrições. Todo mundo tem escolhas que aceitará e escolhas que vetará. Seu trabalho é encontrar um plano que satisfaça a todos ou, se não existir tal plano, descobrir isso o mais rápido possível.

Há uma assimetria inerente entre esses dois resultados possíveis. Uma solução aceitável pode não ser fácil de encontrar, mas uma vez obtida, é fácil convencer qualquer outra pessoa de que funcionará. Mas mesmo que você saiba que o problema é realmente “insatisfatório”, pode não haver um exemplo que forneça prova.

Em 2021, Kothari e Manohar, juntamente com Venkatesan Guruswami da Universidade da Califórnia, Berkeley, fizeram um Grande avanço no estudo de problemas de satisfação de restrições usando uma nova técnica teórica para identificar esses casos complicados e insatisfatórios. Eles suspeitavam que o novo método também seria uma ferramenta poderosa para resolver outros problemas, e o estudante de pós-graduação de Guruswami, Omar Alrabiah, sugeriu que analisassem códigos decodificados localmente com três consultas.

“Este foi um prego com um martelo na nossa mão, por assim dizer”, disse Kothari.

Os resultados surpreendentes de Yekhanin e Efremenko mostraram que os códigos decodificados localmente com três consultas poderiam ser mais eficientes do que os códigos Reed-Muller. Mas seus códigos eram os melhores possíveis ou os códigos decodificáveis ​​localmente com três consultas poderiam se tornar ainda mais eficientes? Kothari, Manohar, Guruswami e Alrabiah pensaram que sua nova técnica poderia ser capaz de provar os limites da eficiência de tais códigos. Seu plano era construir uma fórmula lógica abrangendo a estrutura de todos os códigos possíveis de três consultas decodificáveis ​​localmente de um determinado tamanho e provar que era insatisfatória, mostrando assim que tal código não poderia existir.

Os quatro pesquisadores deram um primeiro passo nessa direção em 2022, estabelecendo um novo limite na eficiência máxima de códigos decodificáveis ​​localmente com três consultas. O resultado foi muito além do que os pesquisadores conseguiram alcançar com outras técnicas, mas não descartou todos os códigos mais eficientes que os de Yekhanin e Efremenko.

Kothari e Manohar suspeitaram que poderiam ir mais longe. Mas o progresso estagnou até que Manohar anotou um cálculo rápido indicando que a técnica poderia funcionar ainda melhor para códigos corrigíveis localmente do que para códigos decodificáveis ​​localmente.

Alguns meses depois, depois de muitos outros falsos começos que os fizeram temer que tivessem sido otimistas demais, a técnica finalmente cumpriu sua promessa. Kothari e Manohar provaram que, como os pesquisadores suspeitavam, é impossível que qualquer código de três consultas corrigível localmente funcione sensivelmente melhor do que os códigos Reed-Muller. Essa escala exponencial é uma limitação fundamental. O seu resultado foi também uma demonstração dramática de que a correcção local e a descodificação local, embora superficialmente semelhantes, diferem realmente num nível fundamental: a última é inequivocamente mais fácil de realizar do que a primeira.

Kothari e Manohar esperam agora estender suas técnicas para estudar códigos que podem fazer mais de três consultas, já que muito pouco se sabe sobre eles atualmente. E o progresso na teoria da correção de erros muitas vezes tem implicações em outros campos aparentemente não relacionados. Em particular, os códigos corrigíveis localmente fazem aparições surpreendentes em todos os lugares, desde o problema de pesquisas em bancos de dados privados em criptografia para provas de teoremas em combinatória. É muito cedo para dizer como a técnica de Kothari e Manohar impactará esses diferentes campos, mas os pesquisadores estão otimistas.

“Há uma nova ideia realmente linda aqui”, disse Dvir. “Acho que há muito potencial.”