t-Resilient Immediate Snapshot is Impossible

Abstract : Immediate snapshot is the basic communication object on which relies the read/write distributed computing model made up of n crash-prone asynchronous processes, called iterated distributed model. Each iteration step (usually called a round) uses a new immediate snapshot object, which allows the processes to communicate and cooperate. More precisely, the x-th immediate snapshot object can be used by a process only when it executes the x-th round. An immediate snapshot object can be implemented by an (n − 1)-resilient algorithm, i.e. an algorithm that tolerates up to (n − 1) process crashes (also called wait-free algorithm). Considering a t-crash system model (i.e. a model in which up to t processes are allowed to crash), this paper is on the construction of an extension of immediate snapshot objects to t-resiliency. In the t-crash system model, at each round each process may be ensured to get values from at least n − t processes, and t-immediate snapshot has the properties of classical immediate snapshot (1-immediate snapshot) but ensures that each process will get values form at least n − t processes. Its main result is the following. While there is a (deterministic) t-resilient read/write-based algorithm implementing t-immediate snapshot in a t-crash system when t = n − 1, there is no t-resilient algorithm in a t-crash model when t ∈ [1..(n−2)]. This means that the notion of t-resilience is inop-erative when one has to implement immediate snapshot for these values of t: the model assumption " at most t < n − 1 processes may crash " does not provide us with additional computational power allowing for the design of genuine t-resilient algorithms (genuine meaning that such a t-resilient algorithm would work in the t-crash model, but not in the (t + 1)-crash model). To show these results, the paper relies on well-known distributed computing agreement problems such as consensus and k-set agreement.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

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

Contributeur : Michel Raynal <>
Soumis le : lundi 27 juin 2016 - 09:45:54
Dernière modification le : mardi 16 janvier 2018 - 15:54:13
Document(s) archivé(s) le : mercredi 28 septembre 2016 - 11:26:08


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01315342, version 4


Carole Delporte, Hugues Fauconnier, Sergio Rajsbaum, Michel Raynal. t-Resilient Immediate Snapshot is Impossible. 2016. 〈hal-01315342v4〉



Consultations de la notice


Téléchargements de fichiers