A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor
Ofer Biran, Shlomo Moran, Shmuel Zaks · 1988
Fischer, Lynch and Paterson showed in a fundamental paper that achieving a distributed agreement for N > I processors is impossible in the presence of one faulty processor.This result was later extended by Moran and Wolfstahl who showed that it holds for any task with a connected input graph and a disconnected decision graph (whcrc a vcrtcx in the input [decision] graph is an N-tuple of input [decision] values of the processors, and there is an edge connecting two vertices if and only if they differ in exactly one component),In this paper we extend that latter result, and in fact we set the exact bordedine between solvable and unsolvable tasks, by giving a necessary and sufficient condition for a task to be solvable in the presence of a faulty processor.We present a universal protocol which solves any task which is found to be solvable by our condition.Using our characterization, we derive a novel technique to prove lower bounds on the number of messages that must be sent due to processor failure; specifically, we show that for each fixed JV > 2 there exist distributed tasks for Iv processors that can be solved in the presence of a faulty processor, but any protocol that solves them must send arbitrarily many messages in the worst case.