Denys Isaichenko 🧘

[LF] Causality

This is a series of notes on topics related to Local-First software.

Problem: Ordering events in a distributed system is challenging due to potential message reordering in the network. This can lead to confusing situations where a reply is received before the original message.

Example: User C receives reply m2 before the initial message m1, making it seem like B predicted A’s statement. This can cause issues, especially with ordered operations like database updates.

Naive Approach (Timestamps): Attaching timestamps from local clocks to messages seems like a solution, but clock synchronization (even with NTP) has limitations and residual skew. This can lead to incorrect ordering based on timestamps.

Happens-Before Relation: A formal way to define the “correct” order of events, capturing causality. Assumes each node has a single thread of execution with a strict local order.

Definition of Happens-Before (a → b):

  1. Local Order: If events a and b occur at the same node and a happens before b in that node’s execution.
  2. Message Passing: If event a is sending a message m, and event b is the receipt of the same message m (assuming unique messages).
  3. Transitivity: If there exists an event c such that a → c and c → b.

Partial Order: The happens-before relation is a partial order, meaning that for some events a and b, neither a → b nor b → a might be true.

Concurrency (a || b): If neither a → b nor b → a, then events a and b are considered concurrent, implying no causal dependency through message exchange.

Causality:

Causal Order: A strict total order ≺ on events is a causal order if (a → b) ⇒ (a ≺ b).

Sources