α-Register

Abstract : 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 .
Type de document :
Communication dans un congrès
Roberto Baldoni and Nicolas Nisse and Maarten van Steen. OPODIS, 2013, Unknown, Springer, 8304, pp.53-67, 2013, Lecture Notes in Computer Science
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00992784
Contributeur : Corentin Travers <>
Soumis le : lundi 19 mai 2014 - 11:51:25
Dernière modification le : mardi 16 janvier 2018 - 15:54:13
Document(s) archivé(s) le : lundi 10 avril 2017 - 23:43:04

Fichier

16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00992784, version 1

Citation

David Bonnin, Corentin Travers. α-Register. Roberto Baldoni and Nicolas Nisse and Maarten van Steen. OPODIS, 2013, Unknown, Springer, 8304, pp.53-67, 2013, Lecture Notes in Computer Science. 〈hal-00992784〉

Partager

Métriques

Consultations de la notice

607

Téléchargements de fichiers

125