[concurrency-interest] Left-Right - A new concurrency control technique

Nathan Reynolds nathan.reynolds at oracle.com
Wed Jan 1 23:26:25 EST 2014


Fascinating!  It kind of reminds me of the following algorithms that 
guarantee exclusivity without atomic operations.

http://en.wikipedia.org/wiki/Bakery_algorithm
http://en.wikipedia.org/wiki/Eisenberg_%26_McGuire_algorithm
http://en.wikipedia.org/wiki/Peterson%27s_algorithm
http://en.wikipedia.org/wiki/Szymanski%27s_Algorithm
http://en.wikipedia.org/wiki/Dekker%27s_algorithm

readersVersion has 2 sub-arrays (i.e. one for each versionIndex). 
Couldn't we only have 1 array?  Instead of having NOT_READING and 
READING flags.  Have 0 or 1 for reading a particular version and -1 for 
not reading.  This would cut the memory usage in half.

It seems that readersVersion has to be instantiated for every instance.  
Couldn't we only have 1 array for the entire process? Combining the 
previous paragraph's idea with this one... readIndicator.arrive() would 
set the versionIndex first, store-store fence and then set the 
pointer/reference.  This ensures that the writer won't see the 
versionIndex change after the pointer/reference has been set.  
readIndicator.depart() would set the pointer/reference to NULL.  The 
writer has to check the pointer and then versionIndex.

In Java-land, one could create a delegate wrapper for any interface with 
Proxy.newProxyInstance 
(http://docs.oracle.com/javase/7/docs/api/java/lang/reflect/Proxy.html). 
When the InvocationHandler is executed, it determines if the method is a 
read or write method and then executes the appropriate left-right 
logic.  This would allow for writing the left-right logic only in the 
InvocationHandler and then be re-used for all sorts of interfaces.  In 
other words, left-right wouldn't have to be built into every data 
structure.  Write Once Use Everywhere.

-Nathan

On 12/25/2013 5:44 AM, Pedro Ramalhete wrote:
> Hello,
>
> We are pleased to announce a new concurrency control technique which 
> we named "Left-Right" and that allows Wait-Free Populations Oblivious 
> read operations. The easiest way to explain what it is, is to say that 
> it's a "kind of" Reader-Writer Lock that doesn't block for Readers, 
> which makes it ideal for low-latency and real-time deployment scenarios:
> http://sourceforge.net/projects/ccfreaks/files/papers/LeftRight/leftright-extended.pdf
>
> In case you missed it above, this means that you can have one Writer 
> and multiple Readers executing simultaneously, and unlike optimistic 
> read locks, you don't have to worry about atomicity, or memory 
> management, or invariants.
>
> Similarly to a Reader-Writer lock, it can be applied to any 
> (non-thread-safe) data structure and enable it to be used in a 
> multi-threaded application, where it will be Blocking for Writers, and 
> Wait-Free for Readers. It can be implemented in Java, Scala, C11, or 
> C++1x.
> Sample source code can be seen here:
> http://sourceforge.net/projects/ccfreaks/files/papers/LeftRight/LRScalableTreeSet.java
> http://sourceforge.net/projects/ccfreaks/files/java/src/com/concurrencyfreaks/leftright/LRScalableGuard.java
>
> Its two main innovations are, the usage of two instances, and the new 
> concurrency control algorithm whose novel state machine gives 
> wait-free guarantees for read operations.
>
>
> There is another technique which also uses two instances but requires 
> 3 locks, which perhaps has already been discovered, that we named 
> "Double Instance Locking" and it is much easier to understand and 
> implement, but it is only Lock-Free for read operations:
> http://sourceforge.net/projects/ccfreaks/files/papers/DoubleInstance/DoubleInstanceLocking.pptx
> http://sourceforge.net/projects/ccfreaks/files/papers/DoubleInstance/DoubleInstanceLockGuard.java
> http://concurrencyfreaks.com/2013/11/double-instance-locking.html
>
> We would like to hear expert's comments on it   ;)
>
> Merry Christmas,
> Pedro & Andreia
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20140101/ea732a55/attachment.html>


More information about the Concurrency-interest mailing list