Using approximate agreement to obtain complete disagreement: the output structure of input-free asynchronous computations

A distributed task for n processes is defined by a decision mapping, which maps each input vector to a set of “correct” decision vectors. For an integer t, the t-solvability problem is the problem of deciding from the specification of a distributed task T whether T can be solved in a completely asynchronous environment in the presence of at most t crash failures. This problem is known to be NP-complete for t=1, but for other values of t it is not even known to be decidable. In this paper we study the t-solvability problem by studying the properties of input/output mappings defined by t-resilient protocols. We concentrate on the restricted case where the input is fixed-which reduces the problem to studying properties of the outputs of input-free protocols, which are protocols designed for a single input vector. Our main result is a complete characterization of the sets of vectors V such that there is an input free t-resilient protocol which outputs V. Somewhat surprisingly, this characterization is independent on t-that is, it is the same for all 1⩽t<n. One implication of our result is that for any n>2 and for any 1⩽t<n, there is a t-resilient protocol which achieves complete disagreement-the output vectors of the protocol are all the binary vectors except the allzero and allone vectors. Another example is a wait-free protocol whose output set consists of all the legal output vectors of the renaming task with n+1 new names. These two results are interesting since the natural multi-input generalizations of those problem cannot be solved by wait-free protocols. In the course of our proof, we present a new, simple version of wait-free approximate agreement protocol