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. Here is how they work:

1. Each node keeps a list of counters, one counter for every node.
2. On each event, a node adds one to its own counter.
3. When it receives a message, it takes the larger of each pair of counters, position by position.

Now compare two lists. If every counter in V(a) is less than or equal to the matching one in V(b), and at least one is strictly less, then a happened before b. If neither list is ahead in every position, the two events happened at the same time, independently. That is a real conflict the system must resolve: the last write wins, the two are merged, or the user is asked (10.5).

The cost is that the list grows with the number of nodes. So real systems limit it: one counter per replica rather than per client, trimming old entries, 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.

Real systems use three ways out:

• Timeouts. Assume the network is usually on time: "if there is no reply in 5 seconds, treat it as failed". That turns something impossible into something that is merely sometimes wrong. The system keeps making progress, but it occasionally guesses wrong. For example, it may declare a leader dead while it is still alive, which is the fencing problem of 10.7.2.
• Randomness.
• Asking for less, such as agreement eventually rather than immediately.

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:
  • Order per key, not across everything.
  • Version numbers and compare-and-set, not timestamps.
  • Sequence numbers from a single writer.
  • Hybrid logical clocks: wall-clock time plus a counter, which never goes backwards.
  • Known uncertainty: Spanner's TrueTime waits until the uncertain moment has passed.
  • Operations that are safe to repeat, or give the same result in any order, so the order 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 it before redesigning anything:

1. Record more on every write: the wall-clock time, and a counter per region that only goes up, plus the ID of the node that wrote it. Then any future conflict can be diagnosed.
2. Measure how far apart the clocks really are between regions, using each host's NTP offset metrics. Expect to find one region's hosts drifting under load, or a quirk of the virtual machines.
3. Search the write log for inversions. An inversion is a pair of writes to the same key where the one that arrived first has the later timestamp. Each one is a possible lost update. If their rate matches the number of support tickets, the theory is confirmed.
4. Check whether the edits are truly at the same time, from two devices, or one after another from different regions. The second is one user moving between regions. It is the common case, and the more embarrassing one, because the user's own edits are racing each other.

The fix, in the order you can ship it.

(a) Short term: limit the damage. Send all of a user's writes to one home region. With only one writer per key, the conflict disappears completely. The cost is slower writes for people who travel, which is a clean and honest trade. Also add conditional writes based on a version number, so an out-of-date write is rejected with a 409 instead of silently winning (9.6.3). The screen then shows "this profile changed somewhere else, please review and try again". Silent data loss becomes something the user can see and fix.

(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."

A card's position, meaning which list and where in it, is the hard part. Simple whole-number positions clash all the time. So use fractional ordering keys, as LexoRank does: a card's position is a value strictly between its two neighbours. Two people inserting into the same gap create different keys, and both succeed, with no coordination. And given the keys, everyone sees the same order.

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.

Real conflicts, handled openly. Two users editing the same field of the same card at nearly the same moment is a real conflict. Resolve it with the hybrid logical clock: the last writer wins. But keep the losing value in the operation log, so the screen can say "someone else changed this to X". The conflict becomes information, as in section 5, instead of silent loss. Two users moving the same card to different lists works the same way: the last move wins, which matches what people expect.

What is deliberately not ordered: anything global. There is no single order across a whole board, and none across boards. Order only exists per card field and per list, using the fractional keys. So there is no central coordinator and no leader, and the system scales evenly as boards are added (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.