Thursday, December 5, 2013

Left-Right: A Concurrency Control Technique with Wait-Free Population Oblivious Reads

Finally, after more than two years of work, we've decided to make public a new Concurrency Control technique which we named Left-Right.
The paper is available here:

http://sourceforge.net/projects/ccfreaks/files/papers/LeftRight/leftright-extended.pdf

What is it?
The easiest way to explain it is, to say it is a kind of Reader-Writer Lock that is Wait-Free for Readers, but in fact, it is much more than that.

Just in case you missed it the first time, this means it does not block Readers... or put in another way, a Writer and multiple Readers can simultaneous execute, and you don't have to worry about atomicity, or memory management, or invariants... and it's wait-free for Readers!

Some Java source code here:
http://sourceforge.net/projects/ccfreaks/files/papers/LeftRight/LRScalableTreeSet.java
http://sourceforge.net/projects/ccfreaks/files/java/src/com/concurrencyfreaks/leftright/LRScalableGuard.java
but this technique can easily be implemented on Scala, C++1x, or C11.


One thing to keep in mind is to not confuse this with "Double Instance Locking", a technique which also uses two instances, but the mechanism is very different: Left-Right is wait-free for read operations, while Double Instance Locking is lock-free for read operations (both are blocking for write operations).
http://concurrencyfreaks.com/2013/11/double-instance-locking.html

We'll talk more about the Left-Right in upcoming posts.

No comments:

Post a Comment