TY - GEN

T1 - Wait-free k-set agreement is impossible

T2 - 25th Annual ACM Symposium on Theory of Computing, STOC 1993

AU - Saks, Michael

AU - Zaharoglou, Fotios

N1 - Funding Information: *This work was supported in part by NSF grant number CCR89-113S8, AFOSR grants F49-620-93-1-0041 and AFOSR-89-0512B and by DIMACS. ‘Department of Mathematics, Rutgers University, New Brunswick, NJ 08903 and Department of Computer Science and Engineering, University of California San Diego, La Jolla, CaEfornia 92093. $De~~tment of computer Science and 13n@eer@, University of Cfllfornia San Diego, La Jolla, California 92093. This work was performed while visiting DIMACS. Publisher Copyright: © 1993 ACM.

PY - 1993/6/1

Y1 - 1993/6/1

N2 - 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, and it is the same for all processors. This problem is unsolvable deterministically in several standard models, including the asynchronous shared-memory model. The k-set agreement problem is a generalization of the classical consensus proposed by S. Chaudhuri, 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 > 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 processors knowledge 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.

AB - 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, and it is the same for all processors. This problem is unsolvable deterministically in several standard models, including the asynchronous shared-memory model. The k-set agreement problem is a generalization of the classical consensus proposed by S. Chaudhuri, 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 > 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 processors knowledge 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.

UR - http://www.scopus.com/inward/record.url?scp=0027188179&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027188179&partnerID=8YFLogxK

U2 - https://doi.org/10.1145/167088.167122

DO - https://doi.org/10.1145/167088.167122

M3 - Conference contribution

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 101

EP - 110

BT - Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993

PB - Association for Computing Machinery

Y2 - 16 May 1993 through 18 May 1993

ER -