Code and SPIN model for the algorithm described in the article with the same name by Jonatan Lindén and Bengt Jonsson, are available here. The article was presented at the International Conference on Principles of Distributed Systems, Nice, France, 2013. An extended version of the conference paper is available here.
Abstract
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 DeleteMin operation. The main idea is to minimize the number of global updates to shared memory that are performed in one DeleteMin. In comparison with other skiplist-based priority queue algorithms, our algorithm achieves a 30 – 80% improvement.