Papers
Time, Clocks, and the Ordering of Events in a Distributed System
Leslie Lamport · Communications of the ACM, 1978
O problema: em um sistema distribuído, 'antes' e 'depois' não são óbvios
Em um sistema distribuído, processos rodam em máquinas separadas e só se comunicam por mensagens que levam um tempo imprevisível para chegar. Nesse cenário, perguntar se um evento aconteceu antes de outro é traiçoeiro: não existe um relógio único e perfeito que todos consultem, e os relógios físicos de cada máquina divergem. Lamport parte dessa observação e argumenta que a noção intuitiva de 'antes' precisa ser redefinida de forma cuidadosa. O artigo examina o conceito de um evento ocorrer antes de outro e mostra que ele define apenas uma ordem parcial dos eventos: alguns pares de eventos têm ordem bem definida, e outros simplesmente não têm. Em seguida, o autor propõe um algoritmo para sincronizar um sistema de relógios lógicos, de modo que os eventos possam ser colocados em uma ordem total. A ideia de fundo é que, para muitos problemas de coordenação, o que importa não é a hora do relógio de parede, e sim a ordem em que as coisas podem ter se influenciado umas às outras. O paper fixa essa distinção, que virou vocabulário básico de quem projeta sistemas distribuídos.
A relação happened-before e a concorrência
O conceito central do paper é a relação 'aconteceu antes' (happened-before). Ela é construída a partir de duas regras simples. Primeiro, se dois eventos ocorrem no mesmo processo, aquele que vem antes na execução desse processo acontece antes do outro. Segundo, o envio de uma mensagem acontece antes do recebimento dessa mesma mensagem. Além disso, a relação é transitiva: se A precede B e B precede C, então A precede C. O resultado é uma ordem parcial estrita, em que nenhum evento acontece antes de si mesmo. Quando dois eventos não podem ser ligados por nenhum caminho de eventos sequenciais e mensagens, o paper os chama de concorrentes: nenhum pode ter causado ou influenciado o outro, e dizer qual veio primeiro não tem sentido físico algum. Essa definição é puramente causal e não depende de nenhum relógio de parede. Ela dá um critério objetivo para saber quando a ordem de dois eventos é uma informação real e quando é só uma coincidência de observação, o que sustenta todo o restante do artigo.
Relógios lógicos e a ordem total
Para tornar a relação happened-before utilizável, Lamport atribui a cada evento um número, o seu timestamp lógico, de forma que, se A acontece antes de B, o número de A seja menor que o de B (a chamada condição de relógio). O algoritmo, na forma descrita em resumos técnicos do mecanismo, tem poucas regras. Cada processo mantém um contador e o incrementa antes de cada evento local, inclusive o envio de uma mensagem. A mensagem sai carregando o valor do contador do remetente. Ao receber, o destinatário ajusta o próprio contador para o maior valor entre o seu e o da mensagem e depois o incrementa. Como timestamps iguais podem aparecer em processos diferentes, o paper propõe desempatar com uma ordenação arbitrária dos processos, como o identificador de cada um, o que produz uma ordem total consistente com a causalidade. Há uma limitação importante: a condição vale em um só sentido. Se A aconteceu antes de B, então o timestamp de A é menor, mas um timestamp menor não prova que A aconteceu antes de B, pois os eventos podem ser concorrentes. Além disso, a ordem total resultante é em parte artificial: o desempate não reflete causalidade real.
Aplicação: exclusão mútua distribuída e máquinas de estado replicadas
Lamport usa a ordem total para resolver um problema de sincronização concreto: dar acesso exclusivo a um recurso compartilhado entre vários processos, sem um coordenador central. Na formulação do algoritmo descrita em resumos do paper, um processo que quer o recurso coloca seu pedido, com timestamp, em uma fila local ordenada e o envia a todos os outros. Quem recebe enfileira o pedido e responde com uma mensagem de resposta, também com timestamp. O processo só entra na seção crítica quando seu pedido é o primeiro da fila e ele recebeu respostas de todos os demais; ao terminar, remove o pedido e avisa todos com uma mensagem de liberação (release). Análises posteriores contam 3(N-1) mensagens por uso do recurso, para N processos, e resumos do paper observam que o esquema pressupõe mensagens entregues de forma confiável e ordenada, e que a falha de um único processo pode travar o progresso. O próprio Lamport diz que o exemplo ilustra algo mais geral: ordenar totalmente os pedidos permite implementar uma máquina de estados distribuída arbitrária. Cada réplica é uma máquina de estados determinística: dado o mesmo estado inicial e a mesma sequência de entradas, ela produz sempre os mesmos resultados. Por isso, se todas as réplicas processam as mesmas entradas na mesma ordem total, chegam às mesmas decisões. Ele nota que muita gente acha que o artigo trata só de ordem causal ou só de exclusão mútua, e ignora esse ponto.
Comportamento anômalo, relógios físicos e legado
O artigo também discute o que acontece quando o sistema interage com o mundo fora dele. Se a causalidade passar por um canal externo, que o relógio lógico não enxerga, a ordem total pode contradizer a ordem em que os usuários percebem os eventos, o que o paper trata como comportamento anômalo. Para evitá-lo, Lamport introduz relógios físicos que obedecem a limites de deriva e de diferença entre si, mantidos sincronizados pelas mensagens trocadas; em resumos, a precisão alcançável depende da deriva dos relógios e dos atrasos das mensagens. Os valores exatos das desigualdades do paper não foram verificados aqui e não são afirmados neste resumo. Lamport conta que o trabalho nasceu de uma nota de Paul Johnson e Bob Thomas baseada em timestamps de mensagens, e que ele percebeu nela uma ordem total de eventos consistente com a causalidade. O paper recebeu o PODC Influential Paper Award em 2000 (depois renomeado Dijkstra Prize) e o SIGOPS Hall of Fame Award em 2007, e Lamport o chama de seu artigo mais citado. Como legado técnico, os timestamps de Lamport são o ponto de partida conceitual dos relógios vetoriais, que generalizam a ideia e recuperam o sentido inverso da condição: comparar dois relógios vetoriais permite concluir causalidade.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.