Time Causality · Happened Before Relation

Key Question

If A happens before B and B happens before C, what can we conclude? And what does it mean for two events to be “concurrent”?

Deep Dive

The third and final rule of the happened-before relation is transitivity: if a → b and b → c, then a → c. This may seem trivial — it is a property we expect from any ordering relation — but it is enormously consequential. Transitivity allows causality to chain across processes and across time, linking events that have no direct connection.

Consider a chain of three processes:

Process P1      Process P2      Process P3
    |               |               |
    a1              |               |
    |               |               |
    a2 ────────────→ b1             |
    |               |               |
    |               b2 ────────────→ c1
    |               |               |
    |               |               c2

a2 → b1 (send-receive)
b2 → c1 (send-receive)
But also: a2 → b1 → b2 → c1, so a2 → c1 (by transitivity)

The event at P1 (sending a message) causally influences an event at P3 two steps away. Even though no message traveled directly from P1 to P3, the information carried by the first message eventually reached P3 through an intermediate process. This is how causality ripples through a distributed system: an action on one machine can have downstream effects on many machines, through chains of message passing.

Now we come to a subtle and important concept: concurrent events. Two events a and b are concurrent (written a || b) if neither a → b nor b → a holds. The term “concurrent” is slightly misleading — it does not mean the events happened at the same physical time. It means there is no causal relationship between them. No chain of causality connects them in either direction.

Process P1      Process P2
    |               |
    a1              b1
    |               |
    a2              b2
    |               |
    a3─────────────→ b3 (send-receive)
    |               |
    a4              b4

In this diagram:

a1 and b1 are concurrent: there is no message connecting them, no causal chain.
a1 and b2 are concurrent: same reason.
a3 and b3: a3 → b3 (send-receive).
a4 and b3: a3 → a4 (same process) and a3 → b3, so a4 and b3? Actually, a3 → a4 and a3 → b3. But do we know a4 → b3? No. a4 happened after the send on P1, but nothing tells us a4 happened before b3 or vice versa. They are concurrent.
Wait, let’s reconsider. a3 → b3. a3 → a4. We have a3 → b3 and a3 → a4. But we don’t have a → b or b → a linking a4 and b3. So a4 || b3. Correct.

Concurrency is the source of all interesting problems in distributed systems. When two events are concurrent, their relative order is undefined — and if they conflict (e.g., two writes to the same data item), the system must decide how to resolve the conflict. This is why the CAP theorem matters, why conflict-free replicated data types (CRDTs) exist, and why vector clocks were invented.

Concurrency also helps us reason about what a process “knows.” If a → b, then b may have information about a. If a || b, then b has no information about a, and any decision made by b is made without knowledge of a.

Check Your Understanding

In the 3-process diagram above, is a1 causally related to c2? Trace the chain.
Explain in one sentence why concurrent does not mean “at the same physical time.”
Two bank transactions update the same account balance. They arrive at different servers that do not communicate. Are the transactions concurrent? What problem does this create?

The “So What?”

Transitivity explains why a change in one service can cascade through a chain of downstream services — a concept central to debugging distributed traces and understanding causal consistency. Concurrency is the fundamental reason distributed databases have conflicts. Every time you see a “conflict detected” error in a distributed system, you are seeing the consequences of concurrent events that the system could not order. Understanding concurrency is understanding the limits of what a distributed system can know.

✏️ Exercises

Topic 3: Happened-Before Relation — Exercises

Exercise 1: Identifying Causal Relationships

Given the space-time diagram below, list ALL pairs of events that are causally related (a → b) and ALL pairs that are concurrent (a || b).

Process A       Process B       Process C
    |               |               |
    a1              |               |
    |               b1              |
    a2─────────────→b2              |
    |               |               c1
    a3─────────────→b3              |
    |               |               c2
    |               |               |

Use the notation (a1, b1) to mean “a1 and b1.” Include all pairing combinations across processes, not just within them. (You do not need to list same-process pairs — they are all ordered by rule 1.)

Exercise 2: Message Chain Causality

Process A sends a message M1 to Process B. After receiving M1, Process B sends a message M2 to Process C. After receiving M2, Process C performs an internal event.

(a) Draw the space-time diagram of this scenario (3 processes, 2 messages). (b) Is A’s send of M1 causally related to C’s internal event? Explain using the happened-before rules. (c) Would the answer change if B sent M2 before receiving M1? Why?

