A liveness condition for concurrent objects: x ‐wait‐freedom

SUMMARY 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 © 2011 John Wiley & Sons, Ltd.