Communications of the ACM

other, then they are said to be concurrent.

Using the example of dinner and movie reservations, Figure 1 shows a distributed system with three nodes. An arrow between nodes represents a message sent and delivered. Both Bob’s positive answer to the dinner suggestion by Alice and Chris’s later request to join the party are influenced by Alice’s initial question about plans for dinner.

In this distributed computation, a simple way to check if an event c could have caused another event e (c happened before e) is to find at least one directed path linking c to e. If such a connection is found, this partial order relation is marked c → e to denote the happened-before relation or potential causality. Figure 1 has a1 → b2 and b2 → c3 (and, yes, also a1 → c3, since causality is transitive). Events a1 and c2 are concurrent (denoted a1  c2), because there are no causal paths in either direction. Notex  y if and only if x  y and y  x. The fact Chris was bored neither influenced Alice’s question about dinner, not the other way around.

Thus, the three possible relations between two events x and y are: (a) x might have influenced y, if x → y; (b) y might have influenced x, if y → x; (c) there is no known influence between x and y, as they occurred concurrently x  y.

Causal Histories

Causality can be tracked in a very simple way by using causal histories. 3, 14 The system can locally assign unique names to each event (for example, node name and local increasing counter) and collect and transmit sets of events to capture the known past.

For a new event, the system creates a new unique name, and the causal history consists of the union of this name and the causal history of the previous event in the node. For example, the second event in node C is assigned the name c2, and its causal history is Hc = {c1, c2} (shown in Figure 2). When a node sends a message, the causal history of the send event is sent with the message. When the message is received, the remote causal history is merged (by set union) with the local history. For example, the delivery of the first message from node A to B

(Time, however, totally orders all events, even those unrelated—thus, it is no substitute for causality—and wall clocks are never perfectly synchronized. 11, 16) This article focuses instead on internal causality—the type that can be tracked by the system.

Happened-Before Relation

In 1978, Leslie Lamport defined a
partial order, referred to as happened
before, that connects events of a dis-
tributed system that are potentially
causally linked. 8 An event c can be
the cause of an event e, or c happened
before e, iff (if and only if) both oc-
cur in the same node and c executed
first, or, being at different nodes, if e
could know about the occurrence of
c thanks to some message received
from some node that knows about c.
If neither event can know about the