Resumo

  • Happened-before é a menor ordem parcial gerada pela sequência local de cada processo, pelo envio antes da recepção da mesma mensagem e pelo fechamento transitivo dessas relações.
  • A Clock Condition vale em uma direção: a → b exige C(a) < C(b). Um valor escalar menor não prova que a causou, informou ou precedeu fisicamente b.
  • Eventos concorrentes não têm caminho happened-before em nenhum sentido. Isso significa ausência de ordem no modelo observado, não ocorrência no mesmo instante de relógio.

Dois serviços produzem registros que parecem decisivos. A recebe o tempo lógico 41; B, 42. O painel ordena as linhas, desenha uma seta e induz a equipe a dizer que A causou B. Os números deixam a narrativa limpa. Não completam a evidência.

O artigo de Leslie Lamport de 1978, Time, Clocks, and the Ordering of Events in a Distributed System, não procurou um relógio universal escondido. Ele delimitou a ordem que um sistema distribuído pode justificar sem possuir um.

A menor ordem produzida pelas arestas observáveis

Lamport modela processos com sequências de eventos ligados por mensagens. Happened-before é a menor relação que satisfaz três regras: um evento anterior de um processo precede um posterior; o envio de uma mensagem precede a recepção da mesma mensagem; e a relação é transitiva.

“Menor” preserva o desconhecido. Se não há a → b nem b → a, os eventos são concorrentes. O modelo não preenche a lacuna apenas para entregar uma linha do tempo bonita.

Lamport explica a → b como a possibilidade de a afetar causalmente b. Existe um caminho para a informação circular. Isso não prova que o conteúdo de a produziu o resultado de b, que alguém desejou o efeito ou que a responsabilidade foi estabelecida. Alcance causal e causa semântica pedem evidências diferentes.

A definição de evento também muda o grafo. Uma nota do artigo observa que a recepção pode ser o acionamento de um bit de interrupção ou a execução do manipulador; a escolha altera a ordem. Antes de perguntar o que veio primeiro, é preciso versionar aquilo que conta como evento.

Uma implicação sem volta automática

Um relógio lógico associa um número a cada evento. A Clock Condition diz que, se a → b, então C(a) < C(b). Cada processo avança seu contador entre eventos, anexa o valor às mensagens e, ao receber uma, move o relógio para além do valor atual e do timestamp recebido.

As regras preservam as setas conhecidas. Não autorizam a inferência contrária: C(a) < C(b) não basta para concluir a → b.

Não é um detalhe de implementação. Se toda comparação numérica fosse happened-before, eventos concorrentes precisariam ter o mesmo valor. Porém, um evento pode ser concorrente com dois eventos ordenados entre si em outro processo; igualar os três violaria a ordem local.

O timestamp escalar certifica que uma aresta conhecida não foi invertida. Não certifica uma aresta causal entre todo par crescente.

Ordem total é política, não mundo recuperado

Algumas aplicações precisam escolher uma resposta onde a ordem parcial admite várias. Lamport mostra como ordenar pelo tempo lógico e desempatar com uma ordem fixa de processos. O resultado é total e consistente com happened-before.

Mas não é único. Outro relógio válido ou outro desempate pode gerar outra linearização. Só a ordem parcial é determinada pelo sistema de eventos.

Uma fila ou serviço replicado pode adotar uma sequência determinística. A sequência deve ser registrada como regra de controle. Quando o desempate é apresentado como descoberta do passado, uma política operacional vira um fato histórico falso.

O telefonema que ficou fora do sistema

O exemplo de “comportamento anômalo” do artigo descreve uma pessoa que envia A em um computador, telefona para alguém em outra cidade e pede que essa pessoa envie B. Como a ligação está fora do sistema, B pode receber um timestamp menor e aparecer antes de A.

Nenhum algoritmo restrito aos eventos internos recupera uma aresta que nunca observou. Lamport propõe carregar explicitamente a informação ausente ou usar relógios físicos bem sincronizados sob hipóteses mais fortes.

Hoje, a aresta omitida pode ser uma chamada de suporte, aprovação humana, webhook ou fila externa. “Nenhum caminho encontrado” significa “nenhum caminho nesta captura”, não “nenhuma influência no mundo”.

Tempo lógico, vetorial e físico

O relógio escalar preserva a implicação necessária e permite uma ordem total coerente. Uma década depois, Colin Fidge e Friedemann Mattern desenvolveram estruturas vetoriais que retêm mais da ordem parcial. Mattern observou que mapear eventos parcialmente ordenados em inteiros lineares perde informação: eventos potencialmente concorrentes recebem números diferentes como se tivessem ordem definida.

Vetores podem permanecer incomparáveis quando nenhum evento está no passado causal do outro. Isso ajuda em depuração, snapshots e conflitos. Ainda depende dos processos, eventos e mensagens registrados; não descobre uma ligação ausente nem demonstra o motivo humano.

O tempo físico responde a outra pergunta. O próprio artigo de Lamport trata de Strong Clock Condition, erro de taxa, deriva, atraso mínimo de mensagens e limites de sincronização. Essas hipóteses aproximam rótulos do tempo real com incerteza declarada; não transformam contador lógico em relógio de parede.

As fronteiras de autoria também importam. Lamport formalizou happened-before e relógios escalares, creditando Paul Johnson e Bob Thomas pela ideia anterior de timestamps em mensagens. Relógios vetoriais pertencem ao trabalho posterior de Fidge e Mattern.

O recibo de uma afirmação de ordem

Uma investigação defensável identifica definição e versão do evento, processo, sequência local, ID da mensagem, par envio-recepção, algoritmo do relógio e limite da telemetria. Uma afirmação física acrescenta fonte e margem de erro; uma afirmação causal precisa do mecanismo que alterou o resultado.

Assim, a conclusão pode ser precisa: happened-before no modelo capturado; concorrência nesse modelo; posição criada por desempate; anterioridade física dentro de uma incerteza; ou causalidade semântica ainda não demonstrada.

A contribuição de Lamport não foi ordenar tudo e chamar o resultado de verdade. Foi separar a ordem que o sistema conhece, a que escolhe e a que ainda não consegue provar.

Fontes