A scalable lock-free stack algorithm

DOI10.1016/j.jpdc.2009.08.011zbMath1233.68224OpenAlexW1970628175MaRDI QIDQ666004

Nir Shavit, Lena Yerushalmi, Danny Hendler

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)

Related Items (12)

Bounded-wait combining: constructing robust and high-throughput shared objects ⋮ Tasks in modular proofs of concurrent algorithms ⋮ Relating trace refinement and linearizability ⋮ Set-linearizable implementations from read/write operations: sets, fetch \& increment, stacks and queues with multiplicity ⋮ Quantifiability: a concurrent correctness condition modeled in vector space ⋮ Common2 extended to stacks and unbounded concurrency ⋮ Fast and scalable rendezvousing ⋮ Liveness-Preserving Atomicity Abstraction ⋮ Proving linearizability with temporal logic ⋮ 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 ⋮ Unnamed Item

Uses Software

• PVS

Cites Work

• Unnamed Item
• Unnamed Item
• A steady state analysis of diffracting trees
• Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors
• Elimination trees and the construction of pools and stacks
• Combining funnels: A dynamic approach to software combining
• Bounded-wait combining: constructing robust and high-throughput shared objects
• Adaptive and Efficient Algorithms for Lattice Agreement and Renaming
• Fully-Adaptive Algorithms for Long-Lived Renaming
• Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors
• Safe memory reclamation for dynamic lock-free objects using atomic reads and writes
• Randomized wait-free concurrent objects (extended abstract)

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