An impossibility about failure detectors in the iterated immediate snapshot model |
| |
Authors: | Sergio Rajsbaum Corentin Travers |
| |
Affiliation: | a Instituto de Matemáticas, Universidad Nacional Autónoma de México, D.F. 04510, Mexico b IRISA, Campus de Beaulieu, 35042 Rennes Cedex, France |
| |
Abstract: | The Iterated Immediate Snapshot model (IIS) is an asynchronous computation model where processes communicate through a sequence of one-shot Immediate Snapshot (IS) objects. It is known that this model is equivalent to the usual asynchronous read/write shared memory model, for wait-free task solvability. Its interest lies in the fact that its runs are more structured and easier to analyze than the runs in the shared memory model. As the IIS model and the shared memory model are equivalent for wait-free task solvability, a natural question is the following: Are they still equivalent for wait-free task solvability, when they are enriched with the same failure detector? The paper shows that the answer to this question is “no”. |
| |
Keywords: | Asynchronous shared memory system Atomic read/write register Distributed computing Distributed computability Failure detector Iterated immediate snapshot model Process crash Snapshot operation |
本文献已被 ScienceDirect 等数据库收录! |