Lamport Timestamps: Ordering Events Without a Global Clock
Series: System Design · Distributed Systems — Pillar 8 of 8
Systems Design
| # | Post | What it covers |
|---|---|---|
| 00 | Distributed Systems: What Happens When Machines Disagree | Twenty concepts covering network partitions, consensus, clocks, distributed transactions, CDC, erasure coding, and observability. The final pillar. |
| 01 | Network Partitions: The Failure Mode You Can't Design Away | Network partitions are inevitable. Learn what happens when nodes can't communicate, how systems choose between availability and consistency, and what that means in practice. |
| 02 | Split-Brain: When Two Nodes Both Think They're the Leader | Split-brain occurs when two nodes both believe they're the primary. Learn how it happens, why it causes data corruption, and how STONITH and fencing prevent it. |
| 03 | Heartbeats: How Nodes Know Their Peers Are Alive | Heartbeats let nodes detect peer failures. Learn how timeouts, phi accrual failure detectors, and the tradeoff between false positives and detection speed work. |
| 04 | Leader Election: Agreeing on Who's in Charge | Leader election coordinates which node acts as primary. Learn the bully algorithm, Raft-based election, and why exactly-one-leader guarantees are hard to achieve. |
| 05 | Consensus Algorithms: Agreeing on a Value Across Failures | Consensus lets distributed nodes agree on a value despite failures. Learn what FLP impossibility means, what Paxos and Raft provide, and where consensus is used. |
| 06 | Quorum: How Many Nodes Must Agree? | Quorum determines how many nodes must agree for an operation to succeed. Learn how R + W > N ensures consistency in distributed databases like Cassandra and DynamoDB. |
| 07 | Paxos: The Algorithm That Started It All | Paxos is the foundational distributed consensus algorithm. Learn how its two phases work, why it's hard to implement, and what systems use it in production. |
| 08 | Raft: Consensus Made Understandable | Raft makes distributed consensus understandable. Learn how leader election, log replication, and safety work in the algorithm that powers etcd, CockroachDB, and TiKV. |
| 09 | Gossip Protocol: Decentralised Cluster Communication | Gossip protocols propagate information across a cluster without a central coordinator. Learn how epidemic spreading works and where it's used in production. |
| 10 | Logical Clocks: When Physical Time Isn't Enough | Physical clocks drift and can't establish event order in distributed systems. Logical clocks track causality instead. Learn why this matters and how it works. |
| 11 | Lamport Timestamps: Ordering Events Without a Global Clock ← you are here | Lamport timestamps assign logical counters to events to establish causal order in distributed systems. Learn how they work and what they can and can't tell you. |
| 12 | Vector Clocks: Knowing When Events Are Truly Concurrent | Vector clocks detect causality and concurrency in distributed systems. Learn how they work, how Dynamo uses them for conflict detection, and their limitations. |
| 13 | Distributed Transactions: When One Machine Isn't Enough | Distributed transactions are hard. Learn why cross-service atomicity is expensive, when to use it, and when eventual consistency is the right alternative. |
| 14 | Two-Phase Commit: Coordinating a Distributed Decision | 2PC ensures distributed atomicity through prepare and commit phases. Learn how it works, the coordinator failure problem, and why it's rarely used in modern systems. |
| 15 | Three-Phase Commit: Solving 2PC's Blocking Problem | 3PC adds a pre-commit phase to eliminate 2PC's blocking problem. Learn how it works, what assumptions it requires, and why it's rarely used in production. |
| 16 | Delivery Semantics: What Does "Delivered" Actually Mean? | Message delivery guarantees define system reliability. Learn what at-most-once, at-least-once, and exactly-once mean, what they cost, and when each is appropriate. |
| 17 | Change Data Capture: Streaming Your Database in Real Time | CDC streams database changes in real time by reading the write-ahead log. Learn how Debezium works, what CDC enables, and when to use it. |
| 18 | Erasure Coding: Fault Tolerance Without Full Replication | Erasure coding stores data across nodes using math, not full replication. Learn how Reed-Solomon works, how S3 uses it, and when it beats 3x replication. |
| 19 | Merkle Trees: Efficiently Finding What's Different | Merkle trees efficiently detect which parts of a large dataset differ between nodes. Learn how Bitcoin, Cassandra, and Git use them for verification and anti-entropy. |
| 20 | Observability: Understanding Your System at Runtime | Logs, metrics, and distributed traces are how you understand a system at runtime. Learn what each pillar provides, the tools involved, and how they work together. |
| 21 | Distributed Systems: Wrap-Up | A recap of all 20 distributed systems concepts and the complete URL shortener architecture spanning all 8 pillars. The final post in the series. |
Lamport Timestamps: Ordering Events Without a Global Clock
The problem
Three services — Link Service, Analytics Service, and Billing Service — exchange messages. We need to determine the order in which events occurred to reconstruct causality during an incident.
Physical timestamps are unreliable (clocks drift). We need a logical clock: a mechanism that assigns order numbers to events such that if event A caused event B, A's number is less than B's.
The core idea
A Lamport timestamp is a monotonically increasing integer counter maintained per process. The rule: before any event, increment the counter. When sending a message, include the current counter. When receiving a message, take the max of the local counter and the received counter, then increment.
This ensures: if A happened-before B (A → B), then timestamp(A) < timestamp(B). The converse is not guaranteed: timestamp(A) < timestamp(B) does not imply A → B — it might just mean A happened on a process with a lower counter.
The analogy: version numbers in a document history
A shared document has a version counter. Every edit increments the version. When two users collaborate, the server takes the higher version and increments it — ensuring every merged version is higher than either contributor's version.
If version 47 preceded version 48, version 47's changes are causally "before" version 48. If two separate branches both produced version 47 independently, they're concurrent — the counter alone can't tell you this.
The algorithm
Each process maintains a local counter C.
On any local event: C = C + 1
On sending a message: C = C + 1, send message with timestamp C
On receiving a message with timestamp T: C = max(C, T) + 1
Process A (C_A): Process B (C_B): Process C (C_C):
C_A = 0 C_B = 0 C_C = 0
Event a1: C_A = 1
Send msg to B (ts=1) →
Receive msg (ts=1):
C_B = max(0,1)+1 = 2
Event b1: C_B = 3
Send msg to C (ts=3) →
Receive msg (ts=3):
C_C = max(0,3)+1 = 4
Event c1: C_C = 5
Event a2: C_A = 2
(no message, concurrent with b1)
From this, we can order: a1(1) < b1(3) < c1(5). And a2(2) is ordered between a1 and b1 in total order, even though a2 is causally independent of b1.
What Lamport timestamps guarantee
If A → B, then ts(A) < ts(B). Always true. This is the useful property: causal ordering is preserved.
If ts(A) < ts(B), we can't conclude A → B. Not true. Low timestamp might just mean a different process. Two concurrent events on different processes could have any relationship between their timestamps.
Total order from Lamport timestamps
Lamport timestamps create a total order: any two events can be compared (ts(A) < ts(B) or ts(A) > ts(B) or ts(A) = ts(B) → break ties by process ID). This total order is consistent with the causal partial order (no causal predecessor has a higher timestamp), but it adds arbitrary ordering for concurrent events.
This total order is used by:
- Distributed mutex algorithms: agree on the order in which processes acquire a lock using Lamport timestamps
- Event log ordering in debugging: total-order all events across services for incident reconstruction
- Serialisable transaction ordering: CockroachDB uses Hybrid Logical Clocks (HLC) — a Lamport-like structure that combines logical and physical time — for transaction ordering
Limitations
Can't detect concurrency. The most significant limitation: ts(A) < ts(B) doesn't tell you whether A happened-before B or they were concurrent. To detect concurrency, you need vector clocks (post 12).
Not useful for conflict detection. If two writes to the same key have different Lamport timestamps, you can order them — but you can't tell if they were concurrent (which would indicate a conflict). Last-write-wins based on Lamport timestamps silently discards one concurrent write without flagging it as a conflict.
The one thing to remember
Lamport timestamps give a simple rule: if event A causally preceded event B, A's timestamp is strictly less than B's. They create a total order consistent with causality, useful for ordering events across services without a global clock. The limitation: they can't detect whether two events with different timestamps are causally related or merely concurrent. For conflict detection, you need vector clocks.
← Previous: Logical Clocks — in distributed systems, physical clocks can't be trusted; logical clocks capture causal relationships between events instead.
→ Next: Vector Clocks — extending Lamport timestamps to detect concurrency: when two events are causally independent, vector clocks make that explicit.
