Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors

Michel Raynal 1 Julien Stainer 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : The base distributed asynchronous read/write computation model is made up of n asynchronous processes which communicate by reading and writing atomic registers only. The distributed asynchronous iterated model is a more constrained model in which the processes execute an infinite number of rounds and communicate at each round with a new object called immediate snapshot object. Moreover, in both models up to n − 1 processes may crash in an unexpected way. When considering computability issues, two main results are associated with the previous models. The first states that they are computationally equivalent for decision tasks. The second states that they are no longer equivalent when both are enriched with the same failure detector. This paper shows how to capture failure detectors in each model so that both models become computationally equivalent. To that end it introduces the notion of a "strongly correct" process which appears particularly well-suited to the iterated model, and presents simulations that prove the computational equivalence when both models are enriched with the same failure detector. The paper extends also these simulations to the case where the wait-freedom requirement is replaced by the notion of t-resilience.
Type de document :
Communication dans un congrès
SIROCCO - Structural Information and Communication Complexity - 19th International Colloquium - 2012, 2012, Reykjavik, Iceland. pp.231-242, 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00733077
Contributeur : Julien Stainer <>
Soumis le : lundi 17 septembre 2012 - 17:07:20
Dernière modification le : mercredi 16 mai 2018 - 11:23:13

Identifiants

  • HAL Id : hal-00733077, version 1

Citation

Michel Raynal, Julien Stainer. Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors. SIROCCO - Structural Information and Communication Complexity - 19th International Colloquium - 2012, 2012, Reykjavik, Iceland. pp.231-242, 2012. 〈hal-00733077〉

Partager

Métriques

Consultations de la notice

778