Classic Paxos vs. fast Paxos: caveat emptor

Abstract

Classic Paxos and Fast Paxos are two protocols that are the core of efficient implementations of replicated state machines. In runs with no failures and no conflicts, Fast Paxos requires fewer communication steps for learners to learn of a request compared to Classic Paxos. However, there are realistic scenarios in which Classic Paxos has a significant probability of having a lower latency. This paper discusses one such scenario with an analytical comparison of the protocols and simulation results. 1