For decades every coherence protocol was snooping, directory, or a hybrid of the two. In 2003, Martin et al. proposed a genuine third classification: Token Coherence token coherence Martin et al.'s third protocol class (2003): T tokens per block, exchanged but never created/destroyed; holding ≥1 token permits reads, all T permits writes. Split into a correctness substrate (token conservation = safety; eventual satisfaction = liveness) and a performance protocol (TokenB broadcasts, TokenM multicasts to predicted sharers). Subsumes snooping and directory (MSI ≈ all/some/none of the tokens). defined in Chapter 9 — open in glossary (TC). Two ideas carry it.
Idea one: count tokens, not states
Associate each block with a fixed number of tokens instead of state bits. Cores may exchange tokens — never create or destroy them. Then permissions become arithmetic:
- ≥ 1 token → may read the block.
- All the tokens → may read or write the block.
SWMR falls out of conservation: while a writer holds all T tokens, every other cache provably holds zero. Try it:
One block, 4 tokens — conserved forever
C0
read: 🚫 · write: 🚫 · ≈I
C1
read: 🚫 · write: 🚫 · ≈I
C2
read: 🚫 · write: 🚫 · ≈I
Memory
home of leftover tokens
Memory holds all 4 tokens — no cache may read or write. Σ tokens = 4/4 — never created, never destroyed. All / some / none of the tokens ≈ MSI's M / S / I.
Idea two: split correctness from performance
Correctness substrate correctness substrate Token coherence's safety-and-liveness layer: guarantees tokens are conserved and every request is eventually satisfied, independent of the performance protocol running above it. defined in Chapter 9 — open in glossary
Guarantees safety — tokens are conserved — and liveness — every request is eventually satisfied. This layer is unconditional: it holds no matter what the layer above does.
Performance protocol performance protocol Token coherence's policy layer: what a cache controller does on a miss (TokenB: broadcast; TokenM: multicast to predicted sharers). Free to be aggressive — the correctness substrate catches everything. defined in Chapter 9 — open in glossary
Decides what a cache controller does on a miss — pure policy. TokenB broadcasts every coherence request; TokenM multicasts to a predicted set of sharers. Predictions may be wrong; that costs time, never correctness — the substrate catches everything.
The split is what traditional protocols lack: there, the request-routing machinery is the correctness machinery, and every race must be enumerated in the state tables. TC lets the routing be speculative and unordered because correctness lives elsewhere.
The subsumption claim
Snooping and directory protocols can be reinterpreted as TC instances. An MSI snooping protocol is exactly a TC protocol with a broadcast performance protocol, where the familiar states are token counts:
| MSI state | Token holding |
|---|---|
| M | All of the block’s tokens |
| S | Some (≥1) of the tokens |
| I | None of the tokens |
That is why TC is a third classification rather than merely a third protocol — the older two fit inside it.
Check yourself
1.What replaces state bits in a token coherence protocol, and what are the two permission rules?
2.Token coherence splits into two parts. Which does what?
3.In what sense does token coherence SUBSUME snooping and directory protocols?
4.Why can a TC performance protocol afford to be speculative (e.g., TokenM's multicast to a PREDICTED sharer set)?