Decidability and complexity for quiescent consistency and its variations

DOI10.1016/J.IC.2017.09.012MaRDI QIDQ1680503zbMATH OpenOpenAlexFDO

Authors Brijesh Dongol, Robert M. Hierons

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Decidability and complexity for quiescent consistency
• Computability and decidability issues in the theory of consistency enforcement
• On quasi-inconsistency and its complexity
• The complexity of weak consistency
• Between linearizability and quiescent consistency. Quantitative quiescent consistency
• On the quantifier-free dynamic complexity of reachability
• On the Quantifier-Free Dynamic Complexity of Reachability
• Computing weak consistency in polynomial time (extended abstract)
• On the complexity of verifying concurrent transition systems

Cites work

• scientific article; zbMATH DE number 3924146 (Why is no real title available?)
• scientific article; zbMATH DE number 3943003 (Why is no real title available?)
• A variant of a recursively unsolvable problem
• Abstraction for concurrent objects
• Between linearizability and quiescent consistency. Quantitative quiescent consistency
• Characterizations of the decidability of some problems for regular trace languages
• Counting networks
• Decidability and complexity for quiescent consistency
• How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
• Model-checking of correctness conditions for concurrent objects
• On verifying causal consistency
• Parameterised linearisability
• Quantitative relaxation of concurrent data structures
• The complexity of equivalence problems for commutative grammars
• The complexity of satisfiability problems
• Tightening the complexity of equivalence problems for commutative grammars
• Tractable refinement checking for concurrent objects
• Verifying concurrent programs against sequential specifications

Cited in

(5)

• A quasi-lower bound on the consistency strength of PFA
• Quasi-linearizability is undecidable
• Between linearizability and quiescent consistency. Quantitative quiescent consistency
• Decidability and complexity for quiescent consistency
• Computing weak consistency in polynomial time (extended abstract)

This page was built for publication: Decidability and complexity for quiescent consistency and its variations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1680503)