Randomized Two-Process Wait-Free Test-and-Set
<|reference_start|>Randomized Two-Process Wait-Free Test-and-Set: 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.<|reference_end|>
@article{tromp2001randomized,
    title={Randomized Two-Process Wait-Free Test-and-Set},
    author={John Tromp (CWI and BioInformatics Solutions) and Paul Vitanyi (CWI
  and University of Amsterdam)},
    journal={arXiv preprint arXiv:cs/0106056},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0106056},
    primaryClass={cs.DC}
}