A Skiplist-based Concurrent Priority Queue with Minimal Memory Contention
2013 (English)In: OPODIS 2013: 17th International Conference On Principles Of DIstributed Systems / [ed] Roberto Baldoni, Nicolas Nisse, Maarten van Steen, Berlin: Springer Berlin/Heidelberg, 2013, 206-220 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
Berlin: Springer Berlin/Heidelberg, 2013. 206-220 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 8304
Concurrent Data Structures, Priority Queue, Lock-free, Non- blocking, Skiplist
Research subject Computer Science
IdentifiersURN: urn:nbn:se:uu:diva-213426DOI: 10.1007/978-3-319-03850-6_15OAI: oai:DiVA.org:uu-213426DiVA: diva2:682052
OPODIS 2013: 17th International Conference On Principles Of DIstributed Systems, Nice, France,December 16-18th, 2013