happenbefore

Happen-before is a relation used in concurrent computation to express a causal ordering of events. If event A happens-before event B, then A is guaranteed to occur earlier than B in a way that allows B to observe the effects of A. The relation is transitive: if A happens-before B and B happens-before C, then A happens-before C. It is a partial order, not a strict timeline, and does not assert real-time timing.

Origins and scope: The concept was introduced by Leslie Lamport for distributed systems and has become central to modern memory models in programming languages. It is used to reason about visibility of writes and the ordering of operations across threads, notably in models such as Java’s Memory Model and the C++11 memory model.

Establishing happen-before: Within a single thread, actions are ordered by program order, so an earlier action happens-before any later action in that thread. Synchronization actions create happen-before edges between threads: releasing a lock happens-before acquiring the same lock, writing to a volatile variable happens-before another thread reads that volatile, starting a new thread places its first action after the creator’s action, and joining a thread proceeds after the joined thread has completed. Transitivity combines these edges to form larger orders.

Implications: If A happens-before B, then B is allowed to observe the effects of A and will not see a state that contradicts A. Establishing happen-before relationships helps prevent data races and clarifies which actions must be visible to others. Conversely, a lack of a happen-before edge can permit visibility races or inconsistent observations.

In practice, happen-before provides a framework for reasoning about correctness in concurrent software, focusing on memory visibility and causal ordering rather than precise timing.