Memory Consistency Models

Category of Access

A memory access is either private or shared.

Shared accesses can be divided into competing and non-competing. A pair of accesses are competing if they access the same location, not ordered and at least one of them is a write.

A competing access can be either sync or async. Sync accesses are used to enforce order.

Sync accesses can be divided into acquire or release accesses. Acquire access is always associated with a read sync, while Release access is always a write sync.

Now, we can discuss about some common MCMs. We’ll use $A\to B$ to represent that model $A$ is more strict than $B$ . Also, we use $\texttt{Op}(\ell)v$ to describe an operation, where $\texttt{Op}$ is either $R$ ead or $W$ rite, $\ell$ stands for the accessed $\ell$ ocation and $v$ for the transmitted $v$ alue. Note that $R(\ell)v$ represents the completion time of a read while $W(\ell)v$ represents the issue time of a write.

An overview of strictness of MCMs can be described as

graph TB;
A[Atomic Consistency] --> B[Sequential Consistency]
B --> C[Causal Consistency]
B --> D[Processor Consistency]
C --> E[PRAM]
D --> E
D --> F[Cache Consistency]
F --> G[Slow Memory]
E --> G

In short, MCMs can be splitted into strong or weak consistency:

strong consistency means that, after update completes, all subsequent accesses will return the updates value.
weak consistency, in contrast, after update completes, accesses do not necessarily return the updated value; some prerequisites must be satisfied beforehand.
- eventual consistency is a sub-category of weak consistency. If no more updates are made to an object, then eventually all reads will return the latest value.

Atomic Consistency (AC)

AKA strict linearizability. In short, it guarantees that if operation A completes before B begins, then B must read the updated value written by A. It can be regarded in a way of operation intervals as dividing time into non-overlapping consecutive slots.

Sequential Consistency (SC)

A memory system is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

The definition has 2 levels of meanings:

Program order is preserved. Each thread’s own operations must happen in the order they appear in its code.
Global atomicity. Operations of different threads may be interleaved.

The execution is similar to “always take one operation from the front of some thread’s OP queue”. If all final results can be obtained in this way, then this memory system is sequentially consistent.

Causal Consistency (CC)

A memory is causally consistent if all processors agree on the order of causally related events. Causally unrelated events (concurrent events) can be observed in different orders.

Implementing Causal Consistency

The core of CC is to keep track of causally related writes. This is usually done with locks. Besides locks, we may update values concurrently, and later try to “merge” them.