You call malloc in your implementation -- you realize that memory allocation takes lock at some point, right? To make it truly lock or wait free you need to implement a corresponding memory allocator as well.

Most of the concurrent lock-free search trees published in literature do not even give a garbage collection strategy(assuming the implementation language has no automatic garbage collection). But they still claim lock-free or wait-free. They make assumption that memory can be reclaimed using recent techniques provided in the literature. I'm not sure sure if there is a lock-free Malloc. But that is not the problem the algorithm is trying to solve.

And almost all these algorithms use Compare-And-Exchange(CAS) instruction which internally uses locks.

With that reasoning, you should write your own kernel too -- you realize that the kernel scheduler will take locks at some point, right?

I think that malloc is a sufficiently abstract operation here that its implementation shouldn't constitute whether the algorithm as a whole is lock-free or not.

Lock-free algorithms don't usually depend on an OS being present. They could just as easily run in an environment that has no scheduler. But if the algorithm calls malloc, that is a hard dependency.

If an algorithm depends on malloc, it needs to prove that lock-free/wait-free malloc() exists before calling itself lock/wait-free.

Not really. Lots of applications where lock free algorithms are justified usually implement their own memory allocators.

Malloc can be lock free if you add a thread which wakes up periodically and ensures there is free memory available.

Also, any algorithm can be made mostly malloc free if you keep a freelist instead of freeing memory. Malloc will then only be called enough times to fill the max utilization.

In short, glibc malloc is wait-free. In long, You may not know that terminology of "lock-free" does not mean that it does not mean never using locks.

This book is published in 2013. Earlier than this arxiv paper.

It's sad to be in "the other cultural circle", isn't it? Imagine that in western Europe a number of theorems by eastern European mathematicians is known by the name of the western professor who would propagate it...

Also: I feel there should be a comma in the sentence above, but can't figure out where to put it :/

I understand what you're trying to convey and agree. I thought you might not have noticed the email address of the authors. Two of the authors' email addresses are of IIT Delhi, one of the universities managed by the Government of India.

So these authors are in "the other cultural circle" too. One in which there's more than 10 times competition in the educational system for funding, compared to not only western and European counterparts but the Japanese one too, which the parent comment I think is/was a part of. Not just funding for cool projects. There is a very dire need for good universities but higher education in a good university is very difficult to have.

I think you want to use commas to set off "in Western Europe". I think it's referred to as an "aside".

After the 3, in place of the period.

Do you suggest that they've used your findings without referencing you? You can make an inquiry I believe. Other than that, if their method is completely different or they've arrived to the same solution independently - there is nothing wrong. It is not about the competition who was first, isn't it?

I think that in this day and age we ought to have a way to share knowledge so that we aren't repeating the same (completed) research unknowingly.

In maths it is thought to be beneficial to come up with a diferent proof of the same theorem though, so maybe in computing the similar idea that coming up with another implementation/demonstration/proof has value too

you rock! So what do the threads do when they are idle? Don't you put them to sleep?