Time, Order, and CRDTs: Coordinating Without a Clock

June 3, 2026 11 min read Software Architecture

distributed-systemsclockscrdtscausalityarchitecturedatabases

Contents

There is a seductive idea that distributed ordering is easy: just timestamp every event with the wall clock and sort. It does not work, and understanding why it does not work is the gateway to a beautiful set of tools for ordering events and merging concurrent changes without any central coordinator. This final post in the distributed-systems fundamentals series is about time and order — why physical clocks lie, how to reason about causality instead, the clever clock designs production databases actually use, and CRDTs, the data structures that let independent replicas edit freely and always merge into the same answer.

It builds directly on consensus (agreement) and consistency and replication (the trade-offs). Where those posts often avoided divergence through coordination, this one is largely about embracing concurrency and reconciling it after the fact.

Why wall-clock time lies

Every machine has a clock, and it is tempting to trust it for ordering events across machines. Do not. Physical clocks fail you in distributed systems in specific, damaging ways:

Clocks drift. Quartz oscillators run slightly fast or slow; without correction, two machines diverge by seconds over time.
NTP corrections jump. The Network Time Protocol periodically nudges a clock back toward true time — which means a clock can jump forward or even backward. A backward jump is catastrophic for “sort by timestamp”: event B that happened after A can get a smaller timestamp.
Skew between machines is real and unbounded. Two servers’ clocks can differ by milliseconds to (misconfigured) seconds. There is no guarantee that machine X’s “10:00:00.000” is the same instant as machine Y’s.
There is no global “now.” Special relativity aside, the practical fact is that no two machines share a clock, and synchronizing them perfectly is impossible.

The damning consequence: if you order events across machines by wall-clock timestamp, you will sometimes get the order wrong — including ordering an effect before its cause. The infamous failure mode is last-write-wins (LWW) conflict resolution keyed on wall-clock time: a write with a slightly-fast clock can clobber a later write with a slightly-slow clock, silently losing data. Wall-clock time is fine for displaying a timestamp to humans; it is unreliable for ordering events in a distributed system.

Causality: order what actually matters

The insight that rescues us, from Lamport’s seminal 1978 paper, is that you usually do not need to know the real-time order of two events — you need to know their causal order: did A cause (or could it have influenced) B? This is the happens-before relation, written A → B. It holds when:

A and B are on the same node and A came first, or
A is the sending of a message and B is its receipt, or
transitively: A → B and B → C implies A → C.

If neither A → B nor B → A, the events are concurrent — they happened independently, with no causal link, and their relative order genuinely does not matter (or must be resolved as a conflict). Causality is the right notion of order because it captures the only orderings that can actually affect correctness: a reply must not appear before its message; a delete must not be reordered before the create it depends on.

   Node A:  a1 ──────► a2 ─────────────► a3
                 \                  (concurrent with b1)
                  \ message
                   ▼
   Node B:         b1 ──────► b2

   a1 → b1 (message)   a1 → a2 → a3   b1 → b2
   a3 and b1: CONCURRENT — no path between them

The job of a logical clock is to capture this happens-before relation using counters instead of unreliable physical time.

Lamport timestamps: a single counter

The simplest logical clock. Each node keeps an integer counter L:

Increment L before each local event.
Send L with every outgoing message.
On receiving a message with timestamp L_msg, set L = max(L, L_msg) + 1.

This guarantees: if A → B, then L(A) < L(B). Causally-ordered events get increasing timestamps, so sorting by Lamport timestamp never puts an effect before its cause. It gives a total order (ties broken by node ID) that is consistent with causality.

The limitation is the converse: L(A) < L(B) does not imply A → B. Two concurrent events can have ordered timestamps purely by coincidence of counting. So a Lamport clock can order events consistently, but it cannot tell you whether two events are concurrent — and detecting concurrency is exactly what you need for conflict resolution. For that, you need more information.

Vector clocks: detecting concurrency

