Who needs linearizability?

I've been reading about the differences between serializability and linearizability, which are both consistency criteria for replicated systems such as replicated databases. However, I don't know in which cases linearizability would be needed, even though it's stronger than serializability.

Could you come up with scenarios where such strong property would actually be necessary?

I've reread Herlihy and Wing many times over the past 15 years. It is a very difficult read. And that is unfortunate, because while there are some subtleties around the edges the basic idea is actually quite reasonable.

In short: linearizability is like serializability, but with the additional requirement that the serialization respect additional ordering constraints between the transactions. The goal is to allow you to reason rigorously about an individual atomic data structure rather than having to reason about the entire system all at once.

Linearizability is also easy to achieve: just associate a mutex with the object you want to linearize. Every transaction on that object starts by locking the mutex and finishes by unlocking the mutex.

Here are the definitions I'll use:


A system is serializabile if given a set of transactions over a set of data, any result of executing the transactions is the same as if the transactions were executed in some sequential order, and the operations within each transaction are contained within their transaction in the order specified by the transaction's code.

Serializability disallows the appearance of interleaving of operations between different transactions, and requires that the chosen ordering of transactions satisfies causality (if transaction A writes the value x, and transaction B reads the value x that A wrote, then transaction A must precede transaction B in the chosen serial order.) But it says nothing about any other constraints on the ordering of transactions (in particular, it says nothing about processes and the order in which processes perceive events.)

There is another related idea that does add in the constraints about the order in which processes executed operations (but doesn't talk about transactions only individual read/write operations):


A system is sequentially consistent if the result of any execution is the same as if the operations of all the processes were executed in some sequential order, and the operations of each individual process appear in this sequence in the order specified by its program. (Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE T Comp 28:9(690-691), 1979).

Implicit in the definition of sequential consistency is that we only accept sequential orders where for each memory location (object) the induced sequential order of operations obeys the rule that the value returned by each read operation to location x must be the same value that was written by the immediately preceding write operation to location x in the sequential order.

Linearizability has the good intentions of (a) combining together the notion of transactions (from serialization) with the notion that processes expect the operations they issue to complete in order (from sequential consistency) and (b) narrowing the correctness criteria to talk about each object in isolation, rather than forcing you to reason about the system as a whole. (I would like to be able to say that my object's implementation is correct even in a system where there are other objects that are not linearizable.)
I believe Herlihy and Wing may have been trying to rigorously define a monitor.

Part (a) is "easy": A sequential consistency-like requirement would be that the transactions on the object issued by each process appear in the resulting sequence in the order specified by the program. A serialization-like requirement would be that the transactions on the object are all mutually exclusive (can be serialized).

The complexity comes from objective (b) (being able to talk about each object independently of all the others).

In a system with multiple objects it is possible that operations on object B place constraints on the order in which we believe operations were invoked on object A. If we are looking at the entire system history then we will be constrained to certain sequential orders, and will need to reject others. But we wanted a correctness criteria that we could use in isolation (reasoning just about what happens to object A without appealing to the global system history).

For example: suppose I am trying to argue about the correctness of object A, which is a queue, suppose object B is a memory location, and suppose I have the following execution histories: Thread 1: A.enqueue(x), A.dequeue() (returns y). Thread 2: A.enqueue(y), A.dequeue() (returns x). Is there an interleaving of events that would allow this implementation of the queue to be correct? Yes:

Thread 1                           Thread 2
A.enqueue(x)                       ...
...                                A.enqueue(y)
...                                A.dequeue() (returns x)
A.dequeue(y) (returns y)           ...

But now what if the history (including object B) is: B starts with value 0. Thread 1: A.enqueue(x), A.dequeue() (returns y), B.write(1). Thread 2: B.read() (returns 1) A.enqueue(y), A.dequeue() (returns x).

```
Thread 1

StackExchange Computer Science Q#13441, answer score: 13