Module A-1 — Consensus, Clocks, and the Ordering Problem

Now the Other Half: Clocks Are Not a Source of Truth

Consensus gives you agreement on an order of operations. The tempting shortcut is to skip it and use timestamps instead — order events by when they happened. That shortcut is responsible for a large fraction of silent data loss in distributed systems, and the reasons are physical.

NTP keeps clocks approximately synchronised, and approximately is doing a lot of work. A well-run NTP setup holds machines within a few milliseconds of each other; a badly-run one drifts by hundreds of milliseconds; a VM resumed from suspension can be off by minutes. Clocks are also adjusted, which means they can step backwards — a machine whose clock was 300 ms fast has it corrected, and now() returns an earlier value than it did a moment ago.

Which produces the single most common clock bug in application code:

// BROKEN: wall clock can step backwards or jump forwards mid-measurement.
const t0 = Date.now();
await doWork();
const elapsed = Date.now() - t0;      // can be negative, or wildly wrong
 
// CORRECT: a monotonic clock only ever moves forward, and is unaffected by NTP.
const t0 = process.hrtime.bigint();
await doWork();
const elapsedMs = Number(process.hrtime.bigint() - t0) / 1e6;

The rule: wall clocks are for displaying and recording human time; monotonic clocks are for measuring durations. Every timeout, lease, rate-limit window and latency measurement wants the monotonic one. A lease whose expiry is evaluated against a wall clock can be extended or expired by an NTP correction, which is a safety failure rather than an inconvenience.

Wall-clock timestamps cannot order cross-region writes

Here is the failure that costs data:

Region EU (clock +40 ms fast)      Region US (clock −30 ms slow)
 t=10:00:00.100 write A            
                                    t=10:00:00.150 write B  (actually 50 ms LATER)
 timestamp recorded: 00.140         timestamp recorded: 00.120
 
Replication converges. Last-write-wins picks the higher timestamp → A wins.
The later write, B, is discarded. No error. No conflict reported. The user's
edit is simply gone.

The clocks were off by 70 ms combined — a completely ordinary amount — and the recorded order is the reverse of the real order. Now note what "last-write-wins" actually did: it did not resolve a conflict, it chose one write and destroyed the other, silently, using evidence that was wrong.

