undefined | Better HN

0 points_vvhw5y ago0 comments

VR was of course developed independently by Barbara Liskov and Brian Oki and then revisited by Barbara Liskov with James Cowling.

However, it is common practice and perfectly acceptable to refer to VR as a variant of "Multi-Paxos" because that's actually EXACTLY what it is in theory, the protocol maps one-to-one, cf. Dan Ports (he explains it nicely here, see slide 46 if you want his bumper sticker version): https://courses.cs.washington.edu/courses/csep552/16wi/slide...

The more you understand VR and Multi-Paxos the more you will see that this is true.

In fact, and you may be surprised/disappointed at this, but Raft is also a variant of Multi-Paxos very similar to VR (cf. Heidi Howard https://groups.google.com/g/raft-dev/c/cBNLTZT2q8o), except with tighter restrictions on leader election that make it less efficient than VR, which is why we chose VR over Raft coincidentally.

By the way, that's a fantastic post by Marc Brooker and was part (along with references by Martin Thompson and Heidi Howard) of what made us pay more attention to VR in the first place.

0 comments

eternalban5y ago

Not surprised or disappointed, really. My take on RAFT is that it's basically Paxos for elections and a more relaxed regime in between.

But Brooker's post (in my OP) actually addresses VR vs Paxos distiction:

It's easy to believe that these two protocols are, in fact, the same. That doesn't appear to be the case. A new paper by van Renesse et. al., titled Vive La Difference: Paxos vs. Viewstamped Replication vs. Zab, looks at Paxos and VR through the lenses of refinement and abstraction, and finds they are not exactly equivalent due to design decisions in the way they refine a model the paper calls Multi-Consensus. One of the key differences is active (Paxos) vs. passive (VR) replication: "Passive vs. Active Replication: In active replication, at least f + 1 replicas each must execute operations. In passive replication, only the sequencer executes operations, but it has to propagate state updates to the backups."

Which reminds of ZAB (of Zookeepr fame), another protocol languishing in relative obscurity.

Anyway, thanks for your input. I have this thing for underdogs and this VR vs Paxos thing is a very minor cause, and I guess you triggered me there. /g

_vvhwOP5y ago

"My take on RAFT is that it's basically Paxos"

You're right that Raft is Paxos for the leader election phase, in the same way that VR is Paxos for the view change phase, or that Paxos is basically VR's view change but for deciding a value.

But a better way of saying this would be that Raft is Multi-Paxos (https://news.ycombinator.com/item?id=23123701), because Raft is much more than Paxos (in the same way that VR is more than Paxos because it not only decides on a value/leader but is also a protocol for replication). I think this is where our misunderstanding came in.

Yes, I've read the linked "Vive La Difference" paper. As the excerpt makes clear, one of the key differences is active replication (Paxos: with multiple concurrent processes that want to decide on a value) vs passive replication (Multi-Paxos variants: VR and Raft and ZAB all protocols with a single leader elected for a given term/view during which multiple rounds of replication take place).

The name Multi-Paxos just means that the first round of Paxos for leader election is reused for multiple rounds of replication, driven by a single leader instead of competing processes always using the minimum two-phase Paxos.

"I have this thing for underdogs"

Yes, me too, and that's why I tried to show that VR is no less than Multi-Paxos in my original comment, and that Raft is not newer than Multi-Paxos in my follow-up. It would be great for VR to receive the recognition it deserves.

eternalban5y ago

Well, in that case we mildly disagree. My take is this:

That functionally M-Paxos and Raft are equivalent does not make them the equivalent. RAFT uses a protocol that looks awfully like Paxos for election of a single leader - so it has nothing to do with multi-Paxos (as I understand it). But that L.E. phase + the interim regime gives you functional equivalence to Multi-Paxos.

1 more reply

j / k navigate · click thread line to collapse

0 points_vvhw5y ago0 comments

VR was of course developed independently by Barbara Liskov and Brian Oki and then revisited by Barbara Liskov with James Cowling.

The more you understand VR and Multi-Paxos the more you will see that this is true.

By the way, that's a fantastic post by Marc Brooker and was part (along with references by Martin Thompson and Heidi Howard) of what made us pay more attention to VR in the first place.

0 comments

eternalban5y ago

Not surprised or disappointed, really. My take on RAFT is that it's basically Paxos for elections and a more relaxed regime in between.

But Brooker's post (in my OP) actually addresses VR vs Paxos distiction:

Which reminds of ZAB (of Zookeepr fame), another protocol languishing in relative obscurity.

Anyway, thanks for your input. I have this thing for underdogs and this VR vs Paxos thing is a very minor cause, and I guess you triggered me there. /g

_vvhwOP5y ago

"My take on RAFT is that it's basically Paxos"

You're right that Raft is Paxos for the leader election phase, in the same way that VR is Paxos for the view change phase, or that Paxos is basically VR's view change but for deciding a value.

"I have this thing for underdogs"

eternalban5y ago

Well, in that case we mildly disagree. My take is this:

1 more reply

j / k navigate · click thread line to collapse