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