A Simple Optimistic Skiplist Algorithm

Because of their highly distributed nature and the lack of global rebalancing, skiplists are becoming an increasingly important logarithmic search structure for concurrent applications. Unfortunately, none of the concurrent skiplist implementations in the literature, whether lock-based or lock-free, have been proven correct. Moreover, the complex structure of these algorithms, most likely the reason for a lack of a proof, is a barrier to software designers that wish to extend and modify the algorithms or base new structures on them.

This paper proposes a simple new lock-based concurrent skiplist algorithm. Unlike other concurrent skiplist algorithms, this algorithm preserves the skiplist properties at all times, which facilitates reasoning about its correctness. Though it is lock-based, the algorithm is highly scalable due to a novel use of optimistic synchronization: it searches without acquiring locks, requiring only a short lock-based validation before adding or removing nodes. Experimental evidence shows that this simpler algorithm performs as well as the best previously known lock-free algorithm under the most common search patterns.