Conceitos
Relógios lógicos e happened-before
Intuição
Imagine duas pessoas em cidades diferentes que só se falam por cartas, e cujos relógios de pulso nunca batem exatamente. Se uma pergunta quem fez algo primeiro, a hora no relógio de cada uma não ajuda muito. O que dá para afirmar com segurança é outra coisa: se uma carta saiu de A e chegou a B, o que A fez antes de enviar vem antes do que B fez depois de ler. Quando nenhuma cadeia de cartas liga dois acontecimentos, perguntar qual veio primeiro simplesmente não tem resposta.
Como funciona
Lamport define a relação happened-before (aconteceu antes) com duas regras: dentro de um mesmo processo, o evento que vem antes na execução acontece antes do seguinte; e o envio de uma mensagem acontece antes do seu recebimento. A relação é transitiva, o que dá uma ordem parcial estrita. Dois eventos que não são ligados por nenhum caminho de eventos sequenciais e mensagens são concorrentes: nenhum pôde influenciar o outro. Para tornar isso computável, cada evento recebe um timestamp lógico tal que, se A aconteceu antes de B, o número de A é menor que o de B. Cada processo mantém um contador, incrementa-o antes de cada evento local (inclusive o envio) e anexa o valor à mensagem; ao receber, ajusta o contador para o maior entre o seu e o da mensagem e então o incrementa. Timestamps iguais em processos diferentes são desempatados por uma ordenação arbitrária dos processos (como um identificador), produzindo uma ordem total consistente com a causalidade. A garantia vale em um só sentido: timestamp menor não prova que um evento aconteceu antes, pois os dois podem ser concorrentes, e o desempate é artificial. Os relógios vetoriais generalizam a ideia e recuperam o sentido inverso, permitindo concluir causalidade ou concorrência ao comparar dois relógios.
Na prática
A ordem total dos relógios lógicos é a base da ideia de máquina de estados replicada: se réplicas determinísticas processam as mesmas entradas na mesma ordem, chegam às mesmas decisões; Lamport também a usa para exclusão mútua sem coordenador central. O Dynamo aplica a versão vetorial: marca cada versão de um objeto com um vector clock, o que permite saber se uma versão descende causalmente de outra ou se são conflitantes, e devolve ao cliente as versões que não consegue ordenar para que a aplicação as una. Use esse raciocínio sempre que precisar distinguir ordem causal real de coincidência de observação sem depender de relógios físicos sincronizados.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.