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?

Estipulate

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

Psychopathist

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.

Alberto

Is your code available anywhere (it's not obvious to me on the Intel site as to where to get it.) – Jos

The algorithm in the paper referred to is neither lock-free nor wait-free. – Meenen

Jonatan, I just took a quick glimpse at the paper again and you may be right. I read so many papers at the time I must have got my wires crossed. That was over two years ago, so I no longer recall which paper I had in mind when thinking of the lock and wait free list. – Alberto

@mdma: In your implementation, for the insert operation, there doesn't seem to be a linearization point, compared to the paper by Shavit et al. Can this cause any problems for a concurrent read operation? – Loreleilorelie