Paxos
O algoritmo de consenso original — matematicamente sólido, mas famoso por ser quase impossível de explicar sem um quadro branco e muita paciência.
Funciona em duas fases: prepare/promise e accept/accepted. Uma maioria dos participantes (quorum) precisa responder às duas antes que um valor seja considerado confirmado. O Multi-Paxos otimiza o processo eliminando a fase de prepare quando o mesmo líder permanece estável por um tempo, o que é o que torna o algoritmo viável na prática e não só no papel.
É famoso por ser difícil de entender — o próprio artigo de Lamport, "Paxos Made Simple", virou piada interna da área por não ter nada de simples. Foi usado no Chubby e no Spanner do Google; hoje a maioria dos sistemas novos escolhe o Raft, pedagogicamente mais simples mas fundamentalmente equivalente.