Chapter 5 · Watch, then practise
Time and State in Distributed Systems
Separate physical time from event ordering. Use the happened-before relation and Lamport clocks to explain which ordering facts messages establish and which facts a timestamp cannot prove.
3 questions · 3 with related videos. Matches are based on playlist titles; broader background matches are labeled.
What to study
- Happened-before relation
- Logical clocks
- Concurrent events
Chapter playlists
Choose a playlist
Notes
Distributed Systems 3.3: Causality and happens-before
Martin Kleppmann · 16:25
Supplementary lecture specifically covers causality and the happened-before relation.
1. Define causality
Which rules create the happened-before relation?
Earlier events within one process precede later ones; a message send precedes its receipt; and the relation is transitive. Events are concurrent when neither precedes the other by these rules. Concurrency here describes causal independence, not necessarily equal physical timestamps.
Lamport logical clock 🔥🔥
Perfect Computer Engineer · 5:03
Lamport-clock explanation; apply the receive rule to this question’s timestamps.
2. Update a logical clock
With the usual increment-by-one Lamport convention, a process has clock 4 and receives a message timestamped 9. What is its receive timestamp?
Set the clock to max(4, 9) + 1 = 10. A subsequent local event becomes 11. This maintains the required increasing order across both local execution and the send–receive edge.
Logical Clocks 🔥🔥
Perfect Computer Engineer · 8:02
Choose a video · 2 lectures
Logical-clock lectures support distinguishing clock order from a causal guarantee.
3. Avoid reversing an implication
If C(a) = 3 and C(b) = 8, does that prove a happened before b?
No. Happened-before implies increasing Lamport timestamps, but increasing timestamps do not imply a causal path. Unrelated processes can produce these values independently. A total order can break ties with process identifiers, but it does not create causality.