Decidability and complexity for quiescent consistency and its variations

摘要

Quiescent consistency is a notion of correctness for a concurrent object that gives meaning the object's behaviour in its quiescent states. This paper shows that the membership problem for quiescent consistency is NP-complete and that the correctness problem is decidable, but coNEXPTIME-complete. We consider restricted versions of quiescent consistency by assuming an upper limit on the number of events between two quiescent points. Here, we show that the membership problem is in PTIME, whereas correctness is PSPACE-complete. 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.