Wait-free k-set agreement is impossible: The topology of public knowledge (Extended abstract)

Michael Saks, Fotios Zaharoglou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

69 Scopus citations

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, 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993
PublisherAssociation for Computing Machinery
Pages101-110
Number of pages10
ISBN (Electronic)0897915917
DOIs
StatePublished - Jun 1 1993
Event25th Annual ACM Symposium on Theory of Computing, STOC 1993 - San Diego, United States
Duration: May 16 1993May 18 1993

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129585

Other

Other25th Annual ACM Symposium on Theory of Computing, STOC 1993
Country/TerritoryUnited States
CitySan Diego
Period5/16/935/18/93

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Wait-free k-set agreement is impossible: The topology of public knowledge (Extended abstract)'. Together they form a unique fingerprint.

Cite this