Using approximate agreement to obtain complete disagreement: the output structure of input-free asynchronous computations
Shlomo Moran · 2002
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/spl les/t2 and for any 1/spl les/t>