Vector clocks and logical time

Logical clocks order events in a distributed system without requiring synchronized wall clocks. They capture causality: did A happen before B, or were they concurrent?

Lamport clocks

Each process maintains a counter. Rules:

• On any local event, increment counter.
• On send, attach counter to message.
• On receive, set counter = max(local, received) + 1.

Property: if A happens-before B, Lamport(A) < Lamport(B). The converse is not true; A and B with Lamport(A) < Lamport(B) might be concurrent.

This gives a total order on events but loses the distinction between causal and concurrent.

Vector clocks

Each process N maintains a vector V[1..N] where V[i] is N's belief about process i's counter.

Rules:

• On local event in process p, increment V_p[p].
• On send from p, attach V_p to message.
• On receive at q with vector V_msg, set V_q[i] = max(V_q[i], V_msg[i]) for all i, then increment V_q[q].

Comparison:

• V1 < V2 (V1 happens-before V2): for all i, V1[i] <= V2[i], and at least one strict <.
• V1 == V2: identical.
• V1 || V2 (concurrent): neither V1 < V2 nor V2 < V1. Some entries higher in V1, some higher in V2.

Vector clocks detect concurrency precisely. That is their value.

Use cases

1. Causal consistency in distributed stores: Riak, Voldemort, COPS.
2. Conflict detection: two concurrent writes to the same key produce sibling versions.
3. Anti-entropy: knowing what each replica has seen.

Hybrid logical clocks

Vector clocks scale O(N) per write, where N is the number of nodes. Bad at scale.

HLC combines wall clock with logical counter. Each timestamp is (physical, logical). Compact, monotonic, and respects causality if you can bound clock skew. Used by CockroachDB, MongoDB cluster time.