NDLI: Decidability and Complexity for Quiescent Consistency

Please wait, while we are loading the content...

Unifying Logical and Statistical AI

Stochastic mechanics of graph rewriting

Deciding First-Order Satisfiability when Universal and Existential Variables are Separated

From positive and intuitionistic bounded arithmetic to monotone proof complexity

Data Communicating Processes with Unreliable Channels

The complexity of regular abstractions of one-counter languages

Plays as Resource Terms via Non-idempotent Intersection Types

Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps

Coinduction All the Way Up

Fixed Points In Quantitative Semantics

First-order definability of rational transductions: An algebraic approach

Interaction Graphs: Full Linear Logic

First-order logic with reachability for infinite-state systems

Comparing Chemical Reaction Networks: A Categorical and Algorithmic Perspective

Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints

A Mechanization of the Blakers-Massey Connectivity Theorem in Homotopy Type Theory

The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems

Winning Cores in Parity Games

Reasoning about Recursive Probabilistic Programs

Rewriting modulo symmetric monoidal structure

Proving Differential Privacy via Probabilistic Couplings

How unprovable is Rabin's decidability theorem?

Church Meets Cook and Levin

A Generalised Twinning Property for Minimisation of Cost Register Automata

Duality in Computer Science

On the Satisfiability of Some Simple Probabilistic Logics

The Diagonal Problem for Higher-Order Recursion Schemes is Decidable

Gödel's functional interpretation and the concept of learning

A New Perspective on FO Model Checking of Dense Graph Classes

Two-Way Visibly Pushdown Automata and Transducers

Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives

Hanf normal form for first-order logic with unary counting quantifiers

Denotational semantics of recursive types in synthetic guarded domain theory

Ability to Count Messages Is Worth Θ(Δ) Rounds in Distributed Computing

Order Invariance on Decomposable Structures

Conflict nets: Efficient locally canonical MALL proof nets

The Complexity of Coverability in ν-Petri Nets

A categorical approach to open and interconnected dynamical systems

Interacting Frobenius Algebras are Hopf

Hybrid realizability for intuitionistic and classical choice

Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction

Healthiness from Duality

Effective Brenier Theorem: Applications to Computable Analysis and Algorithmic Randomness

On Thin Air Reads Towards an Event Structures Model of Relaxed Memory

Solvability of Matrix-Exponential Equations

Complexity Theory of (Functions on) Compact Metric Spaces

Invisible Pushdown Languages

Blockchains and the Logic of Accountability: Keynote Address

Distinguishing Hidden Markov Chains

Two-variable Logic with a Between Relation

Understanding Gentzen and Frege Systems for QBF

Proving Liveness of Parameterized Programs

Automata on Infinite Trees with Equality and Disequality Constraints Between Siblings

Games with bound guess actions

Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic

Type Theory based on Dependent Inductive and Coinductive Types

The Definitional Side of the Forcing

Definability equals recognizability for graphs of bounded treewidth

Infinitary Lambda Calculi from a Linear Perspective

Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete

Differential Refinement Logic

Semi-galois Categories I: The Classical Eilenberg Variety Theory

Trace semantics for polymorphic references

Weak consistency notions for all the CSPs of bounded width

Kolmogorov Extension, Martingale Convergence, and Compositionality of Processes

Quantifier Free Definability on Infinite Algebras

Towards Compositional Feedback in Non-Deterministic and Non-Input-Receptive Systems

Order-Invariance of Two-Variable Logic is Decidable

Semantically Acyclic Conjunctive Queries under Functional Dependencies

Minimization of Symbolic Tree Automata

The Probabilistic Model Checking Landscape

Quantitative Automata under Probabilistic Semantics

Decidability and Complexity for Quiescent Consistency

Unified Semantics and Proof System for Classical, Intuitionistic and Affine Logics

Model and Objective Separation with Conditional Lower Bounds: Disjunction is Harder than Conjunction

Querying Visible and Invisible Information

Program Equivalence is Coinductive

Towards Completeness via Proof Search in the Linear Time μ-calculus: The case of Büchi inclusions

Monadic second order logic as the model companion of temporal logic

On Recurrent Reachability for Continuous Linear Dynamical Systems

A bifibrational reconstruction of Lawvere's presheaf hyperdoctrine

Constructions with Non-Recursive Higher Inductive Types

Graphs of relational structures: restricted types

Quantitative Algebraic Reasoning

Factor Varieties and Symbolic Computation

Divide and Congruence II: Delay and Weak Bisimilarity

A Step Up in Expressiveness of Decidable Fixpoint Logics

A constructive function-theoretic approach to topological compactness

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns

Decidability and Complexity for Quiescent Consistency

Content Provider	ACM Digital Library
Author	Dongol, Brijesh Hierons, Robert M.
Abstract	Quiescent consistency is a notion of correctness for a concurrent object that gives meaning to the object's behaviours in quiescent states, i.e., states in which none of the object's operations are being executed. The condition enables greater flexibility in object design by allowing more behaviours to be admitted, which in turn allows the algorithms implementing quiescent consistent objects to be more efficient (when executed in a multithreaded environment). Quiescent consistency of an implementation object is defined in terms of a corresponding abstract specification. This gives rise to two important verification questions: membership (checking whether a behaviour of the implementation is allowed by the specification) and correctness (checking whether all behaviours of the implementation are allowed by the specification). In this paper, we consider the membership and correctness conditions for quiescent consistency, as well as a restricted form that assumes an upper limit on the number of events between two quiescent states. We show that the membership problem for unrestricted quiescent consistency is NP-complete and that the correctness problem is decidable, coNEXPTIME-hard, and in EXPSPACE. For the restricted form, we show that membership is in PTIME, while correctness is PSPACE-complete.
Starting Page	116
Ending Page	125
Page Count	10
File Format	PDF
ISBN	9781450343916
DOI	10.1145/2933575.2933576
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-05
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Mazurkiewicz trace theory Decidability Quiescent consistency Concurrent objects
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in