α-register - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2013

α-register

Résumé

It is well known that in an asynchronous message-passing system, one can emulate an atomic register providing that more than half of the processes are non-faulty. By contrast, when a majority of the processes may fail, simulating atomic register is not possible. This paper investigates weak variants of atomic registers that can be simulated tolerating a majority of processes failures. Specifically, the paper introduces a new class of registers, called α-register and shows how to emulate them. For atomic registers, a read operation returns the last written value when there is no concurrent write operations. α-registers generalize atomic registers in the following sense: In any interval I, at most α values written before I are returned by the read operations in I. A simulation of an α-register tolerating f failures in a n-processes system is presented for α = 2M − 1, where M = max(1, 2f − n + 2). The simulation is optimal up to a constant multiplicative factor: the paper establishes that α-registers cannot be simulated tolerating f failures if α ≤ M .
Fichier principal
Vignette du fichier
alphareg-longversion.pdf (236.78 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00863060 , version 1 (18-09-2013)
hal-00863060 , version 2 (20-09-2013)

Identifiants

  • HAL Id : hal-00863060 , version 2

Citer

David Bonnin, Corentin Travers. α-register. 2013. ⟨hal-00863060v2⟩

Collections

CNRS
105 Consultations
57 Téléchargements

Partager

Gmail Facebook X LinkedIn More