Decidability and complexity for quiescent consistency and its variations

DOI10.1016/j.ic.2017.09.012zbMath1380.68294OpenAlexW2964094199MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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