BFT-TO: Intrusion Tolerance with Less Replicas

State machine replication (SMR) is a generic technique for implementing fault-tolerant distributed services by replicating them in sets of servers. There have been several proposals for using SMR to tolerate arbitrary or Byzantine faults, including intrusions. However, most of these systems can tolerate at most f faulty servers out of a total of 3f+1. We show that it is possible to implement a Byzantine SMR algorithm with only 2f+1 replicas by extending the system with a simple trusted distributed component. Several performance metrics show that our algorithm, BFT-TO, fares well in comparison with others in the literature. Furthermore, BFT-TO is not vulnerable to some recently presented performance attacks that affect alternative approaches.