Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

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

Résumé

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. An important computability issue associated with these models concerns their respective computability power. When considering distributed computing problems whose main issue is to cope with asynchrony and failures called decision tasks (such as consensus, set agreement, etc.) two main results are associated with the previous models. The first states that these models 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 in order 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. It also presents simulations that proves the computational equivalence when both models are enriched with a failure detector. Interestingly, these simulations works for a large family of failure detector classes. The paper extends also the simulations to the case where the wait-freedom requirement is replaced by the notion of $t$-resilience. Last but not least, a noteworthy feature of the proposed approach lies in its simplicity.
Les modèles de systèmes distribués asynchrones communicant par mémoire partagée sont équivalents, du point de vue de la calculabilité, au modèle itéré où les processus communiquent via une séquence d'objets \emph{write-snapshot}. Cependant, il a été montré que l'utilisation naïve, dans le modèle itéré, des détecteurs de fautes définis pour la mémoire partagée n'apportait aucune puissance de calcul additionelle. Cet article propose une méthode systématique pour porter les détecteurs de fautes du modèle classique communicant par mémoire partagée dans le modèle itéré, ceci en préservant les équivalences de modèles. Dans ce but, il introduit la notion de processus \emph{fortement corrects} qui aide à décrire les possibilités de communication dans le modèle itéré. L'article fournit des simulations génériques (ne dépendant pas ou peu du détecteur de faute) pour prouver les équivalences de modèles. Les cas de plusieurs détecteurs de fautes connus sont traités et le résultat est étendu au cas de la $t$-résilience. Enfin, un algorithme de consensus dans le modèle itéré augmenté du détecteur de faute correspondant à $\Omega$ illustre une des possibilités offertes par cette étude.
Fichier principal
Vignette du fichier
adding-fd-to-iis-v8-rr.pdf (359.63 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00670154 , version 1 (21-02-2012)

Identifiants

  • HAL Id : hal-00670154 , version 1

Citer

Michel Raynal, Julien Stainer. Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors. [Research Report] PI-1991, 2012. ⟨hal-00670154⟩
219 Consultations
208 Téléchargements

Partager

Gmail Facebook X LinkedIn More