| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6873906 | Information and Computation | 2017 | 21 Pages |
Abstract
We also consider quiescent sequential consistency, which strengthens quiescent consistency with an additional sequential consistency condition. We show that the unrestricted versions of membership and correctness are NP-complete and undecidable, respectively. When placing a limit on the number of events between two quiescent points, membership is in PTIME, while correctness is PSPACE-complete. Given an upper limit on the number of processes for every run of the implementation, the membership problem is in PTIME.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Brijesh Dongol, Robert M. Hierons,