Decidability and complexity for quiescent consistency.

摘要

Quiescent consistency is a correctness constraint for concurrent objects that attempts to improve concurrent-execution performance by accepting a broader range of possible operation sequences than do, for example, lineariz-ability or sequential consistency. Given a system under quiescent consistency, this paper examines the tasks of determining whether a particular execution satisfies the correctness constraint (membership), and of determining whether all possible executions are members (correctness). Results show that establishing membership and correctness are intractable for an unbounded number of operations between adjacent quiescent periods, while bounding the number of operations needs polynomial resources for determining membership and correctness.