{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,28]],"date-time":"2026-08-28T03:17:57Z","timestamp":1787887077902,"version":"build-2784847793"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2026,8,27]],"date-time":"2026-08-27T00:00:00Z","timestamp":1787788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"VILLUM FONDEN, and by a research grant from STIBOFONDEN","award":["VIL42117"],"award-info":[{"award-number":["VIL42117"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Syst."],"published-print":{"date-parts":[[2026,8,31]]},"abstract":"<jats:p>\n                    Dynamic analyses are a standard approach to analyzing and testing concurrent programs. Such techniques observe program traces \u03c3 and analyze them to infer the presence or absence of bugs. At its core, each analysis maintains a partial order\n                    <jats:italic toggle=\"yes\">P<\/jats:italic>\n                    that represents order dependencies between the events of \u03c3. Naturally, the scalability of the analysis largely depends on maintaining\n                    <jats:italic toggle=\"yes\">P<\/jats:italic>\n                    efficiently. The standard data structure for this task has thus far been Vector Clocks. These, however, are slow for analyses that follow a non-streaming style, costing\n                    <jats:italic toggle=\"yes\">O(n)<\/jats:italic>\n                    time for inserting (and propagating) each new ordering in\n                    <jats:italic toggle=\"yes\">P<\/jats:italic>\n                    , where\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    is the size of \u03c3, while they cannot handle the deletion of existing orderings.\n                  <\/jats:p>\n                  <jats:p>\n                    In this article, we develop\n                    <jats:italic toggle=\"yes\">Collective Sparse Segment Trees<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">CSSTs<\/jats:italic>\n                    ), a simple but elegant data structure for maintaining a partial order\n                    <jats:italic toggle=\"yes\">P<\/jats:italic>\n                    . CSSTs thrive when the width\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    of\n                    <jats:italic toggle=\"yes\">P<\/jats:italic>\n                    is much smaller than the size\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    of its domain, allowing inserting, deleting, and querying for orderings in\n                    <jats:italic toggle=\"yes\">P<\/jats:italic>\n                    to run in\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) time. For a concurrent trace,\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    normally equals the number of its threads, and is orders of magnitude smaller than its size\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    , making CSSTs fitting for this setting. Our experiments confirm that CSSTs are the best data structure currently to handle a range of dynamic analyses from existing literature.\n                  <\/jats:p>","DOI":"10.1145\/3773085","type":"journal-article","created":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T09:22:34Z","timestamp":1761816154000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Dynamic Concurrency Analysis with Collective Sparse Segment Trees"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9125-8506","authenticated-orcid":false,"given":"H\u00fcnkar Can","family":"Tun\u00e7","sequence":"first","affiliation":[{"name":"Computer Science, Aarhus Universitet","place":["Aarhus, Denmark"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-0696-839X","authenticated-orcid":false,"given":"Yifan","family":"Dong","sequence":"additional","affiliation":[{"name":"Computer Science, Aarhus Universitet","place":["Aarhus, Denmark"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-6393-9188","authenticated-orcid":false,"given":"Ameya Prashant","family":"Deshmukh","sequence":"additional","affiliation":[{"name":"IIT Bombay","place":["Mumbai, India"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4261-090X","authenticated-orcid":false,"given":"Berk","family":"Cirisci","sequence":"additional","affiliation":[{"name":"Amazon Web Services Germany GmbH","place":["Berlin, Germany"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2727-8865","authenticated-orcid":false,"given":"Constantin","family":"Enea","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Paris","place":["Paris, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-0722","authenticated-orcid":false,"given":"Andreas","family":"Pavlogiannis","sequence":"additional","affiliation":[{"name":"Computer Science, Aarhus Universitet","place":["Aarhus, Denmark"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,8,27]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"2024. CSSTs GitHub Repository. https:\/\/github.com\/hcantunc\/cssts. Last accessed: November 16 2025."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360576"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073818"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81685-8_16"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40104-6_4"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360591"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594323"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485541"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3468264.3468549"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632908"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158119"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44681-8_73"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-53288-8_17"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062342"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3290373"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542490"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375618"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575729"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279614"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180225"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276516"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359638"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446711"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276515"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507734"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394783"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378475"},{"key":"e_1_3_2_30_2","first-page":"215","volume-title":"Parallel and Distributed Algorithms: Proceedings of the International Workshop on Parallel & Distributed Algorithms","author":"Mattern Friedemann","year":"1989","unstructured":"Friedemann Mattern. 1989. Virtual time and global states of distributed systems. In Parallel and Distributed Algorithms: Proceedings of the International Workshop on Parallel & Distributed Algorithms, M. Cosnard et\u00a0al. (Ed.). Elsevier Science Publishers B. V., 215\u2013226."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/1855741.1855760"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509514"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371085"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385993"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192385"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/11817963_46"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1791194.1791203"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1785414.1785443"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","unstructured":"Zheng Shi Umang Mathur and Andreas Pavlogiannis. 2024. Optimistic prediction of synchronization-reversal data races. In Proceedings of the IEEE\/ACM 46th International Conference on Software Engineering (Lisbon Portugal) (ICSE\u201924). Association for Computing Machinery New York NY USA Article 134 13 pages. 10.1145\/3597503.3639099","DOI":"10.1145\/3597503.3639099"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591251"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","unstructured":"H\u00fcnkar Can Tun\u00e7 Ameya Prashant Deshmukh Berk Cirisci Constantin Enea and Andreas Pavlogiannis. 2024. CSSTs: A dynamic data structure for partial orders in concurrent execution analysis. InProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS\u201924 Vol. 3). ACM New York NY USA 223\u2013238. DOI:10.1145\/3620666.3651358","DOI":"10.1145\/3620666.3651358"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591291"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3468264.3468572"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59152-6_20"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25543-5_16"}],"container-title":["ACM Transactions on Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3773085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,28]],"date-time":"2026-08-28T02:37:20Z","timestamp":1787884640000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3773085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,27]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,8,31]]}},"alternative-id":["10.1145\/3773085"],"URL":"https:\/\/doi.org\/10.1145\/3773085","relation":{},"ISSN":["0734-2071","1557-7333"],"issn-type":[{"value":"0734-2071","type":"print"},{"value":"1557-7333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,27]]},"assertion":[{"value":"2025-02-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-08-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}