[ideal0227]

I think all these kinds of papers are very confusing. Comparing RSM (replicated state machine) to Paxos is just like comparing a car to an engine. It makes very little or no sense.

In the original Paxos paper (https://lamport.azurewebsites.net/pubs/paxos-simple.pdf), the part 3 (RSM) is not extensively explained. There are countless ways to use Paxos to implement RSM. Multipaxos/Raft/Epaxos try to fill in that gap.

By any means, Paxos itself is 10x simpler than Raft or whatever. Every time I heard a "distributed system" engineer said Paxos is complicated, I know he/she does not have much experience in the field or at least has never implemented the core consensus part...

[wahern]

Indeed, in the paper they're comparing MultiPaxos to Raft.

EDIT: For others, here's a very comprehensive (as of ~2018) review of Paxos-related distributed consensus algorithms with an exposition for each one: https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ That's 17 in all, excluding the original Paxos paper. IMO, it should be linked anywhere Paxos is discussed. The link has been posted twice before by others on HN, but unfortunately hasn't seen any discussion, perhaps because it speaks for itself.

[ideal0227]

There are three main stages about RSM.

1. log replication (m) 2. log consistency (n) 3. log execution (k)

Then you will have m * n * k ways of achieving your goal based on different requirements on the three stages.

[gitgudnubs]

That, or "Paxos" is a fantastic name, and "replicated state machine" is a mouthful.

I've implemented the consensus part of Paxos in 10 minutes. But it's a toy. It's totally useless without the other stuff.

[sriram_malhar]

No, simply not true at all. I've done both a few times. And yes, I have relevant experience.

[ideal0227]

What is not true? 10x simpler, no?

There are two possibilities:

1. You misunderstood Paxos, probably confused that with RSM. For example, Paxos is just the leader election part of Raft. Superficially, it seems different from Paxos, but it what it is under the surface.

2. You implemented RSM incorrectly, probably missed some important features or optimizations. For example, log compaction, membership reconfiguration, pipeline, back pressure on execution, etc.

It is VERY important to differentiate Paxos and RSM. There are tons of optimizations you can do with RSM. But on consensus, there is ONLY Paxos today. Or you do it wrong or you invite something truly new.

[sriram_malhar]

There are two possibilities.

1. You underestimate my understanding.

2. You underestimate my experience.

I am sure you know this: both are comparable as a shared log abstraction. Once you have that, the state machine part is trivial. For the replicated shared log abstraction, you need to do the same kind of things in both the Paxos and Raft worlds. The latter is simpler to implement because the paper is written close to an engineer's understanding. i have written several versions of both, in production.

[ideal0227]

No, Paxos is not a shard log abstraction. Paxos is about agreeing on one value rather than a set of values in sequence. So my possibility 1 is true.

[sriram_malhar]

I can't edit my earlier response, but on second thought, we are both right. Is that consensus? :)

I think the difference in our stances arises from the two ways in which the term 'Paxos' is used. In the part-time-parliament paper, the single-decree paxos is the fundamental building block. I'm assuming this is what you think of as Paxos, and you are right in your assertion. It is defined as the fundamental act of consensus.

However, I have always viewed the single-decree protocol as a pedagogical device; a single write-once distributed register is useless in practice, so the multi-decree protocol is where it becomes useful, and to me is the point of the paper. I say this for a few reasons: a) state machine replication has been Lamport's focus since his early papers, including the 'time clocks and ordering' paper. (b) in engineering-oriented papers such as 'paxos made live', 'chubby' and so on, the term is used as a proxy for a replicated log. The reason for the many variants of Paxos is due to the underlying impulse that basic paxos is not sufficient in and of itself. You need some variant of shared log or equivalently, atomic broadcast.

So, we are both right in our ways. We can have consensus, as long as we sacrifice consistency of the definition of 'Paxos' :)

[sriram_malhar]

Are you speaking of Basic paxos?