Left-Right: State Machine

On this post, we're going to talk about the novel state-machine that is used in the Left-Right mechanism. For those of you who haven't been following our latest posts, the Left-Right technique is a generic concurrency control mechanism that has wait-free read operations.
http://concurrencyfreaks.blogspot.pt/2013/12/left-right-concurrency-control.html

There are two innovations in the Left-Right technique: the first, is the usage of two replicas of the same resource, the second (and much more important) is a new state machine that allows for wait-free progress condition of read operations when accessing the two replicas.

The figure below shows the full state machine for the Writers and the Readers.

All transitions result from an atomic operation, either a get (load) or a set (store). This means that transitions are instantaneous.

A thread performing a write operation starts at state WI and then reads the current value of leftRight, which depending on being either LEFT or RIGHT, and will transition to WL or WR respectively.
I won't go through each and every state and explain why they work the way they do, for that, it's best to read the paper. Instead, I'll cover some important details.
The first of them, is that some of states on the Writer's side will block certain transitions on the Reader's side. One example, is when the Writer is in state W0, the reader's transitions from state P0 to R0 and from P1 to R1, are no longer allowed:


Another important thing to notice is that there are no loops in the state machine of the Readers, which means that the Readers have a finite (constant) number of transitions until they reach the final state F.
Yet another detail, is that the write operation will enter immediately and do its job on the instance opposite to the one indicated by leftRight. It does this because it knows that the previous Writer has already waited for Readers on that instance and all currently running Readers are guaranteed to be on the instance which is currently indicated by leftRight. This way, the algorithm has a state-machine that reduces the number of times the Writer has to wait for Readers as much as possible.

The following movie shows an animation of the state machine of the Readers as a Writer progresses in different scenarios. It starts with the first time a write operation executes, and ends when the third write operation reaches the final state, because the fourth write operation will be similar to the second write operation in terms of state machine configuration:
http://www.youtube.com/watch?v=Npd8UGMiLhw

The youtube video turned out to be a bit too fast, but for the moment that's what we have. We do have another way to represent the same information which was not put on the paper, and it's basically a transition table that shows which states are allowed for the Readers depending on which state the Writer is in:


this table answers the question: When a Writer is in state Wx (column) which Reader's states transitions are allowed (rows) and what are the values of the variables leftRight and versionIndex (bottom two rows)?