Exercise 3: Network Delay and Causality

Two events occur on different machines:

Event a: A sends a message to B.
Event b: B receives the message 5 seconds later (due to network congestion).

After receiving the message, B performs event c.

(a) Is b → c? Why? (b) Is a → b? Why? (c) Now suppose after sending the message, A performs event d (a local computation) 2 seconds before the message is delivered. Is d → c? Trace the chain. (d) What if A and B’s clocks were perfectly synchronized, and the timestamps showed d at T=10:00:00.003, c at T=10:00:00.001? Does this contradict the happened-before relation? Why would clock-based ordering give the wrong answer?

Exercise 4: Concurrent Writes in Practice

A distributed key-value store has three replicas: R1, R2, R3. A client writes value “X” to key “k” and receives acknowledgment from R1. The write propagates to R2 and R3. Meanwhile, another client (unaware of the first write) writes value “Y” to the same key “k” and receives acknowledgment from R2.

(a) Are the two writes concurrent? Why? (b) R3 receives the write of “Y” after it has already received “X.” From R3’s perspective, which value is “correct”? (c) If the system uses last-writer-wins (LWW) based on physical timestamps, and the clocks on client 1 and client 2 differ by 50 seconds, what could go wrong? (d) What does the happened-before relation tell us that timestamps do not, in this scenario?

👁️ View Solutions

Topic 3: Happened-Before Relation — Solutions

Solution 1

Within-process relationships (all by rule 1):

A: a1 → a2 → a3
B: b1 → b2 → b3
C: c1 → c2

Send-receive relationships (rule 2):

a2 → b2 (message from A to B)
a3 → b3 (another message from A to B)

Transitive relationships (rule 3):

From a1:

a1 → a2 → b2, so a1 → b2
a1 → a2 → b2 → b3, so a1 → b3
a1 → a2 → b2 → b3 → b3 → … actually b3 is followed by nothing in B that reaches C. But wait, a3 → b3, not a2 → b2 → b3. Let me re-trace.

Actually let’s reconsider. The diagram shows a2 → b2 and a3 → b3. There is no message from B to C.

So transitive relationships:

a1 → b2 (a1 → a2 → b2)
a1 → b3 (a1 → a2 → b2 → b3? No, a2 → b2, and b2 → b3 in B, so a1 → a2 → b2 → b3, yes)
a1 → b3 also via a1 → a3 → b3 (a1 → a3, a3 → b3, so a1 → b3)
a2 → b3 (a2 → b2 → b3)
a2 → b3 also via a2 → a3 → b3
a3 → b3 directly (message)
No relationships with C — there is no message from A or B to C, and no message from C to A or B.

Concurrent pairs:

All pairs involving C are concurrent (no messages to/from C):

a1 || c1, a1 || c2
a2 || c1, a2 || c2
a3 || c1, a3 || c2
b1 || c1, b1 || c2
b2 || c1, b2 || c2
b3 || c1, b3 || c2

Also concurrent across A and B:

a1 || b1 (no path either direction)
a2 || b1 (a2 → b2, and b1 → b2, but no path a2 → b1 or b1 → a2)
a3 || b1 (similar reasoning)
a3 || b2 (a3 → b3, b2 → b3, no path between a3 and b2 directly)

Any pair not connected by a → b chain is concurrent.

Solution 2

(a)

Process A       Process B       Process C
    |               |               |
    a1 (send M1)───→b1 (recv M1)   |
    |               |               |
    |               b2 (send M2)───→c1 (recv M2)
    |               |               |
    |               |               c2 (internal)

(b) Yes, A’s send (a1) is causally related to C’s internal event (c2).

a1 → b1 (rule 2: send-receive of M1)
b1 → b2 (rule 1: same process)
b2 → c1 (rule 2: send-receive of M2)
c1 → c2 (rule 1: same process)
By transitivity (rule 3): a1 → b1 → b2 → c1 → c2, therefore a1 → c2

(c) If B sent M2 before receiving M1, then b2 (send M2) would come before b1 (receive M1) in process B. In that case:

