Abstract
A distributed task T on n processors is an input/output relation between a collection of processors' inputs and outputs. While all tasks are solvable if no processor may ever crash, the FLP result revealed that the possibility of a failure of just a single processor precludes a solution to the task of consensus. That is consensus is not solvable 1-resiliently. Yet, some nontrivial tasks are wait-free solvable, i.e. n-1-resiliently. What tasks are solvable if at most t<n processors may crash? I.e. what tasks are solvable t-resiliently?
The Herlihy-Shavit condition characterizes wait-free solvability, i.e., when t=n-1. The Borowsky-Gafni (BG) simulation extends this characterization to the t-resilient case for the case "colorless" tasks - tasks like consensus in which one processor can adopt the output of any other processor. It does this by reducing questions about t-resilient solvability, to a question of wait-free solvability. The latter question has been characterized.
In this paper, we amend the BG-simulation to result in the Extended-BG-simulation, an extension that yields a full characterization of t-resilient solvability: A task T on n processors is solvable t-resiliently iff all tasks T' on t+1 simulators s0,..., st created as follows are wait-free solvable. Simulator si is given an input of processor pi as well as the input to a set of processors of size n-(t+1) with ids higher than i. Simulator si outputs for pi as well as for a (possibly different) set of processors of size n-(t+1) with ids higher than i. The input/output of the t+1 simulators have to be a projection of a single original input/output tuple-pair in T.
We demonstrate the convenience that the characterization provides, in two ways. First, we prove a new equivalence result: We show that n processes can solve t-resiliently weak renaming with n+(t+1)-2 names, where n>1 and 0<t<n, iff weak-renaming on t+1 processors is wait-free solvable with 2t names. Second, we reproduce the result that the solvability of n-processors tasks, t-resiliently, for t>1 and n>2, is undecidable, by a simple reduction to the undecidability of the wait-free solvability of 3-processors tasks.
