Why discard another cache's copy instead of sending it the new value? Both invalidation and update policies address replicated data, but they make different promises about when a retained copy can serve a read. This course uses invalidation: remove independent readers, grant exclusive permission, then let the writer perform local stores. Simply sending new bits does not revoke old read permission.
Prerequisites: SWMR and the data-value invariant. Begin at a settled read epoch: both caches are S / 0, H = S{C0,C1}, memory = 0. The earlier reads have completed; this is a snapshot, not an omitted concurrent transaction.
C0 already has the correct data but lacks permission to store. It sends GetM and waits in SM^D (was S, wants M, waiting for Data): loads hit, stores stall. H invalidates C1, collects C1's Inv-Ack, and only then sends Data with M permission and no refill (no bytes need to be resent, since C0 already holds 0). The full step-by-step trace with every state and value lives in Epochs and Serialization; this summary keeps only the boundary.
Step | What happens | C0 | C1 |
|---|---|---|---|
1. GetM(X) | C0 asks H for M permission | SM^D / 0, loads hit, stores stall | S / 0 |
2. Inv(X) | H revokes C1's read permission | SM^D / 0 | I / - |
3. Inv-Ack(X) | H observes revocation, acks 1/1 | SM^D / 0 | I / - |
4. Data(M permission, no refill) | H grants write permission | M / 0 | I / - |
L. Local store X=1 | Now permitted | M / 1 | I / - |
The course model collects Inv-Acks at H, so an upgrade with sharers takes four serial legs (GetM, Inv, Inv-Ack, Data). The Primer's design instead sends the acks straight to the requester and puts the ack count in Data, three legs; C0 then waits until it has Data and every ack. Both are legal; what neither may do is let C0 store before C1's revocation is known.
Question | Invalidate policy used here | Update policy, conceptual comparison |
|---|---|---|
Other cached copies | Lose usable permission before exclusive writes | May be retained under explicit update-ordering rules |
Next read at C1 | Needs a new permission and data transaction | May use a retained copy once the policy makes it current |
Repeated local stores at C0 | Can stay local while exclusive permission lasts | Propagating new values can add traffic even without remote reads |
Safety obligation | Exclude other usable copies before a writable grant | Define ordered writes and when retained copies may satisfy reads |
This is a policy comparison, not an update-protocol trace. We introduce no update opcode or new stable state. A retained reader cannot simply coexist with unrestricted M or E permission; an update design needs its own access and serialization rules. Neither policy wins without a workload: repeated writes with no remote reuse favour suppressing propagation, while prompt remote reuse may make retained copies useful. See the Primer, Chapter 6, invalidate versus update for the design distinction.
No. C0 has not received writable Data, and H still lacks the completion evidence. The controller cannot base a grant on an unobserved remote state. Step 3 clears the dependency, step 4 conveys permission, L performs the store. H must wait here only because the acks go to H; with an ack count in Data and acks to the requester (the Primer's design), H could send Data at once and C0 would wait in SM^AD until all acks arrive.