0

Is anyone aware of any lock-free skiplist implimentations and/or research papers that support the rank operation (i.e. find kth element)? Alternatively, is anyone aware of a fundamental reason why such an operation could never work?

Bonus points:

An implimentation that does not assume garbage collection. It has been my experience quite a few research papers ignore memory management.

Support:

For a description of how the rank operation may be done in a regular skiplist: "A Skip List Cookbook" by William Pugh

For one of the better lock-free skiplist descriptions: "Practical lock-freedom" by Keir Fraser

One of the better lock-free skiplist implimentations: http://www.1024cores.net/home/parallel-computing/concurrent-skip-list

tgoodhart
  • 3,111
  • 26
  • 37

1 Answers1

1

Unlike key, value and level, which are local properties of an element in a skiplist and are not affected by operations with other elements, rank of an element, i.e. its position in the list, is a property that changes with insertion and removal of elements with lower rank. Therefore, for a concurrent skiplist, rank of an element is very ephemeral because it may be changed in any moment by a concurrently running operation that inserts or delets a lower rank element.

For example, suppose you do linear search of k-th element through the level 1 list. At the moment you did k steps, concurrent modifications might add or remove any number of prior elements, so the current rank of the element you just find is in fact unknown. Moreover, while the thread is performing the k forward iterations, concurrent changes can be done between its current position and the element that was k-th when it started the search. So what the search ends up with is neither the element with the current rank of k nor the one that has the rank of k when the search started. It's just some random element!

To say it short, for concurrent list, rank of an element is an ill-defined concept and searching by rank is an ill-defined operation. This is the fundamental reason why it could never work, and why implementers should never bother with providing such operation.

Alexey Kukanov
  • 12,479
  • 2
  • 36
  • 55
  • I think I understand what you're saying, but I think you have precisely the same difficulties in updating the "next" pointers of your nodes at each level. For an insert operation, the "next" pointers of the inserted node's predecessors all need to be updated such that the the properties of the skiplist are maintained. Assuming the rank is stored in each node, then the nodes whose "next" pointers need to be updated also need their rank updated.The real difficulty to me seems to be the need for a multi-word compare and swap to update both the rank and "next" pointer at once. – tgoodhart Feb 06 '12 at 17:18
  • If rank is the position of a node in the list, then when a new item is inserted not only its rank should be set but also all ranks of all subsequent nodes in the list should be updated. – Alexey Kukanov Feb 06 '12 at 19:44
  • Of course, I misspoke. What I meant to say was that each node stores the number of nodes that it skips at each level. I believe this number could be updated at the same time as the predecessor's "next" pointer is updated. – tgoodhart Feb 06 '12 at 22:02
  • But, how do you know how many nodes are skipped at each level? Previous nodes to be updated at each level are recorded when the position is searched, but you cannot correctly count how far away the position is from there, because there could be some nodes inserted or deleted in between at the same time. – Alexey Kukanov Feb 06 '12 at 22:39