Raft is (Equivalent to) Paxos, VR

28 Feb 2017

I shouldn’t have to write this blog post, but one too many times have I received online comments, questions at conferences, and even paper reviews claiming that Raft is more efficient than Paxos. This is not the case; as Ongaro and Ousterhout note, Raft, VR, and Paxos are equivalent in efficiency.

While the original Paxos protocol was rather concise in its description [1], it can be easily modified into a full-featured state machine replication implementation. These modifications have been described in many places (e.g., “Paxos Made Live” [2]). The normal case operation of Paxos is visualized and described below:

1. The client sends its command, \(c\), to the current leader.
2. The leader proposes \(c\) in the latest unfilled slot in its log, sending the proposal to the other replicas.
3. The replicas put \(c\) into the same slot in their logs and respond to the leader.
4. The leader waits for a majority of replicas (including itself) to respond and then executes the command and responds to the client with the result.

Viewstamped Replication (VR) was developed at the same time as Paxos [3, 4]. While VR includes some practical details left out of the original Paxos papers, the core mechanism it uses is the same as Paxos.¹ Moreover, the normal case protocol is exactly the same as described above, and its performance is identical.

Raft was published much later, in an effort to be more understandable than the existing descriptions of Paxos and VR [5], and the Raft protocol is almost identical to VR.² Its normal case operation is also exactly the same as described above. In terms of message delays, number of messages sent and received, and amount of computation needed in the normal case, Raft has no performance benefits compared to VR or a full-featured Paxos implementation.

References

1. Lamport, L. The Part-time Parliament. ACM Transactions on Computer Systems. 16(2):133–169. May 1998.
2. Chandra, T.D., Griesemer, R. and Redstone, J. Paxos Made Live: An Engineering Perspective. In Proceedings of the Twenty-sixth Annual ACM Symposium on Principles of Distributed Computing. Portland, Oregon, USA. 2007. 398–407.
3. Oki, B.M. and Liskov, B.H. Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. In Proceedings of the 7th ACM Symposium on Principles of Distributed Computing (PODC ’88). Toronto, Canada. Aug. 1988.
4. Liskov, B. and Cowling, J. Viewstamped Replication Revisited. Technical Report MIT-CSAIL-TR-2012-021. MIT Computer Science and Artificial Intelligence Laboratory.
5. Ongaro, D. and Ousterhout, J. In Search of an Understandable Consensus Algorithm. In Proceedings of the 2014 USENIX Annual Technical Conference. Philadelphia, PA. 2014. 305–320.