Loading...
Please wait, while we are loading the content...
Similar Documents
A non-topological proof for the impossibility of k-set agreement
| Content Provider | CiteSeerX |
|---|---|
| Author | Castañeda, Armando Attiya, Hagit |
| Abstract | 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 topological 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-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 graph theory result stating that every graph has an even number of vertices with odd degree (the handshaking lemma). |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Correct Process Asynchronous Wait-free Read Write Distinct Value Graph Theory Result Non-topological Proof K-set Agreement Simple Property Non-topological Impossibility Proof K-set Agreement Task Possible Execution Memory Model Odd Degree Topological Argument Handshaking Lemma Immediate Snapshot Execution |
| Content Type | Text |
| Resource Type | Article |
