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  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 s 0 ,..., s t  created as follows are wait-free solvable. Simulator s i  is given an input of processor p i  as well as the input to a set of processors of size n-(t+1) with ids higher than i. Simulator s i  outputs for p i  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 1 and n>2, is undecidable, by a simple reduction to the undecidability of the wait-free solvability of 3-processors tasks.
['Eli Gafni']
The extended BG-simulation and the characterization of t-resiliency