I bought one of the first 2022 Maverick Hybrids and took delivery in January 2022. At the time my build came in at MSRP of $25k (+ tax). I just built the closest equivalent on the Ford website (several standard features then are options now) and it came out to >$34k. Not double, but that feels like whole different price category for the same truck in 4 years.
I am in the minority who thinks Raft is overrated.
I tried teaching Raft one year instead of Paxos but ended up switching back. While it was much easier to understand how to implement Raft, I think my students gained deeper insight when focusing on single-decision Paxos. There is a lightbulb moment when they first understand that consensus is a property of the system that happens first (and they can point at the moment it happens) and then the nodes discover that it has been achieved later. Exploring various failure modes and coming to understand how Paxos is robust against them seems to work better in this setting as well.
I think this paper by Heidi Howard and Richard Mortier is a great way to move on to Multipaxos:
They present Multipaxos in a similar style to how Raft is laid out and show that Multipaxos as it is commonly implemented and Raft are almost the same protocol.
Raft was a great contribution to the engineering community to make implementing consensus more approachable, but in the end I don't think the protocol itself is actually more understandable. It was presented better for implementers, but the implementation focus obscures some of the deep insights that plain Paxos exposes.
I have had the opposite trajectory. Used to teach Paxos, but was so relieved to switch to Raft when the paper came out.
I discuss distributed data structures in the context of maps and sequences.
For maps, I discuss key-value stores (NUMA, Redis). I have them implement cache coherence (MESI protocol, TARDIS 2.0), then linearizable, fault-tolerant, wait-free shared memory registers (the Attiya/Bar-Noy/Dolev algorithm[1]).
For sequences, I cover shared logs and state machine replication, including database log shipping, Kafka, queues and Raft.
I like Raft because it cuts down the design space by making certain very intuitive and pragmatic choices, like using timeouts (which are almost beneath Lamport to discuss :), or idioms like "follow the leader", "if the leader is unreachable, stand for election", "elect the latest & most informed leader", (how I wish that was true in real life!), "always append" etc. There are simple mechanisms to preserve invariants.
The problem with Paxos is that there is such a large range of papers that there is no one paper that makes the leap in easy digestible chunks from Basic to MultiPaxos. When I got students to implement MultiPaxos, I never could get sufficient confidence that it was done right (esp. the "disorderly" filling in of log slots).
Paxos is like Monads; when you get it, you feel compelled to write a "Paxos explained" paper :)
I feel like you are doing your students a disservice. (multi-)Paxos, while complex to wrap your head around, enables far more modes of consensus. The possibilities and papers out there are amazing.
Raft essentially only allows a single mode. Moreover, you are starting to see people putting things on top of Raft instead of something like Paxos, in the enterprise, because they don't know any better nor have the foundation to understand what they are doing is "wrong."
> When I got students to implement MultiPaxos, I never could get sufficient confidence that it was done right
Testing this is fairly straightforward, they should be able to join an already existing cluster. If they got it wrong, it shouldn't take down the cluster, and they should be able to step through their own code. There aren't any timeouts, so they can take their time, going through each step of the process until a value is committed.
At that point, you simply explain each step as an individual algorithm, not the sum of its parts. You can even build each part individually because an existing cluster should recover from a misbehaving peer.
From there, it is a rather simple visualization process to see what is going on.
The hard part of paxos is building it from scratch.
Can you tell more about what other interesting modes multiPaxos allows? For an example of what I find uninteresting, it is proposers or acceptors not having a local disk (I know there are some uses for it, but there are relatively straightforward ways of solving that issue without requiring a whole new protocol). In all examples I have seen, multipaxos and raft are fairly alike, except for parts of their leadership election as Howard and Mortier also describe.
Raft's simplicity and the fact that there's exactly one way to do it is what I find most comforting in the most important component of a distributed system. I can look at an implementation of raft and immediately understand what's going on, and what is missing.
What makes multiPaxos a better learning tool isn't multiPaxos for the sake of multiPaxos, but rather Paxos itself. The write-once consensus primitive is a valuable tool (whether you are implementing Raft or multiPaxos) or thing to know. Especially when it comes to flexible / compartmentalized Paxos. Don't get me wrong, the same things can theoretically be done with Raft (if they haven't already), but that single-degree primitive makes it make that much more sense. This is missing from Raft.
It's like learning about a byte and never learning about endianness because everything is pretty much little-endian these days.
There are many algorithms to implement a single wait-free shared register. I like Basic Paxos, don't get me wrong. I also love the Part-time parliament paper's description of it. What I don't care much for is the generalization to multipaxos; too many things left to the imagination, which, in the hands of people like me without Lamport's reasoning skills, is headed for disaster. There is a reason why they say Paxos is too hard, but few people say that about Raft. A raft implementation is maintainable by ordinary mortals, because like I said, there is only one documented recommended way to do it.
Know that I join you in Raft being overrated. I’m working on a multipaxos implementation right now. There are some really neat capabilities/properties that paxos has that Raft can never achieve (see wpaxos, for example, that lets keys migrate to nodes near the client).
Is there any paper/handouts/video that explains Paxos in depth, especially its implementations and intuitions? Paxos Made Simple gave intuitive explanations, but I feel it still misses a lot of intricate details if I were to build Praxos for production use.
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.
Usage of java is fine ime. It's the principles that matter. The main benefit of this project is the search based tests which thoroughly test your implementation for edge cases. There's nothing else quite like it - few people can successfully complete this project to 100%.
You are telling me your students can safely implement single decree paxos.... I worked on a few paxos production implementations before the RAFT paper, single and multi decree. The idea that paxos, as it is to be implemented, is easy for students to understand... Well let me re-read the paper, but i assure you, raft was a big deal
I've read both the Paxos and Raft papers a few times, and hacked on some implementations, but never quite got one over the line to working...
Raft strikes me as a particular set of decisions made within a Paxos framework, such as having 1 entity for Proposers, Acceptor and Followers. It's frustrating that there isn't a clearly written defacto paper on Paxos - the story style confused the monkeys out of me.
> but never quite got one over the line to working...
I've never implemented something like this. But my first thought is "how do you implement the testing system?"
I feel like once you had a robust testing system that can verify things work correctly in all the different network partition and other scenarios, and allowing rapid iteration of setting up those scenarios, the implementation would be comparatively easy.
This is an interesting insight into the educational side, but now I am curious about the implementation side. Raft is easier to implement but that's just one factor. Looking at real world usages there seems to be a draw. I could easily count as many Paxos implementations as Raft. Is this just historical or are there good reasons for a new project to still implement Oaxos?
Let me make sure I understood this correctly: having a CS degree will turn you into a cartoon stereotype of a technical nerd, but getting any other kind of degree in the world will enable you to be a well rounded person and still learn CS skills. Somebody should really look into the damage being done by CS diplomas.
I feel like the culture surrounding CS biases this substantially. Most people I know who got CS degrees were raised in an environment where communication and interpersonal connections were downplayed and analytical thinking was rewarded (institutions and families constantly do this). College should be the place where these students are pushed mentally and emotionally in all directions, but instead we just give them 4 years of specialized knowledge and throw them out the door. The gen ed system encourages and rewards gameification (because if you take too challenging of a class, it can harm your GPA). It's a problem that starts at the bottom and has been exasturbated by a series of perverse incentives.
I've never really liked the look of the Tikz-generated automata. Something about them always looks a little off to me. I also dislike the use of 0 and 1 as the canonical alphabet. a and b look nicer, they stand out better in written instructions and solutions (when typeset using math mode), and (this sounds silly) sound nicer when talking about them with the class. Using 0 and 1 seems to imply some connection to binary that is not really there and probably confuses or misleads some students.
Of course, everyone will have a different opinion on such aesthetic matters. I taught an undergrad comp theory course for a decade or so and I wrote my own similar package[1] for generating diagrams using Metapost that built on the standard boxes package. Students were able to learn the system pretty quickly and the results were usually good, though it was pretty easy to pick out which students did/did not care about how things look.
I was expecting it to be hard to recognize, but I guess all those countless hours listening to Kid A on repeat back in the day have finally paid off. The moment is unmistakable.
It seems like modern languages adopt more and more ideas from functional programming as time goes by (garbage collection, closures and higher-order functions, parametric polymorphism, immutable values, algebraic types). Modern languages designed for general-purpose use are mostly hybrids, and the functional influence has been steadily growing over the decades.
In English, meaning is defined by common usage. I know the formal logic hipsters have mounted a persistent campaign to make an exception here, but the fact remains that "begging the question" means exactly what ordinary people think it means.
I've spoken and written English for over three decades, and this is the first time I've seen "begging the question" be used to mean this.
It's usually meant as "raises the question", but language lawyers insist it means what the wiki page said.
But this is neither of those two. And if you're the only one who uses a phrase a certain way, and it means other things to everyone else, then that's actually wrong, even in a descriptive language.
This is one of the cases for which, when writing for a broad audience, it's best to avoid the phrase in question, in either of its senses—precisely to avoid confusion or distraction like what's happening in this thread, with the common definition, and to avoid confusing the uninitiated with its more "correct", but jargony, sense—but also to accept the common meaning in others' language without complaint (ahem).
While I agree with you in principle, I think it’s more than permissible to make this distinction on this forum given the audience, IMO, even if the person who made the comment admittedly lacked tact in their approach.
I think that overstates the difference. I think a better analogy is architects vs. construction workers. Any decent architect will have a pretty strong understanding of the realities of construction, and an experienced construction worker who has moved around through different trades could probably design a decent house. But you'd only trust a trained architect on bigger, more complex projects, and you'd want disciplined, experienced construction workers doing the work on anything that is meant to last.
