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
Michael Saks, Fotios Zaharoglou,
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.
Contents 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
Key words distributed computing, consensus, Sperner's lemma, wait-free
Mathmatical Subject Classification 68Q22, 68R10, 54A99