sorted atomic linked list algorithm (priority queue)

Question

Can somebody point me towards an algorithm for a sorted thread-safe atomic (lock-free) linked list/priority queue? I'm aware of how to do just a linked list itself, but now I need one that is sorted. I'm unsure if this is minor change or significant redesign compared to an unsorted list, thus would like to see an existing algorithm before I make my own.

It needn't actually be a list (or technically sorted), but behaves like a priority queue with these properties:

• lowest element is the one with the minimum integer field value
• access to lowest element in constant time
• modification via atomic operations only (no locks)
• insertion/removal in linear time

The contents will likely be pointers to structures. The integer field to sort is one of the members of that structure.

This is for a C++ program, but I don't need code examples, an algorithm description is fine. Algorithms which come close, but not perfect, are also appreciated.

Answer 1

Look at this: "Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems". Googling will give you more links for sure.