How to implement lock-free skip list

algorithm lock-free skip-lists
Maciej Piechotka picture Maciej Piechotka · Aug 13, 2010 · Viewed 10.9k times · Source

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

ire_and_curses picture ire_and_curses · Aug 13, 2010

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

Related questions

Circular lock-free buffer

I'm in the process of designing a system which connects to one or more stream of data feeds and do some analysis on the data than trigger events based on the result. In a typical multi-threaded producer/consumer setup, I …

Read More
Is it possible to implement lock free map in C++

We are developing a network application based C/S, we find there are too many locks adding to std::map that the performance of server became poor. I wonder if it is possible to implement a lock-free map, if yes, …

Read More
Lock-free algorithm library

Is there a library that implements lock-free algorithms(queue, linked list and others) written in C (not in C++)? I've taken a look at some libraries like Intel's, but I would like to use generic libraries, at least more generic …

Read More