000113892 001__ 113892
000113892 005__ 20190316234048.0
000113892 02470 $$2ISI$$a000254431700004
000113892 037__ $$aARTICLE
000113892 245__ $$aThe Weakest Failure Detectors to Boost Obstruction-Freedom
000113892 269__ $$a2007
000113892 260__ $$c2007
000113892 336__ $$aJournal Articles
000113892 520__ $$aIt 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 ⋄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. We also address the issue of minimizing the overhead imposed by contention management in low contention scenarios. We propose two intermittent failure detectors I_Ω* and I_⋄P that are in a precise sense equivalent to, respectively, Ω* and ⋄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_Ω* and I_⋄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.
000113892 6531_ $$aShared memory
000113892 6531_ $$aObstruction-free
000113892 6531_ $$aNon-blocking
000113892 6531_ $$aWait-free
000113892 6531_ $$aContention manager
000113892 6531_ $$aFailure detector
000113892 700__ $$0240335$$g105326$$aGuerraoui, Rachid
000113892 700__ $$aKapalka, Michal
000113892 700__ $$aKouznetsov, Petr$$g128437$$0241770
000113892 773__ $$tDistributed Computing
000113892 8564_ $$uhttps://infoscience.epfl.ch/record/113892/files/of-wfnb-journal.pdf$$zn/a$$s243654
000113892 909C0 $$xU10407$$0252114$$pDCL
000113892 909CO $$ooai:infoscience.tind.io:113892$$qGLOBAL_SET$$pIC$$particle
000113892 937__ $$aLPD-ARTICLE-2007-010
000113892 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000113892 980__ $$aARTICLE