Evolution vs. Intelligent Design in Consensus Protocols
MetadataShow full item record
Song, YeeJiun; van Renesse, Robbert; Schneider, Fred B.; Dolev, Danny
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.
computer information science; technical report
Previously Published As