Who needs linearizability?

Problem Detail: 

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?

Asked By : Eduardo Bezerra

Answered By : Massimo Cafaro

Consider the design of concurrent, wait-free (or lock-free, which is weaker) data structures. In this scenario, linearizability is generally required, even though in some cases, performance and scalability can be improved by satisfying a weaker correctness condition. Whether an implementation satisfying such a weak condition is useful is usually application-dependent. In contrast, a linearizable implementation is always usable, because designers can view it as atomic.

Moreover, linearizability is a non-blocking property: a total operation (defined for all object states) is never required to block. Instead, Serializability is not a non-blocking property. Therefore, in order to increase the degree of concurrency, designers of concurrent data structures always rely on linearizability.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13441