Happened-before and Causal order

Question

I'm reading Lamport's "Time, Clocks, and the Ordering of Events in a Distributed System" and there's a detail that's bugging me.

Lamport defines the "happened before" partial order, which I understand. Then he says that "Another way of viewing the definition is to say that a -> b means that it is possible for event a to causally affect event b".

Consider now two events a and b that are message receptions at a process P1, such that a occurs before b. Further more, suppose a and b are the only two events ever occurring at P1. According to the happened-before relation definition, we have a -> b (which makes sense, since P1 observed those event in this order).

However, I don't see how it is possible for event a to causally affect event b. Those two events are totally unrelated and could have happened in a different order.

What am I missing here?

Answer 1

Note that causality is an undefined term in the paper. Lamport is using it in an informal explanation. He's assuming that could causally affect is an intuitive concept that will mean the same thing to his readers as it does to him. I think for Lamport $a$ could causally affect $b$ actually means something more like information could flow from $a$ to $b$ or $a$ could impact the behavior of $b$, than the classic Aristotelian idea of $b$ is a physical consequence of $a$.

For example, suppose a computer is executing a program with two statements:

a: X := 1
b: print X

I think we could all agree that statement a happens before b but I would not say that "executing the assignment statement (event a) caused the program to execute the print statement (event b)". On the other hand I might say something slightly different: "event a, (assigning the value 1 to X), affected the value printed by event b."

Now let's take a (potentially) more controversial example.

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

a happens before b, but I think most people would say, "there is no causal relationship between a and b." But in this paper there is a causal relationship between a and b. I'll try to explain this as succinctly as I can, but it's going to be long winded.

The paper is about state machines

Here's what Lamport has to say about the paper on his home page:

A distributed system can be described as a particular sequential state machine that is implemented with a network of processors. The ability to totally order the input requests leads immediately to an algorithm to implement an arbitrary state machine by a network of processors, and hence to implement any distributed system. So, I wrote this paper, which is about how to implement an arbitrary distributed state machine. ...

This is my most often cited paper. ... But I have rarely encountered anyone who was aware that the paper said anything about state machines. People seem to think that it is about either the causality relation on events in a distributed system, or the distributed mutual exclusion problem. People have insisted that there is nothing about state machines in the paper. I've even had to go back and reread it to convince myself that I really did remember what I had written.

Each process is a state machine, and the composition of the processes into a distributed system/algorithm is a state machine.

Lamport is implicitly using a short-hand notation which in digital design we call register transfers and each process is (implicitly) an algorithmic state machine. What we really care about is how each event affects the entire state of each process. Each register transfer statement is a succinct way of talking about a set of state transitions that depend on the prior state.

So in our "controversial" example the state of the machine has two parts $\langle X, Y \rangle$. The register transfer statement Y := 1 is shorthand for four different state transitions: $\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$, and $\langle 1, 1 \rangle \rightarrow \langle 1, 1 \rangle$. So what happened in statement a very much impacts the final state produced by statement b. In our case we know that the final state is $\langle 1, 1\rangle$, and that would not be the case had a not executed, or had a been a different statment (like X := 0).

The paper is about how much one of the distributed state machines can know about the states of the other state machines, so it very much matters what order things happen on each individual machine.

Answer 2

As it has been pointed out by both @kramthegram and @Wandering Logic, event $a$ "happened before" event $b$ does not imply that $a$ has physically caused $b$ (to happen).

Such causality used in Lamport's paper is often called potential causality. It captures all possibilities, often inducing a huge causality graph, and in practice it wrecks the scalability/performance of distributed systems.

To address these issues, we can consider explicit causality, or application-specified causal dependencies. One common example is social network applications: Alice has read 100 comments in a conversation thread and replied to 5 of them with a single comment. Her comment's immediate happens-before dependency could only consist of these 5 comments (instead of all these 100 comments with potential causality).

Which is the better causality? Well, it depends. For example, potential causality prevails in the research area of debugging multi-threaded programs. There are two main reasons (in my opinion): First, we have no context/semantics which tells whether two events ($\textsf{read}$ or $\textsf{write}$ operations) are effectively causally-related or not. Secondly, we want to capture all possible causality among events and reveal as many debugs as possible.

For more discussions about potential causality and explicit causality, please refer to this paper: The Potential Dangers of Causal Consistency and an Explicit Solution.

Answer 3

Your missing the selection of the word possible. It doesn't mean that the relationship is actually causal, just that it is possible for a to have a causal effect on b. His statements are not false, you're just reading more into them than he is actually stating. Just because it's possible doesn't mean it's true. The stronger statement is the inverse, if a does not proceed b it is impossible for a to have a causal affect on b. It's just a matter of wording.