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.

@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.

Oh, so I think there lies the key. I only see read-write registers there, what is that I am missing?

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.

@ultimatecause Test&set is an atomic operation that read/write registers do not support.

Hi Friend. Thanks

I did not know that we have this facility. I am new to using this forum.

This corollary is given in the paper "Wait-free Synchronization"

@ultimatecause Yes. What is your question then?

I am just trying to relate and understand your statements. You said that atomic registers are different from read write registers. But that does not seems to be matching with the corollary or at least I don't see how does it conforms.

Just before this corollary he proved that, consensus number of read/write registers in 1 and then he said that we cannot implement any other protocol of greater consensus number. So he seems to be saying that both are same.

@ultimatecause No. What I mean is the following: the atomic test&set register is different from the atomic read/write register. The consensus number of the read/write registers is 1 while that of test&set registers is 2. Therefore, there are no wait-free implementations of test&set registers/operations/instructions using only atomic read/write registers.

Fine, I accept. 1) How are the two things differ? 2) I also see that, in both cases for test&set and read/write register, we have proved that there is no consensus possible. We did not reach to the point of saying that if the protocol is wait-free or not.

@ultimatecause 1) What are the "two things" you are referring to? 2) The concept of consensus number is based on the concept of "wait-free". The term "impossibility" means no wait-free protocols. It does not rule out, for example, lock-free protocols.

I am sorry I will rewrite it - 1) How do test&set register differ from normal read/write register? I see that both are registers where we can read and write. In Herlihy's proof he did not make any such distinction 2) I also see that, for test&set register and read/write register, we have proved that the CONSENSUS itself is NOT possible. We did not reach to the point of saying that if the protocol is wait-free or not.

@ultimatecause 1) 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. 2) The full paper focuses on "wait-free" protocols. See the introduction part of the paper.

Thanks friend. I appreciate that you delayed your work to answer my questions. Is their anyway you get credit for this discussion ?

@ultimatecause You are welcome. I am glad that this discussion helps. You can vote and accept the answer if it does answer your questions.

@ultimatecause See my updated answer.