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

https://hal.inria.fr/hal-00650623
Contributor : Armando Castaneda <>
Submitted on : Monday, December 12, 2011 - 11:27:49 AM
Last modification on : Tuesday, June 15, 2021 - 4:27:59 PM
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⟩

Share

Metrics

Record views

521

Files downloads

312