{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,21]],"date-time":"2026-11-21T19:43:51Z","timestamp":1795290231388,"version":"4.10.3"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T00:00:00Z","timestamp":1576800000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["J-4220"],"award-info":[{"award-number":["J-4220"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>\n            Writing concurrent programs is highly error-prone due to the nondeterminism in interprocess communication. The most reliable indicators of errors in concurrency are\n            <jats:italic>data races<\/jats:italic>\n            , which are accesses to a shared resource that can be executed concurrently. We study the problem of predicting data races in lock-based concurrent programs. The input consists of a concurrent trace\n            <jats:italic>t<\/jats:italic>\n            , and the task is to determine all pairs of events of\n            <jats:italic>t<\/jats:italic>\n            that constitute a data race. The problem lies at the heart of concurrent verification and has been extensively studied for over three decades. However, existing polynomial-time sound techniques are highly incomplete and can miss simple races.\n          <\/jats:p>\n          <jats:p>\n            In this work we develop\n            <jats:italic>M<\/jats:italic>\n            2: a new polynomial-time algorithm for this problem, which has no false positives. In addition, our algorithm is\n            <jats:italic>complete<\/jats:italic>\n            for input traces that consist of two processes, i.e., it provably detects\n            <jats:italic>all<\/jats:italic>\n            races in the trace. We also develop sufficient criteria for detecting completeness\n            <jats:italic>dynamically<\/jats:italic>\n            in cases of more than two processes. We make an experimental evaluation of our algorithm on a challenging set of benchmarks taken from recent literature on the topic. Our algorithm soundly reports\n            <jats:italic>hundreds<\/jats:italic>\n            of real races, many of which are missed by existing methods. In addition, using our dynamic completeness criteria,\n            <jats:italic>M<\/jats:italic>\n            2 concludes that it has detected\n            <jats:italic>all<\/jats:italic>\n            races in the benchmark set, hence the reports are both sound and complete. Finally, its running times are comparable, and often smaller than the theoretically fastest, yet highly incomplete, existing methods. To our knowledge,\n            <jats:italic>M<\/jats:italic>\n            2 is the first sound algorithm that achieves such a level of performance on both running time and completeness of the reported races.\n          <\/jats:p>","DOI":"10.1145\/3371085","type":"journal-article","created":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T19:45:25Z","timestamp":1576871125000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["Fast, sound, and effectively complete dynamic race prediction"],"prefix":"10.1145","volume":"4","author":[{"given":"Andreas","family":"Pavlogiannis","sequence":"first","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,12,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147403.1147416"},{"key":"e_1_2_2_2_1","doi-asserted-by":"crossref","unstructured":"Stephen M. Blackburn Robin Garner Chris Hoffmann Asjad M. Khang Kathryn S. McKinley Rotem Bentzur Amer Diwan Daniel Feinberg Daniel Frampton Samuel Z. Guyer Martin Hirzel Antony Hosking Maria Jump Han Lee J. Eliot B. Moss Aashish Phansalkar Darko Stefanovi\u0107 Thomas VanDrunen Daniel von Dincklage and Ben Wiedermann. 2006. The DaCapo Benchmarks: Java Benchmarking Development and Analysis. In OOPSLA.  Stephen M. Blackburn Robin Garner Chris Hoffmann Asjad M. Khang Kathryn S. McKinley Rotem Bentzur Amer Diwan Daniel Feinberg Daniel Frampton Samuel Z. Guyer Martin Hirzel Antony Hosking Maria Jump Han Lee J. Eliot B. Moss Aashish Phansalkar Darko Stefanovi\u0107 Thomas VanDrunen Daniel von Dincklage and Ben Wiedermann. 2006. The DaCapo Benchmarks: Java Benchmarking Development and Analysis. In OOPSLA.","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806626"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1770351.1770387"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1368088.1368119"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512560"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45718-6_81"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/122759.122767"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250762"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/838237.838485"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02658-4_21"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380240306"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542490"},{"key":"e_1_2_2_14_1","volume-title":"Bond","author":"Gen\u00e7 Kaan","year":"2019"},{"key":"e_1_2_2_15_1","volume-title":"Why Do Computers Stop And What Can Be Done About It? B\u00fcroautomation","author":"Gray Jim","year":"1985"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.1991.184003"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594315"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786805.2786840"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11513988_49"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2009.82"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062374"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009857"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2931037.2931046"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353535.1346323"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542491"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276515"},{"key":"e_1_2_2_28_1","volume-title":"Parallel and Distributed Algorithms: proceedings of the International Workshop on Parallel &amp","author":"Mattern Friedemann"},{"key":"e_1_2_2_29_1","volume-title":"Advances in Petri Nets","author":"Mazurkiewicz A","year":"1986"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855741.1855760"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134018"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/966049.781528"},{"key":"e_1_2_2_33_1","unstructured":"Andreas Pavlogiannis. 2019. Fast Sound and Effectively Complete Dynamic Race Detection. (2019). arXiv: arXiv:1901.08857  Andreas Pavlogiannis. 2019. Fast Sound and Effectively Complete Dynamic Race Detection. (2019). arXiv: arXiv:1901.08857"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/966049.781529"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1889997.1890000"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254127"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192385"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1986308.1986334"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/265924.265927"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/73141.74844"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375584"},{"key":"e_1_2_2_42_1","volume-title":"Formal Methods for Open Object-Based Distributed Systems","author":"Sen Koushik"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869459.1869474"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103702"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/582034.582042"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882291.1882300"},{"key":"e_1_2_2_47_1","unstructured":"SPEC. 2008. SPEC releases free SPECjvm2008 benchmark. (2008). https:\/\/www.spec.org\/jvm2008\/press\/release.html  SPEC. 2008. SPEC releases free SPECjvm2008 benchmark. (2008). https:\/\/www.spec.org\/jvm2008\/press\/release.html"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/504282.504288"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1287624.1287654"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05089-3_17"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-018-0579-5"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095809.1095832"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2338965.2336780"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371085","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:43Z","timestamp":1750273543000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,20]]},"references-count":53,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1145\/3371085"],"URL":"https:\/\/doi.org\/10.1145\/3371085","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,20]]},"assertion":[{"value":"2019-12-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}