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

BioInformatics Solutions); John Tromp (CWI; Paul Vitanyi (CWI; University of Amsterdam)

arxiv: cs/0106056 · v2 · submitted 2001-06-28 · 💻 cs.DC

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

John Tromp (CWI , BioInformatics Solutions) , Paul Vitanyi (CWI , University of Amsterdam) This is my paper

classification 💻 cs.DC

keywords test-and-setelementaryexpectedrandomizedsingletakeswait-freealgorithm

0 comments

read the original 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.

This paper has not been read by Pith yet.

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

discussion (0)