摘要

In the k-set agreement task, each process proposes a value and each correct process has to decide a value which was proposed, so that at most k distinct values are decided. Using topological arguments it has been proved that k-set agreement is unsolvable in the asynchronous wait-free read/write shared memory model, when k %26lt; n, the number of processes. %26lt;br%26gt;This paper presents an elementary, non-topological impossibility proof of k-set agreement. The proof depends on two simple properties of the immediate snapshot executions, a subset of all possible executions, and on the well known handshaking lemma stating that every graph has an even number of vertices with odd degree.

  • 出版日期2013-11-11
  • 单位INRIA