Lamport Clock
Also known as:
Lamport Timestamp
Logical Clock
Definition
A Lamport clock is a single integer counter kept on every node to order events without a shared wall clock. Every event bumps the counter by one, every outgoing message carries it, and on receive a node sets its counter to max(local, received) + 1. This guarantees that if event A causally happened before event B then LC(A) < LC(B), even when the physical clocks are skewed. It is the building block behind vector clocks, the hybrid logical clock, and most log sequence numbers.
Key Takeaways
- A Lamport clock is a per node counter that ticks on every local event, send, and receive, capturing the happens-before relation without synchronized wall clocks.
- The receive rule is the whole pattern:
local = max(local, received) + 1. - Lamport clocks give a partial order. Append the node id and break ties to get a total order.
- A Lamport timestamp says nothing about real time, and it cannot tell whether two events are concurrent. Vector clocks are needed for that.
- Cassandra last-write-wins timestamps, Kafka producer epochs, Raft terms, and Paxos ballot numbers are all Lamport descendants.
How It Works
- Each node keeps one integer counter, starting at zero.
- Before any local event or sending a message, the node increments its counter by one.
- Every outgoing message is stamped with the sender’s current counter.
- On receiving a message, the node sets its counter to the max of its local value and the received value, then adds one.
- To turn the partial order into a total order, compare counters first and break ties with the node id.