Concurrent Lock-Free Unbounded Priority Queue with Mutable Priorities
Document Type
Conference Proceeding
Publication Date
10-20-2018
Publication Title
International Symposium on Stabilizing, Safety, and Security of Distributed Systems
Volume
2018
First page number:
365
Last page number:
380
Abstract
The priority queue with DELETEMIN and INSERT operations is a classical interface for ordering items associated with priorities. Some important algorithms, such as Dijkstra’s single-source-shortest-path, Adaptive Huffman Trees, etc. also require changing the priorities of items in the runtime. Existing lock-free priority queues do not directly support the dynamic mutation of the priorities. This paper presents the first concurrent lock-free unbounded binary heap that implements a priority queue with mutable priorities. The operations are provably linearizable. We also designed an optimized version of the algorithm by combining the concurrent operations that substantially improves the performance. For experimental evaluation, we implemented the algorithm in both C/C++ and Java. A number of micro-benchmarks show that our algorithm performs well in comparison to existing implementations.
Disciplines
Computer Sciences
Language
English
Repository Citation
Walulya, I.,
Chetterjee, B.,
Datta, A. K.,
Niyolia, R.,
Tsigas, P.
(2018).
Concurrent Lock-Free Unbounded Priority Queue with Mutable Priorities.
International Symposium on Stabilizing, Safety, and Security of Distributed Systems, 2018
365-380.
http://dx.doi.org/10.1007/978-3-030-03232-6_24