Ordering & Causality

Table of Contents

🟠 P1 — how distributed systems reason about “what happened before what”

Problem #

In a single process, events have natural total order. In distributed systems, there’s no global clock — “what happened first?” is a hard question.

Key Concepts #

Happens-Before Relation (Lamport, 1978) #

Event A happens-before B if:

A and B in same process and A comes first, OR
A is send, B is corresponding receive, OR
Transitivity: A → C → B

If neither A → B nor B → A, events are concurrent.

Logical Clocks #

Clock Type	Tracks	Limitation
Lamport Clock	Monotonic counter per event/message	Can’t distinguish concurrent from ordered
Vector Clock	One counter per process (vector)	Detects concurrency; size grows with N
Hybrid Logical	Physical time + logical counter	Bounded size; used by CockroachDB

Total vs Partial Ordering #

Partial: Only causally related events ordered (happens-before)
Total: Every pair ordered. Requires consensus (Raft log). Expensive.

Instinct #

Most systems need causal ordering at most, not total. Social feeds need causal (replies after originals). Payment ledgers need total (single sequence per account). Choose the cheapest ordering that satisfies your requirements.

Framing #

Here’s an example of how to frame the balancing of tradeoffs.

“For the activity feed, causal consistency suffices. For the payment ledger, we need total ordering within an account — a single-leader database gives us that within a partition.”

References #

Time, Clocks, and the Ordering of Events in a Distributed System — Lamport (1978)
Jepsen: Consistency Models — interactive ordering/consistency map

DDIA 2e Reference #

Chapter 8: Ordering guarantees and unreliable clocks
Chapter 9: Total order broadcast, consensus, and their equivalence