O problema dos generais bizantinos: a matemática de 1982 que impede que um sensor mentiroso derrube um avião

Por

Imagine um avião comercial com três sensores de altitude idênticos, todos ligados ao mesmo computador de bordo. Dois deles informam “30 mil pés”. O terceiro, com um defeito interno, não trava nem apaga — em vez disso, envia para um circuito “29 mil pés” e para outro circuito “31 mil pés”, ao mesmo tempo, sem que nada pareça obviamente errado com ele. Qual número o computador deve acreditar? E como garantir que todas as partes do sistema cheguem à mesma conclusão, mesmo que o sensor defeituoso esteja, na prática, contando duas histórias diferentes para plateias diferentes?

Esse cenário, incômodo o bastante para tirar o sono de qualquer engenheiro aeroespacial, tem uma resposta matemática precisa — e ela nasceu décadas antes de existir qualquer avião comercial com controle de voo digital em larga escala, e muito antes de a palavra “blockchain” significar qualquer coisa para alguém. Em 1982, três pesquisadores publicaram um artigo com um nome curioso, quase literário, para um problema de engenharia: “The Byzantine Generals Problem” — o problema dos generais bizantinos. A formalização por trás dele explica, até hoje, por que certos sistemas críticos não desmoronam quando um único componente começa a “mentir” — e por que bancos de dados espalhados por continentes inteiros conseguem concordar sobre um mesmo conjunto de fatos sem nunca se contradizerem.

Essa é a história de um quebra-cabeça que começou como ficção militar, virou prova matemática rigorosa e hoje sustenta, silenciosamente, uma fatia enorme da infraestrutura digital do mundo.

O quebra-cabeça dos generais traidores

O artigo de 1982, assinado por Leslie Lamport, Robert Shostak e Marshall Pease e publicado na revista científica ACM Transactions on Programming Languages and Systems, abre com uma metáfora que se tornou clássica na ciência da computação. Várias divisões do exército bizantino cercam uma cidade inimiga, cada uma comandada por um general diferente. Os generais só podem se comunicar por mensageiros. Depois de observar o inimigo, precisam decidir, em conjunto, entre atacar ou recuar — e essa decisão só funciona se todos os generais leais agirem da mesma forma. O problema é que alguns generais podem ser traidores, dispostos a mandar mensagens diferentes para pessoas diferentes, justamente para impedir que os leais cheguem a um acordo.

Os autores explicam o motivo de recorrerem a essa imagem logo no resumo do artigo: “sistemas de computador confiáveis precisam lidar com componentes com mau funcionamento que fornecem informações conflitantes para partes diferentes do sistema”. Traduzindo a alegoria: os generais são computadores ou sensores redundantes dentro de um mesmo sistema; os mensageiros são os canais de comunicação entre eles; e o “traidor” é qualquer componente com defeito — de hardware, de software, ou até um invasor malicioso — capaz de enviar dados contraditórios para partes diferentes da rede.

O resultado matemático do artigo é preciso e, à primeira vista, desanimador: usando apenas mensagens orais (sem nenhum mecanismo de assinatura ou verificação), o problema só tem solução se mais de dois terços dos generais forem leais. Os próprios autores mostram, com apenas três generais e um traidor, que é impossível garantir acordo nessas condições — o traidor sempre consegue contar histórias diferentes para os dois lados sem que nenhum dos dois consiga desmascará-lo com certeza. É preciso, portanto, redundância generosa — e um protocolo específico de trocas de mensagens — para que o sistema sobreviva a um componente mentiroso.

Por que mentir é pior do que simplesmente parar

Antes de 1982, engenheiros de sistemas já sabiam lidar com um tipo de falha mais simples: o componente que trava, para de responder ou apaga. Esse é o cenário de “falha silenciosa” (às vezes chamada de falha por colapso), e é relativamente fácil de detectar — o restante do sistema simplesmente nota a ausência de resposta e a ignora.

O problema formalizado por Lamport, Shostak e Pease é bem mais traiçoeiro, e um artigo anterior dos mesmos três autores — “Reaching Agreement in the Presence of Faults” (“Chegando a um acordo na presença de falhas”), publicado em 1980 no Journal of the ACM — já havia estabelecido a base teórica desse cenário mais difícil, junto com o conceito de “consistência interativa”: cada parte do sistema precisa acabar com a mesma visão dos dados enviados por todas as outras, mesmo que algumas delas estejam ativamente distorcendo o que dizem.

A diferença é sutil, mas decisiva. Um componente falho “à moda antiga” simplesmente some do jogo. Um componente bizantino continua jogando — só que joga sujo, e pode fazer isso de forma coordenada com outros componentes falhos, ou de maneira aparentemente aleatória, sem seguir padrão algum. Ele pode dizer “sim” para um vizinho e “não” para outro na mesma fração de segundo, e cada um dos dois vizinhos, isoladamente, não tem como saber que está sendo enganado. É esse grau de malícia hipotética — sem exigir nenhuma intenção real, apenas a possibilidade teórica de comportamento arbitrário — que torna o problema dos generais bizantinos matematicamente mais exigente do que a tolerância a falhas comuns, e por isso ele exige mais redundância (mais “generais”) do que se bastasse detectar componentes simplesmente desligados.

