{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T10:23:46Z","timestamp":1782987826647,"version":"3.54.5"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"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,12,31]]},"abstract":"<jats:p>A lock is a mechanism to guarantee mutual exclusion with eventual progress, i.e., some degree of fairness. First-come-first-served (FCFS) progress is perfectly fair. FCFS progress can be offered by a locking algorithm or added by wrapping a non-FCFS lock with a separate FCFS algorithm. A new separate FCFS algorithm is presented that creates FCFS progress by wrapping a lock\u2019s entry protocol (acquire). The algorithm addresses an important safety issue in locking, called barging, where arriving threads proceed before waiting threads or waiting threads are serviced with some bias. Barging increases latency for waiting threads and is non-intuitive to concurrent programmers, even though it is inherent to non-deterministic concurrent execution.<\/jats:p>\n          <jats:p>A correctness proof is presented for the new FCFS algorithm and verified with the proof assistant PVS. Experimental tests are performed to ensure the presented wrapper provides FCFS progress when used to transform non-FCFS software and hardware locks. The performance of the non-FCFS and transformed FCFS counterparts is compared and contrasted with locks using inherent FCFS progress. The results show the FCFS transforms are performant for most algorithms, providing an additional tool for application developers to achieve correctness without a significant global performance reduction.<\/jats:p>","DOI":"10.1145\/3669989","type":"journal-article","created":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T10:59:57Z","timestamp":1720436397000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["First-Come-First-Served as a Separate Principle"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1413-4320","authenticated-orcid":false,"given":"Wim H.","family":"Hesselink","sequence":"first","affiliation":[{"name":"University of Groningen, Groningen, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3747-9281","authenticated-orcid":false,"given":"Peter A.","family":"Buhr","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-9077-2486","authenticated-orcid":false,"given":"Colby A.","family":"Parsons","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,11,8]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.80120"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.03.009"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3263"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3659"},{"key":"e_1_3_3_6_2","article-title":"Locking Micro-Benchmarks","author":"Buhr Peter A.","year":"2023","unstructured":"Peter A. Buhr, David Dice, and Wim H. Hesselink. 2023. Locking Micro-Benchmarks. Retrieved from https:\/\/github.com\/pabuhr\/concurrent-locking. [Accessed July 2024].","journal-title":"R"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1981.42"},{"key":"e_1_3_3_8_2","first-page":"833","volume-title":"Proceedings of the 18th Annual Allerton Conference on Communications, Control and Computing, Monticello, Illinois, USA","author":"Burns James E.","year":"1980","unstructured":"James E. Burns and Nancy A. Lynch. 1980. Mutual exclusion using indivisible reads and writes. In Proceedings of the 18th Annual Allerton Conference on Communications, Control and Computing, Monticello, Illinois, USA. 833\u2013842. Retrieved from http:\/\/groups.csail.mit.edu\/tds\/papers\/Lynch\/allertonconf.pdf"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0096-2"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303984"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-67087-0_13"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90100-9"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-013-0178-2"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2015.01.001"},{"key":"e_1_3_3_15_2","unstructured":"W. H. Hesselink. 2023. PVS Proof Scripts for FCFS. (2023). Retrieved from http:\/\/wimhesselink.nl\/mechver\/fcfs. [Accessed July 2024]."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3584696"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/361082.361093"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/5383.5384"},{"key":"e_1_3_3_19_2","doi-asserted-by":"crossref","unstructured":"Leslie Lamport. 1987. A fast mutual exclusion algorithm. ACM Transactions on Computer Systems 5 1 (Jan.1987) 1\u201311.","DOI":"10.1145\/7351.7352"},{"key":"e_1_3_3_20_2","article-title":"QSpinLock: Introducing a 4-byte Queue Spinlock Implementation","author":"Long Waiman","year":"2013","unstructured":"Waiman Long. 2013. QSpinLock: Introducing a 4-byte Queue Spinlock Implementation. Retrieved from https:\/\/lwn.net\/Articles\/561775. [Accessed July 2024].","journal-title":"R"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115370"},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","unstructured":"John M. Mellor-Crummey and Michael L. Scott. 1991. Algorithm for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems 9 1(1991) 21\u201365.","DOI":"10.1145\/103727.103729"},{"key":"e_1_3_3_23_2","volume-title":"PVS Language Reference Version 7.1","author":"Owre S.","year":"2020","unstructured":"S. Owre, N. Shankar, J. M. Rushby, and D. W. J. Stringer-Calvert. 2020. PVS Language Reference Version 7.1. SRI International, Computer Science Laboratory, 333 Ravenswood Avenue, Menlo Park CA, USA. Retrieved from https:\/\/pvs.csl.sri.com\/doc\/pvs-language-reference.pdf, 113 pages"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30186-8_5"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3669989","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3669989","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:05:44Z","timestamp":1750291544000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3669989"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,8]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3669989"],"URL":"https:\/\/doi.org\/10.1145\/3669989","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,8]]},"assertion":[{"value":"2023-05-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}