The Computability of Relaxed Data Structures: Queues and Stacks as Examples

DOI10.1007/978-3-319-25258-2_29zbMath1471.68079OpenAlexW2296386194MaRDI QIDQ3460732

Gadi Taubenfeld, Nir Shavit

Publication date: 8 January 2016

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-25258-2_29

zbMATH Keywords

queuesynchronizationmultisetstackwait-freedomconsensus numberrelaxed data structure

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Data structures (68P05)

Related Items (3)

Improved time bounds for linearizable implementations of abstract data types ⋮ Anomalies and similarities among consensus numbers of variously-relaxed queues ⋮ The computability of relaxed data structures: queues and stacks as examples

Cites Work

• On the Inherent Sequentiality of Concurrent Objects
• Quantitative relaxation of concurrent data structures
• The topological structure of asynchronous computability
• The complexity of obstruction-free implementations
• Impossibility of distributed consensus with one faulty process
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Generalized FLP impossibility result for t-resilient asynchronous computations

This page was built for publication: The Computability of Relaxed Data Structures: Queues and Stacks as Examples