Happens-Before Relationship

The happens-before relation is transitive. If event A happens before event B, and event B happens before event C, then it is guaranteed that A happens before C.

• Formal definition: If A → B and B → C, then A → C.
• Practical impact: This property allows systems to derive indirect causal relationships without direct communication. A node can infer ordering across a chain of events.
• Contract example: If a notice of breach is sent before a cure period expires, and the cure period expires before a termination right activates, the notice causally precedes the termination right.

An event cannot happen before itself. The happens-before relation is irreflexive, meaning no event is causally dependent on its own occurrence.

• Formal definition: For any event A, A → A is always false.
• Why it matters: This prevents circular causal loops in distributed reasoning. A contract obligation cannot trigger itself without an intervening event.
• System design: Irreflexivity ensures that event ordering algorithms terminate and do not create infinite dependency chains.

If event A happens before event B, then B cannot happen before A. The relation is antisymmetric, enforcing a single direction of causal influence.

• Formal definition: If A → B and A ≠ B, then B → A is false.
• Concurrency implication: If neither A → B nor B → A holds, the events are concurrent — they are causally independent.
• Legal relevance: Two contract amendments drafted independently by different parties are concurrent events until one is communicated to the other, establishing a happens-before edge.

The happens-before relation is established through message passing. If event A is the sending of a message and event B is the receipt of that same message, then A → B.

• Lamport's rule: A message cannot be received before it is sent, creating a causal link across process boundaries.
• Distributed contracts: When a smart contract emits an event on one chain and a relay picks it up on another, the emission happens before the relay's processing.
• Practical guarantee: This ordering ensures that a termination notice is always logged before a downstream system acts on it.

The happens-before relation enables logical clocks like Lamport timestamps and vector clocks to capture causality without physical time synchronization.

• Clock condition: If A → B, then the logical timestamp of A is strictly less than the logical timestamp of B.
• Vector clocks: Assign each process a counter; when a message is sent, the sender's counter is incremented and included. Receivers merge and increment, capturing full causal history.
• Contract auditing: Vector clocks can reconstruct the exact causal order of multi-party contract negotiations across independent systems.

The happens-before relation defines a partial order, not a total order. Concurrent events — those with no causal path between them — are incomparable under this relation.

• Partial order: Some event pairs have a defined happens-before relationship; others do not.
• Total order extension: Systems can impose an arbitrary deterministic tiebreaker (e.g., process ID) on concurrent events to create a total order for state machine replication.
• Temporal reasoning: In contract analysis, two independent obligations with no causal link can be executed in any order without violating the agreement's logic.

A logical clock algorithm that establishes a partial ordering of events in a distributed system. Each process maintains a counter incremented on every event; when a message is sent, the sender's counter is included. The receiver advances its own clock to be greater than the received timestamp. This guarantees that if event A happens-before event B, then the Lamport timestamp of A is less than that of B. The converse is not true, making it a consistent but not strongly complete clock.

An extension of Lamport timestamps that captures causality exactly. Each process maintains a vector of counters, one for every process in the system. By comparing vector timestamps, you can definitively determine if two events are causally related or concurrent. If neither vector is less than or equal to the other, the events are concurrent—meaning neither happened-before the other. This is essential for detecting write conflicts in eventually consistent databases like DynamoDB and Riak.

A communication primitive that ensures all correct processes deliver messages in the same total order, and that this order respects the happens-before relationship. If message A is broadcast before message B by the same process, A is delivered before B everywhere. This is the foundation of state machine replication and consensus algorithms like Raft and Paxos. It transforms a concurrent, distributed execution into a linearizable sequence of commands.

Low-level CPU instructions that enforce ordering constraints on memory operations in multi-core processors. Without barriers, hardware may reorder reads and writes for performance, violating the intuitive happens-before expectations of a programmer. A store barrier ensures all preceding stores complete before any subsequent store. A load barrier ensures all preceding loads complete before any subsequent load. These are the primitives used to implement locks, mutexes, and lock-free data structures in languages like C++ and Rust.

Two events are concurrent if neither happens-before the other—they are causally independent and can occur in any order. This is a logical property. Parallel execution means events physically overlap in time on different hardware units. Concurrency is about structure (dealing with multiple things at once); parallelism is about execution (doing multiple things at once). A single-core machine can run concurrent tasks interleaved, but not in parallel. Understanding this distinction is critical for designing correct distributed algorithms.