Linearizability is a well-known correctness condition for concurrent objects. It provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point between its invocation and its response. To prove linearizability of an implementation, it is necessary and sufficient to show that all its possible executions are linearizable with respect to some sequential specification. For this purpose, two common methods have been developed, as summarized in the paper "Linearizable Implementations Do Not Suffice for Randomized Distributed Computation [@STOC'2011]".

However, what are typical methods for showing that some implementation is not linearizable? Logically, it is necessary to identify an execution which is not linearizable. But, how to achieve it? Are there some typical examples of demonstrating the non-linearizablity of an implementation in the literature?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.