Quantitative relaxation of concurrent data structures

DOI10.1145/2429069.2429109MaRDI QIDQ2931807zbMATH OpenOpenAlexFDO

Authors Christoph M. Kirsch, Hannes Payer, Ali Sezgin, Ana Sokolova, Thomas A. Henzinger

Publication date 27 November 2014

Published in Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.308.8033

zbMATH Keywords

concurrent data structurescostsquantitative modelsrelaxed semantics

Mathematics Subject Classification ID

Theory of programming languages (68N15) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Data structures (68P05) Semantics in the theory of computing (68Q55)

Recommendations

• Monotonically relaxing concurrent data-structure semantics for increasing performance: an efficient 2D design framework
• The computability of relaxed data structures: queues and stacks as examples
• The computability of relaxed data structures: queues and stacks as examples
• Decomposable relaxation for concurrent data structures
• Between linearizability and quiescent consistency. Quantitative quiescent consistency

Cited in

(24)

• Improved time bounds for linearizable implementations of abstract data types
• Decidability and complexity for quiescent consistency and its variations
• Lower bounds on message passing implementations of multiplicity-relaxed queues and stacks
• Anomalies and similarities among consensus numbers of variously-relaxed queues
• Relaxed data types as consistency conditions
• Decomposable relaxation for concurrent data structures
• The computability of relaxed data structures: queues and stacks as examples
• Verifying visibility-based weak consistency
• Between linearizability and quiescent consistency. Quantitative quiescent consistency
• The computability of relaxed data structures: queues and stacks as examples
• Strict linearizability and abstract atomicity
• Quantaloids for concurrency
• Set-linearizable implementations from read/write operations: sets, fetch \& increment, stacks and queues with multiplicity
• Quantifiability: a concurrent correctness condition modeled in vector space
• Asynchronous Wait-Free Runtime Verification and Enforcement of Linearizability
• Brief Announcement: Improved, Partially-Tight Multiplicity Queue Lower Bounds
• Monotonically relaxing concurrent data-structure semantics for increasing performance: an efficient 2D design framework
• Intermediate value linearizability: a quantitative correctness criterion
• Fast and space-efficient queues via relaxation
• Relaxed queues and stacks from read/write operations
• Preserving hyperproperties of programs using primitives with consensus number 2
• Strong linearizability using primitives with consensus number 2
• Intermediate value linearizability: a quantitative correctness criterion
• Asynchronous wait-free runtime verification and enforcement of linearizability

This page was built for publication: Quantitative relaxation of concurrent data structures

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