Um problema nascido para salvar aviões, não para inventar moedas digitais

O motivo de tanto rigor matemático não era acadêmico por acaso. As datas de publicação e as notas de financiamento nos dois artigos revelam a origem prática do problema: tanto o artigo de 1980 quanto o de 1982 registram apoio da NASA, através do Langley Research Center, além de agências de pesquisa militar dos Estados Unidos ligadas a defesa antimísseis e ao Army Research Office.

Essa ligação com a NASA não é coincidência de rodapé — é o próprio motivo de o problema existir. Lamport, Shostak e Pease trabalhavam no SRI International, um instituto de pesquisa na Califórnia, dentro do projeto SIFT (“Software Implemented Fault Tolerance”), encomendado pela NASA a partir de 1973 e financiado pelo Langley Research Center sob um contrato específico. O objetivo do SIFT, descrito em detalhe no artigo técnico “SIFT: Design and Analysis of a Fault-Tolerant Computer for Aircraft Control”, publicado nos Proceedings of the IEEE em 1978, era construir um computador de controle de voo capaz de continuar operando com segurança mesmo que um de seus módulos de hardware apresentasse defeito — sem que o piloto sentisse qualquer diferença. A ideia era viabilizar aeronaves comerciais com margens de estabilidade reduzidas, que dependeriam de controles ativos por computador para voar com segurança, exigindo por isso um nível de confiabilidade computacional muito acima do que já se conhecia até então.

Foi tentando resolver um problema de engenharia muito concreto — como sincronizar os relógios e os sensores redundantes de um computador de bordo real, sem que um componente defeituoso arraste o sistema inteiro para um erro — que os três pesquisadores acabaram isolando uma questão matemática pura, geral o bastante para se aplicar bem além da aviação. O artigo de 1978 sobre o SIFT já discutia esse tipo de acordo “interativo” entre componentes redundantes; os artigos teóricos de 1980 e 1982 foram onde esse núcleo do problema ganhou nome, prova formal e a metáfora que o tornaria famoso.

Da cabine do avião ao banco de dados global

A mesma linhagem de pesquisa que produziu o problema dos generais bizantinos segue viva, décadas depois, em lugares que nada têm a ver com aviação. Leslie Lamport, um dos três autores, também é o criador do Paxos, um protocolo de consenso distribuído voltado para um problema relacionado, porém mais restrito: como fazer réplicas de um mesmo dado concordarem entre si quando algumas delas podem falhar silenciosamente — sem, no entanto, precisar tolerar réplicas que mintam de forma ativa. É essa variante “mais simples” do problema de consenso que sustenta, por exemplo, o Spanner, o banco de dados distribuído globalmente do Google: segundo o artigo técnico “Spanner: Google’s Globally-Distributed Database”, apresentado no simpósio Osdi de 2012, o sistema fragmenta os dados em conjuntos de máquinas que rodam o algoritmo Paxos em data centers espalhados pelo mundo, justamente para manter réplicas consistentes mesmo quando servidores individuais falham.

Vale a ressalva: dentro de um data center controlado pelo próprio Google, presume-se que uma máquina com defeito vai parar de responder, não vai começar a mentir deliberadamente para partes diferentes da rede — por isso o Paxos, e não a tolerância bizantina completa, é a ferramenta adequada ali. A versão mais exigente do problema, a que realmente precisa admitir componentes “traidores” no sentido pleno do termo, aparece com mais força em ambientes onde não existe uma autoridade central de confiança — e é exatamente aí que entram as redes de blockchain, que usam variantes de algoritmos com tolerância bizantina (como o PBFT, publicado por Miguel Castro e Barbara Liskov em 1999) para que computadores desconhecidos entre si, e potencialmente adversários, consigam concordar sobre um mesmo livro-razão sem precisar confiar uns nos outros.

Uma ideia com mais de quatro décadas, ainda em uso

O que conecta a cabine de um avião dos anos 1970, um data center do Google hoje e uma rede de blockchain é a mesma pergunta de fundo, formulada com rigor matemático em 1982: como fazer um grupo de partes distribuídas concordar sobre um fato, sabendo que uma ou mais delas pode estar ativamente enviando informações contraditórias para lados diferentes do sistema? A resposta de Lamport, Shostak e Pease — de que é preciso redundância suficiente, protocolos específicos de troca de mensagens e, em alguns casos, mecanismos de assinatura para tornar mensagens infalsificáveis — continua sendo o alicerce teórico de praticamente qualquer sistema distribuído que hoje se propõe a nunca contradizer a si mesmo, esteja ele guiando uma aeronave, replicando um banco de dados ou validando uma transação financeira em uma rede sem dono.

Fontes citadas neste artigo:

Deixe um comentário