|
Abstract : |
Abstract. We investigate the impossibility of solving certain problems in an unreliable distributed system where multiple processes may fail. We assume undetectable crash failures which means that a process may become faulty at any time during an execution and that no event can happen 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 problems are variants of problems which are unsolvable in the presence of a single faulty process (such as consensus, choosing a leader, ranking, matching). In order to prove the impossibility result a contradiction is shown among a set of axioms which characterize any fault-tolerant protocol solving the problems we treat. In the course of the proof, we present two results that appear to be of independent interest: first, we show that for any protocol there is a computation in which some process is a splitter. This process can split the possible outputs of the protocol to two disjoint sets. In case that the protocol is also fault-tolerant, then this splitter must be a decider, that can split its own output values into two different singletons. These results generalize and expand known results for asynchronous systems. 1, |
