[{"month":"10","date_published":"2023-10-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","scopus_import":"1","language":[{"iso":"eng"}],"has_accepted_license":"1","department":[{"_id":"GradSch"}],"conference":{"start_date":"2023-10-09","location":"L'Aquila, Italy","end_date":"2023-10-13","name":"DISC: Symposium on Distributed Computing"},"date_created":"2023-11-05T23:00:53Z","file":[{"access_level":"open_access","date_updated":"2023-11-06T11:45:21Z","checksum":"d9f8d2915cccdf2df5905b7cd1b4a560","date_created":"2023-11-06T11:45:21Z","file_size":646665,"file_name":"2023_LIPIcs_Aksenov.pdf","file_id":"14492","creator":"dernst","relation":"main_file","content_type":"application/pdf","success":1}],"day":"01","type":"conference","intvolume":"       281","status":"public","publication":"37th International Symposium on Distributed Computing","file_date_updated":"2023-11-06T11:45:21Z","year":"2023","doi":"10.4230/LIPIcs.DISC.2023.35","title":"Brief announcement: BatchBoost: Universal batching for concurrent data structures","alternative_title":["LIPIcs"],"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_number":"35","ddc":["000"],"publication_status":"published","citation":{"ieee":"V. Aksenov, M. Anoprenko, A. Fedorov, and M. Spear, “Brief announcement: BatchBoost: Universal batching for concurrent data structures,” in <i>37th International Symposium on Distributed Computing</i>, L’Aquila, Italy, 2023, vol. 281.","apa":"Aksenov, V., Anoprenko, M., Fedorov, A., &#38; Spear, M. (2023). Brief announcement: BatchBoost: Universal batching for concurrent data structures. In <i>37th International Symposium on Distributed Computing</i> (Vol. 281). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2023.35\">https://doi.org/10.4230/LIPIcs.DISC.2023.35</a>","chicago":"Aksenov, Vitaly, Michael Anoprenko, Alexander Fedorov, and Michael Spear. “Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures.” In <i>37th International Symposium on Distributed Computing</i>, Vol. 281. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2023.35\">https://doi.org/10.4230/LIPIcs.DISC.2023.35</a>.","ama":"Aksenov V, Anoprenko M, Fedorov A, Spear M. Brief announcement: BatchBoost: Universal batching for concurrent data structures. In: <i>37th International Symposium on Distributed Computing</i>. Vol 281. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2023.35\">10.4230/LIPIcs.DISC.2023.35</a>","mla":"Aksenov, Vitaly, et al. “Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures.” <i>37th International Symposium on Distributed Computing</i>, vol. 281, 35, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2023.35\">10.4230/LIPIcs.DISC.2023.35</a>.","ista":"Aksenov V, Anoprenko M, Fedorov A, Spear M. 2023. Brief announcement: BatchBoost: Universal batching for concurrent data structures. 37th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 281, 35.","short":"V. Aksenov, M. Anoprenko, A. Fedorov, M. Spear, in:, 37th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023."},"abstract":[{"lang":"eng","text":"Batching is a technique that stores multiple keys/values in each node of a data structure. In sequential search data structures, batching reduces latency by reducing the number of cache misses and shortening the chain of pointers to dereference. Applying batching to concurrent data structures is challenging, because it is difficult to maintain the search property and keep contention low in the presence of batching.\r\nIn this paper, we present a general methodology for leveraging batching in concurrent search data structures, called BatchBoost. BatchBoost builds a search data structure from distinct \"data\" and \"index\" layers. The data layer’s purpose is to store a batch of key/value pairs in each of its nodes. The index layer uses an unmodified concurrent search data structure to route operations to a position in the data layer that is \"close\" to where the corresponding key should exist. The requirements on the index and data layers are low: with minimal effort, we were able to compose three highly scalable concurrent search data structures based on three original data structures as the index layers with a batched version of the Lazy List as the data layer. The resulting BatchBoost data structures provide significant performance improvements over their original counterparts."}],"author":[{"last_name":"Aksenov","full_name":"Aksenov, Vitaly","first_name":"Vitaly"},{"first_name":"Michael","full_name":"Anoprenko, Michael","last_name":"Anoprenko"},{"last_name":"Fedorov","full_name":"Fedorov, Alexander","first_name":"Alexander","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6"},{"full_name":"Spear, Michael","last_name":"Spear","first_name":"Michael"}],"oa":1,"date_updated":"2023-11-07T07:48:01Z","volume":281,"article_processing_charge":"Yes","_id":"14485","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773010"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","oa_version":"Published Version"},{"ddc":["000"],"date_created":"2024-02-14T15:14:13Z","related_material":{"record":[{"relation":"used_in_publication","id":"14260","status":"public"}]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.5281/zenodo.7877757"}],"department":[{"_id":"DaAl"}],"title":"Lincheck: A practical framework for testing concurrent data structures on JVM","publisher":"Zenodo","date_published":"2023-04-28T00:00:00Z","year":"2023","doi":"10.5281/ZENODO.7877757","month":"04","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"14995","article_processing_charge":"No","date_updated":"2024-02-27T07:46:52Z","oa":1,"status":"public","author":[{"last_name":"Koval","full_name":"Koval, Nikita","first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Fedorov, Alexander","last_name":"Fedorov","first_name":"Alexander","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6"},{"first_name":"Maria","full_name":"Sokolova, Maria","last_name":"Sokolova"},{"first_name":"Dmitry","full_name":"Tsitelov, Dmitry","last_name":"Tsitelov"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian"}],"abstract":[{"lang":"eng","text":"Lincheck is a new practical and user-friendly framework for testing concurrent data structures on the Java Virtual Machine (JVM). It provides a simple and declarative way to write concurrent tests. Instead of describing how to perform the test, users specify what to test by declaring all the operations to examine; the framework automatically handles the rest. As a result, tests written with Lincheck are concise and easy to understand. \r\nThe artifact presents a collection of Lincheck tests that discover new bugs in popular libraries and implementations from the concurrency literature -- they are listed in Table 1, Section 3. To evaluate the performance of Lincheck analysis, the collection of tests also includes those which check correct data structures and, thus, always succeed. Similarly to Table 2, Section 3, the experiments demonstrate the reasonable time to perform a test. Finally, Lincheck provides user-friendly output with an easy-to-follow trace to reproduce a detected error, significantly simplifying further investigation."}],"type":"research_data_reference","day":"28","citation":{"apa":"Koval, N., Fedorov, A., Sokolova, M., Tsitelov, D., &#38; Alistarh, D.-A. (2023). Lincheck: A practical framework for testing concurrent data structures on JVM. Zenodo. <a href=\"https://doi.org/10.5281/ZENODO.7877757\">https://doi.org/10.5281/ZENODO.7877757</a>","ieee":"N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, and D.-A. Alistarh, “Lincheck: A practical framework for testing concurrent data structures on JVM.” Zenodo, 2023.","chicago":"Koval, Nikita, Alexander Fedorov, Maria Sokolova, Dmitry Tsitelov, and Dan-Adrian Alistarh. “Lincheck: A Practical Framework for Testing Concurrent Data Structures on JVM.” Zenodo, 2023. <a href=\"https://doi.org/10.5281/ZENODO.7877757\">https://doi.org/10.5281/ZENODO.7877757</a>.","ama":"Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. Lincheck: A practical framework for testing concurrent data structures on JVM. 2023. doi:<a href=\"https://doi.org/10.5281/ZENODO.7877757\">10.5281/ZENODO.7877757</a>","mla":"Koval, Nikita, et al. <i>Lincheck: A Practical Framework for Testing Concurrent Data Structures on JVM</i>. Zenodo, 2023, doi:<a href=\"https://doi.org/10.5281/ZENODO.7877757\">10.5281/ZENODO.7877757</a>.","ista":"Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. 2023. Lincheck: A practical framework for testing concurrent data structures on JVM, Zenodo, <a href=\"https://doi.org/10.5281/ZENODO.7877757\">10.5281/ZENODO.7877757</a>.","short":"N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, D.-A. Alistarh, (2023)."}},{"author":[{"full_name":"Fedorov, Alexander","last_name":"Fedorov","first_name":"Alexander","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6"},{"first_name":"Diba","last_name":"Hashemi","full_name":"Hashemi, Diba","id":"ed9595ea-2f8f-11ee-ba95-d2b546540783"},{"id":"3279A00C-F248-11E8-B48F-1D18A9856A87","last_name":"Nadiradze","full_name":"Nadiradze, Giorgi","first_name":"Giorgi"},{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"lang":"eng","text":"Determining the degree of inherent parallelism in classical sequential algorithms and leveraging it for fast parallel execution is a key topic in parallel computing, and detailed analyses are known for a wide range of classical algorithms. In this paper, we perform the first such analysis for the fundamental Union-Find problem, in which we are given a graph as a sequence of edges, and must maintain its connectivity structure under edge additions. We prove that classic sequential algorithms for this problem are well-parallelizable under reasonable assumptions, addressing a conjecture by [Blelloch, 2017]. More precisely, we show via a new potential argument that, under uniform random edge ordering, parallel union-find operations are unlikely to interfere: T concurrent threads processing the graph in parallel will encounter memory contention O(T2 · log |V| · log |E|) times in expectation, where |E| and |V| are the number of edges and nodes in the graph, respectively. We leverage this result to design a new parallel Union-Find algorithm that is both internally deterministic, i.e., its results are guaranteed to match those of a sequential execution, but also work-efficient and scalable, as long as the number of threads T is O(|E|1 over 3 - ε), for an arbitrarily small constant ε > 0, which holds for most large real-world graphs. We present lower bounds which show that our analysis is close to optimal, and experimental results suggesting that the performance cost of internal determinism is limited."}],"publication_status":"published","citation":{"ama":"Fedorov A, Hashemi D, Nadiradze G, Alistarh D-A. Provably-efficient and internally-deterministic parallel Union-Find. In: <i>Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures</i>. Association for Computing Machinery; 2023:261-271. doi:<a href=\"https://doi.org/10.1145/3558481.3591082\">10.1145/3558481.3591082</a>","mla":"Fedorov, Alexander, et al. “Provably-Efficient and Internally-Deterministic Parallel Union-Find.” <i>Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures</i>, Association for Computing Machinery, 2023, pp. 261–71, doi:<a href=\"https://doi.org/10.1145/3558481.3591082\">10.1145/3558481.3591082</a>.","short":"A. Fedorov, D. Hashemi, G. Nadiradze, D.-A. Alistarh, in:, Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery, 2023, pp. 261–271.","ista":"Fedorov A, Hashemi D, Nadiradze G, Alistarh D-A. 2023. Provably-efficient and internally-deterministic parallel Union-Find. Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures, 261–271.","ieee":"A. Fedorov, D. Hashemi, G. Nadiradze, and D.-A. Alistarh, “Provably-efficient and internally-deterministic parallel Union-Find,” in <i>Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures</i>, Orlando, FL, United States, 2023, pp. 261–271.","apa":"Fedorov, A., Hashemi, D., Nadiradze, G., &#38; Alistarh, D.-A. (2023). Provably-efficient and internally-deterministic parallel Union-Find. In <i>Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures</i> (pp. 261–271). Orlando, FL, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3558481.3591082\">https://doi.org/10.1145/3558481.3591082</a>","chicago":"Fedorov, Alexander, Diba Hashemi, Giorgi Nadiradze, and Dan-Adrian Alistarh. “Provably-Efficient and Internally-Deterministic Parallel Union-Find.” In <i>Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures</i>, 261–71. Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3558481.3591082\">https://doi.org/10.1145/3558481.3591082</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","oa_version":"Published Version","_id":"13262","publication_identifier":{"isbn":["9781450395458"]},"oa":1,"date_updated":"2023-07-31T10:54:32Z","article_processing_charge":"Yes (in subscription journal)","arxiv":1,"title":"Provably-efficient and internally-deterministic parallel Union-Find","external_id":{"arxiv":["2304.09331"]},"doi":"10.1145/3558481.3591082","year":"2023","ddc":["000"],"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","type":"conference","day":"17","page":"261-271","file_date_updated":"2023-07-31T10:53:08Z","publication":"Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures","language":[{"iso":"eng"}],"publisher":"Association for Computing Machinery","scopus_import":"1","date_published":"2023-06-17T00:00:00Z","month":"06","date_created":"2023-07-23T22:01:12Z","file":[{"date_updated":"2023-07-31T10:53:08Z","access_level":"open_access","file_name":"2023_SPAA_Fedorov.pdf","file_size":2087937,"date_created":"2023-07-31T10:53:08Z","checksum":"72e312aabf0c5248c99b5cd3a88e4c88","content_type":"application/pdf","relation":"main_file","creator":"dernst","file_id":"13334","success":1}],"conference":{"start_date":"2023-06-17","end_date":"2023-06-19","location":"Orlando, FL, United States","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures"},"department":[{"_id":"DaAl"},{"_id":"GradSch"}],"has_accepted_license":"1"},{"publication":"35th International Conference on Computer Aided Verification ","page":"156-169","file_date_updated":"2023-09-06T08:16:25Z","intvolume":"     13964","status":"public","day":"17","type":"conference","conference":{"location":"Paris, France","end_date":"2023-07-22","name":"CAV: Computer Aided Verification","start_date":"2023-07-17"},"date_created":"2023-09-03T22:01:16Z","file":[{"content_type":"application/pdf","relation":"main_file","file_id":"14275","creator":"dernst","success":1,"date_updated":"2023-09-06T08:16:25Z","access_level":"open_access","file_name":"2023_LNCS_Koval.pdf","file_size":421408,"date_created":"2023-09-06T08:16:25Z","checksum":"c346016393123a0a2338ad4d976f61bc"}],"has_accepted_license":"1","department":[{"_id":"DaAl"},{"_id":"GradSch"}],"publisher":"Springer Nature","scopus_import":"1","language":[{"iso":"eng"}],"month":"07","date_published":"2023-07-17T00:00:00Z","_id":"14260","publication_identifier":{"isbn":["9783031377051"],"issn":["0302-9743"],"eissn":["1611-3349"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","oa_version":"Published Version","volume":13964,"date_updated":"2024-02-27T07:46:52Z","oa":1,"article_processing_charge":"Yes (in subscription journal)","abstract":[{"text":"This paper presents Lincheck, a new practical and user-friendly framework for testing concurrent algorithms on the Java Virtual Machine (JVM). Lincheck provides a simple and declarative way to write concurrent tests: instead of describing how to perform the test, users specify what to test by declaring all the operations to examine; the framework automatically handles the rest. As a result, tests written with Lincheck are concise and easy to understand. The framework automatically generates a set of concurrent scenarios, examines them using stress-testing or bounded model checking, and verifies that the results of each invocation are correct. Notably, if an error is detected via model checking, Lincheck provides an easy-to-follow trace to reproduce it, significantly simplifying the bug investigation.\r\n\r\nTo the best of our knowledge, Lincheck is the first production-ready tool on the JVM that offers such a simple way of writing concurrent tests, without requiring special skills or expertise. We successfully integrated Lincheck in the development process of several large projects, such as Kotlin Coroutines, and identified new bugs in popular concurrency libraries, such as a race in Java’s standard ConcurrentLinkedDeque and a liveliness bug in Java’s AbstractQueuedSynchronizer framework, which is used in most of the synchronization primitives. We believe that Lincheck can significantly improve the quality and productivity of concurrent algorithms research and development and become the state-of-the-art tool for checking their correctness.","lang":"eng"}],"author":[{"id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita","last_name":"Koval","full_name":"Koval, Nikita"},{"id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","first_name":"Alexander","full_name":"Fedorov, Alexander","last_name":"Fedorov"},{"first_name":"Maria","last_name":"Sokolova","full_name":"Sokolova, Maria"},{"first_name":"Dmitry","full_name":"Tsitelov, Dmitry","last_name":"Tsitelov"},{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","citation":{"chicago":"Koval, Nikita, Alexander Fedorov, Maria Sokolova, Dmitry Tsitelov, and Dan-Adrian Alistarh. “Lincheck: A Practical Framework for Testing Concurrent Data Structures on JVM.” In <i>35th International Conference on Computer Aided Verification </i>, 13964:156–69. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-37706-8_8\">https://doi.org/10.1007/978-3-031-37706-8_8</a>.","apa":"Koval, N., Fedorov, A., Sokolova, M., Tsitelov, D., &#38; Alistarh, D.-A. (2023). Lincheck: A practical framework for testing concurrent data structures on JVM. In <i>35th International Conference on Computer Aided Verification </i> (Vol. 13964, pp. 156–169). Paris, France: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-37706-8_8\">https://doi.org/10.1007/978-3-031-37706-8_8</a>","ieee":"N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, and D.-A. Alistarh, “Lincheck: A practical framework for testing concurrent data structures on JVM,” in <i>35th International Conference on Computer Aided Verification </i>, Paris, France, 2023, vol. 13964, pp. 156–169.","ista":"Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. 2023. Lincheck: A practical framework for testing concurrent data structures on JVM. 35th International Conference on Computer Aided Verification . CAV: Computer Aided Verification, LNCS, vol. 13964, 156–169.","short":"N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, D.-A. Alistarh, in:, 35th International Conference on Computer Aided Verification , Springer Nature, 2023, pp. 156–169.","mla":"Koval, Nikita, et al. “Lincheck: A Practical Framework for Testing Concurrent Data Structures on JVM.” <i>35th International Conference on Computer Aided Verification </i>, vol. 13964, Springer Nature, 2023, pp. 156–69, doi:<a href=\"https://doi.org/10.1007/978-3-031-37706-8_8\">10.1007/978-3-031-37706-8_8</a>.","ama":"Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. Lincheck: A practical framework for testing concurrent data structures on JVM. In: <i>35th International Conference on Computer Aided Verification </i>. Vol 13964. Springer Nature; 2023:156-169. doi:<a href=\"https://doi.org/10.1007/978-3-031-37706-8_8\">10.1007/978-3-031-37706-8_8</a>"},"related_material":{"record":[{"relation":"research_data","id":"14995","status":"public"}]},"ddc":["000"],"alternative_title":["LNCS"],"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"title":"Lincheck: A practical framework for testing concurrent data structures on JVM","year":"2023","doi":"10.1007/978-3-031-37706-8_8"},{"date_published":"2023-02-25T00:00:00Z","doi":"10.1145/3572848.3577512","year":"2023","month":"02","language":[{"iso":"eng"}],"publisher":"Association for Computing Machinery","title":"Unexpected scaling in path copying trees","department":[{"_id":"DaAl"},{"_id":"GradSch"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1145/3572848.3577512"}],"date_created":"2023-03-19T23:00:58Z","conference":{"name":"PPoPP: Sympopsium on Principles and Practice of Parallel Programming","location":"Montreal, QB, Canada","end_date":"2023-03-01","start_date":"2023-02-25"},"type":"conference_poster","publication_status":"published","citation":{"ieee":"V. Aksenov, T. A. Brown, A. Fedorov, and I. Kokorin, <i>Unexpected scaling in path copying trees</i>. Association for Computing Machinery, 2023, pp. 438–440.","apa":"Aksenov, V., Brown, T. A., Fedorov, A., &#38; Kokorin, I. (2023). <i>Unexpected scaling in path copying trees</i>. <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i> (pp. 438–440). Montreal, QB, Canada: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3572848.3577512\">https://doi.org/10.1145/3572848.3577512</a>","chicago":"Aksenov, Vitaly, Trevor A Brown, Alexander Fedorov, and Ilya Kokorin. <i>Unexpected Scaling in Path Copying Trees</i>. <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>. Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3572848.3577512\">https://doi.org/10.1145/3572848.3577512</a>.","mla":"Aksenov, Vitaly, et al. “Unexpected Scaling in Path Copying Trees.” <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Association for Computing Machinery, 2023, pp. 438–40, doi:<a href=\"https://doi.org/10.1145/3572848.3577512\">10.1145/3572848.3577512</a>.","ama":"Aksenov V, Brown TA, Fedorov A, Kokorin I. <i>Unexpected Scaling in Path Copying Trees</i>. Association for Computing Machinery; 2023:438-440. doi:<a href=\"https://doi.org/10.1145/3572848.3577512\">10.1145/3572848.3577512</a>","short":"V. Aksenov, T.A. Brown, A. Fedorov, I. Kokorin, Unexpected Scaling in Path Copying Trees, Association for Computing Machinery, 2023.","ista":"Aksenov V, Brown TA, Fedorov A, Kokorin I. 2023. Unexpected scaling in path copying trees, Association for Computing Machinery,p."},"day":"25","author":[{"first_name":"Vitaly","last_name":"Aksenov","full_name":"Aksenov, Vitaly"},{"id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","full_name":"Brown, Trevor A","last_name":"Brown","first_name":"Trevor A"},{"id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","last_name":"Fedorov","full_name":"Fedorov, Alexander","first_name":"Alexander"},{"full_name":"Kokorin, Ilya","last_name":"Kokorin","first_name":"Ilya"}],"status":"public","abstract":[{"lang":"eng","text":"Although a wide variety of handcrafted concurrent data structures have been proposed, there is considerable interest in universal approaches (Universal Constructions or UCs) for building concurrent data structures. UCs (semi-)automatically convert a sequential data structure into a concurrent one. The simplest approach uses locks [3, 6] that protect a sequential data structure and allow only one process to access it at a time. However, the resulting data structure is blocking. Most work on UCs instead focuses on obtaining non-blocking progress guarantees such as obstruction-freedom, lock-freedom or wait-freedom. Many non-blocking UCs have appeared. Key examples include the seminal wait-free UC [2] by Herlihy, a NUMA-aware UC [10] by Yi et al., and an efficient UC for large objects [1] by Fatourou et al."}],"date_updated":"2023-03-20T07:57:27Z","oa":1,"page":"438-440","article_processing_charge":"No","publication":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"This work was supported by: the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Program grant: RGPIN-2019-04227, and the Canada Foundation for Innovation John R. Evans Leaders Fund (CFI-JELF) with equal support from the Ontario Research Fund CFI Leaders Opportunity Fund: 38512.","oa_version":"Published Version","quality_controlled":"1","_id":"12736","publication_identifier":{"isbn":["9798400700156"]}}]