Left-Right: Classical algorithm

On this post we are going to cover the classic Left-Right algorithm, and then on future posts we will cover each variant separately.
http://concurrencyfreaks.com/2013/12/left-right-concurrency-control.html

The Left-Right (LR) mechanism is a concurrency control technique that enables Wait-Free read operations for any data structure or object. In other words, it's a kind of Reader-Writer Lock that doesn't block.

To use the LR mechanism you need two instances of the same type, which we will name leftInstance and rightInstance. The mechanism itself is composed of:
leftRight: An atomic variable which the Readers use to determine in which instance they will read;
versionIndex: An atomic variable that tells the Readers which readersVersion indicator they will use;
readersVersion: Two read-indicators that the Readers will mark with the arrived()/depart() operations;
 

To make this as simple as possible, let us start with the readerVersion being each an atomic variable that is incremented and decremented atomically with a fetch-and-add operation. a read-indicator is usually defined has having three distinct operations, which in this case will be implemented as such:
arrive(): Atomically increment 1 using fetch-and-add;
depart(): Atomically decrement 1 using fetch-and-add;
isEmpty(): Returns true if counter is 0, false otherwise;
As such, in its most basic variant, the LR mechanism has four atomic variables: leftRight, versionIndex, readersVersion0, and readersVersion1.

Besides the pointers to the leftInstance and rightInstance and the four atomic variables described above, there is also a writersMutex, which is used to serialize write/modify access to the leftInstance and rightInstance by a single Writer at a time, thus causing the LR to be Blocking for Writers.

The algorithm is quite simple and can be described as follow:
Reader:

1. Read the current value of versionIndex and if it is 0 then increment readersVersion0. If it is 1 then increment readersVersion1;
2. Read the current value of leftRight. If it is LEFT, then go and do the read operation on the leftInstance, otherwise do it on the rightInstance;
3. Decrement the previously incremented readersVersion0/1;

Writer:

1. Acquire the writersMutex;
2. Read the current value of leftRight and if it is LEFT then execute the write operation on the rightInstance, and if it is RIGHT then execute on the leftInstance;
3. Toggle leftRight from LEFT to RIGHT or RIGHT to LEFT;
4. If versionIndex is currently zero then wait until readersVersion1 is at zero, otherwise wait until readersVersion0 reaches zero;
5. Toggle versionIndex from 0 to 1 or from 1 to 0;
6. If versionIndex is currently zero then wait until readersVersion1 is at zero, otherwise, wait until readersVersion0 reaches zero;
7. If the current value of leftRigh is LEFT then execute the write operation on the rightInstance, and if it is RIGHT then execute on the leftInstance;
8. Release the writersMutex;

Notice that a Reader does a single read operation on one of the two instances, but a Writer must execute its operation on both instances, one at a time, waiting for ongoing Readers to finish.
You can see an animation of these two I've put on youtube:
http://www.youtube.com/watch?v=JCXkyXSU29I


















Although it may not seem so at first sight, with this procedure, a Writer will never modify an instance that a Reader is currently reading, thus guaranteeing exclusivity for both. Notice also that the Reader is always at most "one write operation behind" relatively to the "other" instance but even so, the LR technique is linearizable (and sequentially consistent).
Much less obvious than any of the above, is that it is not possible to obtain Wait-Free progress conditions for the Readers without using this (or a very similar) technique. For example, the "Double Instance Locking" pattern is simpler, but it is only Lock-Free for Readers.