Understanding Happens-Before in Distributed Systems

The Trouble with Physical Clocks

Your first instinct as an engineer might be to simply attach a timestamp to every operation. When a conflict arises, just pick the one with the later timestamp. This seems simple enough, but which machine's clock do you trust? In a distributed system, there is no single, perfectly synchronized source of time.

Relying on physical clocks leads to several problems:

• Clock Skew: The clocks on different computers drift at different rates. Even with synchronization protocols like NTP (Network Time Protocol), there's always a margin of error. One user's machine might be a few milliseconds ahead of another's.
• Network Latency: A message's travel time across the network can be greater than the clock skew between two machines. This can lead to situations where a reply is timestamped before the original message it's replying to.

The core issue is that physical time doesn't accurately capture causality. A reply is caused by the original message, so it must logically happen after it, regardless of what any wall-clock says. This is why we need to shift our thinking from physical time to logical time.

The "Happens-Before" Relation (→)

Instead of relying on physical clocks, we can define a logical ordering based on a simple, observable principle: a message must be sent before it can be received. Leslie Lamport used this idea to define the happens-before relation, denoted by an arrow (→). The expression a → b is read as "a happens-before b."

This relation is built on three straightforward rules.

As explained in the video, we can say that event a happens-before event b (a → b) if any of the following conditions are true:

1. Same Process: If a and b are events within the same process (e.g., on the same user's device), and a occurred before b, then a → b. This is the natural order of execution on a single machine.
2. Message Passing: If a is the event of sending a message, and b is the event of receiving that same message, then a → b. A message cannot be received before it is sent.
3. Transitivity: If we know that a → c and c → b, then we can infer that a → b. This allows us to chain causal relationships across multiple processes and messages.

This definition is powerful because it's based entirely on the flow of information within the system, not on any external, unreliable clock.

Visualizing Order: Lamport Diagrams

To make this abstract definition concrete, we use space-time diagrams, also known as Lamport diagrams. These diagrams are the standard visual language for reasoning about events in a distributed system.

Let's analyze the diagram above using our rules:

• Rule 1 (Same Process): Within Process P, p1 → p2.
• Rule 2 (Message Passing): A message is sent from Process P at event p1 and received by Process Q at event q1. Therefore, p1 → q1.
• Rule 3 (Transitivity): We know p1 → q1 (from Rule 2) and q1 → q2 (from Rule 1). Therefore, we can conclude that p1 → q2. You can think of this as following a "causal path" from p1 to q2.

Partial Order and Concurrency

What happens if we try to relate p1 and r1 in the diagram?

• There's no path from p1 to r1.
• There's no path from r1 to p1.

According to our definition, neither p1 → r1 nor r1 → p1 is true. When two events are not ordered by the happens-before relation, we say they are concurrent, written as p1 || r1.

This is the most important consequence of the happens-before relation. It defines a partial order, not a total one. It can definitively tell us if one event caused another, but it also identifies events that are causally independent.

Crucially, concurrent does not mean simultaneous. It means the events occurred without knowledge of one another. In your collaborative canvas, if User A moves a node while offline, and User B edits the color of that same node while online, those two operations are concurrent. The happens-before relation cannot order them. These are precisely the situations that CRDT merge functions are designed to handle.

Causality and Causal Anomalies

The happens-before relation is fundamentally about causality.

• If a → b, then a might have caused b. There is a causal pathway for information to flow from a to b.
• If a || b, then a could not have caused b, and b could not have caused a.

When a system displays events in an order that violates the happens-before relation, it leads to confusing "causal anomalies."

Conclusion

In this lesson, we have established a formal, reliable way to reason about the order of events in our distributed system.

Here are the key takeaways:

• Physical clocks are unreliable for ordering events in a distributed system due to clock skew and network latency.
• The happens-before relation (→) provides a partial ordering of events based on causality, not physical time.
• It is defined by three rules: order within a single process, the sending and receiving of messages, and transitivity.
• Events that are not ordered by the happens-before relation are concurrent (||). This means they are causally independent, not necessarily simultaneous.
• Recognizing concurrent operations is the first step toward resolving the "merge problem" we identified in the previous lesson.

You now have the theoretical foundation to understand how events relate to each other in time. However, a partial order isn't always enough. Sometimes, we need to enforce a single, consistent, total order across all users.

In the next lesson, we will build directly on this foundation to implement Lamport timestamps. This is a simple but brilliant algorithm that uses the happens-before logic to assign a number to every event, allowing us to create a total ordering. This will be our first piece of practical, hands-on code for managing time in a distributed system.