Relaxed queues and stacks from read/write operations

DOI10.4230/LIPICS.OPODIS.2020.13MaRDI QIDQ6834040zbMATH OpenFDO

Authors Armando Castañeda, Sergio Rajsbaum, Michel Raynal

Publication date 31 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.OPODIS.2020.13

zbMATH Keywords

asynchronycorrectness conditionlinearizabilitynonblockingprocess crashrelaxed data typeset-linearizabilitywait-freedomwork-stealing

Mathematics Subject Classification ID

Distributed systems (68M14) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites work

• A completeness theorem for a class of synchronization objects
• A Single-Enqueuer Wait-Free Queue Implementation
• Atomic snapshots of shared memory
• Common2 extended to stacks and unbounded concurrency
• Concurrent programming: algorithms, principles, and foundations.
• Distributed Computing
• Help when needed, but no more: efficient read/write partial snapshot
• Laws of order, expensive synchronization in concurrent algorithms cannot be eliminated
• Limited-use atomic snapshots with polylogarithmic step complexity
• Local linearizability for concurrent container-type data structures
• On the inherent sequentiality of concurrent objects
• Polylogarithmic concurrent data structures from monotone circuits
• Quantitative relaxation of concurrent data structures
• Relaxed data types as consistency conditions
• Renaming in an asynchronous environment
• The complexity of obstruction-free implementations
• The computability of relaxed data structures: queues and stacks as examples
• The renaming problem in shared memory systems: an introduction
• Unifying Concurrent Objects and Distributed Tasks
• Wait-free algorithms for fast, long-lived renaming

This page was built for publication: Relaxed queues and stacks from read/write operations

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