{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T01:22:24Z","timestamp":1794360144599,"version":"4.9.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001459","name":"Singapore Ministry of Education","doi-asserted-by":"crossref","award":["MOE-MOET32021-0001"],"award-info":[{"award-number":["MOE-MOET32021-0001"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,10,8]]},"abstract":"<jats:p>\n                    Design of an efficient thread-safe concurrent data structure is a balancing act between its implementation complexity and performance.\n                    <jats:italic toggle=\"yes\">Lock-based<\/jats:italic>\n                    concurrent data structures, which are relatively easy to derive from their sequential counterparts and to prove thread-safe, suffer from poor throughput under even light multi-threaded workload. At the same time,\n                    <jats:italic toggle=\"yes\">lock-free<\/jats:italic>\n                    concurrent structures allow for high throughput, but are notoriously difficult to get right and require careful reasoning to formally establish their correctness.\n                  <\/jats:p>\n                  <jats:p>\n                    In this work, we explore a solution to this conundrum based on a relatively old idea of\n                    <jats:italic toggle=\"yes\">batch parallelism<\/jats:italic>\n                    \u2014an approach for designing high-throughput concurrent data structures via a simple insight: efficiently processing a batch of\n                    <jats:italic toggle=\"yes\">a priori known<\/jats:italic>\n                    operations in parallel is easier than optimising performance for a stream of arbitrary asynchronous requests. Alas, batch-parallel structures have not seen wide practical adoption due to\n                    <jats:italic toggle=\"yes\">(i<\/jats:italic>\n                    ) the inconvenience of having to structure multi-threaded programs to explicitly group operations and\n                    <jats:italic toggle=\"yes\">(ii)<\/jats:italic>\n                    the lack of a systematic methodology to implement batch-parallel structures as simply as lock-based ones.\n                  <\/jats:p>\n                  <jats:p>\n                    We present OB\n                    <jats:sc>atcher<\/jats:sc>\n                    \u2014a Multicore OCaml library that streamlines the design, implementation, and usage of batch-parallel structures. It solves the first challenge (how to use) by suggesting a new lightweight\n                    <jats:italic toggle=\"yes\">implicit batching<\/jats:italic>\n                    design that is built on top of generic asynchronous programming mechanisms. The second challenge (how to implement) is addressed by identifying\n                    <jats:italic toggle=\"yes\">a family of strategies<\/jats:italic>\n                    for converting common sequential structures into efficient batch-parallel ones, and by providing functors that embody those strategies. We showcase OBatcher with a diverse set of benchmarks. Our evaluation of all the implementations on large asynchronous workloads shows that (a) they consistently outperform the corresponding coarse-grained lock-based implementations and that (b) their throughput scales reasonably with the number of processors.\n                  <\/jats:p>","DOI":"10.1145\/3689775","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T03:23:04Z","timestamp":1728357784000},"page":"1814-1842","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Concurrent Data Structures Made Easy"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-6689-9542","authenticated-orcid":false,"given":"Callista","family":"Le","sequence":"first","affiliation":[{"name":"Yale-NUS College, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1877-9871","authenticated-orcid":false,"given":"Kiran","family":"Gopinathan","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-0971-7530","authenticated-orcid":false,"given":"Koon Wen","family":"Lee","sequence":"additional","affiliation":[{"name":"Ahrefs, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3298-7412","authenticated-orcid":false,"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4250-5392","authenticated-orcid":false,"given":"Ilya","family":"Sergey","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,10,8]]},"reference":[{"key":"e_1_3_1_2_1","first-page":"2:1","volume-title":"ESA (LIPIcs, Vol. 173)","author":"Acar Umut A.","year":"2020","unstructured":"Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. 2020. Parallel Batch-Dynamic Trees via Change Propagation. In ESA (LIPIcs, Vol. 173). Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2:1\u20132:23. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.2 10.4230\/LIPIcs.ESA.2020.2"},{"issue":"4","key":"e_1_3_1_3_1","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1017\/S0956796800000885","article-title":"Functional Pearls Efficient sets\u2014a balancing act","volume":"3","author":"Adams Stephen","year":"1993","unstructured":"Stephen Adams. 1993. Functional Pearls Efficient sets\u2014a balancing act. Journal of Functional Programming 3, 4 (1993), 553\u2013561. https:\/\/doi.org\/10.1017\/S0956796800000885 10.1017\/S0956796800000885","journal-title":"Journal of Functional Programming"},{"key":"e_1_3_1_4_1","unstructured":"Georgy Adelson-Velsky and Evgenii Landis. 1962. An algorithm for the organization of information. Proc. of the USSR Academy of Sciences 145 (1962) 263\u2013266. In Russian English translation by Myron J. Ricci in Soviet Doklady 3:1259-1263 1962."},{"key":"e_1_3_1_5_1","first-page":"389","volume-title":"PPoPP","author":"Agrawal Kunal","year":"2014","unstructured":"Kunal Agrawal, Jeremy T. Fineman, Brendan Sheridan, Jim Sukha, and Robert Utterback. 2014. Provably Good Scheduling for Parallel Programs that Use Data Structures through Implicit Batching. In PPoPP. ACM, 389\u2013390. https:\/\/doi.org\/10.1145\/2555243.2555284 10.1145\/2555243.2555284"},{"key":"e_1_3_1_6_1","doi-asserted-by":"crossref","unstructured":"Yaroslav Akhremtsev and Peter Sanders. 2016. Fast Parallel Operations on Search Trees. In 2016 IEEE 23rd International Conference on High Performance Computing (HiPC). 291\u2013300. https:\/\/doi.org\/10.1109\/HiPC.2016.042 10.1109\/HiPC.2016.042","DOI":"10.1109\/HiPC.2016.042"},{"key":"e_1_3_1_7_1","doi-asserted-by":"crossref","unstructured":"Rudolf Bayer. 1972. Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms. Acta Informatica 1 (1972) 290\u2013306. https:\/\/doi.org\/10.1007\/BF00289509 10.1007\/BF00289509","DOI":"10.1007\/BF00289509"},{"key":"e_1_3_1_8_1","first-page":"290","volume-title":"Acta informatica","author":"Bayer Rudolf","year":"1972","unstructured":"Rudolf Bayer and Edward M McCreight. 1972. Symmetric Binary B-trees: Data Structure and Maintenance Algorithms. In Acta informatica, Vol. 1. Springer, 290\u2013306. https:\/\/doi.org\/10.1007\/BF00289509 10.1007\/BF00289509"},{"key":"e_1_3_1_9_1","doi-asserted-by":"crossref","unstructured":"Rudolf Bayer and Mario Schkolnick. 1977. Concurrency of Operations on B-Trees. Acta Informatica 9 (1977) 1\u201321. https:\/\/doi.org\/10.1007\/BF00263762 10.1007\/BF00263762","DOI":"10.1007\/BF00263762"},{"key":"e_1_3_1_10_1","first-page":"253","volume-title":"SPAA","author":"Blelloch Guy E.","year":"2016","unstructured":"Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun. 2016. Just Join for Parallel Ordered Sets. In SPAA. ACM, 253\u2013264. https:\/\/doi.org\/10.1145\/2935764.2935768 10.1145\/2935764.2935768"},{"issue":"2","key":"e_1_3_1_11_1","first-page":"7:1","article-title":"Joinable Parallel Balanced Binary Trees","volume":"9","author":"Blelloch Guy E.","year":"2022","unstructured":"Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun. 2022. Joinable Parallel Balanced Binary Trees. ACM Trans. Parallel Comput. 9, 2 (2022), 7:1\u20137:41. https:\/\/doi.org\/10.1145\/3512769 10.1145\/3512769","journal-title":"ACM Trans. Parallel Comput."},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277660"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312016"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1425"},{"key":"e_1_3_1_15_1","first-page":"276","volume-title":"PPoPP","author":"Brown Trevor","year":"2020","unstructured":"Trevor Brown, Aleksandar Prokopec, and Dan Alistarh. 2020. Non-blocking interpolation search trees with doubly-logarithmic running time. In PPoPP. ACM, 276\u2013291. https:\/\/doi.org\/10.1145\/3332466.3374542 10.1145\/3332466.3374542"},{"key":"e_1_3_1_16_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press.","edition":"3"},{"key":"e_1_3_1_17_1","unstructured":"Simon Cruanes. 2024. An in-memory Datalog implementation for OCaml. Available at https:\/\/github.com\/c-cube\/datalog accessed on 28 March 2024."},{"key":"e_1_3_1_18_1","first-page":"1300","volume-title":"SODA","author":"Dhulipala Laxman","year":"2020","unstructured":"Laxman Dhulipala, David Durfee, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, and Xiaorui Sun. 2020. Parallel BatchDynamic Graphs: Algorithms and Lower Bounds. In SODA. SIAM, 1300\u20131319. https:\/\/doi.org\/10.1137\/1.9781611975994.79 10.1137\/1.9781611975994.79"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/50087.50096"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1980.1675680"},{"key":"e_1_3_1_21_1","doi-asserted-by":"crossref","unstructured":"Panagiota Fatourou and Nikolaos D. Kallimanis. 2011. A highly-efficient wait-free universal construction. In SPAA. ACM 325\u2013334. https:\/\/doi.org\/10.1145\/1989493.1989549 10.1145\/1989493.1989549","DOI":"10.1145\/1989493.1989549"},{"key":"e_1_3_1_22_1","first-page":"128:1","article-title":"Proving highly-concurrent traversals correct","volume":"4","author":"Feldman Yotam M. Y.","year":"2020","unstructured":"Yotam M. Y. Feldman, Artem Khyzha, Constantin Enea, Adam Morrison, Aleksandar Nanevski, Noam Rinetzky, and Sharon Shoham. 2020. Proving highly-concurrent traversals correct. Proc. ACM Program. Lang. 4, OOPSLA (2020), 128:1\u2013128:29. https:\/\/doi.org\/10.1145\/3428196 10.1145\/3428196","journal-title":"Proc. ACM Program. Lang."},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277725"},{"key":"e_1_3_1_24_1","first-page":"531","volume-title":"SPAA","author":"Gilbert Seth","year":"2020","unstructured":"Seth Gilbert and Lawrence Er Lu Li. 2020. How Fast Can You Update Your MST?. In SPAA. ACM, 531\u2013533. https:\/\/doi.org\/10.1145\/3350755.3400240 10.1145\/3350755.3400240"},{"key":"e_1_3_1_25_1","doi-asserted-by":"crossref","unstructured":"Yan Gu Ziyang Men Zheqi Shen Yihan Sun and Zijin Wan. 2023. Parallel Longest Increasing Subsequence and van Emde Boas Trees. In SPAA. ACM 327\u2013340. https:\/\/doi.org\/10.1145\/3558481.3591069 10.1145\/3558481.3591069","DOI":"10.1145\/3558481.3591069"},{"key":"e_1_3_1_26_1","first-page":"1","volume-title":"OSDI","author":"Gupta Vishal","year":"2023","unstructured":"Vishal Gupta, Kumar Kartikeya Dwivedi, Yugesh Kothari, Yueyang Pan, Diyu Zhou, and Sanidhya Kashyap. 2023. Ship your Critical Section, Not Your Data: Enabling Transparent Delegation with TCLOCKS. In OSDI. USENIX Association, 1\u201316. https:\/\/www.usenix.org\/conference\/osdi23\/presentation\/gupta"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810540"},{"key":"e_1_3_1_28_1","first-page":"124","volume-title":"SIROCCO (LNCS, Vol. 4474)","author":"Herlihy Maurice","year":"2007","unstructured":"Maurice Herlihy, Yossi Lev, Victor Luchangco, and Nir Shavit. 2007. A Simple Optimistic Skiplist Algorithm. In SIROCCO (LNCS, Vol. 4474). Springer, 124\u2013138. https:\/\/doi.org\/10.1007\/978-3-540-72951-8_11 10.1007\/978-3-540-72951-8_11"},{"key":"e_1_3_1_29_1","unstructured":"Maurice Herlihy and Nir Shavit. 2008. The Art of Multiprocessor Programming. Morgan Kaufmann. https:\/\/dl.acm.org\/doi\/book\/10.5555\/2385452 10.5555\/2385452"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_3_1_31_1","first-page":"49","volume-title":"SPAA","author":"Italiano Giuseppe F.","year":"2019","unstructured":"Giuseppe F. Italiano, Silvio Lattanzi, Vahab S. Mirrokni, and Nikos Parotsidis. 2019. Dynamic Algorithms for the Massively Parallel Computation Model. In SPAA. ACM, 49\u201358. https:\/\/doi.org\/10.1145\/3323165.3323202 10.1145\/3323165.3323202"},{"key":"e_1_3_1_32_1","first-page":"215","volume-title":"PPoPP","author":"Khalaji Mohammad","year":"2024","unstructured":"Mohammad Khalaji, Trevor Brown, Khuzaima Daudjee, and Vitaly Aksenov. 2024. Practical Hardware Transactional vEB Trees. In PPoPP. ACM, 215\u2013228. https:\/\/doi.org\/10.1145\/3627535.3638504 10.1145\/3627535.3638504"},{"key":"e_1_3_1_33_1","unstructured":"Callista Le Kiran Gopinathan Koon Wen Lee Seth Gilbert and Ilya Sergey. 2024a. Concurrent Data Structures Made Easy (Extended Version). CoRR abs\/2408.13779 (2024). https:\/\/doi.org\/10.48550\/arXiv.2408.13779 10.48550\/arXiv.2408.13779"},{"key":"e_1_3_1_34_1","unstructured":"Callista Le Kiran Gopinathan Koon Wen Lee Seth Gilbert and Ilya Sergey. 2024b. OBatcher: Implementation Data Structures and Experiments (OOPSLA\u201924 Artefact). https:\/\/doi.org\/10.5281\/zenodo.12604575 10.5281\/zenodo.12604575"},{"issue":"4","key":"e_1_3_1_35_1","first-page":"13:1","article-title":"Fast and Portable Locking for Multicore Architectures","volume":"33","author":"Lozi Jean-Pierre","year":"2016","unstructured":"Jean-Pierre Lozi, Florian David, Gael Thomas, Julia Lawall, and Gilles Muller. 2016. Fast and Portable Locking for Multicore Architectures. ACM Trans. Comput. Syst. 33, 4 (2016), 13:1\u201313:62. https:\/\/dl.acm.org\/citation.cfm?id=2845079","journal-title":"ACM Trans. Comput. Syst."},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563337"},{"key":"e_1_3_1_37_1","first-page":"809","volume-title":"PLDI","author":"Mulder Ike","year":"2022","unstructured":"Ike Mulder, Robbert Krebbers, and Herman Geuvers. 2022. Diaframe: automated verification of fine-grained concurrent programs in Iris. In PLDI. ACM, 809\u2013824. https:\/\/doi.org\/10.1145\/3519939.3523432 10.1145\/3519939.3523432"},{"key":"e_1_3_1_38_1","first-page":"23","volume-title":"PODC","author":"Oshman Rotem","year":"2013","unstructured":"Rotem Oshman and Nir Shavit. 2013. The SkipTrie: low-depth concurrent search without rebalancing. In PODC, Panagiota Fatourou and Gadi Taubenfeld (Eds.). ACM, 23\u201332. https:\/\/doi.org\/10.1145\/2484239.2484270 10.1145\/2484239.2484270"},{"key":"e_1_3_1_39_1","first-page":"182","volume-title":"International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications (PDSIA\u201999)","author":"Oyama Yoshihiro","year":"2000","unstructured":"Yoshihiro Oyama, Kenjiro Taura, and Akinori Yonezawa. 2000. Executing Parallel Programs with Synchronization Bottlenecks Efficiently. In International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications (PDSIA\u201999). World Scientific, 182\u2013204."},{"key":"e_1_3_1_40_1","first-page":"14","volume-title":"ICPP","author":"Paige Richard C.","year":"1985","unstructured":"Richard C. Paige and Clyde P. Kruskal. 1985. Parallel Algorithms for Shortest Path Problems. In ICPP. IEEE Computer Society Press, 14\u201320."},{"key":"e_1_3_1_41_1","unstructured":"Simon L. Peyton Jones Roman Leshchinskiy Gabriele Keller and Manuel M. T. Chakravarty. 2008. Harnessing the Multicores: Nested Data Parallelism in Haskell. In FSTTCS (LIPIcs Vol. 2). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik 383\u2013414. https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2008.1769 10.4230\/LIPIcs.FSTTCS.2008.1769"},{"key":"e_1_3_1_42_1","first-page":"136","volume-title":"Euro-Par (LNCS, Vol. 6853)","author":"Prokopec Aleksandar","year":"2011","unstructured":"Aleksandar Prokopec, Phil Bagwell, Tiark Rompf, and Martin Odersky. 2011. A Generic Parallel Collection Framework. In Euro-Par (LNCS, Vol. 6853). Springer, 136\u2013147. https:\/\/doi.org\/10.1007\/978-3-642-23397-5_14 10.1007\/978-3-642-23397-5_14"},{"key":"e_1_3_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_3_1_44_1","first-page":"342","volume-title":"SOSP","author":"Roghanchi Sepideh","year":"2017","unstructured":"Sepideh Roghanchi, Jakob Eriksson, and Nilanjana Basu. 2017. ffwd: delegation is (much) faster than you think. In SOSP. ACM, 342\u2013358. https:\/\/doi.org\/10.1145\/3132747.3132771 10.1145\/3132747.3132771"},{"key":"e_1_3_1_45_1","first-page":"233","volume-title":"Sorted Sequences","author":"Sanders Peter","year":"2019","unstructured":"Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, and Roman Dementiev. 2019. Sorted Sequences. Springer International Publishing, Cham, 233\u2013258. https:\/\/doi.org\/10.1007\/978-3-030-25209-0_7 10.1007\/978-3-030-25209-0_7"},{"key":"e_1_3_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940876"},{"key":"e_1_3_1_47_1","first-page":"77","volume-title":"PLDI","author":"Sergey Ilya","year":"2015","unstructured":"Ilya Sergey, Aleksandar Nanevski, and Anindya Banerjee. 2015. Mechanized Verification of Fine-Grained Concurrent Programs. In PLDI. ACM, 77\u201387. https:\/\/doi.org\/10.1145\/2737924.2737964 10.1145\/2737924.2737964"},{"key":"e_1_3_1_48_1","first-page":"206","volume-title":"PLDI","author":"Sivaramakrishnan K. C.","year":"2021","unstructured":"K. C. Sivaramakrishnan, Stephen Dolan, Leo White, Tom Kelly, Sadiq Jaffer, and Anil Madhavapeddy. 2021. Retrofitting effect handlers onto OCaml. In PLDI. ACM, 206\u2013221. https:\/\/doi.org\/10.1145\/3453483.3454039 10.1145\/3453483.3454039"},{"key":"e_1_3_1_49_1","first-page":"416","volume-title":"PPoPP","author":"Srivastava Anubhav","year":"2022","unstructured":"Anubhav Srivastava and Trevor Brown. 2022. Elimination (a, b)-trees with fast, durable updates. In PPoPP. ACM, 416\u2013430. https:\/\/doi.org\/10.1145\/3503221.3508441 10.1145\/3503221.3508441"},{"key":"e_1_3_1_50_1","volume-title":"Systems programming: coping with parallelism","author":"Treiber R. Kent","year":"1986","unstructured":"R. Kent Treiber. 1986. Systems programming: coping with parallelism. Technical Report RJ 5118. IBM Almaden Research Center."},{"key":"e_1_3_1_51_1","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1137\/1.9781611975499.8","volume-title":"Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX)","author":"Tseng Thomas","year":"2019","unstructured":"Thomas Tseng, Laxman Dhulipala, and Guy Blelloch. 2019. Batch-Parallel Euler Tour Trees. In Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 92\u2013106. https:\/\/doi.org\/10.1137\/1.9781611975499.8 10.1137\/1.9781611975499.8"},{"key":"e_1_3_1_52_1","first-page":"233","volume-title":"SPAA","author":"Tseng Tom","year":"2022","unstructured":"Tom Tseng, Laxman Dhulipala, and Julian Shun. 2022. Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering. In SPAA. ACM, 233\u2013245. https:\/\/doi.org\/10.1145\/3490148.3538584 10.1145\/3490148.3538584"},{"key":"e_1_3_1_53_1","volume-title":"Modular fine-grained concurrency verification","author":"Vafeiadis Viktor","year":"2008","unstructured":"Viktor Vafeiadis. 2008. Modular fine-grained concurrency verification. Ph. D. Dissertation. University of Cambridge."},{"key":"e_1_3_1_54_1","first-page":"75","volume-title":"FOCS","author":"Emde Boas Peter","year":"1975","unstructured":"Peter van Emde Boas. 1975. Preserving Order in a Forest in less than Logarithmic Time. In FOCS. IEEE Computer Society, 75\u201384. https:\/\/doi.org\/10.1109\/SFCS.1975.26 10.1109\/SFCS.1975.26"},{"key":"e_1_3_1_55_1","first-page":"60:1","volume-title":"37th International Symposium on Computational Geometry (SoCG 2021) (LIPIcs, Vol. 189)","author":"Wang Yiqiu","year":"2021","unstructured":"Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun. 2021. A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem. In 37th International Symposium on Computational Geometry (SoCG 2021) (LIPIcs, Vol. 189). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 60:1\u201360:16. https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2021.60 10.4230\/LIPIcs.SoCG.2021.60"},{"key":"e_1_3_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90075-3"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689775","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689775","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T09:07:19Z","timestamp":1770196039000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689775"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,8]]},"references-count":55,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2024,10,8]]}},"alternative-id":["10.1145\/3689775"],"URL":"https:\/\/doi.org\/10.1145\/3689775","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,8]]},"assertion":[{"value":"2024-04-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}