Local linearizability for concurrent container-type data structures

DOI10.4230/LIPICS.CONCUR.2016.6MaRDI QIDQ4608657zbMATH OpenOpenAlexFDO

Authors Andreas Haas, Andreas Holzer, Christoph M. Kirsch, Michael Lippautz, Hannes Payer, Ali Sezgin, Ana Sokolova, Helmut Veith, Thomas A. Henzinger

Publication date 21 March 2018

Full work available at URL http://dx.doi.org/10.4230/LIPIcs.CONCUR.2016.6

zbMATH Keywords

linearizabilityconcurrent data structuresrelaxed semantics

Mathematics Subject Classification ID

Data structures (68P05) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• A sound and complete proof technique for linearizability of concurrent data structures
• Local Proofs for Linear-Time Properties of Concurrent Programs
• Analysing lock-free linearizable datatypes using CSP
• Local Reasoning for Storable Locks and Threads
• Putting strong linearizability in context: preserving hyperproperties in programs that use concurrent objects
• Concurrent specifications beyond linearizability
• Unifying Concurrent Objects and Distributed Tasks
• Linear Structures for Concurrency in Probabilistic Programming Languages

Cited in

(9)

• scientific article; zbMATH DE number 7561456 (Why is no real title available?)
• Verifying visibility-based weak consistency
• Wait-free concurrent graph objects with dynamic traversals
• Improved time bounds for linearizable implementations of abstract data types
• Nonblocking Concurrent Data Structures with Condition Synchronization
• Relaxed data types as consistency conditions
• Monotonically relaxing concurrent data-structure semantics for increasing performance: an efficient 2D design framework
• Between linearizability and quiescent consistency. Quantitative quiescent consistency
• Set-linearizable implementations from read/write operations: sets, fetch \& increment, stacks and queues with multiplicity

This page was built for publication: Local linearizability for concurrent container-type data structures

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