A non-topological proof for the impossibility of $k$-set agreement - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

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

Résumé

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}).
Fichier principal
Vignette du fichier
proofSA-5.pdf (192.39 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00650623 , version 1 (12-12-2011)

Identifiants

  • HAL Id : hal-00650623 , version 1

Citer

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⟩
237 Consultations
212 Téléchargements

Partager

Gmail Facebook X LinkedIn More