Priority queues are fundamental to many multiprocessor applications. Several priority queue algorithms based on skiplists have been proposed, as skiplists allow concurrent accesses to different parts of the data structure in a simple way. However, for priority queues on multiprocessors, an inherent bottleneck is the operation that deletes the minimal element. We present a linearizable, lock-free, concurrent priority queue algorithm, based on skiplists, which minimizes the contention for shared memory that is caused by the sc DeleteMin operation. The main idea is to minimize the number of global updates to shared memory that are performed in one sc DeleteMin. In comparison with other skiplist-based priority queue algorithms, our algorithm achieves a 30 - 80% improvement.
Note: Updated by Technical Report 2018-003, February 2018. See http://www.it.uu.se/research/publications/reports/2018-003.
Available as PDF (331 kB, no cover)
Download BibTeX entry.