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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/hal-01315342
Contributor : Michel Raynal <>
Submitted on : Monday, June 27, 2016 - 9:45:54 AM
Last modification on : Thursday, April 4, 2019 - 10:18:05 AM
Long-term archiving on: Wednesday, September 28, 2016 - 11:26:08 AM

File

RR-2036-Immediate-Snapshot.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01315342, version 4

Citation

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

Share

Metrics

Record views

1489

Files downloads

467