The weakest failure detectors to boost obstruction-freedom

摘要: 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 independent generic oracles called contention managers. This paper determines necessary sufficient conditions implement wait-free non-blocking managers, i.e., managers wait-freedom (resp. non-blockingness) any associated implementation. The hold even when universal objects (like compare-and-swap) or random are available implementation manager. On other hand, assume only basic read/write objects, registers. We show failure detector ⋄P weakest convert algorithm into one, Ω*, new which we introduce this paper, strictly weaker than but stronger Ω, one. also address issue minimizing overhead imposed by management low scenarios. propose two intermittent detectors I_Ω* I_⋄P precise sense equivalent to, respectively, Ω* ⋄P, allow for reducing cost detection eventually synchronous systems there little contention. present managers: one use, I_⋄P. When no contention, first induces very whereas second some non-trivial overhead. unlike their counterparts, impose an inherent contention-free executions.