The Weakest Failure Detectors to Boost Obstruction-Freedom

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 Omega*, a new failure detector which we introduce in this paper, and which is strictly weaker than <>P but strictly stronger than Omega, is the weakest to convert any obstruction-free algorithm into a non-blocking one.


Publié dans:
Proceedings of the 20th International Symposium on Distributed Computing (DISC'06), 399-412
Présenté à:
20th International Symposium on Distributed Computing (DISC'06), Stockholm, Sweden, September 2006
Année
2006
Laboratoires:




 Notice créée le 2006-09-22, modifiée le 2019-03-16

n/a:
Télécharger le document
PDF

Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)