Course contentsShow
← Computer Science
Lesson 2627 of 2,87258. Distributed Systems BasicsFree lesson

Happens-Before Relation

Defining the partial ordering of events in a distributed system based on causality.

Happens-Before Relation

You'll learn how to establish causal ordering between events across distributed nodes without relying on synchronized clocks.

The Core Problem

In a distributed system, we can't use physical timestamps to determine which event truly "caused" another—clocks skew and drift across machines. Instead, we need a logical way to capture causality. That's where the happens-before relation comes in.

What It Is

The happens-before relation (denoted →) defines a partial ordering of events based on observable causality, not wall-clock time. Event A → B means "A happens before B" if:

  1. Same process: A occurs before B on the same node (local execution order)
  2. Message passing: A is the send event and B is the corresponding receive event
  3. Transitivity: If A → B and B → C, then A → C

If neither A → B nor B → A, the events are concurrent (||)—they happened independently, with no causal link.

Why This Matters

This relation lets us reason about causality without synchronized clocks. For example, if you post a message and someone replies, the reply happens-after your post—even if their system clock was set earlier. The message delivery establishes the causal chain.

Think of it like a conversation across rooms: you shout something, your friend hears it and responds. Their response happens-after your shout because they heard you, regardless of what their wristwatch says.

Key Takeaway:
The happens-before relation captures causality in distributed systems through local ordering, message passing, and transitivity—creating a partial order that respects which events could have influenced which, independent of physical clocks.