{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,15]],"date-time":"2026-11-15T11:45:45Z","timestamp":1794743145290,"version":"4.9.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T00:00:00Z","timestamp":1780876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["VIL42117"],"award-info":[{"award-number":["VIL42117"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]},{"name":"STIBOFONDEN","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,6,8]]},"abstract":"<jats:p>\n                    Atomicity is a fundamental abstraction in concurrency, specifying that program behavior can be understood by considering specific code blocks executing atomically. However, atomicity invariants are tricky to maintain while also optimizing for code efficiency, and atomicity violations are a common root cause of many concurrency bugs. To address this problem, several dynamic techniques have been developed for testing whether a program execution adheres to an atomicity specification, most often instantiated as\n                    <jats:italic toggle=\"yes\">conflict-serializability<\/jats:italic>\n                    . The efficiency of the analysis has been targeted in various papers, with the state-of-the-art algorithms\n                    <jats:monospace>RegionTrack<\/jats:monospace>\n                    and\n                    <jats:monospace>Aerodrome<\/jats:monospace>\n                    achieving a time complexity\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mrow>\n                          <mml:mi mathvariant=\"italic\">O<\/mml:mi>\n                          <mml:mrow>\n                            <mml:mo form=\"prefix\" stretchy=\"true\">(<\/mml:mo>\n                            <mml:mi mathvariant=\"italic\">n<\/mml:mi>\n                            <mml:msup>\n                              <mml:mi mathvariant=\"italic\">k<\/mml:mi>\n                              <mml:mn>3<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo form=\"postfix\" stretchy=\"true\">)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    and\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mrow>\n                          <mml:mi mathvariant=\"italic\">O<\/mml:mi>\n                          <mml:mrow>\n                            <mml:mo form=\"prefix\" stretchy=\"true\">(<\/mml:mo>\n                            <mml:mi mathvariant=\"italic\">n<\/mml:mi>\n                            <mml:mi mathvariant=\"italic\">k<\/mml:mi>\n                            <mml:mrow>\n                              <mml:mo form=\"prefix\" stretchy=\"true\">(<\/mml:mo>\n                              <mml:mi mathvariant=\"italic\">k<\/mml:mi>\n                              <mml:mo>+<\/mml:mo>\n                              <mml:mi mathvariant=\"italic\">v<\/mml:mi>\n                              <mml:mo>+<\/mml:mo>\n                              <mml:mo mathvariant=\"italic\">\u2113<\/mml:mo>\n                              <mml:mo form=\"postfix\" stretchy=\"true\">)<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mo form=\"postfix\" stretchy=\"true\">)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    , respectively, for a trace\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mi mathvariant=\"italic\">\u03c3<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    of\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mi mathvariant=\"italic\">n<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    events,\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mi mathvariant=\"italic\">k<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    threads,\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mi mathvariant=\"italic\">v<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    locations, and\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mo mathvariant=\"italic\">\u2113<\/mml:mo>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    locks.\n                  <\/jats:p>\n                  <jats:p>\n                    In this paper we introduce\n                    <jats:monospace>AtomSanitizer<\/jats:monospace>\n                    , a new algorithm for testing conflict-serializability, with time complexity\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mrow>\n                          <mml:mi mathvariant=\"italic\">O<\/mml:mi>\n                          <mml:mrow>\n                            <mml:mo form=\"prefix\" stretchy=\"true\">(<\/mml:mo>\n                            <mml:mi mathvariant=\"italic\">n<\/mml:mi>\n                            <mml:msup>\n                              <mml:mi mathvariant=\"italic\">k<\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo form=\"postfix\" stretchy=\"true\">)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    .\n                    <jats:monospace>AtomSanitizer<\/jats:monospace>\n                    operates in an efficient streaming style, is theoretically faster than all existing algorithms, and also has a smaller memory footprint. Moreover, it is the first algorithm designed to use little locking when deployed in a concurrent monitoring setting. Experiments on standard benchmarks indicate that\n                    <jats:monospace>AtomSanitizer<\/jats:monospace>\n                    is always faster in practice than all existing conflict-serializability testers. Finally, we also implement\n                    <jats:monospace>AtomSanitizer<\/jats:monospace>\n                    inside the\n                    <jats:monospace>TSAN<\/jats:monospace>\n                    framework, for monitoring atomicity in real time. Our experiments reveal that\n                    <jats:monospace>AtomSanitizer<\/jats:monospace>\n                    incurs only a marginal time and space overhead over the data-race detection engine of\n                    <jats:monospace>TSAN<\/jats:monospace>\n                    , and thus is the first algorithm for conflict-serializability demonstrated to be suitable for a runtime monitoring setting.\n                  <\/jats:p>","DOI":"10.1145\/3808248","type":"journal-article","created":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T18:04:09Z","timestamp":1780941849000},"page":"29-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast Atomicity Monitoring"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9125-8506","authenticated-orcid":false,"given":"H\u00fcnkar Can","family":"Tun\u00e7","sequence":"first","affiliation":[{"name":"Uber, Amsterdam, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-0696-839X","authenticated-orcid":false,"given":"Yifan","family":"Dong","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-0722","authenticated-orcid":false,"given":"Andreas","family":"Pavlogiannis","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,8]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3729328"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2847"},{"key":"e_1_3_1_4_2","unstructured":"Shane Bester. 2008. Atomicity violation leading to crash in MySQL 6.0.7. MYSQL AB. https:\/\/bugs.mysql.com\/bug.php?id=38816"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360591"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594323"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1167515.1167488"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2544173.2509519"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1168918.1168866"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3627703.3650080"},{"key":"e_1_3_1_11_2","unstructured":"Jeremy Cole. 2008. Atomicity violation leading to crash in MySQL 5.4.3. MySQL AB. https:\/\/bugs.mysql.com\/bug.php?id=38883"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158113"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","unstructured":"Azadeh Farzan and P. Madhusudan. 2008. Monitoring Atomicity in Concurrent Programs. In Computer Aided Verification Aarti Gupta and Sharad Malik (Eds.). Springer Berlin Heidelberg 52\u201365. doi:10.1007\/978-3-540-70545-1_8","DOI":"10.1007\/978-3-540-70545-1_8"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/982962.964023"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542490"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1377492.1377495"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375618"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/780822.781169"},{"key":"e_1_3_1_19_2","unstructured":"Jocelyn Fournier. 2004. Atomicity violation leading to crash in MySQL 4.1.2. MySQL AB. https:\/\/bugs.mysql.com\/bug.php?id=3596"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-002-1046-6"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507766"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2021.16"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3763123"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009857"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/361227.361234"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1346281.1346323"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168864"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3412377"},{"key":"e_1_3_1_30_2","unstructured":"Umang Mathur. 2024. Rapid: Dynamic Analysis for Concurrent Programs. https:\/\/github.com\/focs-lab\/rapid. Accessed: 2024-12-03."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507734"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394783"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378475"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3742465"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/1855741.1855760"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322158"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1453101.1453121"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1508244.1508249"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371085"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385993"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2786805.2786874"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1065944.1065956"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/1791194.1791203"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/582034.582042"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/1882291.1882300"},{"key":"e_1_3_1_46_2","unstructured":"H\u00fcnkar Can Tun Yifan Dong and Andreas Pavlogiannis. 2026. Fast Atomicity Monitoring. arXiv:2604.11369 [cs.PL] https:\/\/arxiv.org\/abs\/2604.11369"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3620666.3651358"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591291"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","unstructured":"H\u00fcnkar Can Tun\u00e7 Yifan Dong and Andreas Pavlogiannis. 2026. Fast Atomicity Monitoring. doi:10.5281\/zenodo.19615809","DOI":"10.5281\/zenodo.19615809"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/780822.781145"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3808248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T10:41:58Z","timestamp":1790073718000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3808248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,8]]},"references-count":49,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2026,6,8]]}},"alternative-id":["10.1145\/3808248"],"URL":"https:\/\/doi.org\/10.1145\/3808248","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,8]]},"assertion":[{"value":"2025-10-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}