A vector clock carries a counter per node: an array V where V[i] is node i’s count, as known to the holder. Each node increments its own entry on an event; on receiving a message, it takes the element-wise max of its vector and the message’s, then increments its own entry. Now you can compare two events precisely:

V(A) < V(B) (every element ≤, at least one strictly less) ⟹ A → B (A happened before B).
Neither V(A) ≤ V(B) nor V(B) ≤ V(A) ⟹ A and B are concurrent — a genuine conflict to resolve.

   3 nodes → vectors [n0, n1, n2]

   A on n0: [2,1,0]     B on n1: [1,3,0]
   Compare: A[0]=2 > B[0]=1, but A[1]=1 < B[1]=3
   → neither dominates → A and B are CONCURRENT (conflict!)

This is the killer feature: vector clocks detect concurrent updates, which Lamport clocks cannot. Dynamo-style systems used them to surface conflicting versions to the application (or to a merge function). The cost is size: the vector grows with the number of nodes that have ever written, which is why large or churn-heavy systems use variants (dotted version vectors, bounded schemes) or accept the overhead.

Clock	Gives you	Cannot do
Wall clock	Human-readable time	Reliable cross-machine ordering
Lamport	A total order consistent with causality	Detect concurrency
Vector clock	Full causal order and concurrency detection	Stay small as nodes grow

The clocks production databases actually use

Pure logical clocks lose the connection to real time, which you often still want (for “give me a consistent snapshot as of 10:00:00,” or for sane debugging). Two influential designs reconcile physical and logical time.

Google Spanner’s TrueTime

Spanner takes the radical hardware route: equip every datacenter with GPS receivers and atomic clocks, and expose time not as a single value but as an interval. TT.now() returns [earliest, latest] — a range that is guaranteed to contain the true time, with the width reflecting measured uncertainty (kept under a few milliseconds). To commit a transaction with a globally meaningful timestamp, Spanner simply waits out the uncertainty (the “commit wait”): it pauses until it is certain the chosen timestamp is in the past everywhere. This gives Spanner externally-consistent (linearizable) global transactions — but it requires that specialized clock hardware, which is why it was long a Google-only luxury.

Hybrid Logical Clocks (HLC)

The pragmatic answer that swept the industry. An HLC is a 64-bit timestamp combining a physical component (from NTP wall clock) and a logical counter. It tracks physical time closely (so timestamps are human-meaningful and roughly real) while using the logical part to preserve causality even when the physical clock misbehaves — if a message arrives with a higher timestamp than local time, the logical counter advances rather than letting causality break. HLCs give you most of what TrueTime offers — causally-consistent ordering with near-real timestamps — without GPS or atomic clocks, running on commodity hardware with ordinary NTP.

This is why CockroachDB, YugabyteDB, and MongoDB’s cluster time all use HLCs: as of 2026, almost every modern multi-region database picks HLC over TrueTime-style hardware clocks, because HLC needs no special hardware. CockroachDB’s trade-off versus Spanner is explicit — HLC + NTP is good enough for most workloads but causes more transaction retries when clocks drift further apart, whereas Spanner’s tight hardware sync keeps skew tiny at the cost of the hardware. It is a clean illustration of the engineering choice: buy precision with hardware, or absorb a little imprecision in software.

CRDTs: merge without coordination

Logical clocks tell you whether two updates conflict. CRDTs — Conflict-free Replicated Data Types — go further: they are data structures designed so that concurrent updates always merge into the same result, automatically, with no coordination at all. This is a profound shift. Instead of coordinating to prevent divergence (the consensus approach) or detecting conflicts to resolve them manually, CRDTs make the data type itself mathematically guaranteed to converge.

