{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T10:22:32Z","timestamp":1790936552267,"version":"4.1.0"},"reference-count":96,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T00:00:00Z","timestamp":1767830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"National Cybersecurity R&D Programme","award":["NRF-NCR25-Fuzz-0001"],"award-info":[{"award-number":["NRF-NCR25-Fuzz-0001"]}]},{"DOI":"10.13039\/100008398","name":"VILLUM FONDEN","doi-asserted-by":"crossref","award":["VIL42117"],"award-info":[{"award-number":["VIL42117"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]},{"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,1,8]]},"abstract":"<jats:p>\n                    A key computational question underpinning the automated testing and verification of concurrent programs is the\n                    <jats:italic toggle=\"yes\">consistency question<\/jats:italic>\n                    \u2014\n                    <jats:italic toggle=\"yes\">given a partial execution history, can it be completed in a consistent manner?<\/jats:italic>\n                    Due to its importance, consistency testing has been studied extensively for memory models, as well as for database isolation levels. A common theme in all these settings is the use of shared-memory as the primal mode of interthread communication. On the other hand, modern programming languages, such as Go, Rust and Kotlin, advocate a paradigm shift towards channel-based (i.e., message-passing) communication. However, the consistency question for channel-based concurrency is currently poorly understood.\n                  <\/jats:p>\n                  <jats:p>\n                    In this paper we lift the study of fundamental consistency problems to channels, taking into account various input parameters, such as the number of threads executing, the number of channels, and the channel capacities. We draw a rich complexity landscape, including upper bounds that become polynomial when certain input parameters are fixed, as well as hardness lower bounds. Our upper bounds are based on algorithms that can drive the verification of channel consistency in automated verification tools. Our lower bounds characterize minimal input parameters that are sufficient for hardness to arise, and thus shed light on the intricacies of testing channel-based concurrency. In combination, our upper and lower bounds characterize the boundary of\n                    <jats:italic toggle=\"yes\">tractability\/intractability<\/jats:italic>\n                    of verifying channel consistency, and imply that our algorithms are often (nearly) optimal. We have also implemented our main consistency checking algorithm and designed optimizations to enhance its performance. We evaluated the performance of our implementation over a set of 103 instances obtained from open source Go projects, and compared it against a constraint-solving based algorithm. Our experimental results demonstrate the power of our consistency-checking algorithm; it scales to around 1M events, and is significantly faster in running-time performance, compared to a constraint-solving approach.\n                  <\/jats:p>","DOI":"10.1145\/3776643","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T18:59:43Z","timestamp":1767898783000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Testing Message-Passing Concurrency"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5021-7134","authenticated-orcid":false,"given":"Zheng","family":"Shi","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-9670-7039","authenticated-orcid":false,"given":"Lasse","family":"M\u00f8ldrup","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"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, Singapore"}],"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,1,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535845"},{"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\/3276505"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3729328"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81685-8_16"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19835-9_5"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2627752"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.09.034"},{"key":"e_1_3_2_10_2","unstructured":"Zhendong Ang Azadeh Farzan and Umang Mathur. 2025. Enhanced Data Race Prediction Through Modular Reasoning. arXiv:2504.10813 [cs.PL] https:\/\/arxiv.org\/abs\/2504.10813"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632915"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-65630-9_9"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90002-4"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25543-5_19"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360591"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485546"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.014"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_28"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591243"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485541"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2005.86"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523720"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523720"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632908"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158119"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360550"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.44"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2020.42"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632929"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3571248"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASE51524.2021.9678571"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25543-5_30"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3689778"},{"key":"e_1_3_2_35_2","unstructured":"Erlang developing team Erlang developers. 2024. Erlang documentations. https:\/\/www.erlang.org\/doc\/system\/conc_prog.html."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632873"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542490"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375618"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2014.27"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2005.25"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-002-1046-6"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/181014.181328"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279614"},{"key":"e_1_3_2_44_2","unstructured":"Go developing team Go developers. 2024. channel features in Go. https:\/\/github.com\/golang\/go\/blob\/master\/src\/runtime\/chan.go."},{"key":"e_1_3_2_45_2","unstructured":"Go developing team Go developers. 2024. channel features in Go. https:\/\/go.dev\/tour\/concurrency\/2."},{"key":"e_1_3_2_46_2","unstructured":"Go developing team Go developers. 2024. Effective Go. https:\/\/golang.org\/doc\/effective_go.html."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.588521"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.41"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594315"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASE56229.2023.00086"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276516"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062374"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90002-4"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3498711"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81685-8_20"},{"key":"e_1_3_2_57_2","unstructured":"Kotlin developing team Kotlin developers. 2024. Kotlin documentations. https:\/\/kotlinlang.org\/docs\/channels.html."},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2021.16"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_25"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3763123"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454073"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507753"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446711"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_66"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2006.1598123"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276515"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394783"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434317"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378475"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/3742465"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/3627535.3638487"},{"key":"e_1_3_2_72_2","volume-title":"8th USENIX Symposium on Operating Systems Design and Implementation (OSDI 08)","author":"Musuvathi Madanlal","year":"2008","unstructured":"Madanlal Musuvathi, Shaz Qadeer, Thomas Ball, Gerard Basler, Piramanayagam Arumuga Nainar, and Iulian Neamtiu. 2008. Finding and Reproducing Heisenbugs in Concurrent Programs. In 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI 08). USENIX Association, San Diego, CA. https:\/\/www.usenix.org\/conference\/osdi-08\/finding-and-reproducing-heisenbugs-concurrent-programs"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371085"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99527-0_24"},{"key":"e_1_3_2_75_2","unstructured":"Rust developing team Rust developers. 2024. Rust documentations. https:\/\/doc.rust-lang.org\/std\/index.html."},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.5555\/1986308.1986334"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1145\/3676641.3715990"},{"key":"e_1_3_2_78_2","unstructured":"Scala developing team Scala developers. 2024. Scala documentations. https:\/\/www.scala-lang.org\/api\/3.4.2\/docs\/index.html."},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.1145\/1791194.1791203"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3639099"},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","unstructured":"Zheng Shi Lasse M\u00f8ldrup Umang Mathur and Andreas Pavlogiannis. 2025. Artifact. doi:10.5281\/zenodo.18091491","DOI":"10.5281\/zenodo.18091491"},{"key":"e_1_3_2_82_2","unstructured":"Zheng Shi Lasse M\u00f8ldrup Umang Mathur and Andreas Pavlogiannis. 2025. Technical report. arXiv preprint arXiv:2505.05162 (2025). https:\/\/arxiv.org\/abs\/2505.05162"},{"key":"e_1_3_2_83_2","doi-asserted-by":"publisher","DOI":"10.1145\/3364452.3364457"},{"key":"e_1_3_2_84_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70389-3_6"},{"key":"e_1_3_2_85_2","doi-asserted-by":"publisher","DOI":"10.1145\/3236950.3236959"},{"key":"e_1_3_2_86_2","doi-asserted-by":"publisher","DOI":"10.1145\/3236950.3236959"},{"key":"e_1_3_2_87_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304069"},{"key":"e_1_3_2_88_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591251"},{"key":"e_1_3_2_89_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 (ASPLOS \u201924 Vol. 3). Association for Computing Machinery New York NY USA 223\u2013238. doi:10.1145\/3620666.3651358","DOI":"10.1145\/3620666.3651358"},{"key":"e_1_3_2_90_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591291"},{"key":"e_1_3_2_91_2","doi-asserted-by":"publisher","DOI":"10.1145\/3620666.3651358"},{"key":"e_1_3_2_92_2","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510178"},{"key":"e_1_3_2_93_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_2_94_2","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640389"},{"key":"e_1_3_2_95_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-37703-7_13"},{"key":"e_1_3_2_96_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370317"},{"key":"e_1_3_2_97_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59152-6_20"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3776643","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T13:42:39Z","timestamp":1784209359000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3776643"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":96,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2026,1,8]]}},"alternative-id":["10.1145\/3776643"],"URL":"https:\/\/doi.org\/10.1145\/3776643","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-06-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}