Lamport Timestamps: Ordering Events in Distributed Systems

From Time to Causality: The "Happens-Before" Relation

If we can't use physical clocks to order events, we need a new principle. In distributed systems, that principle is causality. Intuitively, if event A must happen for event B to be possible, then we say A "happened before" B. For example, sending a network request happens before receiving the response.

To formalize this, let's watch a video that introduces the problem of causal ordering and defines the crucial "happens-before" relationship.

As the video explained, the "happens-before" relation (often written as A -> B) is defined by three simple rules:

1. On the same node: If event A occurs before event B on the same node, then A -> B. This is based on the local execution order of a single process.
2. Across nodes (messages): If A is the event of sending a message and B is the event of receiving that same message, then A -> B.
3. Transitivity: If A -> B and B -> C, then A -> C. This allows us to chain causal dependencies across the system.

This set of rules defines a partial order. Some events are causally related (one happened before the other), but other events are concurrent. Concurrent events (written A || B) are those where neither A -> B nor B -> A is true. This doesn't mean they happened at the same physical time, but rather that they occurred independently, without knowledge of one another.

Our goal is to create a timestamping system that respects this causal order.

Lamport Timestamps: An Algorithm for Causal Ordering

In 1978, Leslie Lamport introduced a simple algorithm to assign a number to every event in a distributed system, such that the ordering of these numbers is consistent with the happens-before relationship. These numbers are called Lamport timestamps or logical clocks.

Let's watch a short video introducing the concept and the algorithm.

The algorithm is elegant in its simplicity. Each node in the system maintains a single integer counter. Here are the rules, which you've just seen in the video:

1. Initialization: Each node initializes its counter to 0.
2. Local Event: Before executing an event, a node increments its counter.
3. Sending a Message: When a node sends a message, it increments its counter and includes the new counter value in the message.
4. Receiving a Message: When a node receives a message, it updates its own counter by taking the maximum of its current value and the timestamp from the message, and then increments it by 1. In pseudocode: counter = max(local_counter, message_counter) + 1.

Let's look at a static diagram to see this in action.

Now, let's see this animated in the video you started earlier.

Properties and Limitations

Lamport timestamps have one crucial guarantee, known as the Clock Consistency Condition:

If event A happens-before B (A -> B), then the Lamport timestamp of A is less than the Lamport timestamp of B (L(A) < L(B)).

This is exactly what we wanted: the timestamps respect causality.

However, the reverse is not true. If L(A) < L(B), it does not necessarily mean A -> B. It's possible that A and B are concurrent. This is the primary limitation of Lamport clocks. You can't use them to tell if two events are causally related or just happened to get ordered timestamps by chance.

Creating a Total Order

Despite not being able to distinguish concurrency, Lamport clocks can be used to create a total order of all events in the system that is consistent with causality. This is extremely useful for algorithms that require all nodes to process events in the same order (e.g., for state machine replication).

The trick, as you saw, is to use a tie-breaker. Instead of just a timestamp L(E), we use a pair: (L(E), NodeID).

We can then define a total order < such that event A < B if:

• L(A) < L(B), OR
• L(A) = L(B) AND NodeID_A < NodeID_B (assuming node IDs can be lexicographically or numerically compared).

This ensures that every pair of distinct events has a defined order, and that order will never violate causality.

For further reading and a different perspective, the following article provides a concise explanation of Lamport clocks and their properties.

Conclusion

In this lesson, we took our first step into the world of logical time, which is foundational to reasoning about distributed systems.

Here are the key takeaways:

• Causality is Key: When physical time is unreliable, we rely on the happens-before relation (->) to define a partial order of events based on local execution and message passing.
• Lamport Timestamps Capture Causality: Lamport clocks are simple counters that generate timestamps L(E) for every event E, guaranteeing that if A -> B, then L(A) < L(B).
• The Algorithm: The rules are simple: increment for local events, and upon receiving a message, update your clock to max(local, received) + 1.
• Limitation: You cannot infer causality from Lamport timestamps alone. If L(A) < L(B), events A and B might be causally related, or they might be concurrent.
• Total Ordering: By combining the Lamport timestamp with a unique node ID (L(E), NodeID), we can create a total order of all events that is consistent with the partial causal order.

We've seen that Lamport clocks can tell us that A might have caused B, but they can't tell us for sure. What if we need to know definitively whether two events are concurrent?

Preview of the next lesson: We will explore vector clocks. Vector clocks are an extension of Lamport clocks that solve this exact problem. They allow a node to not only determine if one event happened before another but also to detect if two events are concurrent. This provides a much richer understanding of the system's causal history.