Notesdistributed🌱 seedling
Happens-Before
Also: Happened-Before · Happens-Before Relation · Causality · Causal Order · Concurrent Events
Event a happens before b (a → b) if a precedes b on the same process, a is the send of a message b receives, or a chain of those links them. If neither a → b nor b → a, the events are concurrent: neither could have influenced the other.
Why it exists
Wall clocks can't order events across machines reliably (Clock Skew). What correctness actually depends on is causality: whether information from one event could have reached another.
How it works
- Three rules: process order, send before receive, transitivity.
- The result is a partial order. Some pairs are ordered; the rest are concurrent (a ∥ b).
- Concurrent means "no information flowed between them", not "at the same instant". Two events hours apart can be concurrent if the nodes never communicated.
- An event's causal past is everything that happened before it; a consistent snapshot must include the causal past of every event it contains.
- Communication outside the system (a phone call, a second database) creates real causality the system can't see.
Trade-offs
| Ordering by | Gains | Costs |
|---|---|---|
| causality (Lamport Clock, Vector Clock) | correct without synchronized clocks | needs metadata on every message; no real-time ordering |
| real time (TrueTime) | also captures outside-the-system causality | needs bounded clock error and waiting |
In practice
- Conflict detection: Version Vectors decide whether one write descends from another or the two are concurrent and both must be kept.
- Replication: a reply must not become visible before the question it answers (Consistent Prefix Reads, Causal Consistency).
Pitfalls
- Treating "concurrent" as "simultaneous". It's about knowledge, not time.
- Forgetting hidden channels: causality through a side system isn't tracked.
Connections
- Part of
- Distributed Systems
- Learn first
- Partial Failure
- Builds on this
- Causal ConsistencyTrueTimeVersion Vector
- Mentioned
- Clock Skew
Recall
These cards are also in your review deck, scheduled with spaced repetition.