Name
Abstract | ||
|---|---|---|
We present the first explicit, and currently simplest, randomized algorithm for two-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. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/s004460200071 | Distributed Computing |
Keywords | DocType | Volume |
randomized algorithm,cluster computing,symmetry breaking | Journal | 15 |
Issue | ISSN | Citations |
3 | 0178-2770 | 9 |
PageRank | References | Authors |
0.54 | 33 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| John Tromp | 1 | 124 | 12.85 |
| Paul Vitányi | 2 | 2130 | 287.76 |