On the hardness of failure-sensitive agreement problems

doi:10.1016/S0020-0190(00)00171-X

Information Processing Letters

Volume 79, Issue 2, 30 June 2001, Pages 99-104

https://doi.org/10.1016/S0020-0190(00)00171-X Get rights and content

Abstract

Chandra and Toueg [J. ACM 43 (2) (1996)], Fromentin et al. [Proc. IEEE Internat. Conf. on Distrib. Comput., 1999] and Sabel and Marzullo [Tech. Rept. TR95-1488, Cornell Univ., 1995], respectively, stated that the weakest failure detector for any of non-blocking atomic commit, terminating reliable broadcast and leader election is the Perfect failure detector $P$ . This paper presents a counterexample of those results. We exhibit a failure detector that is incomparable to $P$ , and yet solves those problems.

References (6)

T. Chandra et al.
Unreliable failure detectors for reliable distributed systems
J. ACM
(1996)
T. Chandra et al.
The weakest failure detector for solving consensus
J. ACM
(1996)
E. Fromentin, M. Raynal, F. Tronel, About classes of problems in asynchronous distributed systems with process crashes,...

There are more references available in the full text version of this article.

Cited by (19)

The perfectly synchronized round-based model of distributed computing
2007, Information and Computation
The perfectly synchronized round-based model provides the powerful abstraction of crash-stop failures with atomic and synchronous message delivery. This abstraction makes distributed programming very easy. We describe a technique to automatically transform protocols devised in the perfectly synchronized round-based model into protocols for the crash, send omission, general omission or Byzantine models. Our transformation is achieved using a round shifting technique with a constant time complexity overhead. The overhead depends on the target model: crashes, send omissions, general omissions or Byzantine failures. Rather surprisingly, we show that no other automatic non-uniform transformation from a weaker model, say from the traditional crash-stop model (with no atomic message delivery), onto an even stronger model than the general-omission one, say the send-omission model, can provide a better time complexity performance in a failure-free execution.
On the weakest failure detector for hard agreement problems
2003, Journal of Systems Architecture
Citation Excerpt :
In this paper we have presented three new perfect failure detector classes. Our classes are alternatives to the classes P and M, proposed by Chandra and Toueg [1] and Guerraoui [4] respectively. More precisely, two of them are weaker than P and M, and yet can be used to solve non-blocking atomic commitment and terminating reliable broadcast.
Chandra and Toueg [J. ACM 43 (1996) 225] and Fromentin et al. [Proc. IEEE Internat. Conf. on Distrib. Comput., 1999, p. 470], respectively, stated that the weakest failure detector for any of non-blocking atomic commitment and terminating reliable broadcast is the perfect failure detector P. Recently, Guerraoui [IPL 79 (2001) 99] presented a counterexample of those results, exhibiting a failure detector called Marabout (M) that is incomparable to P and yet solves those problems.
In this paper we present three new perfect failure detector classes as alternatives to P and M. All our classes are weaker than P. Furthermore, two of them are also weaker than M, and yet solve non-blocking atomic commitment and terminating reliable broadcast. Interestingly, our failure detector classes are implementable whenever P is implementable (e.g., in a synchronous system), which is not the case with M.
Symbolic Model Checking for TLA+ Made Faster
2023, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
An Eventually Perfect Failure Detector on ADD Channels Using Clustering
2022, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Higher-Order Quantifier Elimination, Counter Simulations and Fault-Tolerant Systems
2021, Journal of Automated Reasoning
An Eventually Perfect Failure Detector for Networks of Arbitrary Topology Connected with ADD Channels Using Time-To-Live Values
2020, Parallel Processing Letters

View all citing articles on Scopus

View full text

Information Processing Letters

On the hardness of failure-sensitive agreement problems

Abstract

Unreliable failure detectors for reliable distributed systems

J. ACM

The weakest failure detector for solving consensus

J. ACM

The perfectly synchronized round-based model of distributed computing

On the weakest failure detector for hard agreement problems

Symbolic Model Checking for TLA+ Made Faster

An Eventually Perfect Failure Detector on ADD Channels Using Clustering

Higher-Order Quantifier Elimination, Counter Simulations and Fault-Tolerant Systems

An Eventually Perfect Failure Detector for Networks of Arbitrary Topology Connected with ADD Channels Using Time-To-Live Values