Logical clocks: ordering cause and effect when service clocks disagree Intermediate

The problem

Orders writes the event “order 42 created” when its machine clock shows 10:00:05. Payments receives the event and logs “processed” when its machine clock shows 10:00:03.

Sort the logs by physical timestamp and “processed” comes before “created”. That is not a Kafka bug: the two machines’ clocks are skewed, or NTP just adjusted the time.

Two different questions:

Question	Tool
How much time has passed?	Wall clock (and a monotonic clock for deadlines)
Which event could have caused which?	Logical clock

Happens-before and the Lamport rule

Happens-before (a → b):

1. In the same process, a runs before b: a → b.
2. a sends a message and b receives that same message: a → b.
3. Transitivity: a → b and b → c imply a → c.

Two events with no causal path between them are concurrent: neither can be ordered first. It does not mean the CPU ran them in the same nanosecond.

Lamport clock: before each local or send event, L = L + 1; a send carries L in the message; on receiving a message carrying m, L = max(L, m) + 1. Guarantee: a → b implies L(a) < L(b). The converse does not hold.

class Lamport {
  private l = 0;
  tick()           { return ++this.l; }                          // local or send
  receive(m: number) { this.l = Math.max(this.l, m) + 1; return this.l; }
}

Drop Math.max and the receiving process can end up with an L lower than at send time, violating a → b ⇒ L(a) < L(b).

Messages carry causal information, not physical clocks

Enlarge diagram

Orders → MessageL=1

◀ Prev▶ PlayNext ▶↺ RestartStep 1/4

Orders increments its logical clock to 1 and sends a message carrying timestamp 1.

Actual demo output (running examples/src/lamport-clock/clock-demo.ts):

Orders sends event: 1 wall-clock: 10:00:05
Payments local event: 1 wall-clock: 10:00:02
Payments receives event: 2 wall-clock: 10:00:03
Orders next local event: 2 wall-clock: 10:00:06

Payments’ wall clock (10:00:03) is lower than Orders’ (10:00:05), but Lamport is still correct: L(send) = 1 < L(receive) = 2. The time strings are assigned on purpose to simulate skew; the script does not change the operating system clock.

Three processes, one concurrent pair

Three processes: Lamport clock and vector clock for each event

◀ Prev▶ PlayNext ▶↺ RestartStep 1/4

P1 sends m1 (a) and P3 has an internal event (d). No message path connects these two events, so a and d are concurrent even though both have L = 1.

Pair	L	Vector clock	Conclusion
a, b	1 < 2	[1,0,0] less than [1,1,0]	a → b (message m1 exists)
d, c	1 < 3	[0,0,1] and [1,2,0] are not comparable	Concurrent, even though L(d) < L(c)
f, e	2 < 4	[2,0,0] and [1,2,2] are not comparable	Concurrent, even though L(f) < L(e)

The Lamport clock gives L(d) < L(c), yet d did not cause c.

A vector clock keeps one component per process, so it captures both directions: V(a) < V(b) if and only if a → b. The price is metadata that grows with the number of processes.

If you only need a total order for tie-breaking, sort by (L, processId); that order does not turn two concurrent events into causally related ones.

Why this matters: last-write-wins

Some stores resolve conflicting writes with last-write-wins (LWW) based on timestamps, for example Cassandra (per cell, timestamp from the client or coordinator) and DynamoDB global tables across regions. (Amazon’s original Dynamo paper used vector clocks and let the application reconcile.) Suppose A’s clock is 5 seconds fast:

Real time	Writer	Value	Written timestamp
10:00:00	A (clock 5 s fast)	x = 1	10:00:05
10:00:02	B (correct clock)	x = 2	10:00:02

LWW keeps x = 1 because its timestamp is larger, even though B wrote later, and no error is reported. This is the real reason to care about clocks: silent data loss. For important data, use versions/vector clocks with a merge rule, or a clock with bounded error as below.

HLC and TrueTime in one line each

Technique	Idea	Used in
Hybrid Logical Clock (HLC)	Timestamp = wall clock plus a logical counter; tracks real time while preserving causality	CockroachDB, MongoDB (cluster time)
TrueTime	An API that returns an interval [earliest, latest] with bounded error; Spanner waits out the uncertainty (commit wait) before committing	Google Spanner

A note on using clocks: use a monotonic clock for deadlines and measuring durations (the wall clock can jump backward on an NTP step or leap second); use the wall clock only for display and logs.

Real-world example

The dashboard shows 'paid' before 'order created'

A dashboard sorts events from several services by each machine’s created_at and shows the payment status before the order-creation log.

• Investigate: attach trace/correlation IDs and message IDs, join send with receive, measure skew between machines.
• Do not fix it by re-sorting on created_at.
• Per-order ordering: use orderId as the partition key (Kafka message key) and a state machine in the consumer.
• Logical clocks help interpret cross-service relationships, but they do not replace the mechanism that orders data.

Adding logical clocks to a real system requires decisions: store them in a header or an envelope, restore them after restart (the demo keeps them in memory, so they are lost when the process dies), and make sure proxies do not drop the header.

Trade-offs

What logical clocks help with

• Preserve the send → receive relationship without perfectly synchronized clocks
• Small metadata, simple rules
• Separate causal order from wall-clock display order

What they do not solve

• Do not measure real time; do not use them as a TTL or deadline
• L(a) < L(b) does not prove a → b (vector clocks are needed)
• Do not by themselves solve concurrent writes, idempotency or cross-service transactions

Common mistakes

Common pitfall

Sorting logs by wall clock and inferring causality. Skew makes the receive appear before the send. Use trace/message IDs to join the chain.

Common pitfall

Seeing L(a) < L(b) and concluding a → b. The three-process table has two concurrent pairs whose L values still differ.

Common pitfall

Using wall-clock LWW for data that must not be lost. A few seconds of skew is enough for an earlier write to overwrite a later one without any warning.

Summary

Key takeaways

• Happens-before: order within a process, send → receive, transitivity
• On receive: L = max(L, m) + 1; a → b implies L(a) < L(b), not the other way around
• Vector clocks capture both directions and detect concurrency, at the cost of metadata per process
• Wall-clock LWW silently loses data when clocks are skewed
• HLC (wall plus logical) and TrueTime (error interval, commit wait) are two safer ways to use real clocks

Self-check: (1) Why does Payments log 10:00:03 even though the message it received was logged at 10:00:05? (2) Are two events with L = 2 concurrent? (3) In the three processes above, what does the vector clock tell you that L does not?

References

• Time, Clocks and the Ordering of Events — Leslie Lamport
• TrueTime and external consistency — Google Cloud Spanner
• Logical Physical Clocks (HLC) — Kulkarni et al.