Liniarizability: A Correctness Condition for Concurrent Objects
Details
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.