Viewstamped Replication for Rust

This is a work-in-progress Rust implementation of the Viewstamped Replication consensus algorithm.

Getting Started

Run the example:

cargo run --example example

To see some debug traces, use RUST_LOG environment variable:

RUST_LOG=trace cargo run --example example

ToDo

• [x] Normal operation
• [x] State transfer
• [x] Deterministic simulator
• [ ] View changes
• [ ] Failed replica recovery
• [ ] Reconfiguration

Testing

You can run the tests with:

cargo test -- --nocapture

The run will print out a seed value such as:

Seed: 10693013600028533629

If the simulation triggers a problem, you can reproduce the exact same run by passing a seed to the simulator:

SEED=10693013600028533629 cargo test -- --nocapture

You can also increase logging level to see more output of the run with:

RUST_LOG=debug cargo test

You can get a test coverage report with:

cargo tarpaulin -o html

References

The implementation of vsr-rs is based on the paper Viewstamped Replication Revisited by Liskov and Cowling. However, the algorithm in the paper has the following known bugs:

• The recovery algorithm described in Section 4.3 can result in the system being in an inconsistent state as reported by Michael et al in Appendix B1 of Recovering Shared Objects Without Stable Storage
• The state transfer algorithm described in Section 5.2 can cause data loss as discovered by Jack Vanlightly in https://twitter.com/vanlightly/status/1596190819421413377 and https://twitter.com/vanlightly/status/1596425599026970624.

The vsr-rs library does not yet implement recovery or view changes so the bugs are not addressed.

For more information on VSR, please also check out the following presentations and blog posts:

• Paper: VR Revisited - An analysis with TLA+
• Reading Group: Viewstamped Replication Revisited
• Viewstamped Replication explained