I\'m reading Lamport\'s \"Time, Clocks, and the Ordering of Events in a Distribu
ID: 647719 • Letter: I
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?
Explanation / Answer
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 generates a huge causality graph, and in practice 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 (read or 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.