{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T18:34:39Z","timestamp":1771958079142,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T00:00:00Z","timestamp":1710115200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>In the last two decades, great attention has been devoted to the design of non-blocking and linearizable data structures, which enable exploiting the scaled-up degree of parallelism in off-the-shelf shared-memory multi-core machines. In this context, priority queues are highly challenging. Indeed, concurrent attempts to extract the highest-priority item are prone to create detrimental thread conflicts that lead to abort\/retry of the operations. In this article, we present the first priority queue that jointly provides: (i) lock-freedom and linearizability; (ii)\u00a0conflict resiliency against concurrent extractions; (iii)\u00a0adaptiveness to different contention profiles; and (iv)\u00a0amortized constant-time access for both insertions and extractions. Beyond presenting our solution, we also provide proof of its correctness based on an assertional approach. Also, we present an experimental study on a 64-CPU machine, showing that our proposal provides performance improvements over state-of-the-art non-blocking priority queues.<\/jats:p>","DOI":"10.1145\/3635163","type":"journal-article","created":{"date-parts":[[2023,12,6]],"date-time":"2023-12-06T12:24:02Z","timestamp":1701865442000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["A Conflict-Resilient Lock-Free Linearizable Calendar Queue"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7589-9274","authenticated-orcid":false,"given":"Romolo","family":"Marotta","sequence":"first","affiliation":[{"name":"University of Rome Tor Vergata, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8727-1329","authenticated-orcid":false,"given":"Mauro","family":"Ianni","sequence":"additional","affiliation":[{"name":"Lockless S.r.l., Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0179-9868","authenticated-orcid":false,"given":"Alessandro","family":"Pellegrini","sequence":"additional","affiliation":[{"name":"University of Rome Tor Vergata, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5616-7980","authenticated-orcid":false,"given":"Francesco","family":"Quaglia","sequence":"additional","affiliation":[{"name":"University of Rome Tor Vergata, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,11]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688523"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/SPDP.1990.143500"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2017.16"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/63039.63045"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-11(1:20)2015"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-27308-2_38"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2013.42"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2018.18"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1233341.1233413"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3876"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2775051.2676963"},{"key":"e_1_3_2_13_2","volume-title":"Practical lock-freedom","author":"Fraser Keir","year":"2004","unstructured":"Keir Fraser. 2004. Practical lock-freedom. Ph.D. Dissertation. University of Cambridge."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2601381.2601393"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/645958.676105"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2769458.2769462"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/1734069"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25873-2_22"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3200921.3200931"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/48022.48024"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/978-3-319-03850-6_15","volume-title":"Principles of Distributed Systems","author":"Lind\u00e9n Jonatan","year":"2013","unstructured":"Jonatan Lind\u00e9n and Bengt Jonsson. 2013. A skiplist-based concurrent priority queue with minimal memory contention. In Principles of Distributed Systems, Roberto Baldoni, Nicolas Nisse, and Maarten van Steen (Eds.). Springer International Publishing, Cham, Germany, 206\u2013220."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/DS-RT.2016.33"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/3021426.3021434"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3064911.3064926"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.simpat.2015.01.009"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3265750"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/249204.249205"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2015.45"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2000.845994"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.12.005"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1103323.1103324"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3635163","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3635163","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:49:06Z","timestamp":1750286946000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3635163"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,11]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3635163"],"URL":"https:\/\/doi.org\/10.1145\/3635163","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,11]]},"assertion":[{"value":"2022-05-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-28","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}