The Weakest Failure Detectors to Boost Obstruction-Freedom

• Publication date: 2006

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.

Keywords: shared memory ; obstruction-free ; non-blocking ; wait-free ; contention manager ; failure detector ; parallelism ; lower bound

Reference

• LPD-REPORT-2006-007

Record created on 2006-03-31, modified on 2012-03-21