Skip to Main content Skip to Navigation

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

2 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
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}).
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]

https://hal.inria.fr/hal-00650623
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

### File

proofSA-5.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00650623, version 1

### Citation

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