Wait-free k-set agreement is impossible: The topology of public knowledge

In the classical consensus problem, each of n processors receives a private input value and produces a decision value which is one of the original inp ut values, with the requirement that all processors decide the same value. A central result in distributed computing is that, in several standard mode ls including the asynchronous shared-memory model, this problem has no dete rministic solution. The k-set agreement problem is a generalization of the classical consensus proposed by Chaudhuri [Inform. and Comput., 105 (1993), pp. 132-158], where the agreement condition is weakened so that the decisi on values produced may be different, as long as the number of distinct valu es is at most k. For n > k greater than or equal to 2 it was not known whet her this problem is solvable deterministically in the asynchronous shared m emory model. In this paper, we resolve this question by showing that for an y k < n, there is no deterministic wait-free protocol for n processors that solves the k-set agreement problem. The proof technique is new: it is base d on the development of a topological structure on the set of possible proc essor schedules of a protocol. This topological structure has a natural int erpretation in terms of the knowledge of the processors of the state of the system. This structure reveals a close analogy between the impossibility o f wait-free k-set agreement and the Brouwer fixed point theorem for the k-d imensional ball.