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

Question

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?

Answer 1

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.

Answer 2

The wikipedia article does have a reference that answers you question, but perhaps you don't want to read that 26 page paper. I'll give a simplified version of the (quite technical) proof, showing that test-and-set can not solve binary consensus for 3 processes. This kind of argument is widely used in proving consensus numbers.

Let's suppose we have a consensus algorithm using TAS registers for 3 processes.

At any point in time, each process will have a move (instruction) ready to be executed. Which of the the three instructions will be executed is non-deterministic.

Suppose that we are in a bivalent state (a state in which both a 0 or a 1 decision is still possible) and whichever process moves next, the subsequent state will be univalent. Such a state must eventually be reached because of the wait-free condition.

Suppose (w.l.g.) that if process 1 moves, the state will be 0-valent, and that if process 2 moves, the state will be 1-valent. Both moves must be a TAS operation (or at least: some kind of write) on the same register, since if they were TAS operations on distinct registers we could not tell whether process 1 moved first or process 2 moved first.

Let's consider these two possible executions:

• Process 1 moves first, then process 2 moves, then process 3 runs alone
• Process 2 moves first, then process 3 runs alone

From the viewpoint of process 3, these states are indistinguishable since it just sees the value written by process 2. However, in the first case it should give 0 as output, and in the second 1 as output. Clearly, this is a contradiction.

Processes 1 and 2 can decide among themselves which moved first (because they can see what value was in the register before their write) but a third spectator process can not.

Answer 3

Another way to prove that test-and-set cannot be used to solve 3-processors consensus is to show that test-and-set can be implemented using 2-processors consensus. Then, assuming that test-and-set can solve 3-processors consensus leads to a contradiction: Suppose that test-and-set can solve 3-processors consensus; then by replacing test-and-set by its implementation using 2-processors consensus one obtains an implementation of 3-processors consensus using 2-processors consensus, which is impossible. Thus test-and-set cannot solve 3-processors consensus.

To implement test-and-set for n-processors using 2-processors consensus, let processors determine a winner of the test-and-set using a tournament in which each match is implemented using 2-processors consensus (in a match, the processors propose their identifier and the consensus result tells them who wins).

Answer 4

In practical sense a less strict consensus definition might be enough (here I call it light-consensus):

Definition. Light-Consensus is reached between n threads iff (a) each thread either decides on the same value or the value is unknown for it, (b) at least one thread knows the value and (c) this value was actually proposed by one of the threads.

Hence this consensus in its lighter sense permits that some thread does not know the consensus, the value that is decided.

Corollary: In this lighter sense test-and-set has infinite light-consensus number.

Claim: This lighter sense is practical. For instance in order to select the thread to enter the critical section it is not necessary to create consensus in the strict sense. That is to say: each thread has to know whether it has been selected or not, however if it is not selected than it won't have to know which was selected. In other words, for mutual exclusion strict-consensus is not necessary, light is enough.