The computability of relaxed data structures: queues and stacks as examples

DOI10.1007/S00446-016-0272-0zbMath1405.68099OpenAlexW2342859886MaRDI QIDQ518927

Nir Shavit, Gadi Taubenfeld

Publication date: 4 April 2017

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-016-0272-0

zbMATH Keywords

queuesynchronizationmultisetstackwait-freedomconsensus number\(k\)-registerrelaxed data structure

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (5)

Set-linearizable implementations from read/write operations: sets, fetch \& increment, stacks and queues with multiplicity ⋮ Brief Announcement: Improved, Partially-Tight Multiplicity Queue Lower Bounds ⋮ Anomalies and similarities among consensus numbers of variously-relaxed queues ⋮ Relaxed data types as consistency conditions ⋮ Lower bounds on message passing implementations of multiplicity-relaxed queues and stacks

Cites Work

• On interprocess communication. I: Basic formalism
• 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
• The Computability of Relaxed Data Structures: Queues and Stacks as Examples
• Impossibility of distributed consensus with one faulty process
• How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
• Reaching Agreement in the Presence of Faults
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Generalized FLP impossibility result for t-resilient asynchronous computations
• The mutual exclusion problem
• The mutual exclusion problem

This page was built for publication: The computability of relaxed data structures: queues and stacks as examples