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

Pitfalls

  • Treating "concurrent" as "simultaneous". It's about knowledge, not time.
  • Forgetting hidden channels: causality through a side system isn't tracked.

Recall

These cards are also in your review deck, scheduled with spaced repetition.