Decidability and complexity for quiescent consistency and its variations

DOI10.1016/j.ic.2017.09.012zbMath1380.68294MaRDI QIDQ1680503

Robert M. Hierons, Brijesh Dongol

Publication date: 16 November 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2017.09.012

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q60: Specification and verification (program logics, model checking, etc.)

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Abstraction for concurrent objects
• On reducing linearizability to state reachability
• Model-checking of correctness conditions for concurrent objects
• Tractable Refinement Checking for Concurrent Objects
• Quantitative relaxation of concurrent data structures
• The complexity of equivalence problems for commutative grammars
• How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
• Counting networks
• Decidability and Complexity for Quiescent Consistency
• Characterizations of the decidability of some problems for regular trace languages
• Parameterised Linearisability
• Between Linearizability and Quiescent Consistency
• Verifying Concurrent Programs against Sequential Specifications
• On verifying causal consistency
• The complexity of satisfiability problems
• A variant of a recursively unsolvable problem