Wall clocks are unreliable across machines. Logical clocks (vectors of counters) track causality precisely. Foundation of many distributed algorithms.

Node A[1,0,0]Node B[0,1,0]Node C[0,0,1]A→B sendA: [2,0,0]B receivesB: [2,2,0]C concurrentC: [0,0,2]Compare vectorsdetect concurrentA < B: causalB saw AB ∥ C: concurrentconflict!send [2,0,0]
Vector clocks track per-node counts; compare vectors to detect causal vs concurrent
Advertisement

The vector

Each node has counter for every node in cluster. Increment own on event. Send full vector with messages. Update by max on receive.

The vector

Each node has counter for every node in cluster. Increment own on event. Send full vector with messages. Update by max on receive.

Advertisement

Causal comparison

V1 < V2 if V1[i] ≤ V2[i] for all i AND V1 ≠ V2. Means V2 causally happened after V1.

Concurrent detection

Not V1 ≤ V2 AND not V2 ≤ V1 → V1 || V2 (concurrent). Two clients wrote without seeing each other. Conflict.

Size grows with cluster

Vector size = # of nodes. 100-node cluster = 100 ints per version. Alternatives: hybrid logical clocks (HLC) bound size.

Used by

Dynamo, Riak, Cassandra (via timestamps + tie-breakers). Anywhere you need conflict resolution without global order.

Vector per node + max on receive + causal compare. Concurrent detection without global clock.