An enhanced two phase commit protocol for high performance consistency management in replicated state machines

Abstract

State Machines are used to represent a set of transitions, which makes it a useful tool for representing life-cycle of a specific set of events. By utilizing this property, a state machine can be replicated into several machines and each one of them can communicate with one another in order to keep track of the order of changes. This is called the replicated state machine approach and it is highly used in replicated data services where there is a need to manage the consistency of a system. In order to provide any consistency, it is necessary to use a communication algorithm which provides both high throughput, and less number of failures in the case of conflicting operations. One of the widely known communication protocols used in our context is the two-phase commit (2PC) protocol. It provides a two step algorithm in order to manage the committing actions between different machines for the same resource. First it checks if every machine in a network is ready for writing operation, then if a machine receives a successful message from all other machines, it will then proceed to commit the specific operation to all of them. Finally it applies the commit to its own resource. In the case of no priority between the writing actions between different machines, algorithm gives the commit rights to the first machine which can successfully receive OK from all others. However, when priority comes into action, and it becomes necessary to cancel out transitions with less importance, algorithm starts to cancel out some incoming transitions, and in most cases, if the writing operations are too frequent, it cancels out a writing operation even if it obtains its OK from other machines. Disadvantage of the common 2PC algorithm in the case of priority introduction, due to its phases follow one another without any transitions, when an incoming writing request fails, it has to repeat all the preceding events from that point again. When the distance between the last important point of no-return, such as reading a value into cache, and the point of 2PC protocol becomes further away, this affect is increased and the number of messages for a successful transition is increased. In order to reduce the overhead introduced by this problem, a new algorithm is implemented by enhancing the existing 2PC algorithm. Both steps of the 2PC algorithm mentioned is separated from one another, and can be freely deployed in any place on a state machine, as long as their order is preserved.