The MathNet Korea
Information Center for Mathematical Science

### 논문검색

Information Center for Mathematical Science

#### 논문검색

SIAM Journal on Computing
( Vol. 29 NO.5 / (2000))
Wait-Free $k$-Set Agreement is Impossible: The Topology of Public Knowledge

Pages. 1449-1483
Abstract 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 input values, with the requirement that all processors decide the same value. A central result in distributed computing is that, in several standard models including the asynchronous shared-memory model, this problem has no deterministic 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 decision values produced may be different, as long as the number of distinct values is at most k. For $n > k geq 2$ it was not known whether this problem is solvable deterministically in the asynchronous shared memory model. In this paper, we resolve this question by showing that for any 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 based on the development of a topological structure on the set of possible processor schedules of a protocol. This topological structure has a natural interpretation in terms of the knowledge of the processors of the state of the system. This structure reveals a close analogy between the impossibility of wait-free k-set agreement and the Brouwer fixed point theorem for the k-dimensional ball. 1. Introduction 2. Definitions and preliminary results 3. Reformulating Theorem 1.1 and a topological analogy 4. Bijections between $\hat{\sum} (P)$ and $Hull (E^P)$ 5. Reviewing the geometric case 6. Proof of Theorem 3.2 distributed computing, consensus, Sperner's lemma, wait-free 68Q22, 68R10, 54A99