a1 → b1 (send-receive of M1)
b2 → c1 (send-receive of M2)
But a1 and b2? We have b2 → b1 (b2 before b1 in B). And a1 → b1. But do we have a1 → b2? No. a1 → b1 and b2 → b1, but we need a1 → … → b2. b2 happens before b1, so a1 cannot → b2. And b2 → a1? No, b2 → c1, no path to a1. So a1 and b2 are concurrent. And since b2 → c1 → c2, we have a1 || c2.

The answer changes completely: if B sends M2 before receiving M1, then M2 was sent without knowledge of M1, and C’s internal event is not causally dependent on A’s send.

Solution 3

(a) Yes, b → c. Both events are in the same process (B), and b (receive) happens before c (internal event). Rule 1: same-process ordering.

(b) Yes, a → b. a is the send event and b is the receive event of the same message. Rule 2: send happens before receive. The 5-second delay does not affect this — the relationship holds regardless of how long the message takes.

(c) Yes, d → c. Here is the chain:

a (send) happens before d (local event after send) on process A: a → d (rule 1)
a → b (rule 2: send-receive)
d and b: a → d and a → b. Is d → b? We don’t know d → b directly. But d happens after a on the same process. b happens after a (message receive after send). But do we have a relation between d and b? a → d and a → b. But do we know d → b? No, d happens after a on A, but we don’t have a message from A to B after d. d and b are either concurrent or… wait.

Actually let me reconsider. a → d (same process). a → b (send-receive). We have a → d and a → b. But no path from d to b. And b happens when it happens — we don’t have b → d either (b is in B, d is in A, no message). So d and b are concurrent.

d → c? We need d → … → c. We have b → c (same process). But if d || b, then d → c is not guaranteed.

Hmm, I was too hasty. Let me reconsider the scenario. The key is: did A send another message after d? The scenario says: A sends a message (a), then performs local computation d (2 seconds before delivery). No second message is sent. So d is not connected to B’s events. Therefore d and b are concurrent, and d and c are concurrent.

Wait, but is d → b possible? d occurs on A after the send. The send is a → B. The message is in transit. d happens before the message is received. But d is on A, b is on B. No message from d to b. So no causal link.

Actually I realize the scenario might be interpreted differently. Let me re-read: “after sending the message, A performs event d (a local computation) 2 seconds before the message is delivered.” So timeline: a (send), then d (local), then b (receive on B). d occurs on A before the message is received on B.

Is d → c? We need a chain. d → … → c. d is on A. Nothing connects d to B (no message from d). So d || b and d || c. The answer is no, d → c is NOT guaranteed.

Wait, but can we say a → d → … and a → b → c? We know a is before both d and b. So a → d and a → b. But from d, is there any path to b or c? No. So d || c.

(d) If timestamps showed c at T=10:00:00.001 and d at T=10:00:00.003, clock-based ordering would say d happened after c. But the happened-before relation says they are concurrent — they have no causal link. If the clocks are not perfectly synchronized (which they never are), the timestamp ordering is meaningless. Even with perfect clocks, the ordering “c at 0.001, d at 0.003” does not mean c → d — causality cannot be established by timestamps alone. The events are on different machines with no message between them, so they are concurrent regardless of what the clocks say.

Solution 4

(a) Yes, the two writes are concurrent. Client 1 writes to R1, and Client 2 writes to R2. Neither client knew about the other’s write — there is no causal chain connecting the two writes. No message, no shared state, no happened-before relation. They are concurrent (w1 || w2).

(b) From R3’s perspective, both values are “correct” in the sense that both writes happened without knowledge of the other. R3 cannot automatically determine which value is the “latest” because there is no causal relationship between the writes. R3 has a conflict: two concurrent values for the same key.

(c) With LWW based on physical timestamps: if Client 1’s clock is 50 seconds ahead of Client 2’s clock, then Client 1’s write of X will have a timestamp 50 seconds “in the future” compared to Client 2’s write of Y. Even if Client 2’s write actually happened later in real time, the timestamp will make it appear older. LWW would select X (the “later” timestamp), even though the correct behavior depends on application semantics, not clock readings.

(d) The happened-before relation tells us that the writes are concurrent — they are causally independent. This means the system cannot automatically resolve the conflict without application help. Timestamps (even with NTP) might assign an arbitrary ordering that could be wrong due to clock drift. The happened-before relation forces the system to acknowledge the conflict and either present both versions to the application or use a deterministic but semantically meaningful tiebreaker (like the application’s own merge logic).