On the parallels between Paxos and Raft, and how to port optimizations

Zhaoguo Wang, Changgeng Zhao, Shuai Mu, Haibo Chen, Jinyang Li

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:

  1. Adding a "ballot" field to log entries.
  2. Modifying follower responses during leader elections to include missing log entries.
  3. Ensuring the protocol maintains a formal refinement relationship with MultiPaxos.
Comparison of variables and functions between Raft* and 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

Abstract

In recent years, Raft has overtaken Paxos as the consensus algorithm of choice. [53] 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.
BibTeX
@inproceedings{wang2019parallels,
  author = {Zhaoguo Wang and Changgeng Zhao and Shuai Mu and Haibo Chen and Jinyang Li},
  title = {{On the parallels between Paxos and Raft, and how to port optimizations}},
  booktitle = {PODC},
  year = {2019},
  url = {https://openreview.net/forum?id=ReTQCBsmVX2},
}

Loading related content...

Figure