t-Resilient Immediate Snapshot Is Impossible.

Abstract : An immediate snapshot object is a high level communication object, built on top of a read/write distributed system in which all except one processes may crash. It allows each process to write a value and obtains a set of pairs (process id, value) such that, despite process crashes and asynchrony, the sets obtained by the processes satisfy noteworthy inclusion properties. Considering an n-process model in which up to t processes are allowed to crash (t-crash system model), this paper is on the construction of t-resilient immediate snapshot objects. In the t-crash system model, a process can obtain values from at least (n−t)(n−t) processes, and, consequently, t-immediate snapshot is assumed to have the properties of the basic (n−1)(n−1)-resilient immediate snapshot plus the additional property stating that each process obtains values from at least (n−t)(n−t) processes. The main result of the paper is the following. While there is a (deterministic) (n−1)(n−1)-resilient algorithm implementing the basic (n−1)(n−1)-immediate snapshot in an (n−1)(n−1)-crash read/write system, there is no t-resilient algorithm in a t-crash read/write model when t∈[1…(n−2)]t∈[1…(n−2)]. This means that, when t
Type de document :
Communication dans un congrès
SIROCCO, Jul 2016, Helsiinki, France. LNCS, 9988, pp.15, 2016, Structural Information and Communication Complexity
Liste complète des métadonnées

https://hal.inria.fr/hal-01416515
Contributeur : Carole Delporte-Gallet <>
Soumis le : mercredi 14 décembre 2016 - 15:36:27
Dernière modification le : mercredi 11 avril 2018 - 02:00:25

Identifiants

  • HAL Id : hal-01416515, version 1

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Michel Raynal, Sergio Rajsbaum. t-Resilient Immediate Snapshot Is Impossible.. SIROCCO, Jul 2016, Helsiinki, France. LNCS, 9988, pp.15, 2016, Structural Information and Communication Complexity. 〈hal-01416515〉

Partager

Métriques

Consultations de la notice

495