Decidability and complexity for quiescent consistency and its variations
- Submitting institution
-
The University of Surrey
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 9025839_2
- Type
- D - Journal article
- DOI
-
10.1016/j.ic.2017.09.012
- Title of journal
- Information and Computation
- Article number
- -
- First page
- 1
- Volume
- 257
- Issue
- 0
- ISSN
- 0890-5401
- Open access status
- Compliant
- Month of publication
- -
- Year of publication
- 2017
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
-
- Research group(s)
-
-
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Quiescent consistency is a relaxed notion of correctness for a concurrent object that gives meaning the object’s behaviour in its quiescent states. This significance of this paper is that it answers crucial decidability and complexity properties for quiescent consistency and variations that make certain restrictions (e.g., bounding the distance between quiescence and the potential parallelism). We also consider quiescent sequential consistency, which strengthens quiescent consistency with an additional sequential consistency restriction. Interestingly, even for such a weak criterion, both the membership and model checking problems are inherently difficult in the unrestricted case.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -