Skip to content

Vector clocks and Lamport timestamps#

2024-04-04

Two related but distinct constructs for reasoning about time in distributed systems. Both were proposed by Lamport in 1978.

Lamport timestamps#

Each event has a scalar timestamp. Update rule:

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

Property: if event A happened-before event B (in the causal sense), then L(A) < L(B). The converse is not true — two events with L(A) < L(B) might be concurrent.

Lamport timestamps give you a total order that respects causality, but they can't distinguish "concurrent" from "causally ordered."

Vector clocks#

Each node maintains a vector: an integer per node in the system. Update rule:

  • On local event, increment your own component.
  • On send, attach the full vector.
  • On receive, component-wise max with received, then increment your own.

Property: V(A) < V(B) iff A happened-before B. Concurrent events have incomparable vectors.

When to use which#

  • Lamport: if you just need a total order (e.g., for a serial log where you want to establish "which came first"). Cheap: one integer per event.
  • Vector: if you need to detect concurrent updates (e.g., for eventual- consistency reconciliation in Dynamo-style systems). Costs O(N) per event where N is cluster size.

Version vectors#

A refinement of vector clocks used in Dynamo/Riak: instead of one component per node, one component per client that has updated the object. Vectors stay small even in large clusters, at the cost of not tracking global order.

Reference#

  • Lamport, Time, Clocks, and the Ordering of Events in a Distributed System (CACM 1978).
  • Fidge, Timestamps in Message-Passing Systems That Preserve the Partial Ordering (Australian Computer Science Communications, 1988).
  • DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007).