On Asymmetric Progress Conditions

Damien Imbs (1) , Michel Raynal (1) , Gadi Taubenfeld (2)

1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
2 IDC - Interdisciplinay Center Herzliya - Israel

Wait-freedom and obstruction-freedom have received a lot of attention in the literature. These are symmetric progress conditions in the sense that they consider all processes as being “equal”. Wait-freedom has allowed to rank the synchronization power of objects in presence of process failures, while obstruction-freedom (that is a much weaker progress condition) allows for simpler and more efficient object implementations. This paper introduces the notion of asymmetric progress conditions. Given an object O in a read/write system of n processes, such a condition assumes that O can be accessed by a subset of y ≤ n processes only (i.e., O has y ports), and requires that O guarantees waitfreedom for x processes and obstruction-freedom for the remaining y - x processes. The paper investigates the power of such a progress condition, called (y; x)-liveness ((n; n)-liveness is wait-freedom while (n; 0)-liveness is obstruction-freedom). The main contributions of the paper are the following. (1) An impossibility result showing that (n; 1)-liveness cannot be obtained from (n - 1; n - 1)-live objects (i.e., from any number of wait-free objects with n - 1 ports). (2) An (n; x)-liveness hierarchy for 0 ≤ x ≤ n. (3) An algorithm based on (x; x)-live objects that constructs a consensus object with an asymmetric group-based progress condition.

Ce rapport étudie les conditions de progression asymétriques dans les systèmes à mémoire partagée.

Mots clés: Wait-freedom; Asynchronous system; Consensus number; Fault-Tolerance; Liveness; Obstruction-freedom; Process crash; Progress condition; Shared memory system; Wait-freedom.

Domaines: Autre [cs.OH]

Damien Imbs, Michel Raynal, Gadi Taubenfeld. On Asymmetric Progress Conditions. [Research Report] PI-1952, 2010, pp.15. ⟨inria-00486977⟩