| Citation key |
GKK-WFDBOF-06 |
| Author |
Guerraoui, Rachid and Kapalka, Michal and Kouznetsov, Petr |
| Title of Book |
Proceedings of the 20th International Conference on Distributed Computing (DISC '06) |
| Pages |
399–412 |
| Year |
2006 |
| ISBN |
978-3-540-44624-8 |
| ISSN |
0302-9743 |
| DOI |
http://dx.doi.org/10.1007/11864219_28 |
| Address |
Berlin / Heidelberg, Germany |
| Volume |
4167 |
| Month |
September |
| Publisher |
Springer |
| Series |
Lecture Notes in Computer Science (LNCS) |
| Abstract |
This paper determines necessary and sufficient conditions to implement wait-free and non-blocking contention managers in a shared memory system. The necessary conditions hold even when universal objects (like compare-and-swap) or random oracles are available, whereas the sufficient ones assume only registers. We show that failure detector ◊P is the weakest to convert any obstruction-free algorithm into a wait-free one, and Ω*, a new failure detector which we introduce in this paper, and which is strictly weaker than ◊P but strictly stronger than Ω, is the weakest to convert any obstruction-free algorithm into a non-blocking one. |
