Ordem aconteceu antes e causal

Estou lendo "O tempo, os relógios e a ordem dos eventos em um sistema distribuído", de Lamport, e há um detalhe que está me incomodando.

Lamport define a ordem parcial "aconteceu antes", o que eu entendo. Então ele diz que "Outra maneira de visualizar a definição é dizer que a -> b significa que é possível que o evento a afete causalmente o evento b".

Considere agora dois eventos aeb que são recepções de mensagens em um processo P1, de modo que a ocorre antes de b. Além disso, suponha que aeb sejam os únicos dois eventos já ocorridos em P1. De acordo com a definição da relação aconteceu antes, temos a -> b (o que faz sentido, pois P1 observou esses eventos nessa ordem).

No entanto, não vejo como é possível que o evento a afete causalmente o evento b. Esses dois eventos são totalmente independentes e poderiam ter acontecido em uma ordem diferente.

O que estou perdendo aqui?

Observe que causalidade é um termo indefinido no artigo. Lamport está usando-o em uma explicação informal. Ele está assumindo que poderia afetar causalmente um conceito intuitivo que significará a mesma coisa para seus leitores do que para ele. Eu acho que para Lamport$a$ poderia afetar causalmente $b$na verdade, significa que algo mais parecido com informações poderia fluir de$a$ para $b$ ou $a$ poderia impactar o comportamento de $b$, do que a idéia aristotélica clássica de $b$ é uma consequência física de $a$.

Por exemplo, suponha que um computador esteja executando um programa com duas instruções:

a: X := 1
b: print X

Acho que todos concordamos que a declaração a aconteceu antes, b mas não diria que "a execução da declaração de atribuição (evento a) fez com que o programa executasse a printdeclaração (evento b)". Por outro lado, posso dizer algo ligeiramente diferente: "evento a(atribuindo o valor 1 a X) afetou o valor impresso pelo evento b".

Agora vamos dar um exemplo (potencialmente) mais controverso.

a: X := 1
b: Y := 1

a acontece antes b , mas acho que a maioria das pessoas diria: "não há relação causal entre ae b". Mas neste artigo há uma relação causal entre aeb . Vou tentar explicar isso da maneira mais sucinta possível, mas vai demorar muito.

O artigo é sobre máquinas de estado

Aqui está o que Lamport tem a dizer sobre o artigo em sua home page :

Um sistema distribuído pode ser descrito como uma máquina de estado seqüencial específica que é implementada com uma rede de processadores. A capacidade de solicitar totalmente as solicitações de entrada leva imediatamente a um algoritmo para implementar uma máquina de estado arbitrária por uma rede de processadores e, portanto, implementar qualquer sistema distribuído. Então, escrevi este artigo, sobre como implementar uma máquina de estado distribuída arbitrária. ...

Este é o meu artigo mais citado. ... Mas raramente encontrei alguém que sabia que o jornal dizia algo sobre máquinas de estado. As pessoas parecem pensar que se trata da relação de causalidade nos eventos em um sistema distribuído ou do problema de exclusão mútua distribuída. As pessoas têm insistido que não há nada sobre máquinas de estado no jornal. Eu até tive que voltar e relê-lo para me convencer de que realmente me lembrava do que havia escrito.

Cada processo é uma máquina de estado e a composição dos processos em um sistema / algoritmo distribuído é uma máquina de estado.

Lamport está implicitamente usando uma notação abreviada que no design digital chamamos de transferências de registradores e cada processo é (implicitamente) uma máquina de estado algorítmica . O que realmente importa é como cada evento afeta todo o estado de cada processo. Cada declaração de transferência de registro é uma maneira sucinta de falar sobre um conjunto de transições de estado que dependem do estado anterior.

Portanto, em nosso exemplo "controverso", o estado da máquina tem duas partes $\langle X, Y \rangle$. A declaração de transferência de registro Y := 1é uma abreviação para quatro transições de estado diferentes:$\langle 0, 0 \rangle \rightarrow \langle 0, 1 \rangle$, $\langle 0, 1 \rangle \rightarrow \langle 0, 1 \rangle$, $\langle 1, 0 \rangle \rightarrow \langle 1, 1 \rangle$e $\langle 1, 1 \rangle \rightarrow \langle 1, 1 \rangle$. Então, o que aconteceu na declaração aafeta muito o estado final produzido pela declaração b. No nosso caso, sabemos que o estado final é$\langle 1, 1\rangle$, e esse não seria o caso anão executado, ou tinha asido uma declaração diferente (como X := 0).

O artigo é sobre o quanto uma das máquinas de estados distribuídas pode saber sobre os estados das outras máquinas de estados, por isso é muito importante a ordem das coisas em cada máquina.

Conforme apontado pelo @kramthegram e pelo @Wandering Logic, o evento $a$ evento "aconteceu antes" $b$que não implica que$a$ causou fisicamente $b$ (acontecer).

Essa causalidade usada no artigo de Lamport é frequentemente chamada causalidade potencial . Ele captura todas as possibilidades, geralmente induzindo um enorme gráfico de causalidade e, na prática, destrói a escalabilidade / desempenho dos sistemas distribuídos.

Para resolver esses problemas, podemos considerar a causalidade explícita ou dependências causais especificadas pelo aplicativo. Um exemplo comum são os aplicativos de rede social: Alice leu 100 comentários em um tópico de conversa e respondeu a 5 deles com um único comentário. O comentário imediato de seu comentário - antes que a dependência pudesse consistir apenas desses 5 comentários (em vez de todos esses 100 comentários com potencial causalidade ).

Qual é a melhor causalidade ? Bem, isto depende. Por exemplo, a causalidade potencial prevalece na área de pesquisa de depuração de programas multithread. Existem duas razões principais (na minha opinião): primeiro, não temos contexto / semântica que indique se dois eventos ($\textsf{read}$ ou $\textsf{write}$operações) estão efetivamente relacionadas à causa ou não. Em segundo lugar, queremos capturar toda a causalidade possível entre os eventos e revelar o maior número possível de depurações.

Para mais discussões sobre causalidade potencial e causalidade explícita , consulte este documento: Os perigos potenciais da consistência causal e uma solução explícita .

Você está perdendo a seleção da palavra possível . Isso não significa que a relação é realmente causal, apenas que é possível para um ter um efeito causal sobre b . Suas declarações não são falsas, você está apenas lendo mais sobre elas do que ele realmente está afirmando. Só porque é possível, não significa que seja verdade. A declaração mais forte é o inverso, se um não procede b é impossível para um para ter um efeito sobre causal b . É apenas uma questão de redação.