10.3 — Time & Order: Clocks, Causality, and Why "Latest" Is Hard

In one process, "which happened first?" is free — the program counter answers it. Across machines it becomes one of the genuinely hard problems, and it hides inside features that sound trivial: last write wins, sort by timestamp, expire after 30 seconds, this event caused that one. This page covers what a clock actually is (two kinds, and using the wrong one is a real outage class), why NTP doesn't save you, logical clocks (Lamport and vector) that track causality without wall time, the FLP result that bounds what's possible at all, and the practical patterns that make ordering work in production.

1. Two clocks, and the outage from confusing them

Every machine has two distinct clocks, and they answer different questions: ^{⚑Clock skew and time synchronization in distributed systems. [EQ-1096b]}

• Wall clock (Date.now(), CLOCK_REALTIME) — "what time is it in the world?" Synchronized by NTP, and therefore jumps: it can move backward when a correction lands, or leap forward. Right for timestamps humans read and cross-machine agreement; wrong for measuring elapsed time.
• Monotonic clock (performance.now(), process.hrtime.bigint(), CLOCK_MONOTONIC) — "how much time has passed since some arbitrary start?" Never jumps, never goes backward, but is meaningless across machines (each has its own zero). Right for durations, timeouts, rate limiters, retries (9.7.5).

The classic bug: measuring a timeout with the wall clock. NTP steps the clock back 500 ms mid-request; your end - start is negative or absurd; a lease looks unexpired (or instantly expired); a rate limiter's window computes garbage. Rule: durations from monotonic, timestamps from wall — and never subtract wall-clock readings from different machines and call the result a duration.

Clock skew is the difference between two machines' wall clocks. NTP keeps it small — typically single-digit milliseconds within a datacenter, tens across the internet — by slewing (gradually adjusting rate) rather than stepping when the error is small. But it guarantees nothing: a VM's clock can drift under CPU pressure, a misconfigured host can be seconds off, and virtualized clocks are notoriously worse. Any design whose correctness depends on "these two machines agree on the time to within X" is a design with a hidden failure mode — the notorious example being last-write-wins by timestamp, where a clock-skewed node's write silently erases a newer one, permanently, with no error anywhere (10.5).

2. Causality without clocks: happens-before

Leslie Lamport's 1978 insight: we rarely need time — we need order, and specifically causal order. Define the happens-before relation (written →):

1. Within one process, if a occurs before b, then a → b.
2. If a is the sending of a message and b its receipt, then a → b.
3. Transitivity: a → b and b → c implies a → c.

Events unrelated by → are concurrent — and that's not a failure, it's a fact: they genuinely have no order, and any system that invents one is making it up. Two mechanisms track this without any clock:

Lamport timestamps — one integer per node: increment on every local event; attach it to outgoing messages; on receipt set counter = max(local, received) + 1. The guarantee: if a → b then L(a) < L(b). The limitation, and it's the exam question: the converse is false — L(a) < L(b) does not mean a → b; they may be concurrent. Lamport clocks give a consistent total order (ties broken by node id) — useful for deterministic tie-breaking — but they cannot detect concurrency.

