Why is the consensus number for test-and-set, 2?

Problem Detail: 

According to Wikipedia,

The test-and-set operation can solve the wait-free consensus problem for no more than two concurrent processes.

Why can't it solve the problem for more than two processes?

Asked By : ben

Answered By : Roy O.

Just to make sure we are on the same page, first let us consider these three definitions:

Definition. Test-and-set is a read-modify-write instruction on some binary register (let's just say that 0 and 1 are possible values) where a thread obtains the old value and writes 1.

Definition. Consensus is reached between $n$ threads iff all $n$ threads decide on the same value (the consistency requirement) and all threads decide on a value that was actually proposed by one of the threads (the validity requirement).

Defintion. A consensus protocol is wait-free iff every method call finishes in a finite number of steps.

Now follow two proof sketches.

Claim 1. The consensus number of test-and-set is at least 2. Proof. Suppose that we have two threads 0 and 1 that need to reach consensus. We could do this by letting each thread follow the consensus protocol below:

1. Write your proposed value to $A[t]$, where $t$ is the thread id and $A$ is an array of size 2.
2. Perform the test-and-set instruction on some register $R$, with $R$ initialised to 0.
3. If the return value is 0, you were first: return $A[t]$. Otherwise, you were second: return $A[|t-1|]$.

You can verify yourself that consensus and wait-freeness are satisfied. $\square$

(For the next proof, I will nest some proofs and definitions because I think it will make it easier to follow.)

Claim 2. The consensus number of test-and-set is at most 2. Proof. By contradiction. Suppose we have three threads $A$, $B$ and $C$ that wish to decide on values $a$, $b$ and $c$, respectively, and that we have some valid wait-free consensus protocol that is implemented using test-and-set (and atomic reads and writes).

We can visualise the consensus process as a directed tree, where:

• The root is the state where none of the threads have 'made a move';
• The left child of a node represents the state that results after a move by $A$, the middle child represents the state that results after a move by $B$, and the right child represents the state that results after a move by $C$;
• A leaf node represents a state in which all threads have finished. Associated with a leaf node is a value $a$, $b$, or $c$, where the value depends on which value was decided on for that particular execution.

Definition. Let a state be multivalent if the outcome of the consensus process is not yet determined. In other words, not all possible interleavings of the remaining moves lead to the same result. Let a state be univalent when the outcome of the consensus process is determined.

The root is multivalent. Proof. If only one thread $X$ is active and the other threads lie dormant forever, then $X$ will finish in a finite number of steps (guaranteed by the wait-freeness assumption) and it will decide $x$ (for it has only access to this value and its decision will satisfy the consensus validity requirement). So for our situation, $a$, $b$ and $c$ are all possible outcomes. $\square$

Definition. Let a critical state be a state which is multivalent, with the additional property that a move by $A$ will determine $a$, and a move by $B$ will determine $b$.

There exists a critical state. Proof. From above we know that we start in a multivalent state. Let $C$ make no move at all. As long as either $A$ or $B$ does not force the tree into a univalent state, let it make a move. Wait-freeness guarantees that the tree is finite, so at some point a critical state must be encountered. $\square$

Now consider a scenario where we are in a critical state. There are at least two possibilities:

1) $A$ makes its move (thereby determining $a$) and halts. $B$ then makes its move and halts. Next $C$ runs until it finishes, eventually deciding $a$.

2) $B$ makes its move (thereby determining $b$) and halts. Next $C$ runs until it finishes, eventually deciding $b$. $A$ does not make a move.

Since atomic reads and writes have consensus number 1, $A$ and $B$'s moves had to be test-and-set instructions on the same register (if the registers are different, then $C$ would not be able to tell the order in which $A$ and $B$'s moves happened). From $C$'s perspective, then, scenarios 1 and 2 are indistinguishable, so we must have that $C$ decides both $a$ and $b$. This is impossible. $\square$

That the test-and-set instruction has consensus number 2 follows from both Claims 1 and 2.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33031