MSL Based Concurrent and Efficient Priority Queue
Priority queues are fundamental in the design of modern multiprocessor algorithms. Priority queues with parallel access are an attractive data structure for applications like prioritized online scheduling, discrete event simulation, or branch-and-bound. This paper proposes an alternative approach: to base the design of concurrent priority queues on the modified skip list data structure. To this end, the authors show that a concurrent modified skip list structure, following a simple set of modifications, provides a concurrent priority queue with a higher level of parallelism. Many algorithms for concurrent priority queues are based on mutual exclusion.