Vector clocks fix that: each node keeps a vector of counters, one per node; it increments its own on each event and takes the element-wise max on receipt. Now compare two vectors: if every element of V(a) is ≤ V(b) and at least one is strictly less, then a → b; if neither dominates, they are concurrent — a genuine conflict the system must resolve (last-write-wins, merge, or surface to the user — 10.5's conflict resolution). The cost: the vector grows with the number of nodes, so real systems bound it (per-replica rather than per-client, pruning, or Dynamo-style version vectors).

Figure 1 — Happens-before and concurrency. Message edges create causal order (a2 → b2 → a3). Events a1 and b1 have incomparable vector clocks: they are genuinely concurrent, and any "which came first" answer would be invented rather than observed.

3. What's actually possible: FLP and its escape hatches

The FLP impossibility result (Fischer, Lynch, Paterson, 1985): in an asynchronous system (no bound on message delay) with even one faulty process, no deterministic algorithm can guarantee consensus — because you cannot distinguish "crashed" from "slow." Every distributed system's coordination story lives under this theorem.

The practical escape hatches, all of which real systems use: timeouts (assume partial synchrony — "if no response in 5 s, presume failure"), which converts an impossibility into a probability and gives you liveness with occasional wrong guesses (a leader declared dead while alive → the fencing problem, 10.7.2); randomization; and weakening the requirement (eventual rather than immediate agreement). Raft and Paxos don't beat FLP — they guarantee safety always and liveness when the network behaves, which is the achievable contract, and stating it that way is the senior answer to "how does Raft handle FLP?"

4. Practical ordering patterns

What production systems actually do, and why each choice is defensible:

• Per-key ordering, not global. Global total order is expensive and almost never required. Partition by entity (customer, account, document) and guarantee order within a partition (10.6) — which is exactly Kafka's model (10.8.2) and enough for nearly every requirement ("this customer's events in order").
• Version numbers over timestamps. Store a monotonically increasing version per entity and reject stale writes with a compare-and-set (9.6.3's ETags). Versions are exact where clocks are approximate.
• Sequence numbers from a single writer. If one component owns a stream (a leader, a partition), its own counter is a perfect order — free, exact, and the reason single-writer designs are so attractive.
• Hybrid Logical Clocks (HLC) — timestamps that combine wall time (so they're human-meaningful and roughly comparable across machines) with a logical counter (so they never go backward and respect causality). Used by CockroachDB and others; the modern default when you want "a timestamp that is also a correct order."
• Bounded-uncertainty clocks — Google Spanner's TrueTime uses GPS/atomic clocks to give an interval ([earliest, latest]) and simply waits out the uncertainty (a few ms) before committing, purchasing externally-consistent global transactions with hardware and latency. The lesson isn't "buy atomic clocks"; it's that making uncertainty explicit and bounded turns an impossible problem into a budgeted one.
• Idempotency instead of ordering. Often the cheapest fix: if operations are commutative and idempotent (10.4), out-of-order delivery stops mattering — designing for reorder-tolerance beats enforcing order.

5. The expert lens

Most "we need timestamps" requirements are actually causality or dedup requirements. "Show the latest version" usually means "show the one that causally follows" (versions), "don't process twice" means dedup (idempotency keys), and "expire after 30 minutes" means a monotonic duration on one machine. Reach for wall-clock ordering only when a human will read the number — and even then, expect skew and never make correctness depend on it.

Concurrency is information, not an error. Vector clocks' real gift is detecting concurrent updates so you can resolve them deliberately — merge (CRDTs, shopping carts that union items), pick by business rule, or surface the conflict to a human (git's merge conflicts are this pattern with a UI). Systems that quietly last-write-wins are choosing to silently discard data; that can be correct, but it must be a decision, written down, not a default nobody noticed (10.5).

Ordering is a cost you should scope as tightly as possible. Global ordering forces a single serialization point (a leader, a lock, a consensus round) and caps throughput at what that point can do. Per-key ordering partitions the cost and scales linearly. The design instinct: ask what is the smallest scope in which order actually matters? — usually one entity — and buy exactly that. It's the same instinct as 9.5.2's per-entity serialization, at network scale.

Next: 10.4 — the concerns that ordering keeps pointing at: who owns state, what delivery guarantees mean, and how idempotency makes duplicates harmless.

Recall

• Two clocks: wall clock (NTP-synced, jumps — for human timestamps and cross-machine comparison) vs monotonic (never backward, machine-local — for durations, timeouts, limiters). Never measure elapsed time with wall time; never subtract wall readings across machines.
• Clock skew is unavoidable (NTP bounds it, guarantees nothing; VMs drift). Any correctness that depends on cross-machine time agreement — notably last-write-wins by timestamp — silently loses data.
• Happens-before (→): program order, send→receive, transitivity; unrelated events are concurrent. Lamport timestamps give a → b ⇒ L(a) < L(b) but not the converse (can't detect concurrency); vector clocks can (incomparable vectors = concurrent = a real conflict), at the cost of size.
• FLP: in an asynchronous system with one faulty process, deterministic consensus is impossible (can't distinguish crashed from slow). Escapes: timeouts (partial synchrony), randomization, weaker guarantees. Raft/Paxos = safety always, liveness when the network behaves.
• Practical patterns: per-key order, not global; versions/CAS over timestamps; single-writer sequence numbers; HLCs (wall + logical, never backward); bounded uncertainty (Spanner TrueTime waits out the interval); and idempotent/commutative operations so reordering stops mattering.
• Lens: most "timestamp" needs are causality or dedup needs; concurrency is information (merge/decide/surface — silent LWW discards data); scope ordering as tightly as possible (per entity), because global order means a single serialization point.

Self-test: Which clock for a 30-second lease, and what breaks with the other? State the Lamport guarantee and its converse. How do vector clocks reveal a conflict? What exactly do Raft/Paxos promise given FLP? Name three ways to order events without trusting clocks.

Quiz Bank

FoundationalWall clock vs monotonic clock: when to use each, and the bug from mixing them up.

Wall clock (Date.now(), CLOCK_REALTIME) reports civil time, is NTP-synchronized, and therefore can jump — forward on correction, backward when a host was ahead. Use it for timestamps humans or other machines will interpret (createdAt, log times, Expires headers).

Monotonic clock (process.hrtime.bigint(), performance.now(), CLOCK_MONOTONIC) counts from an arbitrary origin, never moves backward, and is unrelated across machines. Use it for durations: timeouts, latency measurement, rate-limit windows (9.7.5), retry backoff, lease remaining.

The bug: measuring elapsed time with the wall clock — an NTP step during the measurement produces negative or wildly wrong durations, so a 30-second lease can appear expired instantly or never (both catastrophic if the lease guards exclusive work — 10.7.2), a rate limiter's window computes garbage, and latency metrics show impossible values. The corollary rule:

never subtract wall-clock readings taken on different machines and call the result a duration — that difference includes skew of unknown sign and size.

FoundationalExplain happens-before, Lamport timestamps, and what vector clocks add.

Happens-before (→) is causal order defined without clocks: within a process, earlier events precede later ones; a message's send precedes its receipt; and the relation is transitive. Events not related by → in either direction are concurrent — genuinely unordered. Lamport timestamps implement it cheaply: each node keeps a counter, increments it per event, sends it with messages, and on receipt sets counter = max(local, received) + 1. Guarantee: a → b implies L(a) < L(b).

The converse fails — a smaller Lamport value does not imply causation, so Lamport clocks cannot detect concurrency; they give a consistent total order (tie-break by node id) suitable for deterministic decisions, not for conflict detection. Vector clocks keep one counter per node: increment your own per event, element-wise max on receipt. Now a → b iff V(a) ≤ V(b) element-wise with at least one strict inequality; if neither dominates, the events are concurrent — a real conflict requiring a resolution policy (merge, business rule, or user choice — 10.5). Cost: vectors grow with node count, so production systems bound them (per-replica vectors, pruning, dotted version vectors).

AppliedWhy is last-write-wins by timestamp dangerous, and what should you do instead?

Because it makes correctness depend on cross-machine clock agreement, which nothing guarantees. Concretely: node A's clock is 2 seconds ahead; a user writes on B at real time T, then writes on A at T+0.5 s; A's timestamp (T+2.5) beats B's (T) — fine. But reverse the order: the newer write happens on B (timestamp T+1) while the older one on A carries T+2 — the older write wins and the newer one is silently discarded, permanently, with no error, no log, no conflict surfaced. Skew of a few seconds — routine for VMs under load or a briefly misconfigured host — is enough.

Instead: (1) version numbers with compare-and-set — each entity carries a monotonic version; writes state the version they read and are rejected if stale (9.6.3's ETag/412), making conflicts visible rather than silent; (2)

single-writer sequencing — route all writes for a key through one owner (partition leader) whose local counter is an exact order (10.6); (3) vector clocks or HLCs when multi-writer is genuinely required, so concurrency is detected and resolved by a stated policy; (4)

CRDTs for data types that can merge commutatively (counters, sets — carts, likes), removing the conflict entirely. If LWW is still chosen (it's legitimate for some caches and metrics), record it as a deliberate decision with its data-loss window acknowledged.

InterviewWhat does FLP say, and how do Raft and Paxos live with it?

FLP (1985) proves that in a fully asynchronous system — no upper bound on message delay or processing time — with even one process subject to crash failure, no deterministic protocol can guarantee consensus (agreement, validity, and termination). The intuition: without timing bounds you cannot distinguish a crashed process from an arbitrarily slow one, so any algorithm can be kept from terminating.

How real protocols live with it: they don't beat the theorem — they change the model or the promise. Raft and Paxos assume partial synchrony (the network is eventually well-behaved) and use timeouts as failure detectors, which yields the achievable contract:

safety always (never two conflicting decisions, never a lost committed entry — regardless of timing, partitions, or how wrong the failure detector is) and liveness when the network behaves (progress once a stable leader can talk to a majority). Timeouts mean occasional wrong guesses — a live leader declared dead — which is why fencing tokens and term numbers exist (10.7.2): a stale leader's writes must be rejected rather than merely improbable. Stating the safety/liveness split is the answer interviewers want, because it shows you know what these systems actually promise.

StaffYour multi-region system replicates user profile edits between three regions with last-write-wins. Support reports occasional 'my change disappeared' tickets. Design the investigation and the fix, including what you'd tell affected users.

Investigation: the symptom is the LWW clock-skew signature (sectionApplied). Confirm before redesigning — (1) instrument writes with both the wall timestamp and a per-region monotonic sequence plus the writer's node id, so future conflicts are diagnosable; (2) measure actual skew between regions (NTP offset metrics per host — expect this to reveal one region's hosts drifting under load, or a virtualization artifact); (3) mine the write log for inversions: pairs where a write with an earlier arrival has a later timestamp than a subsequent write to the same key — each inversion is a candidate lost update, and their rate against ticket volume validates the hypothesis; (4) check whether edits are truly concurrent (two devices) or sequential-but-cross-region (one user, moving between regions — the common and more embarrassing case, because it's a single user's own edits racing).

Fix, in order of deployability: (a) short term — bound the damage: pin a user's writes to a home region (single-writer per key removes the conflict entirely, at the cost of cross-region write latency for travelers — a clean, honest trade), and add version-based conditional writes so a stale write is rejected with a 409 rather than silently winning (9.6.3); the UI then shows "this profile changed elsewhere — review and retry," converting silent loss into a visible, recoverable event; (b)

medium — replace LWW with HLCs or version vectors so genuine concurrency is detected and either merged field-wise (profiles merge well: last-writer-per-field is far safer than per-record) or surfaced; (c) long — for fields that can merge commutatively, model them as CRDTs and stop having conflicts.

What to tell users: the honest version — "in rare cases, edits made from two places within a short window could overwrite each other; we've identified affected accounts from the write log, restored the lost values where we can reconstruct them, and changed the system so a conflicting edit now asks you instead of choosing silently."

The design lesson to record: LWW is not a conflict-resolution strategy, it's a decision to lose data quietly whenever clocks disagree — acceptable for caches and metrics, unacceptable for anything a human typed.

Flashcards

FlashTwo clocks

Wall (NTP, jumps — human timestamps, cross-machine) vs monotonic (never backward, machine-local — durations, timeouts, limiters). Never mix.

FlashLamport vs vector clocks

Lamport: a→b ⇒ L(a)<L(b), converse FALSE (can't detect concurrency). Vector: incomparable vectors = concurrent = real conflict; cost grows with node count.

FlashFLP + escapes

Async + one faulty process ⇒ no deterministic consensus (can't tell crashed from slow). Escapes: timeouts (partial synchrony), randomization, weaker guarantees. Raft: safety always, liveness when network behaves.

FlashLWW's danger

Correctness depends on cross-machine clock agreement; skew silently discards the newer write. Use versions+CAS, single-writer sequences, HLC/vector clocks, or CRDTs.

FlashOrdering patterns

Per-key not global · versions over timestamps · single-writer sequence numbers · HLC (wall+logical) · bounded uncertainty (TrueTime waits) · idempotent/commutative ops (reorder stops mattering).

Scenario Drill

DrillDesign the ordering strategy for a collaborative task board (like Trello) used by teams across regions: cards move between lists, multiple people edit simultaneously, mobile clients go offline and sync later, and the board must converge to the same state for everyone. Specify what you order, how, and what you do about genuine concurrency.

Classify the operations first — they have different ordering needs. Card content edits (title, description) are field-level last-writer-wins candidates, but per field, not per card: two users editing different fields of the same card are not in conflict, and a record-level LWW would falsely discard one — so the unit of conflict is the field, which alone eliminates most reported "conflicts."

Card position (which list, what order within it) is the hard one: naive integer indices conflict constantly, so use fractional/lexicographic ordering keys (a card's position is a value strictly between its neighbors — LexoRank-style): two people inserting into the same gap generate different keys and both succeed, no coordination required, and the result is deterministic given the keys.

Card creation/deletion are naturally commutative if identified by UUID (create is idempotent by id; delete is a tombstone, not a removal — otherwise a delete racing a late-arriving edit resurrects the card). The ordering mechanism: every mutation is an operation with (a) a client-generated UUID (dedup on replay — 10.4), (b) an HLC timestamp (wall-comparable and monotonic, so ordering is human-sensible and never inverts), and (c) the card version it was based on. Operations are appended to a per-board log (9.4.15's ledger, again), and every client folds the same log to the same state — convergence by construction, which is what "everyone sees the same board" actually requires.

Offline mobile: the client queues operations locally and replays them on reconnect; because operations are idempotent (UUID) and position keys are conflict-free, replay after hours offline merges cleanly — the field-level and fractional-key choices are precisely what makes this possible without a merge UI.

Genuine concurrency, handled explicitly: two users editing the same field of the same card within the window is a real conflict — resolve by HLC last-writer-wins and keep the losing value in the operation log so the UI can offer "someone else changed this to X" (concurrency as information, section 5, not silent loss); two users moving the same card to different lists is likewise LWW on the position field, which is intuitively right (the last person to move it wins). What is deliberately not ordered: anything global. There is no board-wide total order and no cross-board ordering — ordering scope is per card field and per list (the fractional keys), which means no coordination point, no leader, and linear scalability across boards (10.6).

The property to state in the design doc: the system never needs to decide "which happened first" for operations that don't interact — and for the few that do, the resolution rule is stated, visible in the log, and recoverable by the user. That sentence is the difference between a collaborative system users trust and one that quietly eats their work.