Technical Report CS0586

Title: Impossibility Results in The Presence of Mpltiple Faulty Processes
Authors: G. Taubenfeld, S. Katz, and S. Moran
Abstract: We investigate the impossibility of solving certain problems in an unreliable distributed system where multiple processes may fail. We assume undetectable crash(fail-stop) failures, which means that a process may become faulty at any time during an execution and that no event c,an occur on a process after it fails. A sufficient condition is provided for the unsolvability of problems in the presence of multiple faulty processes. Several problems are shown to be solvable in the presence of t-1 faulty processes but not in the presence of t faulty processes for any t. These are variants of problems unsolvable in the presence of a single faulty process (such as consensus, choosing a leader, ranking, or matching). In order to prove the impossibility result a contradiction is shown among a set of axioms that characterize any faulttolerant protocol solving the problems we treat: In the course of the proof, we present two results of independent interest: first, we show that for any protocol there is a computation in which some procesS is a splitter, i.e., it can split the possible dutputs of the protocol to two disjoint sets. If the protocol is also fault-tolerant, then this splitter must be a decider, i.e., it can split its own output values into two different singletons. These results generalize and extend previously known results for completely asynchronous systems.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion