Who needs linearizability?
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                           Thread 2
A.enqueue(x)                       ...
A.dequeue() (returns y)            ...                       (uh oh!)
B.write(1)                         ...
...                                B.read() (returns 1)
...                                A.enqueue(y)
...                                A.dequeue() (returns x)


Now we'd like our definition of "correctness" to say that this history indicates that either our implementation of A is buggy or our implementation of B is buggy, because there is no serialization that "makes sense" (either Thread 2 needs to read a value from B that hasn't been written yet, or Thread 1 needs to dequeue a value from A that hasn't been enqueued yet.)  So while our original serialization of the transactions on A seemed like a reasonable one, if our implementation allows a history like the second one, then it is  clearly incorrect.

So the constraints that linearization adds are quite reasonable (and necessary even for simple data structures like FIFO queues.)  They are things like: "your implementation should disallow dequeue() a value that won't be enqueued() until some time in the future."
Linearizability is quite easy (and natural) to achieve: just associate a mutex with your object, and each transaction starts by locking and ends by unlocking.  Reasoning about linearizability starts to get tricky when you are trying to implement your atomicity with non-blocking or lock-free or wait-free techniques instead of simple mutexes.

If you are interested in some pointers to the literature, I found the following (although I think the discussion about "real-time" is one of the red-herrings that make linearizabilty more difficult than it needs to be.) https://stackoverflow.com/questions/4179587/difference-between-linearizability-and-serializability