{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T05:12:04Z","timestamp":1788239524578,"version":"build-2803163510"},"reference-count":89,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T00:00:00Z","timestamp":1673222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2007428, 1901069"],"award-info":[{"award-number":["2007428, 1901069"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Singapore Ministry of Education Academic Research Fund","award":["Tier 1 grant"],"award-info":[{"award-number":["Tier 1 grant"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,1,9]]},"abstract":"<jats:p>\n            Happens before-based dynamic analysis is the go-to technique for detecting data races in large scale software projects due to the absence of false positive reports. However, such analyses are expensive since they employ expensive vector clock updates at each event, rendering them usable only for in-house testing. In this paper, we present a sampling-based, randomized race detector that processes only\n            <jats:italic>constantly many<\/jats:italic>\n            events of the input trace even in the worst case. This is the first\n            <jats:italic>sub-linear<\/jats:italic>\n            time (i.e., running in\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) time where\n            <jats:italic>n<\/jats:italic>\n            is the length of the trace) dynamic race detection algorithm; previous sampling based approaches like  run in linear time (i.e.,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )). Our algorithm is a property tester for -race detection \u2014 it is sound in that it never reports any false positive, and on traces that are far, with respect to hamming distance, from any race-free trace, the algorithm detects an -race with high probability. Our experimental evaluation of the algorithm and its comparison with state-of-the-art deterministic and sampling based race detectors shows that the algorithm does indeed have significantly low running time, and detects races quite often.\n          <\/jats:p>","DOI":"10.1145\/3571238","type":"journal-article","created":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T21:58:14Z","timestamp":1673474294000},"page":"1308-1337","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Dynamic Race Detection with O(1) Samples"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6832-0604","authenticated-orcid":false,"given":"Mosaad Al","family":"Thokair","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5017-2228","authenticated-orcid":false,"given":"Minjian","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7610-0660","authenticated-orcid":false,"given":"Umang","family":"Mathur","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7977-0080","authenticated-orcid":false,"given":"Mahesh","family":"Viswanathan","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,1,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2021. Intel\u00ae Inspector. https:\/\/software.intel.com\/content\/www\/us\/en\/develop\/tools\/inspector.html Accessed: 2021-11-01 \t\t\t\t  2021. Intel\u00ae Inspector. https:\/\/software.intel.com\/content\/www\/us\/en\/develop\/tools\/inspector.html Accessed: 2021-11-01"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1119479.1119480"},{"key":"e_1_2_1_3_1","unstructured":"Advanced Simulation and Computing LLNL. 2022. CORAL Benchmarks. https:\/\/asc.llnl.gov\/coral-benchmarks Accessed: 2022-04-11 \t\t\t\t  Advanced Simulation and Computing LLNL. 2022. CORAL Benchmarks. https:\/\/asc.llnl.gov\/coral-benchmarks Accessed: 2022-04-11"},{"key":"e_1_2_1_4_1","unstructured":"Advanced Simulation and Computing LLNL. 2022. CORAL Benchmarks. https:\/\/asc.llnl.gov\/coral-2-benchmarks Accessed: 2022-04-11 \t\t\t\t  Advanced Simulation and Computing LLNL. 2022. CORAL Benchmarks. https:\/\/asc.llnl.gov\/coral-2-benchmarks Accessed: 2022-04-11"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839676.1839697"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175277"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700366528"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/125826.125925"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033019.3033020"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276514"},{"key":"e_1_2_1_12_1","volume-title":"Data Races. In Proceedings of the 3rd USENIX Conference on Hot Topic in Parallelism (HotPar\u201911)","author":"Boehm J.","year":"2011","unstructured":"Hans- J. Boehm . 2011 . How to Miscompile Programs with \u201cBenign \u201d Data Races. In Proceedings of the 3rd USENIX Conference on Hot Topic in Parallelism (HotPar\u201911) . USENIX Association, USA. 3. Hans-J. Boehm. 2011. How to Miscompile Programs with \u201cBenign\u201d Data Races. In Proceedings of the 3rd USENIX Conference on Hot Topic in Parallelism (HotPar\u201911). USENIX Association, USA. 3."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 68\u201378","author":"J.","unstructured":"Hans- J. Boehm and Sarita Adve. 2008. Foundations of the C++ Concurrency Memory Model . In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 68\u201378 . Hans-J. Boehm and Sarita Adve. 2008. Foundations of the C++ Concurrency Memory Model. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 68\u201378."},{"key":"e_1_2_1_14_1","volume-title":"Pacer: Proportional Detection of Data Races. https:\/\/sourceforge.net\/p\/jikesrvm\/research-archive\/28\/ Accessed: 2021-11-01","author":"Bond Michael","year":"2021","unstructured":"Michael Bond . 2021 . Pacer: Proportional Detection of Data Races. https:\/\/sourceforge.net\/p\/jikesrvm\/research-archive\/28\/ Accessed: 2021-11-01 Michael Bond. 2021. Pacer: Proportional Detection of Data Races. https:\/\/sourceforge.net\/p\/jikesrvm\/research-archive\/28\/ Accessed: 2021-11-01"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806626"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2544173.2509519"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1736020.1736040"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236024.3236077"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA \u201998)","author":"Cheng Guang-Ien","unstructured":"Guang-Ien Cheng , Mingdong Feng , Charles E. Leiserson , Keith H. Randall , and Andrew F. Stark . 1998. Detecting Data Races in Cilk Programs That Use Locks . In Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA \u201998) . ACM, New York, NY, USA. 298\u2013309. Guang-Ien Cheng, Mingdong Feng, Charles E. Leiserson, Keith H. Randall, and Andrew F. Stark. 1998. Detecting Data Races in Cilk Programs That Use Locks. In Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA \u201998). ACM, New York, NY, USA. 298\u2013309."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512560"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2012.6237018"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755601"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10664-005-3861-2"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/EMPDP.2005.41"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250762"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1924943.1924954"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02658-4_21"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/258492.258493"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.84874"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349328"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542490"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE \u201910)","author":"Flanagan Cormac","unstructured":"Cormac Flanagan and Stephen N. Freund . 2010. The RoadRunner Dynamic Analysis Framework for Concurrent Programs . In Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE \u201910) . ACM, New York, NY, USA. 1\u20138. Cormac Flanagan and Stephen N. Freund. 2010. The RoadRunner Dynamic Analysis Framework for Concurrent Programs. In Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE \u201910). ACM, New York, NY, USA. 1\u20138."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 27th European Conference on Object-Oriented Programming (ECOOP\u201913)","author":"Flanagan Cormac","unstructured":"Cormac Flanagan and Stephen N. Freund . 2013. RedCard: Redundant Check Elimination for Dynamic Race Detectors . In Proceedings of the 27th European Conference on Object-Oriented Programming (ECOOP\u201913) . Springer-Verlag, Berlin, Heidelberg. 255\u2013280. isbn:978-3-642-39037-1 Cormac Flanagan and Stephen N. Freund. 2013. RedCard: Redundant Check Elimination for Dynamic Race Detectors. In Proceedings of the 27th European Conference on Object-Oriented Programming (ECOOP\u201913). Springer-Verlag, Berlin, Heidelberg. 255\u2013280. isbn:978-3-642-39037-1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1377492.1377495"},{"key":"e_1_2_1_35_1","volume-title":"Introduction to Property Testing","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2017. Introduction to Property Testing . Cambridge University Press . Oded Goldreich. 2017. Introduction to Property Testing. Cambridge University Press."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/10722468_15"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594315"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1999.1574"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2019.00017"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/11513988_49"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522736"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062374"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236024.3236025"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2021.16"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3126908.3126958"},{"key":"e_1_2_1_47_1","unstructured":"LLNL. 2022. ECP Proxy Applications. https:\/\/proxyapps.exascaleproject.org Accessed: 2021-04-01 \t\t\t\t  LLNL. 2022. ECP Proxy Applications. https:\/\/proxyapps.exascaleproject.org Accessed: 2021-04-01"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346281.1346323"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446711"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542491"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276515"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507734"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394783"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434317"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378475"},{"key":"e_1_2_1_56_1","unstructured":"Friedemann Mattern. 1988. Virtual Time and Global States of Distributed Systems. In Parallel and Distributed Algorithms. North-Holland 215\u2013226. \t\t\t\t  Friedemann Mattern. 1988. Virtual Time and Global States of Distributed Systems. In Parallel and Distributed Algorithms. North-Holland 215\u2013226."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1229428.1229457"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428298"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250785"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855741.1855760"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134018"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250738"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/781498.781528"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371085"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/781498.781529"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254127"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062350"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192385"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385993"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.5555\/1986308.1986334"},{"key":"e_1_2_1_71_1","unstructured":"Sandia National Laboratories. 2022. Mantevo Project. Accessed: 2022-04-11 \t\t\t\t  Sandia National Laboratories. 2022. Mantevo Project. Accessed: 2022-04-11"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/265924.265927"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-48340-1_19"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375584"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/11494881_14"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/1791194.1791203"},{"key":"e_1_2_1_77_1","doi-asserted-by":"crossref","unstructured":"Konstantin Serebryany Alexander Potapenko Timur Iskhodzhanov and Dmitry Vyukov. 2011. Dynamic Race Detection with LLVM Compiler. Google. \t\t\t\t  Konstantin Serebryany Alexander Potapenko Timur Iskhodzhanov and Dmitry Vyukov. 2011. Dynamic Race Detection with LLVM Compiler. Google.","DOI":"10.1007\/978-3-642-29860-8_9"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103702"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/582034.582042"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882291.1882300"},{"key":"e_1_2_1_81_1","volume-title":"International Conference on Runtime Verification. 368\u2013385","author":"Surendran Rishi","year":"2016","unstructured":"Rishi Surendran and Vivek Sarkar . 2016 . Dynamic determinacy race detection for task parallelism with futures . In International Conference on Runtime Verification. 368\u2013385 . Rishi Surendran and Vivek Sarkar. 2016. Dynamic determinacy race detection for task parallelism with futures. In International Conference on Runtime Verification. 368\u2013385."},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858651"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781145"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/1287624.1287654"},{"key":"e_1_2_1_85_1","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1145\/1993316.1993534","article-title":"Safe optimizations for shared-memory concurrent programs","volume":"46","author":"\u0160ev\u010d\u00edk Jaroslav","year":"2011","unstructured":"Jaroslav \u0160ev\u010d\u00edk . 2011 . Safe optimizations for shared-memory concurrent programs . SIGPLAN Notices , 46 , 6 (2011), 306 \u2013 316 . Jaroslav \u0160ev\u010d\u00edk. 2011. Safe optimizations for shared-memory concurrent programs. SIGPLAN Notices, 46, 6 (2011), 306\u2013316.","journal-title":"SIGPLAN Notices"},{"key":"e_1_2_1_86_1","volume-title":"Proceedings of the European Conference on Object-Oriented Programming (ECOOP). 27\u201351","author":"\u0160ev\u010d\u00edk Jaroslav","year":"2008","unstructured":"Jaroslav \u0160ev\u010d\u00edk and David Aspinall . 2008 . On the validity of program transformations in the Java memory model . In Proceedings of the European Conference on Object-Oriented Programming (ECOOP). 27\u201351 . Jaroslav \u0160ev\u010d\u00edk and David Aspinall. 2008. On the validity of program transformations in the Java memory model. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP). 27\u201351."},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133893"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40000.2020.00078"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2009.56"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571238","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3571238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:22Z","timestamp":1750183702000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,9]]},"references-count":89,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2023,1,9]]}},"alternative-id":["10.1145\/3571238"],"URL":"https:\/\/doi.org\/10.1145\/3571238","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,9]]},"assertion":[{"value":"2023-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}