Time, clocks and ordering of events

Why time is hard

On one machine, order is easy: the clock only goes forward (mostly). Across machines, there is no shared clock.

• Each machine's clock drifts, and synchronisation (NTP) is only accurate to some milliseconds, sometimes much worse.
• Clocks can jump (corrections, leap seconds, virtual machine pauses).
• Messages take unpredictable time, so "A happened before B" cannot be read from two clocks.

So never use wall-clock timestamps from different machines to order important events (or to decide who wins a conflict, or to measure the timeout of a lock).

Image: National Institute of Standards and Technology (NIST) · Public domain · Source · Wikimedia Commons: NIST-F2 cesium fountain atomic clock

What we can know: happened-before

Event A happened before B if A could have caused B: same process in order, or a message sent at A and received at B (and transitivity). Events with no such chain are concurrent.

Logical clocks

Lamport clock

Each process keeps a counter. Increase it on each event; attach it to messages; on receiving, set it to max(local, received) + 1. Guarantee: if A happened before B, then clock(A) < clock(B). The reverse does not hold, so equal-looking order does not prove causality.

Vector clock

Each process keeps a vector of counters, one per process. Comparing two vectors tells you whether one event happened before the other or whether they are concurrent. Used by Dynamo-style stores to detect conflicting writes.

100%

Figure SDA-CORE-17-1 · Vector clock · © forcsguy.com

Practical choices

Need	Tool
A total order of events	A single leader, or consensus (Raft, Paxos), or a log such as Kafka partitions
Detect concurrent updates	Version vectors, or version numbers with conditional writes
Merge concurrent edits	CRDTs, operational transformation, application-level merge
Unique, roughly time-ordered ids	Snowflake-style ids (accepting small skew)
Real-time bounds	Databases that use atomic clocks and wait out uncertainty (such as Spanner)

Rules of thumb

• Use monotonic clocks (not wall time) to measure durations on one machine.
• Treat timestamps as approximate and for humans; use versions for correctness.
• Make operations idempotent and commutative where possible, so arrival order matters less.

More on this site