A Multi-leader Approach of Byzantine Fault Tolerance

Problem

Parallel requests processing is widely used in state machine replication system to achieve high throughput as presented in many recent research works. It has been explored in the field of Byzantine Fault Tolerance (BFT) as well. However, most of the works focus only on the parallelism in execution stage, the performance bottleneck of their agreement protocols, which is caused by a single leader making big efforts to establish a global total order remains unsolved.

Solution

We present a solution that partitions the service state and introduces parallelism to both agreement and execution stages. Application-specific knowledge is used for partitioning and to determine request dependency. Each replica is responsible for a partition so that multiple BFT instances can run in parallel inside of one replica. A predictor is implemented based on the partitioning to verify the leader of the a request according to the partition it might access.