Causality and Happens-Before

Happens-Before Relation

We assume that there is a strict total order on the events that occur at the same node

Event $a$ happens-before event $b$ (written $a\to b$) iff:

• $a$ and $b$ occurred at the same node, and $a$ occurred before $b$ in that node’s execution order
• event $a$ is the sending of some message $m$, and event $b$ is the receipt of that same message $m$
• there exists an event $c$ such that $a\to c$ and $c\to b$

The happens-before relation is a partial order: it is possible that neither $a\to b$ nor $b\to a$. In that case, $a$ and $b$ are concurrent $a\parallel b$

References

• Distributed Systems Notes. Martin Kleppmann
• Distributed Systems 4.1: Logical time - YouTube
• Distributed Systems 3.3: Causality and happens-before - YouTube
• Distributed Systems 4.1: Logical time - YouTube
• Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. Martin Kleppmann