Dynamic state partitioning in Byzantine Fault Tolerance system

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, so that the requests crossing multiple partitions can be minimized.

Solution

A previous work [2] has explored the possibility of using Machine Learning techniques to smartly partition the service state objects, according to the data access dependency of client requests. It has proposed a combination of linear regression and recursive bi-partitioning approaches to learn the underlying hardware behavior and the knowledge about application requests, and eventually to partition the system state into clusters of highly dependent objects that are represented in undirected weighted graphs. The goal of this work is to explore the possibility of using static and deterministic approaches such as Graph Partitioning to solve the state partitioning problem. It covers two aspects: 1) Determine a Graph Partitioning Algorithm and integrate the algorithm into the BFT system 2) Create a collecting mechanism to monitor state object accessing patterns and create requests dependencies. 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