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
In short, the extended BG-simulation REF goes through establishing T , a "variant" of a task T defined on t + 1 simulators, where each simulator is given values for at least n − t processes in T so that when all t + 1 simulators participate, every process in T is given an input.
The extended BG-simulation and the characterization of t-resiliency
STOC '09
Computer Science