Increasing Performance in Byzantine Fault-Tolerant Systems with On-Demand Replica Consistency

Traditional agreement-based Byzantine fault-tolerant (BFT) systems process all requests on all replicas to ensure consistency. In addition to the overhead for BFT protocol and state-machine replication, this practice degrades performance and prevents throughput scalability. In this paper, we propose an extension to existing BFT architectures that increases performance for the default number of replicas by optimizing the resource utilization of their execution stages. Our approach executes a request on only a selected subset of replicas, using a selector component co-located with each replica. As this leads to divergent replica states, a selector on-demand updates outdated objects on the local replica prior to processing a request. Our evaluation shows that with each replica executing only a part of all requests, the overall performance of a Byzantine fault-tolerant NFS can be almost doubled; our prototype even outperforms unreplicated NFS.