What define concurrent operations on an object to be linearizable is if they are equivalent to sequential computation, where operation on an object are executed by a single process one at a time. Linearizability allow a high degree of concurrency on an object by exploiting the semantics of abstract data types. It permit this by allowing programmers to specify concurrent objects using standard verification techniques. For example what can be acceptable for a concurrent history of a queue can’t be acceptable for a stack. Therefore, it is necessary to take into account object’s specifications.
The difference between linearizability and other consistency models such as serializability, is that former is consider a local property when every object in the system is linearizable. However, serializability deal with a group of objects and operations and only care about their order. Another important property of linearizability, is that its nonblocking which means all concurrent operation on a single object will be instantaneous.
One of things I’m struggling to understand is the nonblocking property of linearizability. From what I understood from the paper and other online blogs (I could be wrong) is that linearizability achieve order of operation by their completion not their invocation, but this implies that some operation can’t be instantaneously and therefore will have to blocked. Of course here I’m assuming the two terms relate to each other which I mentioned in the previous paragraph. For example, the paper mentioned linearizability as a form of strict serializability. However, strict serializability can’t be achieved without using some agreement protocols like two phase commit. This implies that some operations can’t be instantaneously and therefore will have to block. In fairness the paper did mention that each one of them is appropriate for different problem domains.
Reading this paper really helped review different consistency models and how different models are more applicable to certain domains. For example, linearizability is more applicable to a domain where availability is important and serializability is more applicable to a domain where consistency on different objects is more important like database transactions. I’m interested to know what domain would benefit from strict serializability over the other models. Also, would achieving strict serializability require more expensive coordination than serializability or would it be the same.