Lamport & Vector Clocks

Wall clocks are unreliable

Nodes use NTP; clocks drift and jump. Using timestamp = now() for ordering causes:

• Lost updates — clock A ahead of B, LWW picks wrong winner
• Ordering violations — event B happens after A in reality but timestamps say otherwise

Google's TrueTime (Spanner) bounds uncertainty — know it exists as an exception, not the default.

Happened-before

Lamport defined happened-before (→): same process order, or message send before receive. Events not related by → are concurrent.

Lamport timestamps

Each node increments a counter; on message send/receive, merge max(local, received) + 1. Gives a total order that respects causality but cannot detect concurrency — two concurrent events get arbitrary order.

Enough for many total order broadcast schemes; not enough for conflict detection.

Vector clocks

Per-node vector [c1, c2, …, cn]:

• If V(A) < V(B) component-wise (at least one strict), A happened-before B
• If neither dominates, events are concurrent — application must merge

Used in Dynamo-style conflict detection and version vectors on replicas.

Total order broadcast

All nodes deliver messages in the same order — prerequisite for strong consistency on a log. Implemented via consensus (Topic 6) or single leader.

OS cross-reference

OS roadmap covered scheduling order on one machine. Here, no global observer exists — logical order replaces wall clock.