Decidability and complexity for quiescent consistency and its variations

DOI10.1016/J.IC.2017.09.012zbMATH Open1380.68294OpenAlexW2964094199MaRDI QIDQ1680503FDOQ1680503

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

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

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)

Cites Work

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

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)