# 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}).
Type de document :
Communication dans un congrès
13th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Oct 2011, Grenoble, France. 2011

Littérature citée [18 références]

https://hal.inria.fr/hal-00650623
Contributeur : Armando Castaneda <>
Soumis le : lundi 12 décembre 2011 - 11:27:49
Dernière modification le : mercredi 28 février 2018 - 10:22:57
Document(s) archivé(s) le : mardi 13 mars 2012 - 02:21:20

### Fichier

proofSA-5.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• 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. 2011. 〈hal-00650623〉

### Métriques

Consultations de la notice

## 367

Téléchargements de fichiers