The weakest failure detectors to boost obstruction-freedom
Guerraoui, Rachid ; Kapałka, Michał ; Kouznetsov, Petr
In: Distributed Computing, 2008, vol. 20, no. 6, p. 415-433
Add to personal list- Summary
- It is considered good practice in concurrent computing to devise shared object implementations that ensure a minimal obstruction-free progress property and delegate the task of boosting liveness to independent generic oracles called contention managers. This paper determines necessary and sufficient conditions to implement wait-free and non-blocking contention managers, i.e., contention managers that ensure wait-freedom (resp. non-blockingness) of any associated obstruction-free object implementation. The necessary conditions hold even when universal objects (like compare-and-swap) or random oracles are available in the implementation of the contention manager. On the other hand, the sufficient conditions assume only basic read/write objects, i.e., registers. We show that failure detector $$\lozenge{\fancyscript{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 $$\lozenge\fancyscript{P}$$ but strictly stronger than Ω, is the weakest to convert any obstruction-free algorithm into a non-blocking one. We also address the issue of minimizing the overhead imposed by contention management in low contention scenarios. We propose two intermittent failure detectors $$I_{\Omega^*}$$ and $$I_{\lozenge\fancyscript{P}}$$ that are in a precise sense equivalent to, respectively, Ω * and $$\lozenge\fancyscript{P}$$ , but allow for reducing the cost of failure detection in eventually synchronous systems when there is little contention. We present two contention managers: a non-blocking one and a wait-free one, that use, respectively, $$I_{\Omega^*}$$ and $$I_{\lozenge\fancyscript{P}}$$ . When there is no contention, the first induces very little overhead whereas the second induces some non-trivial overhead. We show that wait-free contention managers, unlike their non-blocking counterparts, impose an inherent non-trivial overhead even in contention-free executions