Time Causality · Happened Before Relation

Key Question

How does sending a message create a causal link between two machines?

Deep Dive

The first rule of happened-before ordered events within a single process. But distributed systems involve multiple processes that communicate. Information flows between them through messages. The second rule of the happened-before relation captures this: If a is the event of sending a message, and b is the event of receiving that same message, then a → b.

This is intuitive: you cannot receive a message before it is sent. The act of sending is causally prior to the act of receiving. The message carries information from the sender to the receiver, and anything the receiver does after processing the message is causally influenced by the sender.

Let us walk through a concrete space-time diagram:

Process P1              Process P2
    |                       |
    a1 (local)              |
    |                       |
    a2 (send msg) ─────────→ b1 (receive msg)
    |                       |
    a3 (local)              b2 (local, after processing msg)
    |                       |
                            b3 (local)

Here is what we can say about the happened-before relations:

Within P1: a1 → a2 → a3 (same process ordering)
Within P2: b1 → b2 → b3 (same process ordering)
a2 → b1 (send before receive — rule 2)
a1 → b2: a1 → a2 (rule 1) and a2 → b1 (rule 2) and b1 → b2 (rule 1), so by transitivity (rule 3, which we will cover in the next lesson) a1 → b2.
a3 → b3? a3 happens after the send (a2 → a3) but nothing ties a3 to P2 events. a3 is causally independent of P2’s later events — unless P2 sends a message back.

The critical insight: a2 created a causal connection between P1 and P2. Before the message, the two processes were causally isolated. After the message, the receiver’s subsequent events are causally dependent on the sender. This is how causality propagates across machine boundaries.

Consider a concrete scenario: a social media post. You (P1) type a comment (a1), then press Post (a2). The server (P2) receives your post (b1), stores it (b2), and notifies your followers (b3). Your act of pressing Post is causally prior to every subsequent event. If the server processed the notification before receiving your post, that would violate causality — and indeed, that would be a bug.

The power of message causality is that it works regardless of network delay. Suppose the message from P1 takes 500 ms to reach P2 (congested network). The relation a2 → b1 still holds. Suppose it takes 1 ms. Still holds. Unlike physical time, the happened-before relation is insensitive to the duration of transmission. The only thing that matters is the logical sequence: send, then receive.

This is why the happened-before relation forms a more reliable foundation for reasoning about distributed systems than any clock-based approach. It captures the actual flow of information and influence, not the arbitrary readings of unsynchronized oscillators.

Check Your Understanding

In the space-time diagram above, can we say whether a3 happened before b3? Why or why not?
If a message takes 10 seconds to travel from P1 to P2, does a2 → b1 still hold? What if the message takes 1 millisecond?
Why is the happened-before relation more reliable than timestamps for establishing causality?

The “So What?”

Message causality is the foundation of causal broadcast, causal consistency in databases, and conflict detection in distributed storage. When you see a system that guarantees “causal ordering” of messages, it is enforcing exactly this rule: if message M1 happened before M2, then M2 will not be delivered to any process before M1. Understanding that messages create causal links helps you reason about what information a node has “seen” and what it cannot have seen yet.

✏️ 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).