  Priority queues are abstract data structures which store a set of key/value
pairs and allow efficient access to the item with the minimal (maximal) key.
Such queues are an important element in various areas of computer science such
as algorithmics (i.e. Dijkstra's shortest path algorithm) and operating system
(i.e. priority schedulers).
  The recent trend towards multiprocessor computing requires new
implementations of basic data structures which are able to be used concurrently
and scale well to a large number of threads. In particular, lock-free
structures promise superior scalability by avoiding the use of blocking
synchronization primitives.
  Concurrent priority queues have been extensively researched over the past
decades. In this paper, we discuss three major ideas within the field:
fine-grained locking employs multiple locks to avoid a single bottleneck within
the queue; SkipLists are search structures which use randomization and
therefore do not require elaborate reorganization schemes; and relaxed data
structures trade semantic guarantees for improved scalability.
