Simpler is Better: Revisiting Mencius State Machine Replication

State Machine Replication (SMR) algorithms provide durability and fault tolerance to many crucial applications, systems, and services. Most such systems rely on Viewstamped Replication and Paxos algorithms first proposed in the late 1980s or their more modern incarnation-Raft. However, many other SMR algorithms have been proposed in the past several decades, yet they do not boast successful industrial adoption. There are several reasons for such lack of adoption, ranging from increased implementation complexity to performance issues and unpredictability in various corner-case situations. In this paper, we examine these issues through the lens of Mencius, a multileader SMR algorithm popular in academia. We discuss its weaknesses that may prevent real-world use and propose Mencius Revisited to address them. In particular, our reimagining of the Mencius algorithm streamlines the handling of several corner cases, making it much simpler to implement while boasting multi-fold throughput improvement. Furthermore, Mencius Revisited has more predictable performance, especially under node failures-an ability crucial for production capacity planning. We achieve these improvements through algorithm simplification using opportunistic, low-latency batching and a revised failure-handling mechanism.