Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2508.13399 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |