Please use this identifier to cite or link to this item:
Title: Decidability and complexity for quiescent consistency
Authors: Dongol, B
Hierons, R
Keywords: Quiescent consistency;Concurrent objects;Decidability;Mazurkiewicz Trace Theory
Issue Date: 2016
Publisher: ACM
Citation: Thirty-First Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), New York City, USA, (5 - 8 July 2016)
Abstract: 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. The condition enables greater flexibility in object design by allowing more behaviours to be admitted, which in turn allows the algorithms implementing quiescent consistent objects to be more efficient (when executed in a multithreaded environment). Quiescent consistency of an implementation object is defined in terms of a corresponding abstract specification. This gives rise to two important verification questions: \emph{membership} (checking whether a behaviour of the implementation is allowed by the specification) and \emph{correctness} (checking whether all behaviours of the implementation are allowed by the specification). In this paper, we consider the membership and correctness conditions for quiescent consistency, as well as a restricted form that assumes an upper limit on the number of events between two quiescent states. We show that the membership problem for unrestricted quiescent consistency is NP-complete and that the correctness problem is decidable, coNEXPTIME-hard, and in EXPSPACE. For the restricted form, while correctness is PSPACE-complete.
Appears in Collections:Dept of Computer Science Research Papers

Files in This Item:
File Description SizeFormat 
Fulltext.pdf340.64 kBUnknownView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.