o problema
Todo serviço distribuído quer as mesmas três coisas: devolver sempre o dado mais recente, responder sempre, e continuar de pé quando a rede se parte. O folclore da área já dizia que as três juntas não existem, e em 2000, numa keynote do PODC, Eric Brewer transformou o folclore em conjectura. Conjectura é o nome que se dá a uma afirmação que ninguém sabe provar — e, no caso, ninguém sabia provar porque ninguém tinha definido os termos com precisão suficiente para tentar.
Isso não é preciosismo acadêmico. Sem definição, qualquer discussão sobre “nosso sistema é consistente e disponível” é infalseável: cada lado usa uma palavra diferente. E a decisão é cara. Um site de comércio eletrônico que sai do ar durante uma partição perde dinheiro; um que continua vendendo estoque que não existe também. Alguém precisa escolher antes, e escolher antes exige saber exatamente o que está sendo trocado por quê.
a ideia
Gilbert e Lynch fixam as três palavras. Consistência atômica é linearizabilidade: existe uma ordem total das operações, cada uma parecendo instantânea, e toda leitura devolve o valor da escrita imediatamente anterior nessa ordem. Disponibilidade é fraca de propósito: toda requisição que chega a um nó vivo tem que terminar em alguma resposta — sem prazo, sem limite de tempo. Tolerância a partição é a mais interessante: não é uma propriedade do algoritmo, é o modelo de rede. A rede pode perder arbitrariamente muitas mensagens de um nó para outro, e partição é só o caso extremo em que todas as mensagens entre dois grupos somem.
Essa terceira definição desfaz a leitura preguiçosa do “escolha dois”. Não há três botões. Há um mundo em que a rede perde mensagem, e nele o par consistência-disponibilidade é impossível.
como funciona
O teorema vive num modelo assíncrono: sem relógio, cada nó decide apenas com base nas mensagens que recebeu e na computação local. A prova cabe em dois nós. Parta a rede em dois grupos e descarte tudo que trafega entre eles. Escreva um valor novo no primeiro grupo; a disponibilidade obriga a escrita a terminar. Depois leia do segundo grupo; a disponibilidade obriga a leitura a responder. O segundo grupo não viu nada, então devolve o valor antigo, e a execução não é atômica.
O corolário é o que quase todo mundo esquece. Pegue a mesma execução e concatene: primeiro a escrita isolada, depois a leitura isolada, depois um trecho em que tudo é entregue. Do ponto de vista de cada nó, essa execução é indistinguível de uma em que nenhuma mensagem se perdeu — e ela contém uma resposta não atômica. Logo, no modelo assíncrono, um algoritmo disponível não consegue ser atômico nem quando a rede está perfeita, porque ele não tem como saber que está.
A segunda metade do paper troca de modelo. No modelo parcialmente síncrono, cada nó tem um relógio; os relógios avançam no mesmo ritmo, mas não estão sincronizados — servem como timer, não como fonte de tempo global. Toda mensagem ou é entregue dentro de um prazo conhecido t_msg, ou está perdida. O teorema principal sobrevive: com partição, ainda não dá. O corolário morre. Os autores exibem um protocolo centralizado em que cada leitura ou escrita fala com um nó central e espera 2 · t_msg; se a resposta não chega, o nó conclui que a mensagem se perdeu e devolve o melhor valor que conhece. O nó central serializa as escritas com números de sequência consecutivos e faz broadcast periódico do último valor. Daí eles definem t-Connected Consistency: atomicidade garantida sempre que existe, entre duas operações, um intervalo de tamanho t em que a rede entregou tudo.
o que isso custou
O objeto do teorema é um único registrador read/write sob consistência atômica. Nada aqui fala de transações, de múltiplas chaves, ou de qualquer modelo de consistência mais fraco — os próprios autores encerram dizendo que formalizar e estudar esses modelos intermediários fica como trabalho futuro.
A definição de disponibilidade não tem prazo. Um algoritmo que responde depois de uma hora é disponível pelo teorema e inútil em produção, então o resultado não captura latência, que é justamente onde dói. As construções positivas da seção “dois entre três” são deliberadamente triviais: devolver sempre o valor inicial é disponível e tolerante a partição; rodar tudo num nó só é consistente. Elas provam viabilidade, não utilidade. E a saída parcialmente síncrona depende de t_msg ser conhecido e verdadeiro: se o limite estiver errado, o timeout mente e a garantia evapora.
onde isso aparece hoje
O lado disponível virou uma linhagem inteira de sistemas que aceitam escrita durante a partição e reconciliam depois, com Dynamo e Cassandra como os casos canônicos. Os CRDTs são a pergunta seguinte levada a sério: que estruturas de dados conseguem convergir sozinhas sem coordenação, já que coordenação é exatamente o que a partição tira.
O lado consistente é a família do consenso — Paxos e Raft mantêm a ordem total e simplesmente param de responder na minoria. E o modelo parcialmente síncrono da segunda metade é o terreno do Spanner, que faz do relógio uma peça explícita do protocolo e paga a conta em espera no commit. Quando um time grande escreve sobre o preço de migrar para consistência mais forte, como em Challenges to Adopting Stronger Consistency at Scale, está descrevendo em produção a fronteira que este paper desenhou no papel.