Coherence and the Modification Order of a Single Location

A memory system that kept every core’s view of a single word identical would still be free to present incompatible views of two words. Each core could see a consistent history of x and a consistent history of y while disagreeing with another core about which of x and y changed first. This is not a paradox and it is not a bug in the coherence protocol; it is a demonstration that coherence and consistency are separate properties, and that a system can have the first without the second.

Coherence is about one location

Coherence is a property of a single memory location. A coherent system gives all cores a common order of writes to that location, and each read returns the value of some write in that order. The order is called the modification order, abbreviated mo, and it is total for each location: every write to x precedes or follows every other write to x, and all cores agree on the arrangement.

Four data-value axioms capture the property, and they are the load-bearing part of every formal model of this kind. All four are stated per location, for accesses issued by a single core.

Write-write coherence. Two writes to x from one core are ordered in mo as the core issued them. A core’s later write never precedes its earlier one.

Read-write coherence. A read of x followed by a write to x from the same core does not read the value of that later write, nor the value of any write after it.

Read-read coherence. A read of x followed by another read of x from the same core returns the same value or a value written later in mo, never one written earlier.

Write-read coherence. A read of x that follows a write to x from the same core returns the value of that write or a value written later in mo. A core sees its own writes, in its own order, and never travels backwards past one.

The axioms do not say that a read returns the most recent write in mo. That stronger property is what sequential consistency adds; coherence alone allows a read to return an older value, provided the core’s own program order is respected. The distinction is exactly the gap that IRIW exploits, and it is why “the hardware is coherent” is a weaker claim than it sounds.

The read-read axiom is the one most often violated by broken designs. A cache that serves a stale line after the core has already seen a newer one produces precisely this failure, and the fix is either a protocol that invalidates before serving or a directory that tracks sharers correctly.

Why the four axioms are not enough

Consider two cores, each writing one location, and two cores reading both in opposite orders:

// Core 0        // Core 1        // Core 2        // Core 3
x = 1;           y = 1;           r0 = y;          r2 = x;
                                  r1 = x;          r3 = y;

The interesting outcome is r0 = 1, r1 = 0 on core 2 together with r2 = 1, r3 = 0 on core 3. Core 2 observed y set before x; core 3 observed x set before y. Under the coherence axioms alone this is permitted, because the modification order of x and the modification order of y are independent: neither order constrains the other. Core 2’s observations fit a history in which y was written first, core 3’s fit one in which x was written first, and each core is internally coherent. The system as a whole has no single order.

This pattern is called IRIW — independent reads of independent writes — and it is the cleanest demonstration that coherence does not imply sequential consistency. A sequentially consistent machine would have one total order over all six operations, and the two readers would have to agree on the relative order of x = 1 and y = 1. A machine with per-location coherence and no cross-location ordering can disagree.

What a coherence protocol actually guarantees

Hardware coherence protocols are usually described in terms of states rather than orders. A MESI-like protocol tracks each cache line as modified, exclusive, shared, or invalid, and the protocol’s job is to ensure that at most one cache holds a line in a writable state and that a write is not acknowledged until all other copies are invalidated.

The mapping from states to the axioms is direct for the single-location properties: exclusive ownership before a write gives write-write order, invalidation before a read gives read-write order, and the directory or snooping network provides a serialisation point that defines mo. The protocol says nothing about ordering between different lines, and it is not designed to. A store to x and a store to y may be acknowledged in either order at their respective home nodes, and a core that reads both may see them in either order.

This is why the phrase “the hardware is cache coherent” answers a much narrower question than “the hardware is sequentially consistent”. Coherence is what makes a single shared counter work with atomic read-modify-write instructions. It is not what makes a two-word publish protocol work without a fence.

Modification order in the language model

The C and C++ memory models import a version of the same idea. Every atomic object has a modification order, and every atomic load reads a value from it. The order is total per object and consistent with the sequenced-before order of writes to that object from any single thread. The model then adds a constraint that connects this per-object order to the happens-before relation: a write that happens before a read must not be later in mo than the write the read takes its value from.

That constraint is what makes a relaxed atomic counter usable. Two threads incrementing a relaxed atomic with fetch-add produce a total order of increments, each returning a distinct previous value, even though there is no happens-before edge between them. The values are not predictable in advance, but the set of values returned across all increments is exactly the set of values the counter passed through, with no duplicates and no gaps.

A common misconception is that relaxed atomics permit a read to return an arbitrary value, including one never written. They do not. Relaxed permits reordering, not incoherence: a relaxed load of an atomic that has only ever held the values 0 and 1 returns 0 or 1. What relaxed gives up is the guarantee about when the value is visible relative to other locations.

The guarantee is per object, and it does not by itself cover a cycle of relaxed accesses across several objects, where each read takes the value the next read’s writer produced. Excluding the execution in which such a cycle manufactures a value that no thread ever wrote needs a causality requirement on top of per-object coherence, which is the construction described in causality and out-of-thin-air values.

Where coherence stops being the interesting question

On a bus-based multiprocessor with a single serialisation point, coherence and a global order come close to coinciding, because every transaction passes through the bus in a single order. On a distributed directory system, each line has its own home node and its own order, and the global order is genuinely absent. The same is true on a chip with multiple cache slices and a network-on-chip: the interconnect provides per-address ordering, not a global order.

The distinction also explains a class of hardware bug that appears when a protocol is stressed. A directory that forwards a request to the wrong sharer, or an invalidation that is dropped, produces a coherence violation — a core seeing a stale value after having seen a newer one — and this is a much more serious failure than a consistency violation. A coherence violation breaks the single-location axioms, which no correct program can tolerate. A consistency violation merely permits an outcome that a correct program must already be prepared for.

The practical reading is that coherence is a necessary condition for any usable shared memory, and consistency is the additional structure that decides which programs need fences. The store-buffer model shows how one architecture adds just enough cross-location order to make most programs work without fences, and the release-acquire rules show how the language exposes cross-location order as an explicit, per-operation property.