Randomized Two-Process Wait-Free Test-and-Set

Simple item page
dc.creatorTromp, John
dc.creatorVitanyi, Paul
dc.date2001-06-28
dc.date2002-03-15
dc.date.accessioned2026-07-07T03:17:17Z
dc.date.available2026-07-07T03:17:17Z
dc.descriptionWe 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.
dc.description9 pages, 4 figures, LaTeX source; Submitted
dc.identifierhttps://arxiv.org/abs/cs/0106056
dc.identifierhttp://arxiv.org/abs/cs/0106056
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30671
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectC.2; F.2.2
dc.titleRandomized Two-Process Wait-Free Test-and-Set
dc.typetext

Files

Collections

arXiv