Skip to Main content Skip to Navigation
Conference papers

Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors

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) in which processes communicate 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 restricted 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.
Complete list of metadata

https://hal.inria.fr/hal-00920734
Contributor : Julien Stainer <>
Submitted on : Thursday, December 19, 2013 - 10:08:19 AM
Last modification on : Tuesday, June 15, 2021 - 4:25:53 PM

Identifiers

Citation

Michel Raynal, Julien Stainer. Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors. PODC, Jul 2013, Montréal, Canada. pp.166-175, ⟨10.1145/2484239.2484249⟩. ⟨hal-00920734⟩

Share

Metrics

Record views

1279