[concurrency-interest] Left-Right - A new concurrency control technique
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.
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
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.
On 12/25/2013 5:44 AM, Pedro Ramalhete wrote:
> 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:
> 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
> Sample source code can be seen here:
> 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:
> We would like to hear expert's comments on it ;)
> Merry Christmas,
> Pedro & Andreia
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Concurrency-interest