A scalable lock-free stack algorithm

DOI10.1016/J.JPDC.2009.08.011MaRDI QIDQ666004zbMATH OpenOpenAlexFDO

Authors Danny Hendler, Nir Shavit, Lena Yerushalmi

Publication date 7 March 2012

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jpdc.2009.08.011

zbMATH Keywords

synchronizationeliminationstacklock-freedomshared-memorycompare-and-swap

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Distributed systems (68M14)

Recommendations

• Trace-based derivation of a scalable lock-free stack algorithm
• A fast, scalable mutual exclusion algorithm
• Lock-free concurrent binomial heaps
• A general lock-free algorithm using compare-and-swap

Cites work

• scientific article; zbMATH DE number 2013841 (Why is no real title available?)
• A steady state analysis of diffracting trees
• Adaptive and efficient algorithms for lattice agreement and renaming
• Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors
• Bounded-wait combining: constructing robust and high-throughput shared objects
• Combining funnels: A dynamic approach to software combining
• Elimination trees and the construction of pools and stacks
• Fully-Adaptive Algorithms for Long-Lived Renaming
• Introduction to algorithms.
• Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors
• Randomized wait-free concurrent objects (extended abstract)
• Safe memory reclamation for dynamic lock-free objects using atomic reads and writes

Cited in

(19)

• Relating trace refinement and linearizability
• Tasks in modular proofs of concurrent algorithms
• An optimistic approach to lock-free FIFO queues
• Common2 extended to stacks and unbounded concurrency
• Trace-based derivation of a scalable lock-free stack algorithm
• Rely-guarantee bound analysis of parameterized concurrent shared-memory programs. With an application to proving that non-blocking algorithms are bounded lock-free
• An applicative random-access stack
• Lock-free concurrent binomial heaps
• Quantifiability: a concurrent correctness condition modeled in vector space
• Reuse, don't recycle: transforming lock-free algorithms that throw away descriptors
• Tasks in modular proofs of concurrent algorithms
• Bounded-wait combining: constructing robust and high-throughput shared objects
• Proving linearizability with temporal logic
• Liveness-Preserving Atomicity Abstraction
• scientific article; zbMATH DE number 7407781 (Why is no real title available?)
• Combining funnels: A dynamic approach to software combining
• Set-linearizable implementations from read/write operations: sets, fetch \& increment, stacks and queues with multiplicity
• Fast and scalable rendezvousing
• A scalable, correct time-stamped stack

Describes a project that uses

Uses Software

• PVS

This page was built for publication: A scalable lock-free stack algorithm

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