Abstract. We determine what information about failures is necessary and sufficient to solve Consensus in asynchronous distributed systems subject to crash failures. In Chandra and Toueg [1996], it is shown that {ᐃ, a failure detector that provides surprisingly little information about which processes have crashed, is sufficient to solve Consensus in asynchronous systems with a majority of correct processes. In this paper, we prove that to solve Consensus, any failure detector has to provide at least as much information as {ᐃ. Thus, {ᐃ is indeed the weakest failure detector for solving Consensus in asynchronous systems with a majority of correct processes.
In REF , Chandra and Toueg define the weakest FD capable of solving consensus in asynchronous crash fault systems.
The weakest failure detector for solving consensus
JACM
Computer Science