Revisiting the Relationship between Non-Blocking Atomic Commitment and Consensus

This paper discusses the relationship between the {\em Non-\\Blocking Atomic Commitment problem (NB-AC)} and the Consensus problem in asynchronous systems with {\em unreliable} failure detectors. We first confirm that NB-AC is harder than Consensus. In contrast to Consensus, NB-AC is impossible to solve with unreliable failure detectors even with a single crash failure. We define a weaker problem than NB-AC, called {\em Non-Blocking Weak Atomic Commitment (NB-WAC)}, which is sufficient to solve for most practical situations. A fundamental characteristic of NB-WAC is its {\em reducibility} to Consensus. The previous results on solving Consensus with unreliable failure detectors apply therefore to NB-WAC. An interesting intermediate result of this reducibility is that Uniform Consensus and Consensus are equivalent problems. We show actually that any algorithm that solves Consensus with unreliable failure detectors also solves Uniform Consensus.\\


Published in:
Proceedings of the 9th International Workshop on Distributed Algorithms (WDAG-9), 87-100
Year:
1995
Publisher:
Springer-Verlag
Laboratories:




 Record created 2005-05-20, last modified 2018-03-17

n/a:
Download fulltext
PS

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)