Learning path

Full curriculum

Full curriculum

Unit content

Happens-before and Lamport logical clocks

Distributed events are not naturally arranged on one exact global timeline. What often matters is causality.

Event $a$ happens before event $b$, written $a \rightarrow b$, when

  • both occur in one process and $a$ occurs first;
  • $a$ sends a message that $b$ receives;
  • or the relation follows transitively through intermediate events.

If neither $a \rightarrow b$ nor $b \rightarrow a$, the events are concurrent: the system has no causal evidence that one influenced the other.

A Lamport clock assigns an increasing logical counter to events. A process advances its counter locally and incorporates received timestamps so

$$a \rightarrow b \implies L(a)<L(b).$$

The converse does not hold: a lower Lamport timestamp does not prove causality.

Logical clocks capture an order consistent with causality without requiring synchronized physical clocks.