Round-based Synchrony Weakened by Message Adversaries vs Asynchrony Enriched with Failure Detectors

A message adversary is a daemon that suppresses messages in round-based message-passing synchronous systems in which no process crashes. A property imposed on a message adversary defines a subset of messages that cannot be eliminated by the adversary. It has recently been shown that when a message adversary is constrained by a property denoted TOUR (for tournament), the corresponding synchronous system and the asynchronous crash-prone read/write system have the same computability power for task solvability. This paper introduces new message adversary properties (denoted SOURCE and QUORUM), and shows that the synchronous round-based systems whose adversaries are constrained by these properties are characterizations of classical asynchronous crash-prone systems (1) whose communication is through atomic read/write registers or point-to-point message-passing, and (2) enriched with failure detectors such as Ω and Σ. Hence these properties characterize maximal adversaries, in the sense that they define strongest message adversaries equating classical asynchronous crash-prone systems. They consequently provide strong relations linking round-based synchrony weakened by message adversaries with asynchrony enriched with failure detectors. This not only enriches our understanding of the synchrony/asynchrony duality, but also allows for the establishment of a meaningful hierarchy of property-constrained message adversaries.; 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.