4 ms·

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

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 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 6y ago
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/ 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 6y ago
  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.
sriram_malhar 6y ago
No, simply not true at all. I've done both a few times. And yes, I have relevant experience.
- ideal0227 6y ago
  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 6y ago
    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 6y ago
      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 6y ago
        Are you speaking of Basic paxos?
      - sriram_malhar 6y ago
        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' :)
gitgudnubs 6y ago
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.
- deleted 6y ago
  [deleted]

wahern 6y ago

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/ 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 6y ago
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.

sriram_malhar 6y ago

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

ideal0227 6y ago
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 6y ago
  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 6y ago
    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 6y ago
      Are you speaking of Basic paxos?
    - sriram_malhar 6y ago
      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' :)

gitgudnubs 6y ago

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.

deleted 6y ago
[deleted]