From Byzantine Consensus to BFT State Machine Replication: A Latency-Optimal Transformation

abstract

Projects in this category follow a common pattern:

  1. Students study the corresponding paper and try to understand the consensus algorithm's functioning;
  2. They create a proof of concept implementation it using a technology of choice;
  3. They test the consensus algorithm's robustness agains crash and byzantine faults.

There is an implicit step hidden into the procedure above: consensus algorithms are usually aimed at implementing some sort of SMR system (e.g. a replicated DB). Even if the goal of a project in this category is to study & implement a consensus algorithm, students may need to actually use it in order to test it. To do so they will have to create a simple SMR system, like, e.g. a replicated Key-Value store supporting at least two operations: put and get.

Paper abstract:

We present a new algorithm for state machine replication that is built around a leader-driven consensus primitive. This algorithm requires only two additional communication steps between replicas and clients if the consensus leader is correct and the system is synchronous, being thus the first latency-optimal transformation from Byzantine consensus to BFT state machine replication. We also discuss how to make simple modifications to leader-driven consensus algorithms in order to make them compatible with our transformation.

keywords
BFT
references