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
Figure 1. Happened-before relation.
node A(lice)
node B(ob)
node C(hris)
time
Dinner?
a1
b1
c1 c2 c3
a2
b2 b3
a3
Yes, let’s do it
Bored... Can I join?
Figure 2. Causal histories.
node A
node B
node C
time
{a1}
{b1}
{c1}
{a1, a2}
{c1, c2}
{a1, a2, a3}
{a1, a2, b1, b2}
{a1, a2, b1, b2, b3}
{a1, a2, b1, b2, b3, c1, c2, c3}
Figure 3. Vector clocks.
node A
node B
node C
time
[ 1,0,0] [ 2,0,0] [ 3,0,0]
[0, 1,0]
[ 2, 2,0]
[ 2, 3,0]
[0,0, 1] [0,0, 2] [ 2, 3, 3]