An Efficient Implementation of the Quorum Consensus Protocol

The Quorum Consensus(QC) algorithm, a replication control algorithm whichprovides serializability even in the presence of network partitioning, has beenstudied extensively but is not widely implemented in practice. One of thereasons for its lack of acceptance is that the gathering of a quorum for eachoperation in a transaction is non-trivial to implement. The typical approachis either (i) to send each operation to all replica sites and wait for a quorumof sites to respond, or (ii) to send each operation to a random quorum set,then retry if not all responses are received after a timeout. Bothalternatives are difficult to implement.This paper proposes a simple implementation approach which makes use of anestimated uplist at the site of a transaction coordinator. Such a listprovides a hint on which replica sites are currently communicable. We arguethat such a list is typically maintained for systems on modern-day networks forfault tolerance and/or network routing. Using such a list, a transactioncoordinator dispatches an operation to a quorum set whose members arecommunicable. The operation is successful if all members respond in time;otherwise, it has failed and the transaction is subsequently aborted.The implementation of this algorithm is straightforward. Our simulationresults indicate that it yields better response time and throughput whencompared with the typical implementation approaches, and at the same time itprovides comparable data availability.