Concurrent Double-Ended Priority Queues This research was supported by the Greek Ministry of Education, Religious Affairs and Sports though the HARSH project (project no. Y Π \Pi 3TA - 0560901), which is carried out within the framework of the National Recovery and Resilience Plan - Greece 2.0 - wit

Panagiota Fatourou, Eric Ruppert, Ioannis Xiradakis · 2025

Read Concurrent Double-Ended Priority Queues This research was supported by the Greek Ministry of Education, Religious Affairs and Sports though the HARSH project (project no. Y Π \Pi 3TA - 0560901), which is carried out within the framework of the National Recovery and Resilience Plan - Greece 2.0 - wit by Panagiota Fatourou, Eric Ruppert, Ioannis Xiradakis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-13399.txt.

Introduction

Panagiota Fatourou and two co-authors give the first concurrent design built specifically for a double-ended priority queue, a structure serving both the smallest and largest items. Many threads may insert and extract at once, so the structure must stay consistent under parallel use. Their trick is general: it adds a largest-item extraction to any concurrent queue that already supports insertion and smallest-item extraction.

The construction pairs two single-consumer queues to make a dual-consumer one, keeping operations linearizable and lock-free. A lock-based combining layer then allows many consumers at each end. The authors show the technique at work on a list-based queue. Because the recipe is general, existing concurrent queues can gain a second end without a redesign from scratch.

Catalog record

CREATORPanagiota Fatourou, Eric Ruppert, Ioannis Xiradakis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-13399

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Concurrent Double-Ended Priority Queues This research was supported by the Greek Ministry of Education, Religious Affairs and Sports though the HARSH project (project no. Y Π \Pi 3TA - 0560901), which is carried out within the framework of the National Recovery and Resilience Plan - Greece 2.0 - with funding from the European Union - NextGenerationEU. Panagiota Fatourou, Eric Ruppert, Ioannis Xiradakis Abstract This work provides the first concurrent implementation specifically designed for a double-ended priority queue (DEPQ). We do this by describing a general way to add an ExtractMax operation to any concurrent priority queue that already supports Insert and ExtractMin operations. The construction uses two linearizable single-consumer priority queues to build a linearizable dual-consumer DEPQ (only one process can perform Extract operations at each end). This construction preserves lock-freedom. We then describe how to use a lock-based combining scheme to allow multiple consumers at each end of the DEPQ. To illustrate the technique, we apply it to a list-based priority queue. FORTH ICS, Greece and University of Crete, [email protected]://orcid.org/0000-0002-6265-6895 York University, [email protected]://orcid.org/0000-0001-5613-8701 FORTH ICS, Greece and University of Crete, [email protected]://orcid.org/0009-0009-4974-4901 ccs Theory of computation Concurrent algorithms ccs Theory of computation Data structures design and analysis keywords shared-memory, data structure, double-ended, priority queue, priority deque, heap, skip list, combining † † runningauthor: P. Fatourou, E. Ruppert, I. Xiradakis 1 Introduction Priority queues, which store a set of keys and support an Insert operation that adds a key to the set and an ExtractMin operation that removes and returns the minimum key, have long been recognized as an important data structure for concurrent systems. They have been used in operating systems for job queues and load balancing, heuristic searches [ 39 ] , graph algorithms (e.g., [ 2 , 24 ] ) and for event-driven simulations [ 18 , 26 ] . There are numerous concurrent implementations of priority queues, including [ 3 , 20 , 23 , 25 , 28 , 29 , 30 , 40 , 44 , 45 , 47 ] . In the single-process setting, there has also been much research on the problem of designing a double-ended priority queue (DEPQ), which supports an ExtractMax operation to extract the maximum key, as well as the operation that extracts the minimum key. Applications of DEPQs include external sorting [ 41 ] , coding theory [ 43 ] , and constraint programming [ 10 ] . The problem of implementing a concurrent DEPQ, has not been explored previously. We approach this problem by giving a general transformation to construct a concurrent DEPQ from a concurrent implementation of an ordinary (single-ended) priority queue. We assume a shared-memory system with asynchronous processes and we use linearizability [ 22 ] as the correctness condition for data structure implementations. Many of the single-process DEPQ implementations are based on more complex variants of heaps like min-max pair heaps [ 37 ] , deaps [ 5 ] , min-max heaps [ 1 ] , or others surveyed by Sahni [ 41 ] . Designing a linearizable concurrent version of such a data structure directly would be quite challenging because an insertion or extraction typically requires making multiple changes to the data structure. In a concurrent setting, it is difficult to ensure that all the changes appear to take place atomically. Instead, we take our inspiration from the insight that some of these sequential DEPQ data structures can be viewed as being constructed from a pair of single-ended priority queues [ 8 ] . Even using this approach, an update operation on the DEPQ often requires two operations on the underlying priority queues to appear atomic. Our construction uses a lightweight synchronization mechanism to achieve this. Designing simple mechanisms to build complex concurrent data structures in a modular way is an important goal and can be quite challenging. Indeed, in spite of the simplicity of our basic construction, the argument that it produces a linearizable DEPQ is subtle. Our general construction in Section 3 shows how to use two linearizable, concurrent priority queues to construct a linearizable dual-consumer DEPQ, which allows only one process to perform ExtractMin and one process to perform ExtractMax at a time. The construction works even if the priority queues used are single-consumer , meaning that only one process at a time may perform ExtractMin operations. Our DEPQ relies on the synchronization mechanisms of the single-ended priority queues to coordinate the actions of insertions and extractions within each priority queue, but we add a new layer of synchronization between the two processes that perform ExtractMin and ExtractMax operations. Our construction preserves the property of linearizability. It also preserves the lock-free progress property: if the priority queue is lock-free, then so is the resulting DEPQ. Some concurrent priority queue data structures (for example, those based on concurrent skip lists) could be augmented to support deletion of an arbitrary element, given a reference to the location of the element in the data structure. In this case, we prove time and space bounds for our DEPQ, depending on the bounds for the (single-ended) priority queue. We describe how to adapt our dual-consumer DEPQ to produce a linearizable DEPQ that can handle multiple concurrent Extract operations at each end in Section 4 . A simple solution is to add two locks: one that must be acquired by ExtractMin operations and one for ExtractMax operations. To reduce the overhead of having each Extract operation acquire and release a lock, we show how to use the combining technique [ 15 , 20 ] . This is particularly appropriate for Extract operations on a priority queue because all Extract operations attempt to remove an item from the same location in the data structure, causing a hotspot of contention [ 16 , 20 ] . At a high level, each process that acquires the lock for one end of the DEPQ can perform a whole batch of Extract operations, lowering the overhead for synchronization. Insertions can proceed concurrently with one another and with Extract operations. Our technique is general enough to be applied to any concurrent priority queue. For ease of illustration, we provide an example in Section 5 that applies our technique (including combining) to a simple list-based priority queue. Since a single-consumer priority queue suffices for our construction, this enables us to optimize the list-based priority queue using the simplifying assumption that only one process can perform ExtractMin operations on it at a time. We also use this example to illustrate how the code generated by our generic construction can be simplified when it is applied to a particular priority queue implementation. For example, we save space by sharing nodes between the two lists that represent the two priority queues. We believe techniques similar to the one introduced here could be applicable to other settings where a new data structure can be built by combining two simpler data structures. For example, a binary search tree threaded with additional pointers to predecessors and successors of each node can be thought of as a binary search tree and a doubly-linked list that share the same nodes. Building concurrent implementations of the two components separately is easier than trying to design one that maintains consistency among all pointers of both

Read the complete text