Decidability and complexity for quiescent consistency and its variations

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.