Abstract
In recent years, Raft has overtaken Paxos as the consensus algorithm of choice. While many have pointed out similarities between the two protocols, no one has formally mapped out their relationships. In this paper, we show how Raft and Paxos are formally related despite their surface differences. Based on the formal mapping between the two protocols, we show how to automatically port a certain class of optimizations from Paxos to Raft with guaranteed correctness. As case studies, we port and evaluate two optimizations, Mencius and Paxos Quorum Lease to Raft.
Introduction
Consensus is a fundamental building block in distributed systems, allowing a cluster of servers to agree on a sequence of operations despite node failures. For decades, Paxos was the gold standard, leading to a vast ecosystem of optimized variants tailored for specific environments like low-latency wide-area networks. Recently, Raft has gained popularity due to its perceived simplicity and ease of implementation. However, the lack of a formal mathematical link between the two has meant that engineers must manually "reinvent the wheel" to adapt Paxos optimizations for Raft, risking bugs and inconsistencies. This paper addresses this gap by formally mapping Raft to Paxos.
Bridging the Gap: Raft* and Refinement Mapping
The authors utilize a formal method known as refinement mapping to prove that one protocol correctly implements another. They identified that standard Raft contains specific "surface differences"—such as its log entry erasure mechanism—that obstruct a direct mapping to Paxos. To overcome this, they introduced Raft*, a variant designed to be a formal refinement of MultiPaxos.
Raft* introduces three key changes:
- Adding a "ballot" field to log entries.
- Modifying follower responses during leader elections to include missing log entries.
- Ensuring the protocol maintains a formal refinement relationship with MultiPaxos.
This mapping enables an automated porting method for "non-mutating" optimizations. These are improvements that introduce new state or rules without altering the core logic of the original protocol. By using the TLA+ formal specification language, the authors demonstrate that these ported optimizations remain correct by construction.
Evaluation and Results
The methodology was validated by porting two major Paxos optimizations to Raft* and testing them in a global Amazon EC2 environment across five regions (Oregon, Ohio, Ireland, Canada, and Seoul) using a YCSB-like workload.
- Raft*-PQL (Paxos Quorum Lease): This optimization enables local reads at any replica holding a lease. In workloads with 90-99% reads, it delivered a 1.6x to 1.9x throughput improvement over standard Raft.
- Raft*-Mencius: This variant balances load by rotating the "default leader" for different log segments. In wide-area network tests, it achieved 70% higher throughput than standard Raft by effectively utilizing the bandwidth of all replicas.
The authors also provided a machine-checkable proof using the TLA+ Proof System, confirming that Raft* is a valid refinement of Paxos.
Conclusion and Future Work
While this work establishes a powerful bridge between Paxos and Raft, it is currently limited to "non-mutating" optimizations. Complex variants that fundamentally alter state storage are not yet supported by the automated porting method. Furthermore, while the TLA+ specifications are formally verified, the transition from specification to actual code (e.g., in Go or C++) still relies on manual implementation, leaving room for human error. Future work may involve extending this mapping to a broader class of optimizations and narrowing the gap between formal specification and production code.
Summary updated