Linearizability and sequential consistency
Why does linearizability compose when sequential consistency does not?
Linearizability
Definition. Every operation appears to take effect atomically at one instant between its invocation (when the client sent it) and its response (when the client got the answer), and that order respects real time. Equivalently: the system behaves as if there were one copy with atomic operations.
Example: Anika writes balance = 50, and the call returns at 10:00:00.100. Sam starts a read at 10:00:00.200. A linearizable system must return 50 (or something written later), never the old value. Real time matters.
Three properties, each with a consequence.
Its scope is one object. Linearizability on x and on y permits a client to see x updated and y not. That is not a defect. It is the boundary of the specification. Closing that gap is the job of the transactional levels of Transactional isolation and the unification in The unification and its price.
It is local, and that is why it is the universal primitive. Herlihy and Wing proved: a system is linearizable if and only if each of its objects is. If you compose linearizable objects, you get a linearizable system, free. Serializability does not compose. Sequential consistency does not compose. The reason is the elegant part. Linearizability anchors every object's order to the same wall clock, so two objects' orders cannot disagree about which event came first. Sequential consistency has no such anchor, so two orders that are each consistent can be jointly impossible to realize. Real time is what makes composition free.
Here the stronger property is also the cheaper one to reason about. That is exactly why locks, leases, configuration registers and conditional writes are all specified against linearizability and not against something weaker. (A log partition, as its consumers see it, is sequentially consistent: see below.)
It is not a transaction, and it does not need to be. A linearizable compare-and-swap (CAS: "set to new only if the current value is still old") on one key is the maximum atomicity on offer. That is sufficient. The general technique for any multi-object commit is: choose one atomic item, and let it speak for many others. Example: to switch a table from version 7 to version 8, you write all new files first, then flip one pointer from 7 to 8 with a CAS. Whoever reads the pointer sees all of version 8 or none of it. So the strongest single-object model in this article is the primitive from which the multi-object guarantees of Transactional isolation are built. This seam is the reward for refusing to merge the two hierarchies.
Verifying it is hard. Checking whether a general history is linearizable is NP-complete (Gibbons and Korach). That is why practical tools infer a dependency graph and hunt for cycles instead of searching for a valid linearization. This is the approximation rule, moved from the implementation to the verifier.
Linearizability is one-copy-per-object plus real time, and real time is precisely what makes it compose.
Sequential consistency
Definition. There is one total order that all clients agree on, and each client's own operations appear in that order in program order (the order that client issued them). There is no real-time requirement. A read may return an arbitrarily old value, provided everyone's story is mutually consistent.
An honest note on how it is used. Sequential consistency is historically central: Lamport defined it for multiprocessors. In practice it is almost absent as a stated guarantee in data systems. It is strictly weaker than what people usually want from "strong consistency". It is also non-composable, which disqualifies it as a building block. A product that advertises "strong consistency" almost always means linearizable.
Where it matters for a data engineer is the replicated log. A single partition of a log read by many consumers gives sequential consistency: everyone agrees on the order, and nobody gets recency. Consumer 1 may be 3 seconds behind consumer 2, but both read the same sequence. That is the general shape of log-based architecture. A total order is nearly free. Current state is not. This is the reason "read the log" is cheap, while "read the latest" is a different purchase.
The non-composability bites where stream engineers do not expect it. Two ordered topics, composed, are not ordered. Example: topic payments and topic notifications each preserve order. A consumer reading both can still see the notification "payment received" before the payment. "Each of our topics preserves order" says nothing about cross-topic order, and no amount of per-topic correctness fixes it.