On Asymmetric Progress Conditions - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Reports (Research Report) Year : 2010

On Asymmetric Progress Conditions

Abstract

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.
Fichier principal
Vignette du fichier
PI-1952.pdf (269.34 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00486977 , version 1 (27-05-2010)

Identifiers

  • HAL Id : inria-00486977 , version 1

Cite

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

Share

Gmail Facebook X LinkedIn More