Evolution vs. Intelligent Design in Consensus Protocols

Abstract

Consensus is an important building block for building replicated systems, and many consensus protocols have been proposed. In this paper, we show that many consensus protocols can be derived from the same simple genes. We present these genes in the form of a skeleton algorithm that can be configured to produce, among others, three well-known consensus protocols: Paxos, Chandra- Toueg, and Ben-Or. Although each of these protocols specify only one quorum system explicity, we show that all employ a second quorum system. We use the skeleton algorithm to implement a replicated service, allowing us to compare the performance of these consensus protocols under various workloads and failure scenarios. From this we learn, for example, that weak leader election in Paxos unnecessarily causes performance degradation in certain failure scenarios.