Quorum-Based Commit Protocol

The problem with 3-phase commit protocol

As we observed in the previous lesson, the main issue with the 3PC protocol occurs at the end of the second phase, where a potential network partition can bring the system to an inconsistent state.

This can happen when participants attempt to unblock the protocol by taking the lead without having a picture of the overall system, resulting in a split-brain situation.

Coping with the problem

Ideally, we would like to cope with this network partition without compromising the safety of the protocol. This can be done using a concept we have already learned in this course: a quorum.

This approach is followed by the quorum-based commitD. Skeen, “A Quorum-Based Commit Protocol,” 1982. protocol.

This protocol is significantly more complex when compared to the other two protocols we described previously, so we should study the original paper carefully to examine all the possible edge cases. However, we will attempt to give a high-level overview of the protocol in this section.

As we mentioned before, this protocol leverages the concept of a quorum to ensure that different sides of a partition do not arrive at conflicting results.

The protocol establishes the concept of a commit quorum $(V_C)$ and an abort quorum $(V_A)$.

A node can proceed with committing only if a commit quorum has been formed, while a node can proceed with aborting only if an abort quorum has been formed.

The values of the abort and commit quorums have to be selected so that the following property holds:

$V_A + V_C > V$

$V$ is the total number of participants of the transaction.

Based on the fact that a node can be in only one of the two quorums, it’s impossible for both quorums to be formed at two different sides of the partition and lead to conflicting results.

Sub-protocols in quorum-based commit protocol

The quorum-based commit protocol comprises three different sub-protocols used in different cases:

• The commit protocol, which is used when a new transaction starts
• The termination protocol, which is used when there is a network partition
• The merge protocol, which is used when the system recovers from a network partition

Commit protocol

This protocol is very similar to the 3PC protocol. The only difference is that the coordinator waits for $V_C$ number of acknowledgments at the end of the third phase to proceed with committing the transaction.

If there is a network partition at this stage, the coordinator can be rendered unable to complete the transaction. In this case, the participants on each side of a partition will investigate whether they can complete the transaction, using the following protocol.

Termination protocol

Initially, a (surrogate) coordinator will be selected from amongst the participants with a leader election.

Note that it’s irrelevant which leader election algorithm is used. Even if multiple leaders are elected, the correctness of the protocol is not violated.

The elected coordinator queries the nodes of the partition for their status.

If there is at least one participant that has committed (or aborted), the coordinator commits (or aborts) the transaction, maintaining the atomicity property.

If there is at least one participant at the prepare-to-commit state, and at least $V_C$ participants waiting for the result of the votes, the coordinator sends prepare-to-commit to the participants and continues to the next step.

Alternatively, if there’s no participant at the prepare-to-commit state and at least $V_A$ participants waiting for the results vote, the coordinator sends a prepare-to-abort message.

Note that this message does not exist in the commit protocol, but only in the termination protocol.

The last phase of the termination protocol waits for acknowledgments and attempts to complete the transaction in a similar fashion to the commit protocol.

Merge protocol

The merge protocol is simple. It includes a leader election amongst the leaders of the two partitions that are merged, and then the execution of the termination protocol we described.