Date Added: Sep 2011
The authors present two asynchronous Byzantine fault-tolerant state machine replication (BFT) algorithms, which improve previous algorithms in terms of several metrics. First, they require only 2f + 1 replicas, instead of the usual 3f + 1. Second, the trusted service in which this reduction of replicas is based is quite simple, making a verified implementation straightforward (and even feasible using commercial trusted hardware). Third, in nice executions the two algorithms run in the minimum number of communication steps for non-speculative and speculative algorithms, respectively 4 and 3 steps. Besides the obvious benefits in terms of cost, resilience and management complexity - fewer replicas to tolerate a certain number of faults - their algorithms are simpler than previous ones, being closer to crash fault-tolerant replication algorithms.