Distributed Systems

Lamport timestamps

Logical counter per process; causal ordering of events.

In plain terms

Lamport 1978. Each event is max(local, received) + 1. Two events with timestamps in different order may have any real-time ordering — but causally-ordered events keep their order.

Origin

Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM, July 1978. The most cited distributed systems paper ever. Lamport won the Turing Award in 2013 partly for this work.

Where it shows up in production

Cassandra last-write-wins Cell-level timestamps drive conflict resolution; effectively Lamport-style logical time.
Git commit graph Parent pointers encode happens-before — Git is a partial-order Lamport timeline of source-code events.
Kafka offsets Per-partition offsets give total order within a partition (Lamport timestamps with one process).

On Semicolony

Paper papers

Sources & further reading

Paper Lamport — Time, Clocks, and the Ordering of Events (1978)
Talk Martin Kleppmann — Distributed Systems lecture 4

Found this useful?