Paxos vs Raft: Have we reached consensus on distributed consensus?

For those wondering what the differences between Raft and Paxos are: I can highly recommend the following paper https://arxiv.org/abs/2004.05074 It presents Paxos similarly to how Raft was originally presented.

There’s also the side-by-side Paxos/Raft comparison in Howard & Mortier’s “Consensus on consensus”[1] paper, which is not enough to understand either by itself, but a great help if have a longer explanation you’re going through. [1] https://dl.acm.org/doi/10.1145/3380787.3393681

https://arxiv.org/abs/2004.05074 This paper argues basically argues that raft has a different leadership election mechanism than paxos, but that if you tweak some terminology, and make a few relatively reasonable implementation choices for paxos they are otherwise pretty equivalent. It even gives a raft style single page description of paxos (using raft style terminology), and shows how little it differs from the equivalent single page summary of raft. The main implementation choices they use are: - combined roles into a single server role - enforce that log messages are decided in sequence (largely to avoid the having to specify the behavior of newly elected leader to propose operations for the gaps (possibly no-ops)) - numeric ballot number, rather than lexicographical pair (but this changes nothing except making the summary slightly easier to express)

Best in what metric? raft and paxos are basically the same, besides leader election, which raft's take makes it simply easier and possible even more efficient[0]. I say "possible" because that depends very much on the consensus state over time, which in most actual workloads can be pretty stable, so at least in some practice, e.g., with hypervisor-cluster like we do, they perform almost the same. The simpler approach of raft can help if you create a library for it from scratch, or for easier understanding when coming into that space, otherwise the differences does not matter too much (in practice), IMO. [0]: https://arxiv.org/abs/2004.05074

As it pertains to reaching consensus, everything in the "Basic Paxos" section of the article is the same for Raft as it is Paxos. Raft can be seen as instance of Paxos with different terminology and prescribed solutions for leader elections, solving dueling leader issues, and persisting past outcomes. Here's a nice paper on this that dives deeper into the matter and also shows how Paxos can be just as "understandable" as Raft with a few vocabulary changes: https://arxiv.org/pdf/2004.05074.pdf

That's interesting because the recent arxiv paper[1] by Heidi Howard indicated that Raft just has a clearer presentation rather than some technical superiority of being simpler (discussion here [2]). So perhaps people who believe in Paxos need to come up with similarly easy explanations for the community that learn from the presentation that Raft focused on? [1] https://arxiv.org/abs/2004.05074 [2] https://news.ycombinator.com/item?id=22994420

The papers and talks[1] by Heidi Howard and Richard Mortier, in particular “Paxos vs Raft: Have we reached consensus on distributed consensus?”[2,3] and “Flexible Paxos”[4,5], are what finally made things click for me. A real implementation also needs other stuff[6], though, such as dynamic membership and state machine replication, which I still don’t know how to do. [1] https://fpaxos.github.io/ [2] https://dl.acm.org/doi/abs/10.1145/3380787.3393681 or https://arxiv.org/abs/2004.05074 [3] https://www.youtube.com/watch?v=0K6kt39wyH0 [4] https://doi.org/10.4230/LIPIcs.OPODIS.2016.25 or https://arxiv.org/abs/1608.06696 [5] https://www.youtube.com/watch?v=r6NG_1HM0lA [6] https://github.com/heidihoward/distributed-consensus-reading...

> [Viewstamped replication] predates Paxos but looks more like Raft. Heidi Howard and Richard Mortier’s paper[1] on the topic of Paxos vs Raft has (multi-decree) Paxos and Raft written out in a way that makes it clear that they are very, very close. I’m very far from knowing what consequences (if any) this has for the implementation concerns you state, but the paper is lovely and I wanted to plug it. (There was also a presentation[2], but IMO the text works better when you want to refer back and forth.) [1] https://doi.org/10.1145/3380787.3393681 [2] https://www.youtube.com/watch?v=0K6kt39wyH0

You might be interested in this paper [1] which presents Paxos in the same way as Raft is presented in the Raft paper. In my view it really illustrates that most of the simplicity of Raft comes from its excellent presentation and not necessarily from its algorithmic simplicity. [1]https://arxiv.org/pdf/2004.05074

(Multi-)Paxos and Raft are incredibly similar. I would even argue that Raft is just a variant of Paxos in the same way that e.g. Fast Paxos and EPaxos are variants of Paxos. Most of the Raft algorithm is identical to the Paxos algorithm. The main difference between the two algorithms is how leadership election works. In my view the main reason why Raft is considered to be simpler is because it was presented in a really clear paper. Paxos becomes equally simple when using a similar representation as used in that paper. See this paper: https://arxiv.org/pdf/2004.05074