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

DOI10.1007/S004460200071MaRDI QIDQ5138376zbMATH OpenOpenAlexFDO

Authors John Tromp, Paul M. B. Vitányi

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

adaptive adversaryasynchronous distributed protocolsatomicityfault-tolerancerandomized algorithmsshared memorysymmetry breakingtest-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) Distributed algorithms (68W15) Randomized algorithms (68W20)

Abstract: We present the first explicit, and currently simplest, randomized algorithm for 2-process wait-free test-and-set. It is implemented with two 4-valued single writer single reader atomic variables. A test-and-set takes at most 11 expected elementary steps, while a reset takes exactly 1 elementary step. Based on a finite-state analysis, the proofs of correctness and expected length are compressed into one table.

Recommendations

• On the time and space complexity of randomized test-and-set
• Efficient randomized test-and-set implementations
• Test-and-set in optimal space
• Sublogarithmic test-and-set against a weak adversary
• scientific article; zbMATH DE number 1555924

Cites work

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

Cited in

(5)

• Efficient randomized test-and-set implementations
• On the time and space complexity of randomized test-and-set
• Test-and-set in optimal space
• Sublogarithmic test-and-set against a weak adversary
• Efficient multi-word locking using randomization

This page was built for publication: Randomized two-process wait-free test-and-set

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