Part 1 · 2 chapters · ~18 min

Time and Ordering

Physical clocks drift, are corrected by NTP and jump, so cross-machine timestamps cannot order events and last-write-wins loses data; TrueTime bounds the uncertainty. Then logical time: happened-before, Lamport clocks, vector clocks that detect concurrency, and the practical options.

3

Physical clocks

why timestamps cannot order events across machines
  1. Drift runs at 10 to 100 ppm. Use the wall clock for time of day and the monotonic clock for durations.
  2. NTP slews or steps the clock. Its accuracy depends on how symmetric the network path is.
  3. Clocks jump, sometimes backwards, so a computed duration can come out negative.
  4. Last-write-wins by timestamp silently loses later writes from a slower clock.
  5. Bounded uncertainty (TrueTime) lets Spanner order events by real time.
  6. The lesson: physical time is for humans, monotonic time for durations, logical clocks for order.
code
// measure durations with the monotonic clock, never Date.now()
const t0 = performance.now();            // browser and Node: monotonic
await doWork();
const ms = performance.now() - t0;       // never negative, unaffected by NTP steps

// Node: process.hrtime.bigint() is also monotonic
// Go: time.Since(t0) uses the monotonic reading automatically
// Java: System.nanoTime(), not System.currentTimeMillis()
PHYSICAL CLOCKS LIE
drift, NTP, leap seconds and why two machines' timestamps cannot order events
swipe the figure sideways, or tap expand for full screen
1/6
drift
Drift: a quartz oscillator runs slightly fast or slow, by 10 to 100 parts per million depending on temperature and age. Left alone, two machines diverge by up to several seconds a day. Wall-clock time (time of day) and monotonic time (a counter that only goes forward, for measuring durations) are different clocks: never measure a timeout with the wall clock.
4

Lamport clocks, vector clocks and causality

order by cause, not by clock
  1. Happened-before is defined by process order and by messages.
  2. Lamport clocks give a total order consistent with causality.
  3. The limit: Lamport clocks cannot detect concurrency.
  4. Vector clocks: V(a) < V(b) exactly when a happened before b.
  5. Concurrency shows up as two vectors that cannot be compared. Keep siblings and merge them.
  6. In practice: version vectors, hybrid logical clocks, a single leader, or TrueTime.
code
// a vector clock in 20 lines
type VC = Record<string, number>;
const tick  = (v: VC, me: string): VC => ({ ...v, [me]: (v[me] ?? 0) + 1 });
const merge = (a: VC, b: VC, me: string): VC => {
  const out: VC = { ...a };
  for (const [k, n] of Object.entries(b)) out[k] = Math.max(out[k] ?? 0, n);
  return tick(out, me);
};
const leq = (a: VC, b: VC) => Object.keys({ ...a, ...b }).every(k => (a[k] ?? 0) <= (b[k] ?? 0));
export const compare = (a: VC, b: VC) =>
  leq(a, b) && leq(b, a) ? 'equal' : leq(a, b) ? 'before' : leq(b, a) ? 'after' : 'concurrent';

compare({ p1: 2 }, { p3: 1 });            // 'concurrent': keep both, merge in the app
the frontend version
Offline-first apps (the FSD course part 8) meet the same problem: two devices edit the same note while offline. Either the server sequences the edits (one leader), or a CRDT merges them deterministically. Last-write-wins by device clock is the option that silently drops one user's work.
LAMPORT AND VECTOR CLOCKS
ordering events by what could have caused what, without any shared clock
swipe the figure sideways, or tap expand for full screen
1/6
happened-before
Happened-before: three processes exchange messages. On P1, a then b; P1 sends m1 at b, P2 receives it at c; P2 sends m2 at d, P3 receives it at e. So a → b → c → d → e. P3's earlier event f has no path from a: neither happened before the other; they are concurrent.