A Sound and Complete Proof Technique for Linearizability of Concurrent Data Structures

Efficient implementations of data structures such as queues, stacks or hash-tables allow for concurrent access by many processes at the same time. To increase concurrency, these algorithms often co...