Improve Dynamic State Partitioning in Parallel BFT Systems

Problem

The traditional Byzantine Fault Tolerance (BFT) state machine replication (SMR) system requires a total order of all requests. There is already new mechanism exploiting parallelism in modern replication systems. The entire state of a service can be split into different partitions and therefore requires only a partial order on the requests visiting the same partition. Our previous work [1] describes such a multi-leader BFT framework. This however arises the new challenge to define the partitions in a proper way, which has been later addressed by a high-performance dynamic partitioning mechanism [3]. However, this work leaves a few open issues that can be solved to further improve the quality of state partitioning as well as the system performance.

Solution

A previous work DyPart [3] has leveraged a Graph Partitioning Algorithm to dynamically partition the service state. It utilizes requests dependencies for partitioning, which are collected by monitoring objects accessing patterns of clients. It associates the partitioning mechanism with the existing checkpoint mechanism to continuously update partition knowledge to adapt to changing requests. Evaluation results show that DyPart can achieve good performance as well as balanced workload between replicas, while the mechanism can still be further optimized. The goal of this work is to improve DyPart by addressing the following issues:

• 1) Improve partition knowledge with exponential smoothing average technique
• 2) Decouple the graph partitioning computation from the deployment of new knowledge.

Requirement

A very good skill of Java is required.

[1]: https://www.ibr.cs.tu-bs.de/theses/bli/ml-bft.html

[2]: https://www.ibr.cs.tu-bs.de/theses/bli/partitioning.html

[3]: https://www.ibr.cs.tu-bs.de/theses/bli/self-partitioning.html