@koakuma Sadly only lockfree and not waitfree.
Hm~ why does the lower bound assume that critical steps are CASes and not simple atomic writes? That's probably true in the setup where the number of threads is not bounded, but otherwise I see no obvious reason for that to be true.
Scratch that, I'm reading too inattentively. Still seems slightly fishy in different ways, but I'm probably still reading too inattentively.
@robryk Wait, which lower bound? I only see them saying that their method needs k+1 CASes when uncontended but nothing else I see
As for the bound in section 3, the details escape my understanding but what I do understand is that they are claiming that a k-word MCAS needs to do at least k CASes, but otherwise it doesn't seem to get used elsewhere in the paper?
The abstract made me think that one can assign "worst-case(?) number of CAS per MCAS" to any implementation of MCAS and that they prove that: (a) lower bound for that is k (b) their implementation achieves k+1. That would be a near-optimality claim about their implementation. However, that's not the case, because there are actually two different such values: the one the lower bound (in the Impossibility section) talks about is not the one they show is equal to k+1 in their implementation.
In fact, one can probably show that any such implementation, for some adversarial scheduling and operation sequences, might need to do unboundedly many CASes for some MCAS operations (otherwise it would be waitfree).
@robryk re:waitfree, interestingly the paper refers to another MCAS paper that claims to be waitfree: https://www.researchgate.net/publication/271738671_A_Wait-Free_Multi-Word_Compare-and-Swap_Operation
The main downside seem to be that it doesn't have a dedicated "writefree" read operation; reads are basically just an MCAS with funny operands?
(Not on computer now so this is just based on a skim)
@koakuma
Do you understand what is the thing they're providing bounds on? The lower bound seems to be on number of CASes needed pessimistically under some interleaving of contended MCASes and the upper seems to be on number of CASes needed for _uncontended_ MCAS operations.