Logical Clocks

Logical Clocks

Logical clocks turn the happens before relation into numbers without needing synchronized wall clocks.

A Lamport clock is a single integer per process. Each process increments its counter before every local event. When it sends a message it attaches its counter, and when it receives one it sets its counter to the maximum of its own value and the received value, then increments. This guarantees that if A happens before B then the timestamp of A is less than the timestamp of B. The reverse does not hold. A smaller timestamp does not prove a causal relationship, so Lamport clocks can order causally related events but cannot detect concurrency.

Vector clocks fix that. Each process keeps a vector with one entry per process. It increments its own entry on each event and, on receiving a message, takes the element wise maximum then increments its own entry. Comparing two vectors reveals the exact relationship. If every entry of A is less than or equal to B and at least one is strictly less, then A happens before B. If neither dominates the other, the events are concurrent. So vector clocks detect concurrency, which Lamport clocks cannot.

• Lamport One number, gives a consistent total order but hides concurrency.
• Vector One number per process, detects concurrency at the cost of size.
• Both need no synchronized physical clock.

Key idea

Lamport clocks order causally related events with a single counter but cannot detect concurrency, while vector clocks use one counter per process to reveal whether two events are causally ordered or concurrent.