{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:03:37Z","timestamp":1767927817936,"version":"3.49.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,9,17]],"date-time":"2024-09-17T00:00:00Z","timestamp":1726531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>This article addresses the long-standing problem of program correctness for programs that describe systems of parallel executing processes. We propose a new method for proving correctness of parallel implementations of high-level models expressed as transition systems. The implementation language underlying the method is based on the concurrency model of actors and active objects. The method defines program correctness in terms of a simulation relation between the transition system that specifies the program semantics of the parallel program and the transition system that is described by the correctness specification. The simulation relation itself abstracts from the fine-grained interleaving of parallel processes by exploiting a global confluence property of the concurrency model of the implementation language considered in this article. As a proof of concept, we apply our method to the correctness of a parallel simulator of multicore memory systems.<\/jats:p>\n          <jats:p\/>","DOI":"10.1145\/3660630","type":"journal-article","created":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T10:24:03Z","timestamp":1713608643000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Proving Correctness of Parallel Implementations of Transition System Models"],"prefix":"10.1145","volume":"46","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3950-6271","authenticated-orcid":false,"given":"Frank","family":"de Boer","sequence":"first","affiliation":[{"name":"CWI, Amsterdam, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5382-3949","authenticated-orcid":false,"given":"Einar Broch","family":"Johnsen","sequence":"additional","affiliation":[{"name":"University of Oslo, Oslo, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8763-5548","authenticated-orcid":false,"given":"Violet Ka I","family":"Pun","sequence":"additional","affiliation":[{"name":"Western Norway University of Applied Sciences, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9948-2748","authenticated-orcid":false,"given":"Silvia Lizeth","family":"Tapia Tarifa","sequence":"additional","affiliation":[{"name":"University of Oslo, Oslo, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,9,17]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195881"},{"key":"e_1_3_3_3_2","volume-title":"ACTORS\u2014A Model of Concurrent Computation in Distributed Systems","author":"Agha Gul A.","year":"1990","unstructured":"Gul A. Agha. 1990. ACTORS\u2014A Model of Concurrent Computation in Distributed Systems. MIT Press."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54862-8_46"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/S11761-013-0148-0"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892236"},{"key":"e_1_3_3_7_2","volume-title":"Foundations of Multithreaded, Parallel, and Distributed Programming","author":"Andrews Gregory R.","year":"2000","unstructured":"Gregory R. Andrews. 2000. Foundations of Multithreaded, Parallel, and Distributed Programming. Addison Wesley."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90185-I"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67262-5_11"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-16722-6_20"},{"key":"e_1_3_3_11_2","volume-title":"Deployment by Construction for Multicore Architectures with Locks","author":"Bijo Shiji","year":"2018","unstructured":"Shiji Bijo, Einar Broch Johnsen, Ka I Pun, Christoph Seidl, and Silvia Lizeth Tapia Tarifa. 2018. Deployment by Construction for Multicore Architectures with Locks. Research Report 491. Department of Informatics, University of Oslo."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03418-4_26"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44802-2_3"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68034-7_4"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.SCICO.2019.04.003"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2024716.2024718"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/S11334-012-0184-5"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676982"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063454"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71999-1"},{"key":"e_1_3_3_21_2","volume-title":"Parallel Computer Architecture\u2014A Hardware\/Software Approach","author":"Culler David E.","year":"1999","unstructured":"David E. Culler, Jaswinder Pal Singh, and Anoop Gupta. 1999. Parallel Computer Architecture\u2014A Hardware\/Software Approach. Morgan Kaufmann."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54494-5_25"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00165-020-00527-y"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3122848"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/S10817-017-9426-4"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44482-6_8"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21401-6_35"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2014.10.001"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103719"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/1795772"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40615-7_1"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/1624775.1624804"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25271-6_8"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-47169-3_39"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2014.07.001"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.14279\/tuj.eceasst.76.1070"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.SCICO.2018.07.001"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2023.102928"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.310.8"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1538788.1538814"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-009-9155-4"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2009.32"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC2.2017.32"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49665-7_4"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/1105734.1105747"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.018"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.08.004"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2010.5416635"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/319301.319345"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-6687-0"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlap.2004.03.009"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.3233\/978-1-61499-810-5-186"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-78142-2_1"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.SCICO.2022.102861"},{"key":"e_1_3_3_55_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/978-3-319-90089-6_8","volume-title":"It\u2019s All About Coordination\u2014Essays to Celebrate the Lifelong Scientific Achievements of Farhad Arbab,","author":"Schlatte Rudolf","year":"2018","unstructured":"Rudolf Schlatte, Einar Broch Johnsen, Jacopo Mauro, Silvia Lizeth Tapia Tarifa, and Ingrid Chieh Yu. 2018. Release the beasts: When formal methods meet real world data. In It\u2019s All About Coordination\u2014Essays to Celebrate the Lifelong Scientific Achievements of Farhad Arbab,Lecture Notes in Computer Science, Vol. 10865. Springer, 107\u2013121."},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.03.026"},{"issue":"4","key":"e_1_3_3_57_2","first-page":"385","article-title":"Modeling and verification of reactive systems using Rebeca","volume":"63","author":"Sirjani Marjan","year":"2004","unstructured":"Marjan Sirjani, Ali Movaghar, Amin Shali, and Frank S. de Boer. 2004. Modeling and verification of reactive systems using Rebeca. Fundam. Inf. 63, 4 (2004), 385\u2013410.http:\/\/content.iospress.com\/articles\/fundamenta-informaticae\/fi63-4-05","journal-title":"Fundam. Inf."},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1201\/b20200"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.2200\/S00346ED1V01Y201104CAC016"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2023.111750"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45234-6_7"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3660630","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3660630","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:21Z","timestamp":1750287021000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3660630"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,17]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3660630"],"URL":"https:\/\/doi.org\/10.1145\/3660630","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,17]]},"assertion":[{"value":"2022-11-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-31","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}