Premium
A liveness condition for concurrent objects: x ‐wait‐freedom
Author(s) -
Imbs Damien,
Raynal Michel
Publication year - 2011
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.1741
Subject(s) - liveness , asynchronous communication , object (grammar) , crash , computer science , asynchrony (computer programming) , degrees of freedom (physics and chemistry) , process (computing) , set (abstract data type) , base (topology) , distributed computing , theoretical computer science , mathematics , artificial intelligence , programming language , computer network , mathematical analysis , physics , quantum mechanics
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.