[Solved]: Happened-before and Causal order

Problem Detail: 

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?

Asked By : Nemo

Answered By : Wandering Logic

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40061