Skip to Main content Skip to Navigation
Reports

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
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
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.
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-00787978
Contributor : Julien Stainer <>
Submitted on : Friday, February 22, 2013 - 6:16:42 PM
Last modification on : Tuesday, June 15, 2021 - 4:25:50 PM
Long-term archiving on: : Sunday, April 2, 2017 - 4:34:54 AM

File

RR-Fds-Msg-adversaries-V8.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

1347

Files downloads

402