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?.