Time, Clocks, and the Ordering of Events in a Distributed System
Citation: Lamport, L. (1978). Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM, 21(7), 558-565.
Core Contribution
Introduced logical clocks (Lamport timestamps) as a way to capture the “happens-before” relationship in distributed systems without relying on synchronized physical clocks. Proved that events can be totally ordered in a way consistent with causality.
Key Concepts
- Happens-before relation (→): a → b means a happened before b (causally)
- Logical clock: Each process maintains a counter incremented for every event
- Lamport timestamp: C(e) for event e, where a → b implies C(a) < C(b)
- Total ordering: Events can be ordered even when causally unrelated
- Mutual exclusion: Total ordering enables distributed algorithms
The Happened-Before Relation
a → b if:
1. a and b are in the same process, and a occurred before b
2. a is the sending of a message, and b is the receipt of that message
3. Transitive: a → b and b → c implies a → c
Why It Matters
Before this paper, distributed systems lacked a principled way to reason about ordering of events across independent nodes. This paper provided the foundation:
- Eventual consistency
- Distributed transactions
- Vector clocks (extension of logical clocks)
- Byzantine fault tolerance research
The Bakery Algorithm
Included in the paper: a mutual exclusion algorithm for distributed systems using only shared memory and atomic reads/writes, inspired by a bakery number system.
See Also
- Networking (distributed systems)
- Operating Systems (concurrency)
- Algorithms (mutual exclusion)