Concurrent Double-Ended Priority Queues
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909742766489600 |
|---|---|
| author | Fatourou, Panagiota Ruppert, Eric Xiradakis, Ioannis |
| author_facet | Fatourou, Panagiota Ruppert, Eric Xiradakis, Ioannis |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_13399 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Concurrent Double-Ended Priority Queues Fatourou, Panagiota Ruppert, Eric Xiradakis, Ioannis Data Structures and Algorithms 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. |
| title | Concurrent Double-Ended Priority Queues |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.13399 |