Skip to Main content Skip to Navigation
Conference papers

A non-topological proof for the impossibility of $k$-set agreement

Abstract : In the \emph{$k$-set agreement} task each process proposes a value, and it is required that each correct process has to decide a value which was proposed and at most $k$ distinct values must be decided. Using topological arguments it has been proved that $k$-set agreement is unsolvable in the asynchronous \emph{wait-free} read/write shared memory model, when $k < n$, the number of processes. This paper presents a simple, non-topological impossibility proof of $k$-set agreement. The proof depends on two simple properties of the \emph{immediate snapshot executions}, a subset of all possible executions, and on the well known graph theory result stating that every graph has an even number of vertices with odd degree (the \emph{handshaking lemma}).
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Armando Castaneda Connect in order to contact the contributor
Submitted on : Monday, December 12, 2011 - 11:27:49 AM
Last modification on : Friday, January 21, 2022 - 3:10:20 AM
Long-term archiving on: : Tuesday, March 13, 2012 - 2:21:20 AM


Files produced by the author(s)


  • HAL Id : hal-00650623, version 1


Attiya Hagit, Armando Castaneda. A non-topological proof for the impossibility of $k$-set agreement. 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Oct 2011, Grenoble, France. ⟨hal-00650623⟩



Record views


Files downloads