In this paper, the author extends the classic Paxos algorithm and proposes a fast consensus algorithm, Fast Paxos. In the normal case, Fast Paxos guarantees that learning can occur in two message delays when there is no collision. If there exists a collision, learning can be guaranteed to occur in three message delays. This paper first introduces the classic Paxos algorithm, and then present new designs about Fast Paxos. In order to save time, the proposer sends its proposals directly to the acceptors, bypassing the leader. However, collisions may occur because proposals are not issued by the leader. Once a collision is detected, the leader will step in and resolve it with a classic round. After that, the author discusses some implementation considerations about how to choose quorums, how to avoid collisions in uncoordinated recovery and the cost of Fast Paxos.
- The author improves the performance of the classic Paxos algorithm.
- The author gives a TLA+ specification of Fast Paxos, which is general enough to encompass all the variants.
- Fast Paxos requires only two message delays when there is no collision, which is faster than the Paxos algorithm in the normal cases.
- Even if a collision does occur, the uncoordinated recovery of Fast Paxos only introduces one more message delay.
- Fast Paxos can be further generalized to handle Byzantine failures.
- Fast Paxos is based on the assumption of stable storage that survives failure and restarts, but this cannot always be guaranteed.
- Fast Paxos requires more acceptors in the fast quorums.
- Starting recovery will incur extra costs if there is a collision in a fast round.