How to implement lock-free skip list

Question

I need to implement a lock-free skip list. I tried to look for papers. Unfortunatly all I found was lock-free single linked lists (in many flavors). However how to implement lock-free skip list?

Answer 1

Lock-free skip lists are described in the book The Art of Multiprocessor Programming, and the technical report Practical lock-freedom, which is based on a PhD thesis on the subject. The skip list discussion begins on page 53. An example implementation, based on these sources, is included in this google code project.

There are related discussions, links to literature and implementations (not necessarily lock-free) in the SO questions Skip List vs. Binary Tree, and Skip Lists - ever used them?.

Answer 2

This paper presents a lock-free and wait-free skip list. It's straightforward to implement - I implemented this a few weeks ago as part of the Intel Threading Challenge 2010 (see the SkipList tab halfway down the page.)

Java includes an implementation of a concurrent skip list, java.util.concurrent.ConcurrentSkipListMap.