Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 36 ยท Time and Ordering

Lamport Clocks and Happens-Before

Learn the happens-before relation and implement Lamport logical clocks with message passing to get a consistent total order of events in Python.

If physical clocks cannot be trusted to order events across machines, what can? In 1978 Leslie Lamport gave an answer that reshaped the field: stop asking when an event happened, and ask what could have influenced what. Two events are ordered if one could have caused the other, and unordered if neither could have.

From that idea comes a very small algorithm, the Lamport clock: a counter on each node, updated by two simple rules. It uses no hardware time at all, yet it gives every event a number consistent with causality. In this lesson you will learn the happens-before relation, implement the clock, and turn it into a total order of events.

The happens-before relation

Write a โ†’ b to mean "a happens before b". This is not about wall-clock time; it is defined by three rules:

  1. Same node. If a and b are events on the same node and a comes first in that node's local order, then a โ†’ b.
  2. Messages. If a is the sending of a message and b is the receiving of that same message, then a โ†’ b. (A message cannot arrive before it was sent.)
  3. Transitivity. If a โ†’ b and b โ†’ c, then a โ†’ c.

If neither a โ†’ b nor b โ†’ a, the events are concurrent, written a โˆฅ b. Concurrent does not mean "at the same instant". It means no chain of local steps and messages connects them, so neither could have affected the other. The nodes simply have not heard from each other yet.

sequenceDiagram
    participant A
    participant B
    participant C
    A->>A: a1
    A->>B: send m1
    B->>B: receive m1 (b1)
    B->>C: send m2
    C->>C: c1 (concurrent with a1)
    C->>C: receive m2 (c2)

Here a1 โ†’ b1 (via m1) and b1 โ†’ c2 (via m2), so a1 โ†’ c2. Event c1 happened with no message link to a1 or b1, so it is concurrent with them.

Two rules run a Lamport clock

Local event Add 1 to your counter.
Send Add 1, then stamp the message with the counter.
Receive Set counter to max(yours, message) + 1.

The counter never decreases, and a receive always jumps past the send.

1 / 2

The Lamport clock algorithm

Each node keeps an integer time, starting at 0.

  • Before any event on the node (a local step or a send), increment: time = time + 1. A send attaches the new time to the message.
  • On receive of a message stamped t: set time = max(time, t) + 1.

That is all. It gives the clock condition: if a โ†’ b, then L(a) < L(b). A cause always has a smaller number than its effect, because each message hop pushes the receiver's clock past the sender's stamp.

The converse is not true. If L(a) < L(b) you cannot conclude a โ†’ b; the events might be concurrent. Lamport clocks tell you "if smaller number is false, definitely not caused by it", but not the other direction. Detecting concurrency is the job of vector clocks.

Implementing it

We model each node as a small object and deliver messages by hand, so you can follow every stamp.

Python Lamport clocks with message passing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the stamps by hand. When B receives m1 (stamped 2) its own clock was 1, so it jumps to max(1, 2) + 1 = 3: the receive is after the send, as it must be. When C receives m2 (stamped 4) its clock was 2, so it jumps to 5. Note that C's two unrelated events have small numbers (1 and 2) even though they might have happened later in real time: they are concurrent with A's work, and any number is consistent with that.

From partial order to total order

Happens-before is a partial order: some pairs of events are not ordered at all. Many algorithms want a single list, the same on every node. The trick is to sort by Lamport time, and break ties with the node identifier:

(L(a), node_a) < (L(b), node_b)

This is a total order consistent with causality: if a โ†’ b, then a sorts before b. Different events from different nodes may have the same Lamport time, so the tie-break makes the order deterministic. The order between concurrent events is arbitrary, but crucially every node computes the same arbitrary order once it knows about the same events.

Python A total order with tie-breaks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

What can you build with it?

Lamport's own example was a distributed mutual exclusion algorithm: each node broadcasts a request stamped with its Lamport time, and every node grants access in the order of those stamps. Because everyone sorts the requests the same way, they agree on who goes first without a central coordinator. Other uses:

  • Replicated state machines. If all nodes apply operations in the same total order, they stay identical (the foundation behind Raft and Paxos).
  • Versioning. Using (counter, node) pairs as version numbers gives a deterministic winner for conflicting writes. Unlike wall-clock LWW, a causally later write never loses to an earlier one, because it carries a larger counter.
  • Logging and debugging. Stamp log lines with Lamport times so an effect never appears before its cause when logs from several machines are merged.

Limits

Lamport clocks alone cannot tell you whether two events are concurrent, and the total order they give has no relationship to real time: an event that happened an hour later on a quiet node may have a smaller stamp. They also do not provide liveness in a faulty system: for the mutual-exclusion example, a crashed node that never replies blocks everyone, since all nodes must hear from all others. That is why we need failure detection and consensus protocols.

Many real systems use a hybrid logical clock: a physical timestamp combined with a Lamport-style counter, so numbers stay close to real time but still respect causality. The idea is the same: take the maximum of what you have seen, then add one.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does "a happens before b" (a โ†’ b) mean in this lesson?

    Happens-before is about possible causality. It is built from local order on one node, message send and receive, and transitivity, not from physical time.
  2. 2. A node's Lamport clock is 7 and it receives a message stamped 12. What is its clock afterwards?

    The rule is max(7, 12) + 1 = 13. The receive must be stamped later than the send.
  3. 3. If L(a) < L(b) for two events, what can you conclude?

    Lamport clocks guarantee only one direction: a โ†’ b implies L(a) < L(b). Smaller stamps do not prove causality, which is why vector clocks exist.
  4. 4. Why do we add a node id when sorting events by Lamport time?

    Different nodes can produce the same Lamport number. Comparing (time, node id) makes the order deterministic and identical everywhere.

Summary

  • Happens-before (โ†’) orders events by possible causality: same-node order, send before receive, and transitivity; unrelated events are concurrent.
  • A Lamport clock is a counter: increment on every event, and on receive set it to max(local, message) + 1.
  • If a โ†’ b then L(a) < L(b), but the reverse does not hold.
  • Sorting by (Lamport time, node id) gives a total order that all nodes can compute identically and that respects causality.
  • To detect concurrency you need more information than one number per node.

Next: Vector Clocks and Causality, which can tell causal order from concurrency.