21–30 of 91 posts
Author here. I'm happy to answer any questions although this project was from 10+ years ago so I could be a little rusty. Over the years I've been trying to find better ways to do this kind of visualization but for other CS topics. Moving to video is the most realistic option but using something like After Effects takes A LOT of time and energy for long-form visualizations. It also doesn't produce a readable output f…
Earlier quoted context omitted.
Right, but Paxos is double hard in comparison. I’ve read both papers multiple times, tried to implement and failed, and I still don’t think I understand Paxos.
I'm on the other side. I think Leslie Lamport asserted that Paxos is minimal, and that "all other consensus algorithms are just Paxos with more steps". I'm inclined to believe him. I've implemented Paxos but I can't get through "Raft for dummies" style blog posts. Regarding Raft [1]: > The consensus problem is divided into three sub-problems: Leader election, Replication and Safety. What is leader election? It's a di…
I am curious on your thoughts here.
[0]: https://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf
Earlier quoted context omitted.
Weirdly it's also kinda worse is better: raft is non-deterministic and has an unboundedly long election cycle time. IIRC: - it assumes no hysteresis in network latencies and if there is a hysteresis it's possible that elections can be deterministically infinite. - this fact and the use of raft in production has caused real, large scale network outages. Paxos is of course a beast and hard to understand. There is an al…
> - this fact and the use of raft in production has caused real, large scale network outages. While this has surely happened, I am not so confident about what the reasons were for this. If you've got links on details I'd love to read. > which is easy to understand I've implemented core bits of Raft twice now and have looked at VSR a couple of times and VSR wasn't easier for me to understand. I'm sure I could implemen…
(Howard, Abram et al)
Me: note this can also occur if there isn't a complete outage, if the latency back to the shit leader is different from the latency out of the shit leader.
> nobody ships consensus implementations exactly in line with the original paper. There are dozens or hundreds of papers on variations
As the paper above explains once you add extensions you might have broken the correctness proofs in raft. More to the original point, you're now in a state where it's no longer "simple"... I would go so far as to say if you have to consider the extensions, which are distributed over several papers and sometimes not even papers at all, you're in "deceptively simple" land.
As a pedagogical tool, raft is valuable because it can be a launching ground for conversations like these... But maybe we shouldn't use it in prod when there are better, straightforward options? I get the feeling that being hard sold as simple nerdsniped devs into writing it and someone r/very smart put it into prod and with social proof more people did and now here we are
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 mome…
Can't proof-of-work be used as a leader election algorithm? If the proof is hard enough to generate then one node should be able to generate one and broadcast it before the other nodes can, then that node becomes the leader.
This is one of my favorite pieces of software engineering because it took something difficult and tried to design something easy to understand as a main criteria for success. The PHD Thesis has a lot more info about this if anyone is curious, it is approachable and easy to read: https://web.stanford.edu/~ouster/cgi-bin/papers/OngaroPhD.pd... I think this was core to Raft’s success, and I strive to create systems like…
Weirdly it's also kinda worse is better: raft is non-deterministic and has an unboundedly long election cycle time. IIRC: - it assumes no hysteresis in network latencies and if there is a hysteresis it's possible that elections can be deterministically infinite. - this fact and the use of raft in production has caused real, large scale network outages. Paxos is of course a beast and hard to understand. There is an al…
Earlier quoted context omitted.
> - this fact and the use of raft in production has caused real, large scale network outages. While this has surely happened, I am not so confident about what the reasons were for this. If you've got links on details I'd love to read. > which is easy to understand I've implemented core bits of Raft twice now and have looked at VSR a couple of times and VSR wasn't easier for me to understand. I'm sure I could implemen…
> A known limitation of the base Raft protocol is that partial/asymmetric network partitions can cause a loss of liveness [27, 32]. For instance, if a leader can no longer make progress because it cannot receive messages from the other nodes, it continues to send AE heartbeats to followers, preventing them from timing out and from electing a new leader who can make progress. (Howard, Abram et al) Me: note this can al…
Real-world raft implementations make the leader step down if it hasn’t heard from a quorum for a while. Not part of vanilla raft though.
Can't proof-of-work be used as a leader election algorithm? If the proof is hard enough to generate then one node should be able to generate one and broadcast it before the other nodes can, then that node becomes the leader.