Development and Evaluation of CheapBFT: An Efficient Byzantine Fault Tolerant Protocol

Abstract: With the growth of computer services in Internet, the availability and integrity of these services, and the consequence which their failures might bear, becomes more evident. Inconsistent responses of services as a result of arbitrary behaviour of replicas, called Byzantine failures, will be handled by more additional replicas compared to usual crash stop failures. In this thesis, CheapBFT a new Byzantine Fault Tolerant state machine replication(BFT) is described. It is tuned to a minimal resource usage compared with other BFT protocols. Most BFT protocols tolerate f Byzantine failures with replication of services on 3f + 1 replicas whereas CheapBFT requires only f + 1 replicas at the agreement as well as the execution stage during normal operation. In case of suspected or detected faults, we rapidly activate up to f  additional nodes to participate in consensus and execution. Besides the clear benefits in cost, maintenance, management, and complexity of having less replicas to tolerate a certain number of faults, our protocol is simpler than previous ones. The performance evaluation shows that it has better throughput than previous algorithms and better response time with the increasing number of requests.