2
$\begingroup$

I read this answer below and got into another question.

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

I also read that read/write registers have consensus number 1.

But I see that in test&set (also in compare&swap) by using read write registers alone, we still arrive at consensus.

I think I am missing something very fundamental here. Need help.

The protocol in the accepted answer of the link is as mentioned below

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|].
Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Consensus number and consensus hierarchy are defined in the classic paper "Wait-Free Synchronization" by Maurice Herlihy, 1991.

Note the keyword: wait-free.

Since you did not give the algorithms for test&set using read/write registers only, I guess that they are not wait-free. (They may be lock-free instead.)

Added:

After the discussions with the OP in the comments, I realize that the OP has not fully understood the difference between atomic test&set registers and atomic read/write registers. He/she thought that the protocol given in the post uses read/write registers only. In fact, it uses test&set registers/operations/instructions in the second step.

A test&set register supports the test&set operation, which is a combination of test and set that cannot be interrupted. See this wiki for more details.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks hengxin. I have edited the question with the protocol, that was provided in accepted answer. I agree with the wait-free part, but I see that in the proofs for test&set and read-write registers we have problem of consensus itself, rather than being wait-free. $\endgroup$
    – ultimate cause
    Jul 15, 2017 at 14:44
  • $\begingroup$ @ultimatecause The protocol in the answer to the linked post implements consensus using test&set. It is not a protocol implementing consensus using only read/write registers. "I see that in test&set (also in compare&swap) by using read write registers alone, we still arrive at consensus." I want to know such protocols and I guess that they are not wait-free. $\endgroup$
    – hengxin
    Jul 15, 2017 at 14:51
  • $\begingroup$ Oh, so I think there lies the key. I only see read-write registers there, what is that I am missing? $\endgroup$
    – ultimate cause
    Jul 15, 2017 at 14:57
  • $\begingroup$ @ultimatecause In the second step, it use the "test-and-set instruction". So it uses test&set registers. If it were a read/write register, only the read or write operations can be applied. $\endgroup$
    – hengxin
    Jul 15, 2017 at 15:02
  • $\begingroup$ Do you mean, two consecutive operations by same process without being interleaved, in which one is read and other is write are not allowed? Because in the tree for read/write registers in Maurice Herlihy's paper two processes one reading and the other writing on same register is allowed. Test&Set instruction also uses read-write registers alone. $\endgroup$
    – ultimate cause
    Jul 15, 2017 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.