Name
Abstract | ||
|---|---|---|
We consider parameterized verification of concurrent programs under the Total Store Order (TSO) semantics. A program consists of a set of processes that share a set of variables on which they can perform read and write operations. We show that the reachability problem for a system consisting of an arbitrary number of identical processes is PSPACE-complete. We prove that the complexity is reduced to polynomial time if the processes are not allowed to read the initial values of the variables in the memory. When the processes are allowed to perform atomic read-modify-write operations, the reachability problem has a non-primitive recursive complexity.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1145/3371094 | Proceedings of the ACM on Programming Languages |
Keywords | Field | DocType |
Model-Checking, Parameterized Verification, Total Store Ordering, Weak Memory Models | Parameterized complexity,Programming language,Computer science,PSPACE-complete,Theoretical computer science,Total store order,Reachability problem,Time complexity,Semantics,Recursion | Journal |
Volume | Issue | Citations |
4 | POPL | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Parosh Aziz Abdulla | 1 | 2010 | 122.22 |
| Mohamed Faouzi Atig | 2 | 505 | 40.94 |
| Rojin Rezvan | 3 | 0 | 0.34 |