hengxin

@ultimatecause See my updated answer.

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

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

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

@ultimatecause Yes. What is your question then?

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

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

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

I checked $H_8$ and it is what the authors claimed. So it is probably we now have the right concepts of serializability and linearizability.

A and B are two different processes. We can put all the operations issued by B before those issued by A. Sequential consistency only requires the individual program order.

In the same way, I think the authors are correct in $H_8$. I will check it now.

Being sequential consistent, we can put all the the operations issued by B before those issued by A.

@WanderingLogic I made a mistake. $H_7$ is actually sequential consistent.

@WanderingLogic Now I see. It seems that queues have been treated as stacks (or we have wrong understandings of Linearizability and Serializability).

Yes, I agree. And the authors also agree (the last sentence of the paragraph quoted). So I am afraid that I don't get your confusion.

when A and B are interpreted as transactions instead of processes.

?? The authors also claim that $H_8$ is not even serializable.

@WanderingLogic I don't know whether they are local properties for transactions (I am not aware of how to define "local" when referring to transactions). Do you have references for strict serializability for objects?

@WanderingLogic I think for transactions linearizability is equivalent to strict serializability.

@WanderingLogic Yes. I have just checked (just Ctrl + F) the "Software Transactional Memory" paper (by Nir Shavit and Dan Touitou). They use the term "linearizability".

So do we have the same understanding now: I used linearizability for transactions and you used strict serializability? Maybe strict serializability is earlier and more classic than linearizability, when used for transactions.

"linearizability was defined for objects, not transactions.", I agree. However, I think many papers have also used the term linearizability for transactions. When used for transactions, it is strict serializability.

@WanderingLogic By "real-time" order, I mean: If transaction T1 commits before another transaction T2 starts, then T1 is called to precede before T2. Such "precedes" relation defines the "real-time" partial order between transactions.

In contrast, Serializability does not enforce such "real-time" order. It only enforces the basic program order between transactions issued by each individual process. In this sense, Linearizability is stronger than Serializability, since "real-time" order implies program order.

@WanderingLogic To me, "instantaneously" means something more than just "grouped together and not interleaved with any other instructions". In my understanding, Linearizability for transactions requires each transaction to appear to take effect instantaneously at some moment between its start event and commit event. This is, it enforces the "real-time" partial order between transactions.

@SimonMarkett OK. I have to go back to the dormitory now. I will think over it. Thanks for your time.

@SimonMarkett Could you please state your condition again? Maybe I have misunderstood it.

I agree with you that the current $k-1$ condition is stronger than $\forall S'_i \in S', \forall S_j \in S: S_i' \cap S_j = \emptyset$ when $k \ge 2$. That is my want.

Yes, I don't want the $S_i' \cap S_j' = \emptyset$ explicitly.

@SimonMarkett According to your comment, I have added the $k$-intersect property and $k-1$-nonintersect property. These two properties are what I want at first. And I don't want the "reverse" direction of the $k-1$-nonintersect property (For any $S_i \in QS$ there exist $k−1$ sets in $S′$ such that their union doesn't intersect $S_i$). Thanks for pointing them out.

@SimonMarkett Generally, I don't need this "direction" of $k-1$-property. However, I don't figure out the subtle difference between $k-1$-property and this "reverse" $k-1$-property.

@SimonMarkett They ($S_{ij}'$) are distinct and $n \ge k$. I have modified it. Thx.

@dtldarek Yes, the non-intersect property is necessary. I have added it. Thx.