A scalable lock-free stack algorithm

DOI10.1016/J.JPDC.2009.08.011zbMATH Open1233.68224OpenAlexW1970628175MaRDI QIDQ666004FDOQ666004

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

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

zbMATH Keywords

synchronizationeliminationstacklock-freedomshared-memorycompare-and-swap

Mathematics Subject Classification ID

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

Cites Work

• Introduction to algorithms.
• Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors
• Randomized wait-free concurrent objects (extended abstract)
• Title not available (Why is that?)
• Safe memory reclamation for dynamic lock-free objects using atomic reads and writes
• Adaptive and efficient algorithms for lattice agreement and renaming
• Combining funnels: A dynamic approach to software combining
• 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
• Bounded-wait combining: constructing robust and high-throughput shared objects
• Fully-Adaptive Algorithms for Long-Lived Renaming

Cited In (19)

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

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)