A liveness condition for concurrent objects: x-wait-freedom
The liveness of concurrent objects despite asynchrony and failures is a fundamental problem. To that end several progress conditions have been proposed. Wait-freedom is the strongest of these conditions: it states that any object operation must terminate if the invoking process does not crash. Obstruction-freedom is a weaker progress condition as it requires progress only when a process executes in isolation for a long enough period. This paper explores progress conditions in n-process asynchronous read/write systems enriched with base objects with consensus number x, 1<x <= n (i.e. objects that wait-free solve consensus in a set of x processes). It is easy to solve consensus in such a system if progress is required only when one of the x processes allowed to access the underlying consensus object invokes this object and does not crash. This paper proposes and investigates a stronger progress condition that we call x-wait-freedom (n-wait-freedom is wait-freedom). This condition includes additional scenarios in which progress is required even when none of the x processes allowed to access the underlying consensus object participates. The paper then presents and proves correct a consensus algorithm that satisfies this progress condition. Copyright (C) 2011 John Wiley & Sons, Ltd.
liveness wait-freedom progress condition obstruction-freedom consensus number asynchronous system fault-tolerance process crash shared memory system