Logical Clocks
Ordering global transactions without physical hardware metrics — covering Lamport Timestamps (sequential integer causality), Vector Clocks (integer array concurrent update detection), and sequence-tracking algorithms.
What you'll learn
- Lamport Timestamps — Rules
- Lamport Timestamps — Limitation
- Vector Clocks — Structure
- Vector Clocks — Detecting Concurrency
- Dotted Version Vectors
- Version Vectors vs. Vector Clocks
TL;DR
Ordering global transactions without physical hardware metrics — covering Lamport Timestamps (sequential integer causality), Vector Clocks (integer array concurrent update detection), and sequence-tracking algorithms.
Visual System Topology
Logical Clocks Execution Topology
Concept Overview
Logical clocks are mechanisms for ordering events in distributed systems without relying on synchronized physical clocks. They capture the causal structure of a distributed computation: which events caused which other events, and which events happened concurrently with no causal relationship.
Two fundamental implementations: Lamport Timestamps (scalar integer clocks that preserve the happens-before ordering) and Vector Clocks (arrays of integers, one per process, that fully capture causal history and can detect concurrent events).
Logical clocks are foundational to distributed databases, collaborative applications, and event sourcing systems. They are the mechanism behind DynamoDB's conflict detection, Riak's concurrent write handling, and distributed version control systems like Git.
Key Architectural Pillars
Lamport Timestamps — Rules
Three rules: (1) Before each local event, increment your counter. (2) Include your counter in every message you send. (3) On receiving a message with timestamp T, set your counter = max(local_counter, T) + 1. This ensures that if A happens-before B, then Lamport(A) < Lamport(B) — but NOT the reverse.
Lamport Timestamps — Limitation
Lamport timestamps only partially capture causality. If L(A) < L(B), A may or may not have caused B. Two concurrent events (no causal relationship) can still have different Lamport timestamps. You cannot use Lamport timestamps alone to detect concurrency.
Vector Clocks — Structure
Each process maintains an array V of size N (one slot per process). On local event: V[self]++. On send: attach full V array. On receive(V_msg): for each i, V[i] = max(V[i], V_msg[i]); then V[self]++. Comparing two vectors: V(A) < V(B) iff all elements of V(A) ≤ V(B) and at least one is strictly less.
Vector Clocks — Detecting Concurrency
Events A and B are concurrent (no causal relationship) iff V(A) ≤ V(B) is false AND V(B) ≤ V(A) is false. This is the key advantage over Lamport timestamps. Concurrent events are exactly the cases where conflict resolution is needed.
Dotted Version Vectors
An optimization over vector clocks used in Riak and some versions of DynamoDB. Reduces the size of the causal context that needs to be stored by tracking only the "dot" (which replica originated the write) alongside the causal history.
Version Vectors vs. Vector Clocks
Version vectors track the version of data items across replicas (for conflict detection at the data level). Vector clocks track causal relationships between events (for ordering events). The distinction matters: version vectors attach to data; vector clocks attach to events.