A Non-topological Proof for the Impossibility of k-Set Agreement

摘要

In the 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 topo-logical arguments it, has been proved that k-set agreement is unsolvable in the asynchronous 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-sct agreement. The proof depends on two simple properties of the 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 handshaking lemma).