Liniarizability: A Correctness Condition for Concurrent Objects

Arun Ramachandran presents Linearizability: A Correctness Condition for Concurrent Objects, by Maurice P. Herlihy and Jeannette M. Wing.

How can we create the illusion that an abstract data type is modified one operation at a time, when in fact we have several concurrent processes? The answer lies in linearizability. It's a correctness condition whereby we can enforce upon the pre-conditions and post-conditions of an abstract data type as if it were operated on by a single sequential process.

Arun has studied concurrent data structures. His research is heavily based upon the work of Herlihy. Let's get his take on this paper.

http://www.cs.toronto.edu/~christoff/files/Linearizability-ACorrectnessConditionForConcurrentObjects.pdf