Resumo

  • Fischer, Lynch e Paterson provaram que todo protocolo determinístico e parcialmente correto de consenso possui, no modelo assíncrono deles com no máximo uma falha, uma execução admissível que nunca decide.
  • A bivalência mantém dois resultados alcançáveis. O adiamento do evento crítico e a comutação de passos independentes permitem preservar essa condição sem perder mensagens para sempre.
  • Sincronia parcial, detectores de falhas e aleatoriedade acrescentam premissas. Um timeout orienta uma decisão local, mas não prova que o processo remoto parou.

O relógio de uma eleição expira. A interface chama o líder de indisponível, mas a observação é mais estreita: nenhuma resposta chegou antes de um limite escolhido. Num sistema sem limite conhecido de demora, essa ausência não separa um processo morto de um processo lento.

Foi essa lacuna de conhecimento que Michael J. Fischer, Nancy A. Lynch e Michael S. Paterson transformaram em teorema em 1985. Impossibility of Distributed Consensus with One Faulty Process não elimina o consenso prático. Mostra que, no modelo especificado, nenhum algoritmo determinístico seguro garante uma decisão em todas as execuções admissíveis quando uma falha é permitida.

Uma rede confiável que não promete horário

Os processos são determinísticos e trocam mensagens. Não existe limite para a velocidade relativa dos processos, para a demora de entrega ou um relógio sincronizado. As mensagens podem chegar fora de ordem e arbitrariamente tarde, mas não são descartáveis: uma mensagem destinada a um processo não defeituoso precisa acabar entregue se ele continuar recebendo.

Uma execução admissível contém no máximo um processo defeituoso e cumpre essa entrega. Um processo não defeituoso dá infinitos passos. A prova, portanto, não depende de um buraco negro na rede. O escalonador pode servir processos e mensagens com justiça, mantendo ainda assim o estado global longe de uma decisão.

O requisito de terminação atacado é fraco: bastaria algum processo decidir em toda execução admissível. Se nem isso pode ser prometido, condições mais fortes também não podem.

Bivalência é uma propriedade do futuro

Uma configuração reúne o estado interno de cada processo e as mensagens pendentes. Ela é 0-valente se toda continuação que decide escolhe 0, 1-valente para 1, e bivalente se as duas escolhas continuam possíveis.

A prova encontra primeiro uma configuração inicial bivalente. Caso todas fossem univalentes, seria possível mudar as entradas uma por vez até achar duas configurações vizinhas com valências opostas. Elas difeririam apenas no estado de um processo. Se ele falhasse antes de agir, os demais não saberiam em qual mundo estão, embora devessem produzir respostas incompatíveis.

Depois vem o evento crítico, como a entrega de uma mensagem a um processo. Suponha que, depois de qualquer adiamento, aplicar esse evento sempre force uma única valência. Haveria então uma fronteira em que um passo fixa o resultado. Mas eventos em processos diferentes comutam: executar A antes de B produz a mesma configuração que B antes de A. O quadrado de comutação faz caminhos supostamente opostos terminarem no mesmo estado, uma contradição.

Logo, sempre existe um trecho finito que preserva a bivalência até o evento escolhido ser atendido. Repetindo a operação e alternando processos e mensagens, obtém-se uma execução infinita, admissível e sem decisão.

Existência não é frequência

O teorema afirma que uma execução ruim existe, não que todas as execuções são ruins. Sistemas reais chegam a consenso porque sua execução específica é favorável ou porque o projeto assume condições adicionais. O que desaparece é a garantia sem condições.

Uma pausa operacional também não é, por si, “FLP”. Perda de pacotes, armazenamento saturado, erro de configuração, falha correlacionada ou bug de software exigem evidência própria. A referência ao teorema só é informativa se a análise expõe o modelo, a restrição de segurança e a impossibilidade de distinguir demora de falha.

Três contratos mais fortes

Dwork, Lynch e Stockmeyer formalizaram a sincronia parcial: os limites podem existir sem serem conhecidos, ou valer apenas após um instante desconhecido de estabilização. Quando essa fase chega, protocolos podem progredir.

Os detectores de falhas de Chandra e Toueg adicionam informação especificada por completude e precisão. Eles não convertem silêncio em certeza; oferecem um serviço com garantias. Protocolos aleatórios como o de Ben-Or alteram a premissa determinística e passam a falar de terminação probabilística.

Cada caminho torna explícito o recurso adicional que sustenta o progresso. É a confirmação da fronteira, não sua negação.

O legado de Lynch sem apagar os coautores

No relato posterior de Lynch, ela e Fischer começaram a perseguir o problema em 1982; Paterson entrou no trabalho que levou à forma final da prova. Preservar essa autoria conjunta faz parte da precisão histórica.

O ensinamento operacional é publicar as condições ao lado da promessa: falhas toleradas, propriedades do relógio e do detector, prioridade da segurança e hipótese de vivacidade. O FLP não manda parar de construir. Ele obriga o sistema a dizer em que mundo suas garantias valem.

Fontes