{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T01:53:14Z","timestamp":1782870794855,"version":"3.54.5"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"European Union\u2019s Horizon 2020 research and innovation program","award":["882500 erc"],"award-info":[{"award-number":["882500 erc"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>Priority queues are used in a wide range of applications, including prioritized online scheduling, discrete event simulation, and greedy algorithms. In parallel settings, classical priority queues often become a severe bottleneck, resulting in low throughput. Consequently, there has been significant interest in concurrent priority queues with relaxed semantics.<\/jats:p>\n                  <jats:p>\n                    In this article, we present the\n                    <jats:italic toggle=\"yes\">MultiQueue<\/jats:italic>\n                    , a highly scalable and flexible relaxed priority queue. Its design is based on leveraging multiple internal priority queues using the seemingly paradoxical technique of \u201cwait-free locking\u201d. The practical performance of the MultiQueue is further enhanced by element buffering, batched operations on the internal queues, and cache-optimized access patterns.\n                  <\/jats:p>\n                  <jats:p>\n                    We evaluate the quality-throughput tradeoff of the MultiQueue against state-of-the-art competitors. The quality is measured using two complementary metrics:\n                    <jats:italic toggle=\"yes\">rank error<\/jats:italic>\n                    (the distance of a deleted element to the best element), and\n                    <jats:italic toggle=\"yes\">delay<\/jats:italic>\n                    (the number of elements with lower priority deleted before a given element). Extensive experiments on both micro-benchmarks and benchmarks based on real-world applications (shortest-path and branch-and-bound) show that the MultiQueue consistently outperforms its competitors. Additionally, its design allows users to easily tune the balance between throughput and quality to meet specific application requirements, and we believe that \u201cwait-free locking\u201d may be of broader interest for converting sequential data structures into high-performance, relaxed concurrent ones.\n                  <\/jats:p>","DOI":"10.1145\/3771738","type":"journal-article","created":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:35:19Z","timestamp":1760441719000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The MultiQueue: A Simple and Fast Relaxed Concurrent Priority Queue"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1990-0899","authenticated-orcid":false,"given":"Marvin","family":"Williams","sequence":"first","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology","place":["Karlsruhe, Germany"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3330-9349","authenticated-orcid":false,"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology","place":["Karlsruhe, Germany"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,12]]},"reference":[{"key":"e_1_3_8_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210411"},{"key":"e_1_3_8_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087810"},{"key":"e_1_3_8_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688523"},{"key":"e_1_3_8_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1925844.1926442"},{"key":"e_1_3_8_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_3_8_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444435X"},{"key":"e_1_3_8_8_2","unstructured":"Timo Bingmann. 2018. TLX: Collection of Sophisticated C++ Data Structures Algorithms and Miscellaneous Helpers. Retrieved from https:\/\/panthema.net\/tlx. retrieved Oct. 7 2020."},{"key":"e_1_3_8_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-43659-3_34"},{"key":"e_1_3_8_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_28"},{"key":"e_1_3_8_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00128644"},{"key":"e_1_3_8_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_3_8_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/165231.165246"},{"key":"e_1_3_8_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3544585.3544600"},{"key":"e_1_3_8_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/08072646X"},{"key":"e_1_3_8_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281106"},{"key":"e_1_3_8_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2019.03.011"},{"key":"e_1_3_8_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2482767.2482789"},{"key":"e_1_3_8_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2480359.2429109"},{"key":"e_1_3_8_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/C2011-0-06993-4"},{"key":"e_1_3_8_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_3_8_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.45"},{"key":"e_1_3_8_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(75)90001-0"},{"key":"e_1_3_8_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174145"},{"key":"e_1_3_8_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03850-6_15"},{"key":"e_1_3_8_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3309206"},{"key":"e_1_3_8_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/98124"},{"key":"e_1_3_8_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0164-1212(98)10034-1"},{"key":"e_1_3_8_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01782776"},{"key":"e_1_3_8_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90022-P"},{"key":"e_1_3_8_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00076-2"},{"key":"e_1_3_8_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0013-1_9"},{"key":"e_1_3_8_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_3_8_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_3_8_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503221.3508432"},{"key":"e_1_3_8_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_3_8_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49543-6_13"},{"key":"e_1_3_8_38_2","doi-asserted-by":"publisher","unstructured":"Hamza Rihani Peter Sanders and Roman Dementiev. 2014. MultiQueues: Simpler Faster and Better Relaxed Concurrent Priority Queues. 10.48550\/arXiv.1411.1209","DOI":"10.48550\/arXiv.1411.1209"},{"key":"e_1_3_8_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755616"},{"key":"e_1_3_8_40_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2019.31"},{"key":"e_1_3_8_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-85665-6_24"},{"key":"e_1_3_8_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-52709-3_23"},{"key":"e_1_3_8_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60321-2_30"},{"key":"e_1_3_8_44_2","doi-asserted-by":"publisher","DOI":"10.5445\/IR\/997"},{"key":"e_1_3_8_45_2","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1429"},{"key":"e_1_3_8_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384249"},{"key":"e_1_3_8_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25209-0"},{"key":"e_1_3_8_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2000.845994"},{"key":"e_1_3_8_49_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.086.013"},{"key":"e_1_3_8_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683268"},{"key":"e_1_3_8_51_2","unstructured":"Stefan Walzer and Marvin Williams. 2024. A Simple yet Exact Analysis of the MultiQueue. arXiv:2410.08714. Retrieved from https:\/\/arxiv.org\/abs\/\/:2410.08714"},{"key":"e_1_3_8_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/512274.512284"},{"key":"e_1_3_8_53_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.81"},{"key":"e_1_3_8_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2858788.2688547"},{"key":"e_1_3_8_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356160"},{"key":"e_1_3_8_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3626183.3659962"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3771738","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T13:15:28Z","timestamp":1765977328000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3771738"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,12]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3771738"],"URL":"https:\/\/doi.org\/10.1145\/3771738","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,12]]},"assertion":[{"value":"2024-08-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-22","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}