Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2508.13399 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Inhaltsangabe:
- 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.