Fault-tolerant decision making in totally asynchronous distributed systems
Michael F. Bridgland, Ronald J. Watro · 1987
According to a theorem of Fischer, Lynch, and Paterson [2], there is no algorithm for binary consensus decisions in a totally asynchronous distributed system of mortal processes, i.e., processes that are subject to deaths (unannounced failstop faults).Until recently, this result seems to have been interpreted to mean that to-talIy asynchronous systems are incapable of fault-tolerant decision making, and therefore of accomplishing nontrivial tasks determinist icalIy.The primary objective of this paper is to show that the ability or inability of a totally asynchronous distributed system to make decisions despite process deaths depends largely on the kinds of decisions to be made.On the one hand, we show that a broad class of decisions-including not only consensus, but all decisions enabling a system to adapt to the loss of data known only to faulty processes-cannot be made.On the other hand, we show that some types of This work was supported by the U. S.