Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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
Abstract : 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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Julien Stainer Connect in order to contact the contributor
Submitted on : Friday, February 22, 2013 - 6:16:42 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:27 AM
Long-term archiving on: : Sunday, April 2, 2017 - 4:34:54 AM


Files produced by the author(s)


  • HAL Id : hal-00787978, version 2


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



Record views


Files downloads