This is worth stating as a design rule: last-write-wins is not a conflict resolution strategy, it is a data loss strategy with a tolerable failure rate. It is acceptable when losing one of two concurrent writes is genuinely fine (a cache entry, a presence flag, a user's theme preference). It is not acceptable for anything additive — a shopping cart, a set of collaborators, a counter, a ledger — because the lost write was information nobody can reconstruct.

---

Three Answers: Lamport Clocks, Vector Clocks, Hybrid Logical Clocks

If physical time cannot order events, order them logically.

Lamport clocks. Each node keeps a counter. Increment on every local event; when sending a message, attach the counter; on receipt, set local = max(local, received) + 1.

A: 1 ──► 2 ─────────────► 3
              ╲ msg(2)
B:             3 ──► 4

This guarantees that if event X caused event Y then L(X) < L(Y). What it cannot do is the converse: L(X) < L(Y) does not mean X happened before Y — they may be concurrent. So a Lamport clock gives you a consistent total order (ties broken by node ID) but cannot detect a conflict, which is exactly what you need to know before choosing to discard a write.

Vector clocks. Each node keeps a counter per node. Comparing two vectors gives three outcomes rather than two:

V1 = {A:2, B:1}   V2 = {A:2, B:3}   →  V1 < V2, so V1 happened before V2
V1 = {A:3, B:1}   V2 = {A:2, B:3}   →  neither dominates: CONCURRENT

That third outcome is the whole point: vector clocks detect concurrency, which lets the system surface a genuine conflict instead of guessing. Dynamo and Riak used them to return siblings — both versions — leaving resolution to the application, which is honest but pushes real work onto every caller. The cost is size: a vector grows with the number of writers, so a system with many clients needs pruning heuristics, and pruning can reintroduce false conflicts.

Hybrid logical clocks (HLC) combine both, and are what modern systems actually use. A timestamp is (physical, logical): take the max of your physical clock and any timestamp you have seen; if the physical component did not advance, increment the logical counter.

// Monotonic, causally consistent, and still close to real time.
function hlcNow(last: {p: number, l: number}, seen?: {p: number, l: number}) {
  const wall = Date.now();
  const p = Math.max(wall, last.p, seen?.p ?? 0);
  const l = (p === last.p && p === seen?.p) ? Math.max(last.l, seen.l) + 1
          : (p === last.p) ? last.l + 1
          : (p === seen?.p) ? seen.l + 1 : 0;
  return { p, l };
}

HLC gives you three properties at once: timestamps that respect causality, timestamps that are comparable to real time (so a human can read them and a query can filter on them), and constant size. Its bound is that it tracks physical time only as well as your clocks do — a badly skewed clock pushes HLC timestamps into the future and they stay there, because the clock is monotonic by construction. CockroachDB and MongoDB both use HLCs, with a configured maximum tolerated skew beyond which a node removes itself from the cluster rather than corrupting ordering.

And CRDTs, where convergence has to be automatic

Vector clocks tell you a conflict exists; somebody still has to resolve it. If there is no human in the loop — offline-first clients, collaborative editing, multi-region active-active — the data type itself must be built so that concurrent updates merge deterministically. That is a CRDT: a grow-only counter that merges by taking the max per replica; an add/remove set that keeps tombstones so a remove cannot be undone by a stale add; a sequence type (as in collaborative text editors) where concurrent insertions interleave to the same result on every replica.

The trade is that you give up arbitrary semantics for guaranteed convergence — a CRDT set can converge on "both items added," but it cannot express "only one of these two may exist," because that requires coordination. Module A-9 develops this where it belongs, in multi-region design; the point here is that when last-write-wins is unacceptable and no human can arbitrate, a CRDT is the alternative, not a cleverer clock.

---

What TrueTime Buys, and What It Costs

Google's Spanner takes the opposite approach: rather than abandoning physical time, make the uncertainty explicit and bounded.

TrueTime is a time service backed by GPS receivers and atomic clocks in every datacentre. Its API does not return an instant, it returns an interval:

TT.now() → [earliest, latest] with (latest − earliest) typically 1–7 ms

The guarantee is that the true absolute time lies inside that interval. And that turns time into something you can reason about: instead of "my clock says X" you have "the real time is definitely between X−ε and X+ε."

Spanner uses it via commit-wait: after a transaction picks a commit timestamp, it waits out the uncertainty window before making its writes visible. That wait guarantees that any transaction starting afterwards, anywhere on the planet, will see a strictly later timestamp — which gives external consistency, the strongest practical guarantee: if transaction A completes before transaction B begins in real time, A's timestamp is smaller, globally, with no coordination between them.

What that buys is remarkable: globally distributed, strongly consistent, linearizable reads and writes with SQL, without vector clocks or application-level conflict resolution.

What it costs, and why nobody else simply copies it:

• Specialised hardware in every datacentre, plus the operational discipline to keep ε small. Cloud Spanner rents you this; you cannot build it on commodity VMs.
• Commit latency has a floor equal to ε, plus consensus round trips. Every commit pays it.
• ε is a correctness dependency. If uncertainty grows — a GPS antenna fails, a clock drifts — Spanner's latency degrades, deliberately, rather than its correctness. That is the right trade and it means clock health is a production SLI.

The transferable lesson for systems that are not Spanner: the useful move is not "trust the clock" or "ignore the clock" but bound the uncertainty and design against the bound. A lease held for 30 seconds with a 10-second safety margin is a system reasoning about clock error explicitly. A lease that assumes clocks agree is one that will hand the same lock to two holders.

Why this matters in production: clock problems do not announce themselves. There is no error when a timestamp is 200 ms wrong; there is a lost edit, a lease held by two owners, a rate-limit window that resets twice, a monitoring graph with a gap or a spike that never happened, or a JWT rejected as not-yet-valid because the issuer's clock is ahead of the verifier's. Every one of those is diagnosed by checking clock offset — and almost nobody checks clock offset, because nothing points there. ntp_offset on every host is one of the cheapest and least-collected metrics in existence (Module O-1).

---

Where This Shows Up in Your Stack

• PostgreSQL: streaming replication is not consensus — there is no automatic, safe leader election in core Postgres, which is why HA tooling (Patroni, Stolon) delegates that decision to etcd or Consul. Even synchronous_commit = remote_apply gives durability on a replica, not agreement about who the primary is; promote two primaries and you have split brain with no protocol to prevent it. For time: always timestamptz, know that now() is transaction-start time while clock_timestamp() is the actual current instant (the distinction that produced Module P-23's polling bug), and never derive ordering across nodes from now().
• Node.js: Date.now() for recording when, process.hrtime.bigint() for measuring how long — the wall-clock-elapsed bug is endemic and produces negative durations and impossible latency percentiles. JWT nbf/exp validation is a clock dependency between two services, so a small clockTolerance is not sloppiness, it is acknowledging reality.
• Redis: Sentinel and Cluster failover are not consensus-safe. Failover can lose acknowledged writes because replication is asynchronous, and a partitioned master keeps accepting writes until it notices. This is fine for a cache and unacceptable for a lock or a counter that matters — the direct setup for Module A-2's Redlock discussion.
• Kafka: the modern control plane (KRaft) is Raft, replacing ZooKeeper for metadata — the canonical "consensus for metadata, log replication for data" split. acks=all with min.insync.replicas=2 on a 3-replica partition is a quorum-shaped durability guarantee, and the leader epoch is exactly Raft's term doing exactly Raft's job: fencing a zombie leader whose messages carry a stale epoch and are rejected.
• etcd / ZooKeeper / Consul: consensus you rent rather than write. Use them for leader election, configuration, membership, service registries and leases (Module A-5). Respect their nature: small values, low write rates, and an odd number of nodes — an etcd cluster used as a general-purpose datastore will fail in exactly the way this module's latency section predicts.

---

Summary

• The only failure detector on a network is a timeout, and FLP says no deterministic algorithm can guarantee consensus in a fully asynchronous system with even one possible failure. Real protocols escape by assuming partial synchrony and by giving up liveness under sustained bad conditions while never giving up safety — a flapping cluster stops making progress rather than deciding two values.
• A quorum is a strict majority, and the safety argument is that two majorities must overlap. Two nodes are strictly worse than one, because a quorum of two tolerates zero failures; even node counts waste a node; three is the minimum and five is the standard for anything important.
• Majorities make split brain impossible for commits, not for beliefs. A deposed leader on the minority side cannot commit, but it can still act — which is why fencing exists (Module A-2).
• Raft's term is both its logical clock and its fencing mechanism: any message with a stale term is rejected, neutralising a deposed leader the instant it speaks. Randomised election timeouts prevent perpetual split votes, an entry is committed once a majority has persisted it, and the safety property is that a candidate must have an up-to-date log to win — which is what makes "committed" irrevocable. Membership changes are the most dangerous operation and must go through the protocol, one node at a time.
• Consensus does not scale writes; it makes them safe. The latency floor is a round trip to the median-slowest quorum member — sub-millisecond in one AZ, 50–150 ms across regions — and throughput is bounded by the single leader. Therefore use consensus for metadata, not the data path: leadership, shard maps, membership, leases. Scale by sharding into many consensus groups.
• Wall clocks are for recording human time; monotonic clocks are for measuring durations. NTP corrections can step a wall clock backwards, so Date.now() deltas produce negative and nonsensical elapsed times, and any lease or timeout evaluated against a wall clock is a safety bug rather than an inaccuracy.
• Wall-clock timestamps cannot order cross-region writes. Seventy milliseconds of combined skew — an ordinary amount — inverts the recorded order of writes fifty milliseconds apart. Last-write-wins is therefore not conflict resolution, it is data loss with a tolerable failure rate: fine for a theme preference, wrong for anything additive like a cart, a collaborator set, or a counter, because the discarded write is information nobody can reconstruct.
• Lamport clocks respect causality but cannot detect concurrency, so they give a total order without telling you whether a conflict exists. Vector clocks detect concurrency — the property you need before deciding to discard a write — at a size that grows with the number of writers. Hybrid logical clocks give causality, constant size, and timestamps comparable to real time, which is why CockroachDB and MongoDB use them; their bound is that a badly skewed clock pushes timestamps forward permanently, so they pair with a maximum-skew threshold beyond which a node ejects itself.
• When no human can arbitrate a conflict, the data type must converge on its own — a CRDT — and the price is that you cannot express constraints requiring coordination, such as uniqueness (Module A-9).
• TrueTime makes uncertainty explicit and bounded — an interval rather than an instant — and Spanner's commit-wait pays out that interval to obtain external consistency globally. It costs atomic clocks and GPS in every datacentre and a commit-latency floor equal to the uncertainty, and clock health becomes a correctness dependency. The transferable lesson is the method, not the hardware: bound your clock error and design against the bound, rather than trusting or ignoring the clock.
• Clock problems are silent, producing lost edits, double-held leases, JWTs rejected as not-yet-valid, and monitoring graphs with impossible shapes. ntp_offset per host is among the cheapest and least-collected metrics there is.

The next module, Distributed Locks and Coordination, is this module's consequences made concrete. Everything above says a node can believe it holds something it does not — so a lock built on a timeout is a lock that will occasionally have two holders, and the mechanism that saves you is not a better lock but a fencing token carried into the resource being protected. It also asks the more useful question: which of your locks can be designed away entirely.

---