Back to Search
Start Over
t-Resilient Immediate Snapshot Is Impossible
- Source :
- LNCS, SIROCCO, SIROCCO, Jul 2016, Helsiinki, France. pp.15, Structural Information and Communication Complexity ISBN: 9783319483139
- Publication Year :
- 2016
- Publisher :
- HAL CCSD, 2016.
-
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.
- Subjects :
- Theoretical computer science
Linearizability
Consensus
t-resilience
Computer science
Distributed computabil-ity
Crash
0102 computer and information sciences
02 engineering and technology
[INFO] Computer Science [cs]
01 natural sciences
Shared memory
Iterated model
0202 electrical engineering, electronic engineering, information engineering
[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
[INFO]Computer Science [cs]
Asynchronous system
Impossibility
Immediate snapshot
k-Set Agreement
Snapshot object
Process crash failure
020207 software engineering
Atomic read/write register
ACM: F.: Theory of Computation
010201 computation theory & mathematics
Wait-freedom
Snapshot (computer storage)
Process identifier
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-319-48313-9
- ISBNs :
- 9783319483139
- Database :
- OpenAIRE
- Journal :
- LNCS, SIROCCO, SIROCCO, Jul 2016, Helsiinki, France. pp.15, Structural Information and Communication Complexity ISBN: 9783319483139
- Accession number :
- edsair.doi.dedup.....4539db9f9b6e1f924b186c24c57da13c