Why strict serializability doesn’t compose
In their seminal paper introducing linearizability, Herlihy and Wing highlight a key advantage of the model: it is a local property. A system is linearizable if each of its individual objects is linearizable. That locality is what lets engineers build concurrent systems modularly — each linearizable object can be implemented and verified independently, without a centralized scheduler coordinating across objects.
Sequential consistency and its multi-object cousin serializability don’t share that property. But Herlihy and Wing also note, almost in passing, that strict serializability — serializability plus a real-time ordering constraint, so transactions must appear to take effect atomically at some point between invocation and completion — is also nonlocal.
This is surprising. Add real-time constraints to sequential consistency and you get linearizability, which is local. Why doesn’t the same trick work for serializability? Why don’t multi-object transactions with real-time constraints compose? Herlihy and Wing answer with a deceptively simple history, affectionately called H8. It deserves close attention.
The history that breaks composition
Consider two FIFO queues, x and y. Processes A and B enqueue and dequeue numbers. All operations complete immediately, before the next begins. On queue x, A enqueues 1, B enqueues 2, and then B dequeues 1:
process f queue value
B enq x 2
A enq x 1
B deq x 1
This history is sequential — we can reorder it to (A enq x 1) (B enq x 2) (B deq x 1), which is legal for a queue — and since each operation is its own transaction, it is serializable too. But because every operation returns immediately, no reordering is allowed, so it is not strict serializable.
If instead we group each process’s actions into a single transaction, [(A enq x 1)] and [(B enq x 2) (B deq x 1)], the two transactions overlap in time, so a strict serializable system may order them either way. Ordering A before B is legal, so this view of the history is strict serializable.
We can build a parallel history on a separate queue y, swapping A with B and 1 with 2:
process f queue value
A enq y 1
B enq y 2
A deq y 2
Both subhistories are independently sequential, serializable, and strict serializable — given the right choice of transaction boundaries.
Composing the two histories
Now interleave the two histories into one composite history. Each key taken alone remains sequential, serializable, and strict serializable under the chosen transactions:
process f queue value
A enq y 1
B enq x 2
A enq x 1
B enq y 2
A deq y 2
B deq x 1
The composite history, however, is not sequential. For A to dequeue 2 from y, B must have enqueued 2 before A starts — since A’s first action on y is to enqueue 1, B’s enqueue must come first. That means B’s enqueue on x also precedes A’s work on x, so x must begin with 2. But B then cannot dequeue 1: a contradiction.
If each operation is its own transaction, we can salvage serializability by moving conflicting enqueues after dequeues. But that reordering violates real-time constraints, since all operations complete immediately. So the single-operation view is not strict serializable.
The multi-operation transaction view is also unsatisfying in the composite system. It happens to stay strict serializable — the single-enqueue transactions can be moved to the front without violating real time:
(A enq x 1)
(B enq y 2)
(A enq y 1) (A deq y 2)
(B enq x 2) (B deq x 1)
But the composite system lets us form transactions that don’t exist in either subhistory. Suppose each process performs one transaction spanning both queues:
(A enq y 1) (A enq x 1) (A deq y 2)
(B enq x 2) (B enq y 2) (B deq x 1)
There is no legal order. A needs B to enqueue 2 on y before A can dequeue it, and B needs A to enqueue 1 on x first. The two transactions deadlock: neither can precede the other.
Locality is about scope
This construction reveals something subtle about how we talk about locality. Saying “H|x is strict serializable but H is not” is strange, because the transactions in H may not meaningfully exist in H|x. What would it mean to run [(A enq y 1) (A enq x 1)] on x alone? If we restrict attention to transactions that do apply to a single object, those transactions still serialize fine in the full history.
Locality, then, is about the scope of legal operations. For two queues x and y, the composite system’s single-operation space is just the union of operations on each queue, and linearizability handles that cleanly. Multi-operations on one key at a time also remain strict serializable across the composite system. The problem is that transaction space grows multiplicatively, not by union: a transaction on x and another on y can be joined into a single transaction on {x, y}, and nothing in the component guarantees that new transaction will serialize.
One way to view strict serializability is as linearizability plus multi-object transactions. But the reverse is just as instructive: linearizability is strict serializability with transactions restricted to a single object — and that restriction is precisely what buys locality. The object can be as small as a register or as large as an entire database. A key-value store may have each key independently linearizable, but reading two keys “together” in a linearizable way is not something the model provides.
For implementers, locality is a real gift: independent coordinators per object, and the whole still behaves as one linearizable system. But from the user’s side, locality is almost tautological — it just defines which objects you may use together. You cannot glue two strict serializable systems together and expect the composite to be strict serializable, and you likewise cannot set two linearizable systems side by side and use them jointly in a linearizable way. In both cases, you have to examine the full set of transactions on the composite structure and prove no nonlinearizable history exists. Linearizable systems compose in theory, but composing them remains a design task, not a freebie.
