o problema
Um conjunto de processos precisa concordar em um valor — qual comando executar, quem é o dono do lock, qual escrita vale. O modelo é o pior razoável: processos rodam em velocidade arbitrária, param, reiniciam; mensagens atrasam sem limite, duplicam, somem. Só não corrompem, e ninguém mente. Nesse mundo, a solução ingênua é ter um único acceptor que fica com o primeiro valor que receber. Funciona e é trivialmente correto — até esse processo cair, e aí nada mais avança.
Trocar um acceptor por vários resolve a disponibilidade e cria o problema de verdade. Se cada acceptor aceita o primeiro valor que chega, três proposers simultâneos podem deixar o grupo dividido, com nenhum valor tendo maioria e nenhuma forma de saber o que foi decidido. Havia um algoritmo que resolvia isso desde 1998, o “The Part-Time Parliament”, mas apresentado como a arqueologia de um parlamento grego fictício, e a comunidade decidiu que era difícil. Este paper de 2001 é Lamport reescrevendo o mesmo algoritmo em prosa, e argumentando que ele não é engenhoso: ele é a única coisa que sobra depois que você lista as propriedades que quer.
a ideia
Duas maiorias de um mesmo conjunto sempre compartilham pelo menos um membro. Esse fato de contagem é o algoritmo inteiro. Se um valor foi escolhido por uma maioria, qualquer maioria futura vai conter alguém que se lembra disso — desde que ele se lembre.
Daí vem a segunda metade. Como um acceptor precisa poder aceitar mais de uma proposta (senão o grupo empaca), as propostas ganham números, e a invariante passa a ser: se a proposta de valor v foi escolhida, toda proposta de número maior também tem valor v. Um proposer que quer emitir a proposta n precisaria então saber tudo que será aceito abaixo de n. Prever isso é impossível; o que ele faz é proibir. Ele pede a uma maioria a promessa de nunca mais aceitar nada abaixo de n, e junto com a promessa vem a maior proposta que cada um já aceitou. Se veio alguma, o valor dele deixa de ser dele: ele é obrigado a repropor o valor mais alto que ouviu.
como funciona
Três papéis — proposer, acceptor, learner — que na prática moram no mesmo processo.
Fase 1: o proposer escolhe um número n e manda um prepare a uma maioria de acceptors. Cada acceptor que nunca respondeu a um prepare maior responde com uma promessa de não aceitar mais nada abaixo de n e com a proposta de maior número que já aceitou, se houver. Quem já respondeu a algo maior ignora o pedido.
Fase 2: com respostas de uma maioria, o proposer manda um accept com número n e valor v, onde v é o valor da proposta de maior número entre as respostas — ou qualquer valor, se ninguém reportou nada. O acceptor aceita, a menos que já tenha prometido a alguém com número maior.
Cada acceptor guarda só dois campos: a maior proposta aceita e o maior número de prepare respondido. Ambos vão para storage estável antes da resposta sair. Números únicos saem de conjuntos disjuntos por proposer, e cada proposer lembra o maior que já usou.
Para máquina de estados replicada, roda-se uma instância desse algoritmo por posição na sequência de comandos. O líder é o único proposer. Ele executa a fase 1 de todas as instâncias abertas de uma vez, com uma mensagem curta e o mesmo número de proposta, porque um acceptor sem nada aceitado responde só “ok”. Buracos na sequência — que aparecem porque o líder pode ir até α comandos à frente antes de saber o resultado dos anteriores — são preenchidos com um comando no-op, para poder executar o que vem depois. Reconfigurar o conjunto de servidores é um comando de máquina de estados como outro qualquer, valendo α posições adiante.
o que isso custou
Progresso não é garantido, e Lamport mostra o contraexemplo em cinco linhas: p termina a fase 1 com n1, q termina com n2 > n1, os accepts de p são recusados, p volta com n3 > n2, e os dois se atropelam para sempre. A saída é eleger um proposer distinguido — e o resultado de Fischer, Lynch e Paterson implica que essa eleição precisa de aleatoriedade ou de tempo real, ou seja, de timeouts. O paper não define requisitos precisos de liveness e não os prova; o que ele garante é que a segurança sobrevive a qualquer fracasso da eleição, inclusive a dois líderes simultâneos.
Aprender também é frouxo. Cada acceptor avisando todo learner custa o produto dos dois números; concentrar em um learner distinguido custa a soma, mais um round, e um ponto único de falha. E perda de mensagem pode fazer um valor ser escolhido sem que learner nenhum descubra — nesse caso o jeito de saber é pedir a um proposer que emita uma nova proposta.
onde isso aparece hoje
O padrão líder + log replicado + maioria virou infraestrutura. O Chubby do Google é um serviço de lock construído sobre Paxos, e o Spanner replica cada shard com um grupo Paxos. O Raft nasce como reação explícita a este trabalho: mesma garantia, decomposição diferente, com a tese de que a dificuldade de entender Paxos é um problema de engenharia e não um detalhe. A abordagem de máquina de estados que o paper aplica ao consenso vem do artigo de relógios lógicos do próprio Lamport, Time, Clocks, and the Ordering of Events, citado aqui como referência.