On classes of problems in asynchronous distributed systems with process crashes

This paper is on classes of problems encountered in asynchronous distributed systems in which processes can crash but links are reliable. The hardness of a problem is defined with respect to the difficulty to solve it despite failures: a problem is easy if it can be solved in presence of failures, otherwise it is hard. Three classes of problems are defined: F, NF and NFC. F is the class of easy problems, namely, those that can be solved in presence of failures (e.g., reliable broadcast). The class NF includes harder problems, namely, the ones that can be solved in a non-faulty system (e.g., consensus). The class NFC (NF-complete) is a subset of NF that includes the problems that are the most difficult to solve in presence of failures. It is shown that the terminating reliable broadcast problem, the non-blocking atomic commitment problem and the construction of a perfect failure detector (problem P) are equivalent problems and belong to NFC. Moreover the consensus problem is not in NFC. The paper presents a general reduction protocol that reduces any problem of NF to P. This shows that P is a problem that lies at the core of distributed fault-tolerance.