Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.08238 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909645025574912 |
|---|---|
| author | Abdulla, Parosh Anastasiadi, Elli Atig, Mohamed Faouzi Grahn, Samuel |
| author_facet | Abdulla, Parosh Anastasiadi, Elli Atig, Mohamed Faouzi Grahn, Samuel |
| contents | The Release-Acquire (RA) semantics and its variants are some of the most fundamental models of concurrent semantics for architectures, programming languages, and distributed systems. Several steps have been taken in the direction of testing such semantics, where one is interested in whether a single program execution is consistent with a memory model. The more general verification problem, i.e., checking whether all allowed program runs are consistent with a memory model, has still not been studied as much. The purpose of this work is to bridge this gap. We tackle the verification problem, where, given an implementation described as a register machine, we check if any of its runs violates the RA semantics or its Strong (SRA) and Weak (WRA) variants. We show that verifying WRA in this setup is in O([)n5 ], while verifying the RA and SRA is in both NP- and coNP-hard, and provide a PSPACE upper bound. This both answers some fundamental questions about the complexity of these problems, but also provides insights on the expressive power of register machines as a model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_08238 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Verification of the Release-Acquire Semantics Abdulla, Parosh Anastasiadi, Elli Atig, Mohamed Faouzi Grahn, Samuel Programming Languages The Release-Acquire (RA) semantics and its variants are some of the most fundamental models of concurrent semantics for architectures, programming languages, and distributed systems. Several steps have been taken in the direction of testing such semantics, where one is interested in whether a single program execution is consistent with a memory model. The more general verification problem, i.e., checking whether all allowed program runs are consistent with a memory model, has still not been studied as much. The purpose of this work is to bridge this gap. We tackle the verification problem, where, given an implementation described as a register machine, we check if any of its runs violates the RA semantics or its Strong (SRA) and Weak (WRA) variants. We show that verifying WRA in this setup is in O([)n5 ], while verifying the RA and SRA is in both NP- and coNP-hard, and provide a PSPACE upper bound. This both answers some fundamental questions about the complexity of these problems, but also provides insights on the expressive power of register machines as a model. |
| title | Verification of the Release-Acquire Semantics |
| topic | Programming Languages |
| url | https://arxiv.org/abs/2506.08238 |