o problema
Especificação de sistema vive falando de tempo. Um pedido de reserva deve ser aceito se foi feito antes de o voo lotar; um recurso deve ser concedido na ordem em que foi requisitado. Enquanto tudo roda numa máquina só, “antes” é barato: existe um relógio, todo mundo lê o mesmo relógio, acabou. Assim que os processos estão separados no espaço e o atraso das mensagens deixa de ser desprezível em relação ao intervalo entre eventos, a palavra “antes” para de ter referente óbvio. Ou o sistema contém relógios físicos de verdade — que não são exatos e não marcam tempo físico preciso —, ou a especificação está falando de uma coisa que o sistema não consegue observar.
O erro que isso produz não é teórico. Lamport monta o caso mínimo: um processo escalonador central P0 que concede o recurso na ordem em que os pedidos chegam. P1 manda um pedido para P0 e depois manda uma mensagem para P2; P2, ao receber essa mensagem, manda o próprio pedido para P0. O pedido de P2 pode chegar antes do de P1. O escalonador central, que parecia a solução trivial, concede na ordem errada — e a ordem está errada num sentido que qualquer usuário reconheceria, porque P1 causou o pedido de P2.
a ideia
Em vez de perguntar quando cada evento ocorreu, pergunte quais eventos puderam influenciar quais. Isso se define sem relógio nenhum, por três regras: dentro de um processo, o que vem antes na sequência aconteceu antes; o envio de uma mensagem aconteceu antes do recebimento dela; e a relação é transitiva. Dois eventos que não se alcançam por nenhum caminho são concorrentes — nenhum pôde afetar o outro, e o sistema não tem base para ordená-los.
O resultado é uma ordem parcial, não total, e o paper insiste que esse é o ponto: os problemas aparecem quando as pessoas não percebem que a ordem é parcial. Num diagrama espaço-tempo, a → b quer dizer que dá para ir de a até b andando para cima pelas linhas de processo e de mensagem. Lamport aponta a semelhança com a relatividade especial, com uma ressalva honesta: a relatividade ordena pelo que poderia ser transmitido, e aqui só contam as mensagens que de fato foram enviadas, porque a corretude de um sistema tem que ser julgável pelos eventos que ocorreram.
como funciona
Cada processo Pi mantém um registrador Ci. Duas regras de implementação: IR1, incrementar Ci entre dois eventos sucessivos; IR2, toda mensagem carrega um timestamp Tm igual ao Ci do envio, e quem recebe ajusta Ci para um valor maior que Tm. Isso é tudo. As duas regras garantem a Condição do Relógio: se a → b, então C(a) < C(b).
A ordem total sai daí por desempate: a ⇒ b se C(a) < C(b), ou se os valores empatam e Pi vem antes de Pj numa ordem arbitrária dos processos. Com ela, exclusão mútua fica mecânica. Para pedir o recurso, Pi manda “Tm: Pi pede o recurso” a todos os outros e enfileira a própria mensagem; quem recebe enfileira e responde com um ack timestampado; para liberar, remove da fila e avisa todos. Pi entra quando duas coisas valem na sua fila local: o pedido dele é o primeiro pela ordem ⇒, e ele já recebeu de cada outro processo alguma mensagem com timestamp maior que Tm. A segunda condição é o que impede o caso do escalonador central — ela força Pi a ter ouvido tudo que precede o próprio pedido. Ambos os testes são locais.
Generalizando: descreva a sincronização como uma máquina de estados, e faça todo processo simular a mesma máquina aplicando os comandos na ordem ⇒. Todos veem a mesma sequência, logo chegam ao mesmo estado.
o que isso custou
A ordem total é arbitrária, e o preço aparece como comportamento anômalo. Alguém emite um pedido no computador A, telefona para um amigo em outra cidade, e o amigo emite um pedido no computador B. O pedido B pode ficar antes de A, porque a precedência trafegou por um canal externo ao sistema. Só há duas saídas: devolver o timestamp ao usuário e transferir a ele a responsabilidade, ou introduzir relógios físicos que satisfaçam a Condição Forte do Relógio.
O algoritmo de máquina de estados exige participação ativa de todos. Um processo precisa conhecer todos os comandos emitidos pelos outros, então a falha de um só processo impede qualquer outro de executar comandos e para o sistema. Lamport não resolve isso aqui; remete a outro trabalho. E observa que falha é um conceito que só existe em tempo físico — sem ele, um processo morto e um processo pausado são indistinguíveis, e o que revela o crash é o usuário cansado de esperar.
Há mais letra miúda. O algoritmo supõe canais FIFO entre cada par, entrega garantida, e que cada processo fale direto com todos. Cada requisição gera mensagem para todos, ack de todos e release para todos. Do lado físico, o teorema exige grafo fortemente conexo de diâmetro d, uma mensagem a cada τ segundos por arco com atraso imprevisível abaixo de ξ, e relógios que nunca são atrasados — só adiantados, porque voltar o relógio violaria C1. Sob isso, os relógios ficam dentro de ε = d(2κτ + ξ), com κ na casa de 10⁻⁶ para cristal típico, depois de τd segundos. O limite não é zero e cresce com o diâmetro da rede.
onde isso aparece hoje
A simulação distribuída de máquina de estados virou o vocabulário padrão da replicação: é o modelo que Paxos Made Simple e Raft implementam com tolerância à falha que este paper deixou em aberto. A generalização do contador para um vetor por processo é o que sustenta detecção de conflito em sistemas sem coordenação, como o Dynamo e os CRDTs. E o caminho oposto — pagar por relógio físico bom e expor a incerteza em vez de escondê-la — é a aposta do Spanner, que trata o ε deste paper como uma quantidade a ser medida e esperada.