IMPOSSIBILITY RESULTS IN THE PRESENCE OF MULTIPLE FAULTY PROCESSES

We investigate the possibility of solving certain problems in an unrel iable asynchronous distributed system where multiple processes may fai l. We assume undetectable crash failures, which means that a process m ay become faulty at any time during execution and that no event can oc cur on a process after it fails. A sufficient condition is provided fo r the unsolvability of problems in the presence of multiple faulty pro cesses. Families of problems are shown to be solvable in the presence of t - 1 faulty processes but unsolvable in the presence of t faulty p rocesses for any t. These are variants of problems unsolvable in the p resence of a single faulty process such as consensus, choosing a leade r, or renaming. Consequently, we exhibit a strict solvability hierarch y of classes of problems, depending on the number of failures. In orde r to prove the impossibility result a contradiction is shown among a s et of axioms that characterize any fault-tolerant protocol solving the problems we treat. Six axioms are presented that define the essential properties of asynchronous computation. An additional axiom defines a protocol to be nontrivial if in some execution n - t processes have t heir input values read, and yet the output value for one of the proces ses is still undetermined. In the course of the proof, we present two results of independent interest. We show that any nontrivial asynchron ous protocol must have a splitter process, regardless of any faults. I ntuitively, if left to run on its own at some point, a splitter -nay f orce choosing either of two distinct output values for some (possibly other) process. Then we show that in any nontrivial protocol that tole rates up to t greater-than-or-equal-to 1 crash failures, such a splitt er must be a decider, where a decider is a splitter for its own values . (C) 1994 Academic Press, Inc.