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

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00650623
Contributeur : Armando Castaneda <>
Soumis le : lundi 12 décembre 2011 - 11:27:49
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
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〉

Partager

Métriques

Consultations de la notice

429

Téléchargements de fichiers

140