Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Decidability and complexity for quiescent consistency
Dongol B., Hierons R.  LICS 2016 (Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, New York, NY, Jul 5-8, 2016)116-125.2016.Type:Proceedings
Date Reviewed: Mar 1 2017

Quiescent consistency is a correctness constraint for concurrent objects that attempts to improve concurrent-execution performance by accepting a broader range of possible operation sequences than do, for example, linearizability or sequential consistency. Given a system under quiescent consistency, this paper examines the tasks of determining whether a particular execution satisfies the correctness constraint (membership), and of determining whether all possible executions are members (correctness). Results show that establishing membership and correctness are intractable for an unbounded number of operations between adjacent quiescent periods, while bounding the number of operations needs polynomial resources for determining membership and correctness.

Analysis proceeds over traces generated by labeled finite automata (FA) modeling operations under quiescent consistency. Operations are broken into start and end events; constraints over start-end pairings determine legal executions and quiescent periods. Membership reduces to determining if a trace is in an FA language; correctness reduces to determining a subset relation between FA languages. For traces with an unbounded number of operations between quiescence, membership is NP-complete, and correctness is decidable, coNEXPTIME-hard, and in EXPSPACE. The analysis introduces traces with a bounded number of operations between quiescence; it shows membership for such traces is in PTIME, and correctness is PSPACE-complete.

There is a clear trail through this paper; the first half reads with reasonable ease, but the second half quickly enters steep and rugged terrain. Complexity theoreticians should feel at home throughout. Practitioners may find value in the paper’s first half if they can derive sufficient motivation from the correspondence between quiescent consistency and similar ideas in replicated databases.

Reviewer:  R. Clayton Review #: CR145095 (1705-0276)
Bookmark and Share
 
Software/ Program Verification (D.2.4 )
 
 
Logics Of Programs (F.3.1 ... )
 
 
Parallelism And Concurrency (F.1.2 ... )
 
 
Semantics (D.3.1 ... )
 
 
Formal Definitions And Theory (D.3.1 )
 
 
Modes Of Computation (F.1.2 )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "Software/Program Verification": Date
Verification of sequential and concurrent programs
Krzysztof R., Olderog E., Springer-Verlag New York, Inc., New York, NY, 1991. Type: Book (9780387975320)
Jul 1 1992
On verification of programs with goto statements
Lifschitz V. (ed) Information Processing Letters 18(4): 221-225, 1984. Type: Article
Mar 1 1985
The validation, verification and testing of software
Ince D. (ed), Oxford University Press, Inc., New York, NY, 1985. Type: Book (9789780198590040)
Sep 1 1987
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy