[{"OA_type":"gold","oa_version":"Published Version","date_created":"2026-02-16T15:41:15Z","title":"An almost-logarithmic lower bound for leader election with bounded value contention","alternative_title":["LIPIcs"],"publication_status":"published","conference":{"location":"Berlin, Germany","end_date":"2025-10-31","start_date":"2025-10-27","name":"DISC: Symposium on Distributed Computing"},"file":[{"file_name":"2025_LIPIcs_Alistarh.pdf","checksum":"3825a0e6e6a05503e842a59f95528bd9","file_id":"21310","date_updated":"2026-02-18T06:46:02Z","relation":"main_file","creator":"dernst","access_level":"open_access","date_created":"2026-02-18T06:46:02Z","file_size":1492189,"success":1,"content_type":"application/pdf"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"Yes","corr_author":"1","tmp":{"short":"CC BY (4.0)","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)"},"oa":1,"doi":"10.4230/LIPIcs.DISC.2025.3","acknowledgement":"The work of Dan Alistarh is supported by grants from ERC, Austrian FWF, and the Google and NVIDIA corporations. Faith Ellen was supported in part by the Natural Science and Engineering Research Council of Canada (NSERC) grant RGPIN-2020-04178.","department":[{"_id":"DaAl"},{"_id":"GradSch"}],"month":"10","author":[{"orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"},{"first_name":"Faith","full_name":"Ellen, Faith","last_name":"Ellen"},{"last_name":"Fedorov","full_name":"Fedorov, Alexander","first_name":"Alexander","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6"}],"volume":356,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"year":"2025","intvolume":"       356","OA_place":"publisher","date_published":"2025-10-22T00:00:00Z","quality_controlled":"1","type":"conference","_id":"21250","abstract":[{"text":"We investigate the step complexity of the Leader Election problem (and implementing the corresponding test-and-set object) in asynchronous shared memory, where processes communicate through registers supporting atomic read and write and must coordinate so that a single process becomes the leader. Determining tight step complexity bounds for solving this problem is one of the key open problems in the theory of shared memory distributed computing. The best known algorithm is a randomized tournament-tree, which has worst-case expected step complexity O(log N) for N processes. There are provably no deterministic wait-free algorithms, and only restricted lower bounds are known for obstruction-free and randomized wait-free algorithms. We introduce a new lower bound that establishes an Ω((log N)/(log log N + log Q)) step complexity for any obstruction-free Leader Election algorithm, where N is the number of processes, and 2 ≤ Q ≤ N is a bound on the value contention, which we define as the maximum number of different values that processes can be simultaneously poised to write to the same register in any execution of the algorithm. Our result is strictly stronger than previous bounds based on write contention. In particular, it implies new lower bounds on step complexity that depend on register size.","lang":"eng"}],"language":[{"iso":"eng"}],"day":"22","citation":{"chicago":"Alistarh, Dan-Adrian, Faith Ellen, and Alexander Fedorov. “An Almost-Logarithmic Lower Bound for Leader Election with Bounded Value Contention.” In <i>39th International Symposium on Distributed Computing</i>, 356:3:1-3:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.3\">https://doi.org/10.4230/LIPIcs.DISC.2025.3</a>.","ista":"Alistarh D-A, Ellen F, Fedorov A. 2025. An almost-logarithmic lower bound for leader election with bounded value contention. 39th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 356, 3:1-3:16.","ama":"Alistarh D-A, Ellen F, Fedorov A. An almost-logarithmic lower bound for leader election with bounded value contention. In: <i>39th International Symposium on Distributed Computing</i>. Vol 356. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025:3:1-3:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.3\">10.4230/LIPIcs.DISC.2025.3</a>","apa":"Alistarh, D.-A., Ellen, F., &#38; Fedorov, A. (2025). An almost-logarithmic lower bound for leader election with bounded value contention. In <i>39th International Symposium on Distributed Computing</i> (Vol. 356, p. 3:1-3:16). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.3\">https://doi.org/10.4230/LIPIcs.DISC.2025.3</a>","short":"D.-A. Alistarh, F. Ellen, A. Fedorov, in:, 39th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 3:1-3:16.","ieee":"D.-A. Alistarh, F. Ellen, and A. Fedorov, “An almost-logarithmic lower bound for leader election with bounded value contention,” in <i>39th International Symposium on Distributed Computing</i>, Berlin, Germany, 2025, vol. 356, p. 3:1-3:16.","mla":"Alistarh, Dan-Adrian, et al. “An Almost-Logarithmic Lower Bound for Leader Election with Bounded Value Contention.” <i>39th International Symposium on Distributed Computing</i>, vol. 356, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 3:1-3:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.3\">10.4230/LIPIcs.DISC.2025.3</a>."},"has_accepted_license":"1","page":"3:1-3:16","status":"public","file_date_updated":"2026-02-18T06:46:02Z","date_updated":"2026-02-18T06:49:38Z","publication":"39th International Symposium on Distributed Computing"},{"file":[{"access_level":"open_access","file_size":421408,"date_created":"2023-09-06T08:16:25Z","success":1,"content_type":"application/pdf","file_name":"2023_LNCS_Koval.pdf","checksum":"c346016393123a0a2338ad4d976f61bc","file_id":"14275","relation":"main_file","creator":"dernst","date_updated":"2023-09-06T08:16:25Z"}],"conference":{"end_date":"2023-07-22","location":"Paris, France","name":"CAV: Computer Aided Verification","start_date":"2023-07-17"},"publication_status":"published","title":"Lincheck: A practical framework for testing concurrent data structures on JVM","alternative_title":["LNCS"],"date_created":"2023-09-03T22:01:16Z","oa_version":"Published Version","publication_identifier":{"isbn":["9783031377051"],"issn":["0302-9743"],"eissn":["1611-3349"]},"author":[{"last_name":"Koval","full_name":"Koval, Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita"},{"first_name":"Alexander","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","last_name":"Fedorov","full_name":"Fedorov, Alexander"},{"first_name":"Maria","full_name":"Sokolova, Maria","last_name":"Sokolova"},{"first_name":"Dmitry","last_name":"Tsitelov","full_name":"Tsitelov, Dmitry"},{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"}],"volume":13964,"department":[{"_id":"DaAl"},{"_id":"GradSch"}],"month":"07","doi":"10.1007/978-3-031-37706-8_8","oa":1,"related_material":{"record":[{"relation":"research_data","id":"14995","status":"public"}]},"article_processing_charge":"Yes (in subscription journal)","tmp":{"short":"CC BY (4.0)","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)"},"publisher":"Springer Nature","day":"17","citation":{"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.","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>","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>.","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.","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>.","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>"},"has_accepted_license":"1","external_id":{"isi":["001310786500008"]},"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"}],"_id":"14260","language":[{"iso":"eng"}],"quality_controlled":"1","type":"conference","date_published":"2023-07-17T00:00:00Z","intvolume":"     13964","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ddc":["000"],"year":"2023","publication":"35th International Conference on Computer Aided Verification ","date_updated":"2025-09-09T12:51:52Z","isi":1,"file_date_updated":"2023-09-06T08:16:25Z","scopus_import":"1","status":"public","page":"156-169"},{"date_published":"2023-10-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"year":"2023","article_number":"35","intvolume":"       281","citation":{"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.","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>","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>.","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.","short":"V. Aksenov, M. Anoprenko, A. Fedorov, M. Spear, in:, 37th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","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>.","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>"},"day":"01","has_accepted_license":"1","quality_controlled":"1","type":"conference","_id":"14485","language":[{"iso":"eng"}],"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."}],"scopus_import":"1","status":"public","publication":"37th International Symposium on Distributed Computing","date_updated":"2024-10-09T21:07:14Z","file_date_updated":"2023-11-06T11:45:21Z","oa_version":"Published Version","alternative_title":["LIPIcs"],"title":"Brief announcement: BatchBoost: Universal batching for concurrent data structures","date_created":"2023-11-05T23:00:53Z","publication_identifier":{"isbn":["9783959773010"],"issn":["1868-8969"]},"file":[{"access_level":"open_access","content_type":"application/pdf","success":1,"file_size":646665,"date_created":"2023-11-06T11:45:21Z","checksum":"d9f8d2915cccdf2df5905b7cd1b4a560","file_name":"2023_LIPIcs_Aksenov.pdf","relation":"main_file","date_updated":"2023-11-06T11:45:21Z","creator":"dernst","file_id":"14492"}],"conference":{"location":"L'Aquila, Italy","end_date":"2023-10-13","start_date":"2023-10-09","name":"DISC: Symposium on Distributed Computing"},"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"Yes","corr_author":"1","tmp":{"short":"CC BY (4.0)","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)"},"month":"10","department":[{"_id":"GradSch"}],"author":[{"first_name":"Vitaly","last_name":"Aksenov","full_name":"Aksenov, Vitaly"},{"last_name":"Anoprenko","full_name":"Anoprenko, Michael","first_name":"Michael"},{"first_name":"Alexander","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","full_name":"Fedorov, Alexander","last_name":"Fedorov"},{"full_name":"Spear, Michael","last_name":"Spear","first_name":"Michael"}],"volume":281,"oa":1,"doi":"10.4230/LIPIcs.DISC.2023.35"},{"language":[{"iso":"eng"}],"_id":"12736","abstract":[{"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.","lang":"eng"}],"publication_status":"published","conference":{"name":"PPoPP: Sympopsium on Principles and Practice of Parallel Programming","start_date":"2023-02-25","end_date":"2023-03-01","location":"Montreal, QB, Canada"},"quality_controlled":"1","type":"conference_poster","day":"25","citation":{"short":"V. Aksenov, T.A. Brown, A. Fedorov, I. Kokorin, Unexpected Scaling in Path Copying Trees, Association for Computing Machinery, 2023.","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.","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>.","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>","ista":"Aksenov V, Brown TA, Fedorov A, Kokorin I. 2023. Unexpected scaling in path copying trees, Association for Computing Machinery,p.","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>","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>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["9798400700156"]},"year":"2023","date_created":"2023-03-19T23:00:58Z","title":"Unexpected scaling in path copying trees","date_published":"2023-02-25T00:00:00Z","main_file_link":[{"url":"https://doi.org/10.1145/3572848.3577512","open_access":"1"}],"oa_version":"Published Version","oa":1,"doi":"10.1145/3572848.3577512","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.","author":[{"last_name":"Aksenov","full_name":"Aksenov, Vitaly","first_name":"Vitaly"},{"first_name":"Trevor A","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","full_name":"Brown, Trevor A","last_name":"Brown"},{"first_name":"Alexander","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","full_name":"Fedorov, Alexander","last_name":"Fedorov"},{"last_name":"Kokorin","full_name":"Kokorin, Ilya","first_name":"Ilya"}],"publication":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","date_updated":"2024-10-21T06:01:21Z","month":"02","department":[{"_id":"DaAl"},{"_id":"GradSch"}],"article_processing_charge":"No","status":"public","page":"438-440","publisher":"Association for Computing Machinery","scopus_import":"1"},{"oa_version":"Published Version","title":"Provably-efficient and internally-deterministic parallel Union-Find","date_created":"2023-07-23T22:01:12Z","publication_identifier":{"isbn":["9781450395458"]},"arxiv":1,"file":[{"date_updated":"2023-07-31T10:53:08Z","file_id":"13334","creator":"dernst","relation":"main_file","checksum":"72e312aabf0c5248c99b5cd3a88e4c88","file_name":"2023_SPAA_Fedorov.pdf","success":1,"content_type":"application/pdf","date_created":"2023-07-31T10:53:08Z","file_size":2087937,"access_level":"open_access"}],"publication_status":"published","conference":{"name":"SPAA: Symposium on Parallelism in Algorithms and Architectures","start_date":"2023-06-17","end_date":"2023-06-19","location":"Orlando, FL, United States"},"publisher":"Association for Computing Machinery","tmp":{"short":"CC BY (4.0)","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)"},"corr_author":"1","article_processing_charge":"Yes (via OA deal)","month":"06","department":[{"_id":"DaAl"},{"_id":"GradSch"}],"author":[{"first_name":"Alexander","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","last_name":"Fedorov","full_name":"Fedorov, Alexander"},{"full_name":"Hashemi, Diba","last_name":"Hashemi","first_name":"Diba","id":"ed9595ea-2f8f-11ee-ba95-d2b546540783"},{"full_name":"Nadiradze, Giorgi","last_name":"Nadiradze","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","first_name":"Giorgi","orcid":"0000-0001-5634-0731"},{"last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X"}],"doi":"10.1145/3558481.3591082","oa":1,"date_published":"2023-06-17T00:00:00Z","year":"2023","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ddc":["000"],"has_accepted_license":"1","citation":{"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>.","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.","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>","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>","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.","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.","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>."},"day":"17","type":"conference","quality_controlled":"1","_id":"13262","abstract":[{"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.","lang":"eng"}],"language":[{"iso":"eng"}],"external_id":{"arxiv":["2304.09331"],"isi":["001108889000024"]},"scopus_import":"1","status":"public","page":"261-271","isi":1,"date_updated":"2025-09-09T12:43:18Z","publication":"Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures","file_date_updated":"2023-07-31T10:53:08Z"},{"doi":"10.5281/ZENODO.7877757","oa":1,"author":[{"last_name":"Koval","full_name":"Koval, Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita"},{"full_name":"Fedorov, Alexander","last_name":"Fedorov","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","first_name":"Alexander"},{"full_name":"Sokolova, Maria","last_name":"Sokolova","first_name":"Maria"},{"first_name":"Dmitry","full_name":"Tsitelov, Dmitry","last_name":"Tsitelov"},{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X"}],"date_updated":"2025-09-09T12:51:51Z","month":"04","department":[{"_id":"DaAl"}],"article_processing_charge":"No","status":"public","publisher":"Zenodo","related_material":{"record":[{"status":"public","id":"14260","relation":"used_in_publication"}]},"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."}],"_id":"14995","type":"research_data_reference","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.” 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>","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>.","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>","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>.","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.","short":"N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, D.-A. Alistarh, (2023)."},"day":"28","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2023","title":"Lincheck: A practical framework for testing concurrent data structures on JVM","date_created":"2024-02-14T15:14:13Z","date_published":"2023-04-28T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.5281/zenodo.7877757"}],"oa_version":"Published Version"}]