Distributed systems
Part 3 of 6 · Time, Clocks & OrderingLamport Clocks - Happens-Before, Logical Timestamps & Total Order
Happens-before precisely; Lamport clock rules and total order with (ts, pid) tie-break (runnable); runnable proof that the clock condition holds but L(a)<L(b) does not imply causality; Lamport vs wall vs vector vs HLC vs consensus log index; Raft terms and fencing tokens as logical clocks; pitfalls (tie-break, persistence).
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
When does a happen before b?
Answer
Earlier on the same process, a send before its matching receive, or a chain of those.
L2
State the clock condition.
Answer
If a happens-before b, then L(a) < L(b). The converse is false.
L3
How do you get a total order?
Answer
Sort by (timestamp, process id). Every node must use the same tie-break.
L4
Why is receive max(local, message) + 1?
Answer
The receiver may already be ahead. The max keeps program order, and +1 is strictly after the send and the previous local event.
L5
Can Lamport clocks detect a conflict?
Answer
No. Concurrent writes get different timestamps and one wins. Detection needs vector clocks, version vectors, or a merge.
L6
How is a Raft term related?
Answer
A term is a monotonic number carried on messages. A node that sees a higher term updates and steps down, the same role a Lamport clock plays for leadership.
L7
What must you not forget across a restart?
Answer
The counter must not go backwards. Persist it or re-derive it from the log.
Failure modes
Concurrent edits get a silent winner
The example has 10 concurrent pairs with L(a) < L(b). A last-writer-wins rule on those numbers drops an edit nobody saw.
Equal counters without a tie-break
Two events with the same counter have no defined order, so replicas can diverge.
The counter restarts at zero
New events sort before events this process already issued.
Misconceptions
L(a) < L(b) means a caused b.
It means a might have happened before b, or they were concurrent.
Lamport timestamps answer what happened in the last hour.
The counter is not wall time. It only orders events.
A total order of events you have seen is the full history.
A late message with a smaller timestamp can still extend the order. Protocols that need 'everything before T' wait to hear from every process.
Interviewer traps
Proving causality from a smaller Lamport timestamp.
State the clock condition, then give a concurrent counterexample such as x and b on this page.
Using a vector clock when a total order is all the caller needs.
Say you would pay O(n) metadata and still need a tie-break to linearize concurrent events.
Design scenario
Same prompt for every reader.
Requirements
Causal overwrites must beat the version they read. Concurrent writes must not be described as detected.
Traffic / scale
The lesson trace: P1 sends m1 at L=2, P2 receives at 3, P3 has concurrent local events at 1 and 2.
Latency
The stamp piggybacks on the message. There is no quorum round trip.
Consistency
The total order respects happens-before. It does not identify concurrency.
Availability
Ordering does not wait for a leader. A protocol that needs every prior event must still hear from every process.
Failure assumptions
- Two events can be concurrent.
- A process can restart.
- A message can arrive after others have already sorted a prefix.
Constraints
- Do not use the wall clock for this causal stamp.
- Do not claim the numbers detect the conflict.
Prompt
Replicas apply writes with a client-carried counter. Two users edit the same key without seeing each other.
API
What does the client send with a write that must beat the version it read?
Data
What pair do you sort, and what do you persist across restart?
Architecture
Where would you switch to a vector clock or a quorum log instead?
What a Lamport number is allowed to mean
Prefer
A causality-respecting total order
If a happened before b, the number is smaller. Every replica sorts (timestamp, process id) the same way.
- No synchronized clocks.
- The example trace has zero clock-condition violations.
- Causal last-writer-wins can stamp max(seen, local) + 1.
Alternative
Reading the number as proof of cause
Concurrent events still receive comparable timestamps, and one of them silently wins.
- The example has 10 concurrent pairs where the first number is still smaller.
- L(x) = 1 and L(b) = 3 even though x and b are concurrent.
- Two users who never saw each other still lose one edit.
From an event to one shared order
The sequence on this page is the same trace the Python and TypeScript snippets run.
- 1
Stamp local events and sends
Increment the process counter. The message carries that value. - 2
Take max plus one on receive
The receiver may already be ahead. max keeps its program order, and +1 puts the receive after both the send and its previous event. - 3
Sort by timestamp, then process id
Without the process id, equal counters have no order and replicas can diverge. - 4
Do not infer concurrency from the numbers
The runnable check finds 0 clock-condition violations and 10 misleading concurrent pairs.
Overview
Lamport's 1978 insight was to stop asking "what time is it?" and ask "what could have influenced what?". The happens-before relation captures causality: a -> b if a came earlier in the same process, or a was a send and b the matching receive, or there is a chain of those. A Lamport clock is just a counter per process that respects this relation: if a -> b then L(a) < L(b). Add the process id as a tie-breaker and every node can compute the same total order of events without synchronized clocks. What it cannot do is tell you that two events were concurrent; the numbers alone never prove causality.
Happens-before, precisely
- Program order: if a and b are on the same process and a comes first, a -> b.
- Messages: if a is "send m" and b is "receive m", a -> b.
- Transitivity: if a -> b and b -> c, then a -> c.
- Concurrency: if neither a -> b nor b -> a, then a and b are concurrent (a || b). They could not have influenced each other, whatever the wall clocks say.
This is the same idea as the happens-before relation in language memory models (Java, C++, Go), applied to processes and messages instead of threads and memory operations.
The algorithm
- Each process keeps an integer counter, starting at 0.
- Before every local event or send, increment the counter and stamp the event with it.
- Every message carries the sender's counter.
- On receive, set counter = max(local, message) + 1 and stamp the receive event.
- For a total order, compare (counter, process id) lexicographically.
Sequence
- 1
"P1"
"Step 1: local event a, L=1"
- 2
"P3"
"Step 2: local events x (L=1) and y (L=2), concurrent with P1 and P2"
- 3
"P1" → "P2"
"Step 3: send m1 with L=2"
- 4
"P2"
"Step 4: receive m1, L = max(0, 2) + 1 = 3"
- 5
"P2" → "P3"
"Step 5: send m2 with L=4"
- 6
"P3"
"Step 6: receive m2, L = max(2, 4) + 1 = 5"
- 7
"P1"
"Step 7: local event b, L=3 (concurrent with x and y, yet L(x) < L(b))"
Lesson map
Lamport Clocks - Happens-Before, Logical Timestamps & Total Order
Happens-before precisely; Lamport clock rules and total order with (ts, pid) tie-break (runnable); runnable proof that the clock condition holds but L(a)<L(b) does not imply causality; Lamport vs wall vs vector vs HLC vs consensus log index; Raft terms and fencing tokens as logical clocks; pitfalls (tie-break, persistence).
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB p1["P1"] p2["P2"] p3["P3"] p1 -->|Step 3: send m1 with L=2| p2 p2 -->|Step 5: send m2 with L=4| p3
Lamport clocks in code (runnable)
# Lamport clocks on three processes, plus the (timestamp, process id) total order.
# Rule 1: before each local event or send, counter += 1.
# Rule 2: on receive, counter = max(counter, msg_ts) + 1.
class Process:
def __init__(self, pid: str):
self.pid, self.clock, self.log = pid, 0, []
def local(self, what: str):
self.clock += 1
self.log.append((self.clock, self.pid, what))
def send(self, what: str) -> int:
self.clock += 1
self.log.append((self.clock, self.pid, f"send {what}"))
return self.clock # timestamp travels with the message
def recv(self, what: str, msg_ts: int):
self.clock = max(self.clock, msg_ts) + 1
self.log.append((self.clock, self.pid, f"recv {what}"))
P1, P2, P3 = Process("P1"), Process("P2"), Process("P3")
P1.local("a: deposit") # P1:1
m1 = P1.send("m1") # P1:2
P3.local("x: unrelated write") # P3:1 (concurrent with everything on P1/P2 so far)
P3.local("y: unrelated write") # P3:2
P2.recv("m1", m1) # P2: max(0,2)+1 = 3
m2 = P2.send("m2") # P2:4
P3.recv("m2", m2) # P3: max(2,4)+1 = 5
P1.local("b: audit") # P1:3
events = P1.log + P2.log + P3.log
print("per-process logs (ts, pid, event):")
for p in (P1, P2, P3):
print(" ", p.pid, [(ts, ev) for ts, _, ev in p.log])
# Total order: sort by (Lamport ts, process id). Every node computes the SAME order,
# which is what Lamport's mutual-exclusion algorithm and replicated state machines rely on.
print("\ntotal order by (ts, pid):")
for ts, pid, ev in sorted(events):
print(f" ({ts}, {pid}) {ev}")
# The catch: L(P3 'x') = 1 < L(P1 'b') = 3, yet 'x' and 'b' are concurrent.
# Lamport timestamps never let you conclude causality from the numbers alone.Output:
per-process logs (ts, pid, event):
P1 [(1, 'a: deposit'), (2, 'send m1'), (3, 'b: audit')]
P2 [(3, 'recv m1'), (4, 'send m2')]
P3 [(1, 'x: unrelated write'), (2, 'y: unrelated write'), (5, 'recv m2')]
total order by (ts, pid):
(1, P1) a: deposit
(1, P3) x: unrelated write
(2, P1) send m1
(2, P3) y: unrelated write
(3, P1) b: audit
(3, P2) recv m1
(4, P2) send m2
(5, P3) recv m2Every node that collects these events and sorts by (timestamp, process id) gets exactly this order. That determinism is what makes Lamport timestamps useful for replicated state machines, total order broadcast and Lamport's own mutual-exclusion algorithm (each process queues requests ordered by timestamp and enters the critical section when its request is first and it has heard from everyone with a later timestamp).
The blind spot: concurrency (runnable)
The code below computes the true happens-before relation with graph reachability, then checks two things on the same trace: the clock condition always holds, and yet many concurrent pairs still have "smaller" Lamport timestamps.
// Clock condition check: if a -> b (happens-before) then L(a) < L(b).
// The converse is FALSE: L(a) < L(b) does not mean a -> b. We prove both on a small trace
// by computing true happens-before with graph reachability and comparing to Lamport numbers.
type Ev = { id: string; proc: string; kind: "local" | "send" | "recv"; from?: string };
// Program order per process plus message edges (recv.from = matching send id).
const trace: Ev[] = [
{ id: "a", proc: "P1", kind: "local" },
{ id: "s1", proc: "P1", kind: "send" },
{ id: "x", proc: "P3", kind: "local" },
{ id: "r1", proc: "P2", kind: "recv", from: "s1" },
{ id: "y", proc: "P3", kind: "local" },
{ id: "s2", proc: "P2", kind: "send" },
{ id: "b", proc: "P1", kind: "local" },
{ id: "r2", proc: "P3", kind: "recv", from: "s2" },
];
// 1) Lamport timestamps.
const clock = new Map<string, number>();
const L = new Map<string, number>();
for (const e of trace) {
const c = clock.get(e.proc) ?? 0;
const next = e.kind === "recv" ? Math.max(c, L.get(e.from!)!) + 1 : c + 1;
clock.set(e.proc, next);
L.set(e.id, next);
}
// 2) Happens-before edges: program order + send -> recv.
const edges = new Map<string, string[]>();
const lastOnProc = new Map<string, string>();
for (const e of trace) {
const prev = lastOnProc.get(e.proc);
if (prev) edges.set(prev, [...(edges.get(prev) ?? []), e.id]);
if (e.from) edges.set(e.from, [...(edges.get(e.from) ?? []), e.id]);
lastOnProc.set(e.proc, e.id);
}
function hb(a: string, b: string): boolean { // depth-first reachability a ~> b
const stack = [...(edges.get(a) ?? [])];
const seen = new Set<string>();
while (stack.length) {
const n = stack.pop()!;
if (n === b) return true;
if (!seen.has(n)) { seen.add(n); stack.push(...(edges.get(n) ?? [])); }
}
return false;
}
let violations = 0;
const misleading: string[] = [];
for (const a of trace) for (const b of trace) {
if (a.id === b.id) continue;
if (hb(a.id, b.id) && !(L.get(a.id)! < L.get(b.id)!)) violations++;
const concurrent = !hb(a.id, b.id) && !hb(b.id, a.id);
if (concurrent && L.get(a.id)! < L.get(b.id)!) misleading.push(`${a.id}(${L.get(a.id)}) < ${b.id}(${L.get(b.id)})`);
}
console.log("Lamport:", [...L].map(([k, v]) => `${k}=${v}`).join(" "));
console.log("clock-condition violations (must be 0):", violations);
console.log(`concurrent pairs where L(a) < L(b) anyway: ${misleading.length}`);
console.log(" e.g.", misleading.slice(0, 4).join(", "));Output:
Lamport: a=1 s1=2 x=1 r1=3 y=2 s2=4 b=3 r2=5
clock-condition violations (must be 0): 0
concurrent pairs where L(a) < L(b) anyway: 10
e.g. a(1) < y(2), x(1) < s1(2), x(1) < r1(3), x(1) < s2(4)ExpectedLamport: a=1 s1=2 x=1 r1=3 y=2 s2=4 b=3 r2=5 clock-condition violations (must be 0): 0 concurrent pairs where L(a) < L(b) anyway: 10 e.g. a(1) < y(2), x(1) < s1(2), x(1) < r1(3), x(1) < s2(4)
Press Run. Snippets must be self-contained — no network, files, or native modules.
So L(a) < L(b) means "a might have happened before b, or they were concurrent". If two users edited the same document on different replicas without seeing each other, a Lamport timestamp will happily pick a winner and the other edit is gone. To detect that case you need vector clocks (next page).
Lamport clocks vs alternatives
| Approach | What you get | Cost | Typical use |
|---|---|---|---|
| Wall clock | Approximate real-time order, no causal guarantee | 8 bytes, NTP | Logs, human timestamps |
| Lamport clock | Causality-respecting total order | 8 bytes, piggybacked on messages | Total order broadcast, ordering operations in a log, LWW with causal safety |
| Vector clock | Exact causality and concurrency detection | One entry per node or actor | Multi-writer replication, conflict detection |
| Hybrid logical clock | Lamport guarantees plus closeness to wall time | Time + small counter | MVCC timestamps in distributed databases |
| Consensus log index (Raft, Paxos) | Total order agreed by a quorum | Quorum round trips | Replicated state machines, metadata stores |
A useful framing: a Raft log index is a coordinated total order (a quorum agrees on position N), while a Lamport timestamp is an uncoordinated total order (each node computes the same order from the stamps it has seen, but there is no agreement on when you have seen everything).
Where Lamport-style clocks show up
- Total order broadcast and state machine replication: early designs and teaching examples order commands by (timestamp, node).
- Kafka-style sequence numbers and Raft terms: not Lamport clocks exactly, but the same "monotonic counter that only moves forward and carries causality" idea; a Raft term is effectively a logical clock for leadership.
- Fencing tokens: a lock service hands out increasing numbers so a resource can reject requests from an older holder, which is a logical clock used for safety.
- Causal LWW: many systems stamp writes with max(seen, local) + 1 so a client's later write always beats the version it read, avoiding the skewed wall-clock LWW bug from the hub page.
- Logical timestamps in CRDTs: LWW-registers and sequence CRDTs often use Lamport timestamps plus a replica id as the tie-break.
Pitfalls
- Forgetting the tie-break: without the process id, two events with the same counter have no defined order and replicas can diverge.
- Not persisting the counter: after a restart the counter must not go back below what the node has already issued, or new events can sort before old ones. Persist it or re-derive it from the log.
- Treating timestamps as time: L=1,000,000 says nothing about when; you cannot answer "what happened in the last hour" with Lamport clocks.
- Assuming you have seen everything: a total order over the events you know about can still be extended by a late message with a smaller timestamp. Protocols that need "everything before T is known" (like Lamport's mutex) wait to hear from every process.
What happens if you choose otherwise
- Wall clock instead of Lamport for causal LWW: the skewed-node bug: a reply can be stamped before the message it answers.
- Vector clocks when a total order is all you need: you pay O(n) metadata and still need a tie-break to linearize concurrent events.
- Consensus when ordering does not need agreement: you pay quorum latency and availability for a guarantee the application doesn't use.
Interview Q&A
State the clock condition and its converse.
Answer
Clock condition: if a -> b then L(a) < L(b). The converse (L(a) < L(b) implies a -> b) is false; concurrent events get arbitrary relative timestamps.
How do you get a total order from Lamport clocks?
Answer
Order by (timestamp, process id). Any deterministic tie-break works as long as every node uses the same one.
Why is the receive rule max(local, msg) + 1 and not just msg + 1?
Answer
The receiver may already be ahead because of its own events; taking the max keeps its own program order intact, and the +1 makes the receive strictly later than both the send and the receiver's previous event.
Can Lamport clocks tell you that two writes conflicted?
Answer
No. Two concurrent writes get different timestamps and one of them simply "wins". Detecting the conflict requires vector clocks, version vectors, or a CRDT that merges both.
How is a Raft term related to a logical clock?
Answer
A term is a monotonically increasing number that every message carries; a node that sees a higher term updates and steps down. It plays the same role as a Lamport clock for leadership: stale leaders are recognized by their lower number.
What happens if you omit the process-id tie-break?
Answer
Two events with the same counter have no defined order. Replicas can sort them differently and diverge. Any deterministic tie-break works if every node uses the same one.
Why persist the Lamport counter?
Answer
After a restart the counter must not fall below values the node has already issued, or new events sort before old ones. Persist it, or re-derive it from the log.
How is a fencing token a logical clock?
Answer
The lock service hands out increasing numbers. The protected resource rejects a request whose number is older, so a stale holder cannot write even if it still believes it holds the lock.
Check yourself
Draw three processes and one message. Assign Lamport numbers by hand, then name one pair that is concurrent even though the numbers increase. Check it against the total order printed on this page.
Elsewhere in the library
These pages stay as they are. This lesson only points at them: Happens-Before & Memory Visibility, Raft Consensus — Leader Election, Log Replication & Safety, Partition Keys — Ordering Guarantees vs Parallel Throughput, Ordering, Partitions, Poison Messages & Retry/DLQ Strategy.