2026-09-13T04:32:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24852 2026-09-05T18:59:19Z ddc:004 open_access

PIPQ: Strict Insert-Optimized Concurrent Priority Queue Grimes, Olivia Hassan, Ahmed Fatourou, Panagiota Palmieri, Roberto Priority Queue Concurrent Data Structures Synchronization This paper presents PIPQ, a strict and linearizable concurrent priority queue whose design differs from existing solutions in literature because it focuses on enabling parallelism of insert operations as opposed to accelerating delete-min operations, as traditionally done. In a nutshell, PIPQ’s structure includes two levels: the worker level and the leader level. The worker level provides per-thread data structures enabling fast and parallel insertions. The leader level contains the highest priority elements in the priority queue and can thus serve delete-min operations. Our evaluation, which includes an exploration of different data access patterns, operation mixes, runtime settings, and an integration into a graph-based application, shows that PIPQ outperforms competitors in a variety of cases, especially with insert-dominant workloads. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Olivia Grimes and Ahmed Hassan and Panagiota Fatourou and Roberto Palmieri 2025 Is Part Of LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2025.35 urn:nbn:de:0030-drops-248525 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.35 eng https://creativecommons.org/licenses/by/4.0/legalcode