Quantitative relaxation of concurrent data structures

DOI10.1145/2429069.2429109zbMath1301.68176MaRDI 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

costs; concurrent data structures; quantitative models; relaxed semantics

Mathematics Subject Classification ID

68N15: Theory of programming languages

68Q55: Semantics in the theory of computing

68P05: Data structures

68N30: Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)

Related Items

Verifying Visibility-Based Weak Consistency, Strict Linearizability and Abstract Atomicity, Set-linearizable implementations from read/write operations: sets, fetch \& increment, stacks and queues with multiplicity, Quantifiability: a concurrent correctness condition modeled in vector space, The computability of relaxed data structures: queues and stacks as examples, 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