Time, Clocks & Ordering in Distributed Systems - Physical Clocks, Lamport, Vector Clocks, HLC & TrueTime

# Why "just use timestamps" loses data: last-writer-wins (LWW) on skewed wall clocks,
# compared with a logical clock and a vector clock on the same two writes.
# All millisecond values are EXAMPLE values chosen to make the failure visible.

SKEW_B_MS = -120  # replica B's wall clock runs 120 ms behind true time (example)

def wall(node: str, true_ms: int) -> int:
    """What each replica's wall clock *reads* at a given true time."""
    return true_ms + (SKEW_B_MS if node == "B" else 0)

# The real-world sequence: a user writes v1 via replica A, reads it back,
# then 50 ms later writes v2 via replica B. v2 is causally AFTER v1.
writes = [
    {"value": "v1", "node": "A", "true_ms": 1_000},
    {"value": "v2", "node": "B", "true_ms": 1_050},
]

# 1) Wall-clock LWW: each write is stamped with the local wall clock, highest wins.
for w in writes:
    w["wall"] = wall(w["node"], w["true_ms"])
lww = max(writes, key=lambda w: w["wall"])
print("1) wall-clock LWW")
for w in writes:
    print(f"   {w['value']} via {w['node']}: true={w['true_ms']} stamped={w['wall']}")
print(f"   winner={lww['value']}  -> the NEWER write v2 is silently discarded\n")

# 2) Lamport-style LWW: the client carries the max timestamp it has seen (from reading v1),
#    and the writer stamps max(local_counter, seen) + 1. Causal order is now preserved.
seen_by_client = 0
lamport = {"A": 0, "B": 0}
stamps = {}
for w in writes:
    n = w["node"]
    lamport[n] = max(lamport[n], seen_by_client) + 1
    stamps[w["value"]] = (lamport[n], n)   # (counter, node id) tie-break gives a total order
    seen_by_client = lamport[n]            # client read its own write back
print("2) Lamport-stamped LWW:", stamps, "-> winner", max(stamps, key=lambda v: stamps[v]))

# 3) Vector clocks: tell 'v2 happened after v1' apart from 'v2 was concurrent with v1'.
def descends(a: dict, b: dict) -> bool:
    return all(a.get(k, 0) >= v for k, v in b.items())

v1 = {"A": 1}
v2_after_read = {"A": 1, "B": 1}   # client passed v1's context along with its write
v2_blind = {"B": 1}                # client never saw v1
print("3) vector clocks")
print("   v2 (with context) descends v1:", descends(v2_after_read, v1), "-> safe overwrite")
print("   v2 (blind) vs v1 concurrent:", not descends(v2_blind, v1) and not descends(v1, v2_blind),
      "-> keep both as siblings, let the app merge")

1) wall-clock LWW
   v1 via A: true=1000 stamped=1000
   v2 via B: true=1050 stamped=930
   winner=v1  -> the NEWER write v2 is silently discarded

2) Lamport-stamped LWW: {'v1': (1, 'A'), 'v2': (2, 'B')} -> winner v2
3) vector clocks
   v2 (with context) descends v1: True -> safe overwrite
   v2 (blind) vs v1 concurrent: True -> keep both as siblings, let the app merge

// A tiny decision helper: which time/ordering mechanism fits a requirement?
// The mapping mirrors the comparison table on the hub page; it is a teaching aid, not a library.
type Need = {
  name: string;
  humanReadableTime: boolean;   // do people or SLAs read this timestamp?
  causalOrder: boolean;         // must "B saw A" imply ts(A) < ts(B)?
  detectConcurrency: boolean;   // must we notice two writes that did not see each other?
  externalConsistency: boolean; // must real-time order across the whole system match commit order?
  measureDuration: boolean;     // timeouts, latency, lease countdowns
};

function choose(n: Need): string {
  if (n.measureDuration) return "monotonic clock (never wall clock) for elapsed time";
  if (n.externalConsistency) return "TrueTime-style bounded clock + commit wait (or a single timestamp oracle)";
  if (n.detectConcurrency) return "vector clock / dotted version vector (or a CRDT)";
  if (n.causalOrder && n.humanReadableTime) return "hybrid logical clock (HLC)";
  if (n.causalOrder) return "Lamport clock with node-id tie-break";
  return "NTP-synced wall clock, treated as approximate";
}

const needs: Need[] = [
  { name: "request timeout / lease countdown", humanReadableTime: false, causalOrder: false, detectConcurrency: false, externalConsistency: false, measureDuration: true },
  { name: "log line timestamps for humans",     humanReadableTime: true,  causalOrder: false, detectConcurrency: false, externalConsistency: false, measureDuration: false },
  { name: "replicated log / total order",       humanReadableTime: false, causalOrder: true,  detectConcurrency: false, externalConsistency: false, measureDuration: false },
  { name: "MVCC versions in a geo-distributed DB", humanReadableTime: true, causalOrder: true, detectConcurrency: false, externalConsistency: false, measureDuration: false },
  { name: "multi-writer shopping cart",          humanReadableTime: false, causalOrder: true, detectConcurrency: true,  externalConsistency: false, measureDuration: false },
  { name: "global bank ledger, strict serializable", humanReadableTime: true, causalOrder: true, detectConcurrency: false, externalConsistency: true, measureDuration: false },
];

for (const n of needs) {
  console.log(`${n.name.padEnd(42)} -> ${choose(n)}`);
}

request timeout / lease countdown          -> monotonic clock (never wall clock) for elapsed time
log line timestamps for humans             -> NTP-synced wall clock, treated as approximate
replicated log / total order               -> Lamport clock with node-id tie-break
MVCC versions in a geo-distributed DB      -> hybrid logical clock (HLC)
multi-writer shopping cart                 -> vector clock / dotted version vector (or a CRDT)
global bank ledger, strict serializable    -> TrueTime-style bounded clock + commit wait (or a single timestamp oracle)