{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:06:20Z","timestamp":1767927980929,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T00:00:00Z","timestamp":1658275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"SERB","award":["MTR\/2019\/000095"],"award-info":[{"award-number":["MTR\/2019\/000095"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538445","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"482-492","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Parameterized Verification under Release Acquire is PSPACE-complete"],"prefix":"10.1145","author":[{"given":"Shankaranarayanan","family":"Krishna","sequence":"first","affiliation":[{"name":"Indian Institute of Technology, Bombay, Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adwait","family":"Godbole","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roland","family":"Meyer","sequence":"additional","affiliation":[{"name":"TU Braunschweig, Braunschweig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Soham","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"TU Delft, Delft, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"crossref","unstructured":"P. A. Abdulla J. Arora M. F. Atig and S. N. Krishna. 2019. Verification of programs under the release-acquire semantics. In PLDI. ACM 1117--1132.  P. A. Abdulla J. Arora M. F. Atig and S. N. Krishna. 2019. Verification of programs under the release-acquire semantics. In PLDI. ACM 1117--1132.","DOI":"10.1145\/3314221.3314649"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434337"},{"key":"e_1_3_2_2_3_1","volume-title":"Ahmed Bouajjani, and Tuan Phong Ngo.","author":"Abdulla Parosh Aziz","year":"2018","unstructured":"Parosh Aziz Abdulla , Mohamed Faouzi Atig , Ahmed Bouajjani, and Tuan Phong Ngo. 2018 . A Load-Buffer Semantics for Total Store Ordering. Log. Methods Comput. Sci . 14, 1 (2018). https:\/\/doi.org\/10.23638\/LMCS-14(1:9)2018 10.23638\/LMCS-14(1:9)2018 Parosh Aziz Abdulla, Mohamed Faouzi Atig, Ahmed Bouajjani, and Tuan Phong Ngo. 2018. A Load-Buffer Semantics for Total Store Ordering. Log. Methods Comput. Sci. 14, 1 (2018). https:\/\/doi.org\/10.23638\/LMCS-14(1:9)2018"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371094"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1993.287591"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01784241"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627752"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627752"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706299.1706303"},{"key":"e_1_3_2_2_10_1","volume-title":"ESOP 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Tallinn, Estonia, March 24 - April 1, 2012. Proceedings (Lecture Notes in Computer Science","volume":"46","author":"Atig Mohamed Faouzi","year":"2012","unstructured":"Mohamed Faouzi Atig , Ahmed Bouajjani , Sebastian Burckhardt , and Madanlal Musuvathi . 2012 . What's Decidable about Weak Memory Models?. In Programming Languages and Systems - 21st European Symposium on Programming , ESOP 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Tallinn, Estonia, March 24 - April 1, 2012. Proceedings (Lecture Notes in Computer Science , Vol. 7211), Helmut Seidl (Ed.). Springer, 26-- 46 . https:\/\/doi.org\/10.1007\/978--3--642--28869--2_2 10.1007\/978--3--642--28869--2_2 Mohamed Faouzi Atig, Ahmed Bouajjani, Sebastian Burckhardt, and Madanlal Musuvathi. 2012. What's Decidable about Weak Memory Models?. In Programming Languages and Systems - 21st European Symposium on Programming, ESOP 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Tallinn, Estonia, March 24 - April 1, 2012. Proceedings (Lecture Notes in Computer Science, Vol. 7211), Helmut Seidl (Ed.). Springer, 26--46. https:\/\/doi.org\/10.1007\/978--3--642--28869--2_2"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3376902"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1925844.1926394"},{"key":"e_1_3_2_2_13_1","volume-title":"Robustness Against Transactional Causal Consistency. In 30th International Conference on Concurrency Theory, CONCUR 2019","author":"Beillahi Sidi Mohamed","year":"2019","unstructured":"Sidi Mohamed Beillahi , Ahmed Bouajjani , and Constantin Enea . 2019 . Robustness Against Transactional Causal Consistency. In 30th International Conference on Concurrency Theory, CONCUR 2019 , August 27 --30 , 2019, Amsterdam, the Netherlands. 30:1--30:18. https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2019.30 10.4230\/LIPIcs.CONCUR.2019.30 Sidi Mohamed Beillahi, Ahmed Bouajjani, and Constantin Enea. 2019. Robustness Against Transactional Causal Consistency. In 30th International Conference on Concurrency Theory, CONCUR 2019, August 27--30, 2019, Amsterdam, the Netherlands. 30:1--30:18. https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2019.30"},{"key":"e_1_3_2_2_14_1","volume-title":"Horn clause solvers for program verification","author":"Bj\u00f8rner Nikolaj","unstructured":"Nikolaj Bj\u00f8rner , Arie Gurfinkel , Ken McMillan , and Andrey Rybalchenko . 2015. Horn clause solvers for program verification . In Fields of Logic and Computation II. Springer , 24--51. Nikolaj Bj\u00f8rner, Arie Gurfinkel, Ken McMillan, and Andrey Rybalchenko. 2015. Horn clause solvers for program verification. In Fields of Logic and Computation II. Springer, 24--51."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38856-9_8"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951860.2951873"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009888"},{"key":"e_1_3_2_2_18_1","volume-title":"Logic Programming and Databases","author":"Ceri Stefano","unstructured":"Stefano Ceri , Georg Gottlob , and Letizia Tanca . 1990. Syntax and semantics of datalog . In Logic Programming and Databases . Springer , 77--93. Stefano Ceri, Georg Gottlob, and Letizia Tanca. 1990. Syntax and semantics of datalog. In Logic Programming and Databases. Springer, 77--93."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011276507260"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2842603"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00102-X"},{"key":"e_1_3_2_2_22_1","volume-title":"Shankara Narayanan Krishna, and Roland Meyer","author":"Godbole Adwait","year":"2021","unstructured":"Adwait Godbole , Shankara Narayanan Krishna, and Roland Meyer . 2021 . Safety Verification of Parameterized Systems under Release-Acquire . https:\/\/doi.org\/ 10.48550\/ARXIV.2101.12123 10.48550\/ARXIV.2101.12123 Adwait Godbole, Shankara Narayanan Krishna, and Roland Meyer. 2021. Safety Verification of Parameterized Systems under Release-Acquire. https:\/\/doi.org\/ 10.48550\/ARXIV.2101.12123"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00012-9"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-017-0518-x"},{"key":"e_1_3_2_2_25_1","volume-title":"Descriptive complexity","author":"Immerman Neil","unstructured":"Neil Immerman . 2012. Descriptive complexity . Springer Science & Business Media . Neil Immerman. 2012. Descriptive complexity. Springer Science & Business Media."},{"key":"e_1_3_2_2_26_1","volume-title":"Strong Logic for Weak Memory: Reasoning About Release- Acquire Consistency in Iris. In 31st European Conference on Object-Oriented Programming, ECOOP 2017","volume":"29","author":"Kaiser Jan-Oliver","year":"2017","unstructured":"Jan-Oliver Kaiser , Hoang-Hai Dang , Derek Dreyer , Ori Lahav , and Viktor Vafeiadis . 2017 . Strong Logic for Weak Memory: Reasoning About Release- Acquire Consistency in Iris. In 31st European Conference on Object-Oriented Programming, ECOOP 2017 , June 19 --23 , 2017, Barcelona, Spain (LIPIcs, Vol. 74), Peter M\u00fcller (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1--17: 29 . https:\/\/doi.org\/10.4230\/LIPIcs.ECOOP.2017.17 10.4230\/LIPIcs.ECOOP.2017.17 Jan-Oliver Kaiser, Hoang-Hai Dang, Derek Dreyer, Ori Lahav, and Viktor Vafeiadis. 2017. Strong Logic for Weak Memory: Reasoning About Release- Acquire Consistency in Iris. In 31st European Conference on Object-Oriented Programming, ECOOP 2017, June 19--23, 2017, Barcelona, Spain (LIPIcs, Vol. 74), Peter M\u00fcller (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1--17:29. https:\/\/doi.org\/10.4230\/LIPIcs.ECOOP.2017.17"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"crossref","unstructured":"Jeehoon Kang Chung-Kil Hur Ori Lahav Viktor Vafeiadis and Derek Dreyer. 2017. A promising semantics for relaxed-memory concurrency. In POPL. ACM 175--189.  Jeehoon Kang Chung-Kil Hur Ori Lahav Viktor Vafeiadis and Derek Dreyer. 2017. A promising semantics for relaxed-memory concurrency. In POPL. ACM 175--189.","DOI":"10.1145\/3093333.3009850"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158105"},{"key":"e_1_3_2_2_29_1","unstructured":"Christos Kozyrakis. [n.d.]. Phoenix 2.0 Benchmarks. https:\/\/github.com\/kozyraki\/ phoenix.  Christos Kozyrakis. [n.d.]. Phoenix 2.0 Benchmarks. https:\/\/github.com\/kozyraki\/ phoenix."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3326938.3326942"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385966"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837643"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Ori Lahav Nick Giannarakis and Viktor Vafeiadis. 2016. Taming release-acquire consistency. In POPL. ACM 649--662.  Ori Lahav Nick Giannarakis and Viktor Vafeiadis. 2016. Taming release-acquire consistency. In POPL. ACM 649--662.","DOI":"10.1145\/2914770.2837643"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314604"},{"key":"e_1_3_2_2_35_1","volume-title":"ICALP (LNCS","volume":"323","author":"Lahav Ori","year":"2015","unstructured":"Ori Lahav and Viktor Vafeiadis . 2015 . Owicki-Gries Reasoning forWeak Memory Models . In ICALP (LNCS , Vol. 9135). Springer, 311-- 323 . Ori Lahav and Viktor Vafeiadis. 2015. Owicki-Gries Reasoning forWeak Memory Models. In ICALP (LNCS, Vol. 9135). Springer, 311--323."},{"key":"e_1_3_2_2_36_1","volume-title":"Andersen","author":"Lloyd Wyatt","year":"2011","unstructured":"Wyatt Lloyd , Michael J. Freedman , Michael Kaminsky , and David G . Andersen . 2011 . Don't settle for eventual: scalable causal consistency for wide-area storage with COPS.. In SOSP, Ted Wobber and Peter Druschel (Eds.). ACM , 401--416. http:\/\/dblp.uni-trier.de\/db\/conf\/sosp\/sosp2011.html#LloydFKA11 Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. 2011. Don't settle for eventual: scalable causal consistency for wide-area storage with COPS.. In SOSP, Ted Wobber and Peter Druschel (Eds.). ACM, 401--416. http:\/\/dblp.uni-trier.de\/db\/conf\/sosp\/sosp2011.html#LloydFKA11"},{"key":"e_1_3_2_2_37_1","unstructured":"Brian Norris. [n.d.]. Model Checker Benchmarks. https:\/\/github.com\/ computersforpeace\/model-checker-benchmarks.  Brian Norris. [n.d.]. Model Checker Benchmarks. https:\/\/github.com\/ computersforpeace\/model-checker-benchmarks."},{"key":"e_1_3_2_2_38_1","volume-title":"Operational Aspects of C\/C++ Concurrency. CoRR abs\/1606.01400","author":"Podkopaev Anton","year":"2016","unstructured":"Anton Podkopaev , Ilya Sergey , and Aleksandar Nanevski . 2016. Operational Aspects of C\/C++ Concurrency. CoRR abs\/1606.01400 ( 2016 ). arXiv:1606.01400 http:\/\/arxiv.org\/abs\/1606.01400 Anton Podkopaev, Ilya Sergey, and Aleksandar Nanevski. 2016. Operational Aspects of C\/C++ Concurrency. CoRR abs\/1606.01400 (2016). arXiv:1606.01400 http:\/\/arxiv.org\/abs\/1606.01400"},{"key":"e_1_3_2_2_39_1","volume-title":"ESOP 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, Thessaloniki, Greece, April 14--20, 2018, Proceedings. 940--967","author":"Raad Azalea","year":"2018","unstructured":"Azalea Raad , Ori Lahav , and Viktor Vafeiadis . 2018 . On Parallel Snapshot Isolation and Release\/Acquire Consistency. In Programming Languages and Systems - 27th European Symposium on Programming , ESOP 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, Thessaloniki, Greece, April 14--20, 2018, Proceedings. 940--967 . https:\/\/doi.org\/10.1007\/ 978--3--319--89884--1_33 Azalea Raad, Ori Lahav, and Viktor Vafeiadis. 2018. On Parallel Snapshot Isolation and Release\/Acquire Consistency. In Programming Languages and Systems - 27th European Symposium on Programming, ESOP 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, Thessaloniki, Greece, April 14--20, 2018, Proceedings. 940--967. https:\/\/doi.org\/10.1007\/ 978--3--319--89884--1_33"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Aaron Turon Viktor Vafeiadis and Derek Dreyer. 2014. GPS: navigating weak memory with ghosts protocols and separation. In OOPSLA. ACM 691--707.  Aaron Turon Viktor Vafeiadis and Derek Dreyer. 2014. GPS: navigating weak memory with ghosts protocols and separation. In OOPSLA. ACM 691--707.","DOI":"10.1145\/2714064.2660243"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Viktor Vafeiadis and Chinmay Narayan. 2013. Relaxed separation logic: a program logic for C11 concurrency. In OOPSLA. ACM 867--884.  Viktor Vafeiadis and Chinmay Narayan. 2013. Relaxed separation logic: a program logic for C11 concurrency. In OOPSLA. ACM 867--884.","DOI":"10.1145\/2544173.2509532"},{"key":"e_1_3_2_2_42_1","volume-title":"Proc. STOC. 137--146","author":"Vardi M","year":"1982","unstructured":"M Vardi . 1982 . The complexity of relational database queries . In Proc. STOC. 137--146 . M Vardi. 1982. The complexity of relational database queries. In Proc. STOC. 137--146."}],"event":{"name":"PODC '22: ACM Symposium on Principles of Distributed Computing","location":"Salerno Italy","acronym":"PODC '22","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538445","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538445","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:21Z","timestamp":1750191141000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538445"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":42,"alternative-id":["10.1145\/3519270.3538445","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538445","relation":{},"subject":[],"published":{"date-parts":[[2022,7,20]]},"assertion":[{"value":"2022-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}