  Quiescent consistency is a notion of correctness for a concurrent object that
gives meaning to the object's behaviours in quiescent states, i.e., states in
which none of the object's operations are being executed. Correctness of an
implementation object is defined in terms of a corresponding abstract
specification. This gives rise to two important verification questions:
membership (checking whether a behaviour of the implementation is allowed by
the specification) and correctness (checking whether all behaviours of the
implementation are allowed by the specification). In this paper, we show that
the membership problem for quiescent consistency is NP-complete and that the
correctness problem is decidable, but coNP-hard and in EXPSPACE. For both
problems, 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 in PSPACE.
  Quiescent consistency does not guarantee sequential consistency, i.e., it
allows operation calls by the same process to be reordered when mapping to an
abstract specification. Therefore, 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
by placing a limit on the number of events between two quiescent points,
membership is in PTIME, while correctness is in PSPACE. Finally, we consider a
version of quiescent sequential consistency that places an upper limit on the
number of processes for every run of the implementation, and show that the
membership problem for quiescent sequential consistency with this restriction
is in PTIME.
