Dynamic State Partitioning in Parallelized Byzantine Fault Tolerance

Recent research works have shown that applying parallelization to request processing in Byzantine Fault Tolerance (BFT) can bring significant performance improvement. Based on partitioned service state, parallelism is introduced to both agreement and execution to address performance and scalability limitations caused by the global total order of all requests. However, in case of inefficient state partitioning, expensive synchronization among partitions is expected, which leads to a considerable performance loss. To improve the efficiency of parallel processing, we present Dynamic State Partitioning (DYPART), a framework that maps service state into multiple partitions and periodically reconfigures the partitions for different usage patterns. DYPART relies on the knowledge about relations between the state objects for partitioning, which is obtained by collecting request dependencies. It utilizes a high-performance graph partitioning algorithm to ensure that the resulting state partitions can achieve both workload balance and low synchronization among partitions. Our evaluation of a key-value store shows that compared to a random partitioning, DYPART can improve the performance by at least 40%.