JEPSEN

Strict Serializability

Informally, strict serializability (a.k.a. PL-SS, Strict 1SR, Strong 1SR) means that operations appear to have occurred in some order, consistent with the real-time ordering of those operations; e.g. if operation A completes before operation B begins, then A should appear to precede B in the serialization order.

Strict serializability is a transactional model: operations (usually termed “transactions”) can involve several primitive operations performed in order. Strict serializability guarantees that operations take place atomically: a transaction’s sub-operations do not appear to interleave with sub-operations from other transactions.

It is also a multi-object property: operations can act on multiple objects in the system. Indeed, strict serializability applies not only to the particular objects involved in a transaction, but to the system as a whole–operations may act on predicates, like “the set of all cats”.

Strict serializability cannot be totally or sticky available; in the event of a network partition, some or all nodes will be unable to make progress.

Strict serializability implies serializability and linearizability. You can think of strict serializability as serializability’s total order of transactional multi-object operations, plus linearizability’s real-time constraints. Alternatively, you can think of a strict serializable database as a linearizable object in which the object’s state is the entire database.

Formally

When Herlihy and Wing introduced linearizability, they defined strict serializability in terms of a serializable system which is compatible with real-time order.

A history is serializable if it is equivalent to one in which transactions appear to execute sequentially, i.e., without interleaving. A (partial) precedence order can be defined on non-overlapping pairs of transactions in the obvious way. A history is strictly serializable if the transactions’ order in the sequential history is compatible with their precedence order.

“The obvious way” means that transaction A precedes transaction B if A completes before B begins; this is the real-time constraint from linearizability.