Left-Right Brief Announcement

The Left-Right technique was accepted as a brief announcement in DISC 2015.
You can get the proceedings of DISC here (behind a paywall).

It was super-cool to have our work accepted at one of the major conferences, and on top of that we got to see a bit of Tokyo, and we saw some interesting talks there. There were two that caught my attention:

- Wait-Freedom is Harder than Lock-Freedom under Strong Linearizability

https://denysyuk.files.wordpress.com/2015/07/main.pdf
This one is interesting because it shows a proof that there is a strong relation between the choice of Consistency Model and the provided Progress Condition. This idea is not new, what is new is that they were able to prove that for certain situations, it is not possible to have wait-freedom under a consistency model named Strong Linearizability, which as the name implies, is stronger than Linearizability. If you don't know what Linearizability is then take a look at my CppCon talk, but basically it's the consistency model that locks provide, so it's very intuitive to reason about it.

It was already intuitive that relaxing the consistency makes it easier to provide algorithms and data structures that are lock-free and wait-free, or that are "faster" (whatever that means), but having a formal proof that this is so (at least for a specific scenario) is a very welcomed addition.

Something that I asked one of the presenters of this paper was: If Lock-Free is possible under Strong Linearizability but Wait-Free is not, how about everything in between?
Lock-Free gives the guarantee that at least one thread is making progress, and Wait-Free gives the guarantee that all threads are making progress, but what if I have an algorithm that gives the guarantee that there are always at least two threads making progress? Or an algorithm that guarantees that at least N-1 threads are making progress?
Where is the distinction? Is it when we transition from N-1 to N (wait-freedom) or is it somewhere in between?
I guess this question is a bit on the theoretical side, but still interesting (to me anyways).
Perhaps future work will address it.

- Torwards Automatic Lock Removal for Scalable Synchronization

https://labs.yahoo.com/publications/8476/towards-automatic-lock-removal-scalable-synchronization-full-version
This one was about an optimistic concurrency technique, but I have several things to say about it, so I'll try to dedicate a post to it.