Randomized two-process wait-free test-and-set

DOI10.1007/s004460200071zbMath1448.68477arXivcs/0106056OpenAlexW1672483193MaRDI QIDQ5138376

Paul M. B. Vitányi, John Tromp

Publication date: 3 December 2020

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

Full work available at URL: https://arxiv.org/abs/cs/0106056

zbMATH Keywords

symmetry breakingfault-tolerancerandomized algorithmsshared memoryatomicityadaptive adversaryasynchronous distributed protocolstest-and-set objectswait-free read/write registers

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

Efficient randomized test-and-set implementations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On interprocess communication. II: Algorithms
• The choice coordination problem
• Bounded time-stamps
• The topological structure of asynchronous computability
• Bounded concurrent timestamp systems using vector clocks
• Fast randomized consensus using shared memory
• Impossibility of distributed consensus with one faulty process
• Data Requirements for Implementation of N -Process Mutual Exclusion Using a Single Shared Variable
• Concurrent Reading While Writing
• A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment
• Atomic snapshots of shared memory
• The elusive atomic register
• Bounded Concurrent Time-Stamping
• How to share concurrent wait-free variables
• Time- and Space-Efficient Randomized Consensus
• Randomized wait-free concurrent objects (extended abstract)
• Immediate atomic snapshots and fast renaming