Improving fast paxos: Being optimistic with no overhead

The paper addresses the cost of consensus algorithms. It has been shown that in the best case, consensus can be solved in two communication steps with f < n/2, and in one communication step with f < n/3 (f is the maximum number of faulty processes). This leads to a dilemma when choosing a consensus algorithm: greater efficiency or higher resiliency degree. Recently Lamport has proposed a solution called Fast Paxos, for partly escaping from this dilemma. The idea is to combine two types of rounds in a single consensus algorithm: fast rounds and rounds of the ordinary Paxos algorithm. In the best case, Fast Paxos solves consensus in one fast round, that is it requires only one communication step. Unfortunately, the combination induces some time overhead, and so Fast Paxos becomes more expensive than ordinary Paxos when fast rounds do not succeed. In this paper we go one step further: we show that it is possible to tentatively execute a fast round before a classical round without any time overhead if the fast round does not succeed.