Round-based Synchrony Weakened by Message Adversaries vs Asynchrony Enriched 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
Résumé : Un suppresseur de message est une entité qui retire des messages dans un système synchrone à passage de messages dans lequel aucune défaillance ne survient. Les propriétés contraignant les suppresseurs de messages definissent les sous-ensembles de messages pouvant être retirés. Il a été récemment prouvé qu'un système synchrone dans lequel le suppresseur de message est contraint par une propriété notée TOUR (pour tournoi) a la même puissance de calcul vis-à-vis des tâches qu'un système asynchrone sujet à des défaillances dans lequel les processus partagent de la mémoire. Ce rapport introduit de nouvelles propriétés pour contraindre les suppresseurs de messages (notées SOURCE et QUORUM), et montre que les systèmes asynchrones dans lesquels les suppresseurs de messages suivent ces propriétés sont des caractérisations des systèmes asynchrones (1) communicant par mémoire partagée ou par passage de message, (2) enrichis avec des detecteurs de fautes tels que Σ ou Ω. Ces propriétés mettent en évidence de fortes relations liant les modèles synchrones affaiblis par des suppresseurs de messages et les modèles asynchrones renforcés par des détecteurs de fautes. Ceci enrichi notre compréhension de la dualité syn- chrone/asynchrone mais permet également l'établissement d'une hiérarchie au sein des propriétés caractérisant les suppresseurs de messages.
Type de document :
Rapport
[Research Report] PI-2002, 2013
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00787978
Contributeur : Julien Stainer <>
Soumis le : vendredi 22 février 2013 - 18:16:42
Dernière modification le : mardi 16 janvier 2018 - 15:54:13
Document(s) archivé(s) le : dimanche 2 avril 2017 - 04:34:54

Fichier

RR-Fds-Msg-adversaries-V8.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00787978, version 2

Citation

Michel Raynal, Julien Stainer. Round-based Synchrony Weakened by Message Adversaries vs Asynchrony Enriched with Failure Detectors. [Research Report] PI-2002, 2013. 〈hal-00787978v2〉

Partager

Métriques

Consultations de la notice

738

Téléchargements de fichiers

284