The magic requirement: the merge operation must be commutative, associative, and idempotent (order, grouping, and duplicates do not change the result). If merge has those properties, then no matter what order replicas receive updates in, no matter how messages are duplicated or delayed, every replica that has seen the same set of updates ends up in the same state. This property is called Strong Eventual Consistency — stronger than plain eventual consistency because convergence is guaranteed by construction, not hoped for.

   Replica X: add "a", add "b"        Replica Y: add "b", add "c"
              {a, b}                              {b, c}
                    \                            /
                     merge (set union — commutative,
                            associative, idempotent)
                              ▼
                          {a, b, c}      ← both replicas converge here,
                                            regardless of message order

Common CRDTs, from simple to rich:

G-Counter / PN-Counter — counters that merge by per-node maxima (grow-only) or a pair of them (increment/decrement). Useful for distributed counts (likes, views) that must be accurate without locking.
G-Set / OR-Set — sets supporting add (and, for OR-Set, remove handled with unique tags so concurrent add/remove resolves sanely).
LWW-Register — a register using a timestamp for last-write-wins (here the clock caveats matter; pair with logical time).
Sequence CRDTs (RGA, Logoot, YATA, etc.) — ordered lists where concurrent insertions at the same position converge deterministically. These power collaborative text editors.

There are two implementation styles: state-based (CvRDTs), which ship and merge whole states (robust to lost/duplicated messages, but heavier), and operation-based (CmRDTs), which ship individual operations (lighter, but require reliable delivery). Production CRDT libraries (Yjs, Automerge) optimize these heavily for real use.

Where CRDTs earn their keep

CRDTs are not a universal replacement for coordination — they shine in specific, increasingly common situations:

Collaborative editing. Google-Docs-style real-time co-editing is the flagship use. Multiple people type into the same document with no central lock; a sequence CRDT (in libraries like Yjs or Automerge) merges everyone’s edits into an identical document on every client. The alternative (Operational Transformation) is notoriously hard to get right; CRDTs make it tractable.
Offline-first / local-first apps. Note-takers, mobile apps, field tools that must work with no connection and sync later. Each device edits its local CRDT copy freely; when connectivity returns, copies merge automatically with no “resolve conflict” dialog. This is the foundation of the local-first software movement.
Geo-distributed state and multi-region databases. When you want each region to accept writes locally (low latency, high availability — the PA/EL corner from the previous post) and reconcile across regions, CRDTs let regions diverge and converge safely. Redis offers CRDT-backed active-active geo-replication; Riak built data types on them.
Distributed counters, presence, shopping carts — anywhere concurrent updates are common and a merge rule beats a lock.

The trade-off, stated honestly: CRDTs guarantee convergence, not your preferred outcome. Set union converges, but if two users concurrently set a field to different values, the CRDT picks a deterministic winner that may not be the one a human would choose. They also carry metadata overhead (tombstones for deletes, version tags) that must be managed. CRDTs are the right tool when availability and offline capability matter and the data has a sensible automatic merge — and the wrong tool when you need a single authoritative decision (use consensus) or strict invariants like “balance never goes negative” (which require coordination CRDTs cannot provide).

The series, tied together

Across three posts the throughline is a single tension: coordination buys you strong guarantees but costs latency and availability; avoiding coordination buys you speed and availability but forces you to handle divergence.

Consensus (post 1) is maximal coordination: a majority agrees on one log, one truth — at the cost of unavailability under partition.
Consistency and replication (post 2) is the spectrum of how much coordination to buy, from linearizable to eventual, framed by CAP and PACELC.
Time, order, and CRDTs (this post) is the toolkit for the low-coordination end: order events by causality (logical and hybrid clocks) instead of unreliable wall time, and use CRDTs to let replicas diverge and guarantee they reconverge.

You will not memorize the merge laws of an OR-Set, and you do not need to. What lasts is the judgment: distrust wall-clock ordering, reach for causality, and know that for the right kind of data, you can have correctness and offline, coordination-free availability — a combination that once seemed impossible. That judgment is what separates engineers who fear distributed systems from those who design them on purpose.

Sources: