Quantitative relaxation of concurrent data structures

DOI10.1145/2429069.2429109zbMath1301.68176OpenAlexW2082679906MaRDI QIDQ2931807

Ana Sokolova, Ali Sezgin, Hannes Payer, Christoph Kirsch, 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

costsconcurrent data structuresquantitative modelsrelaxed semantics

Mathematics Subject Classification ID

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

Related Items (14)

Verifying Visibility-Based Weak Consistency ⋮ Improved time bounds for linearizable implementations of abstract data types ⋮ The Computability of Relaxed Data Structures: Queues and Stacks as Examples ⋮ Decidability and complexity for quiescent consistency and its variations ⋮ 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 ⋮ Decomposable Relaxation for Concurrent Data Structures ⋮ Anomalies and similarities among consensus numbers of variously-relaxed queues ⋮ The computability of relaxed data structures: queues and stacks as examples ⋮ Relaxed data types as consistency conditions ⋮ Lower bounds on message passing implementations of multiplicity-relaxed queues and stacks ⋮ Strict Linearizability and Abstract Atomicity

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