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:
https://arxiv.org/abs/2004.05074
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 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 :)
[1]https://groups.csail.mit.edu/tds/papers/Attiya/PODC90.pdf
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.
[2] https://dl.acm.org/doi/abs/10.1145/3380787.3393681 or https://arxiv.org/abs/2004.05074
[3] https://www.youtube.com/watch?v=0K6kt39wyH0
[4] https://doi.org/10.4230/LIPIcs.OPODIS.2016.25 or https://arxiv.org/abs/1608.06696
[5] https://www.youtube.com/watch?v=r6NG_1HM0lA
[6] https://github.com/heidihoward/distributed-consensus-reading...
I suggest https://github.com/emichael/dslabs.
It will take 100-200 hours to fully implement with all tests passing.
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.
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.
https://maheshba.bitbucket.io/blog/2021/12/14/Modularity.htm...
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 file format that could be shared, diff'd, & tweaked.
I spent some time on a project recently to build out an SVG-based video generation tool that can use a sidecar file for defining animations. It's still a work in progress but hopefully I can get it to a place where making this style of visualizations isn't so time intensive.
Consider UTXO-based events. There can be an event E1 that consumes UTXO1 and UTXO2 and event E2 that consumes UTXO2 and UTXO3. Hashgaphs that contain one of these events are consistent but their union is not. This can be used to perform some byzantine things, I can think of at least two of them: doublespend and degradation of service.
This paper is a clear example of how to make a thing that has no obvious problems.
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 this with understandability as a first goal.
- 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 alternative, VSR (which was developed ~time of paxos) which is easy to understand and does not have the issues caused by election nondeterminism in raft.
Of course everyone uses raft so raft dominates.
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 implement VSR and would like to some day, but just comparing the papers alone I personally felt like Raft was better presented (i.e. easier to understand).
Also keep in mind that nobody ships consensus implementations exactly in line with the original paper. There are dozens or hundreds of papers on variations and extensions of Raft/Paxos and every actual implementation is going to implement some selection of these extensions/variations. You have to look at each implementation carefully to know how it diverges from the original paper.
Paxos as well, I remember full cloud GCP outage that had something to do with Paxos, and I can’t find the data on it but I thought there was a nasty bug in zookeeper paxos implementation.
That isn’t to say any of these are perfect or bug free, it’s made by humans and we’re going to make mistakes, but my experience implementing both was I had a working raft implementation and paxos baked my brain until I gave up.
I think everyone uses raft _because_ it was possible to implement for a working dev, so there are a number of implementations, and it’s easier to understand the phases the application is in.
I’ll check out VSR I appreciate the rec.
Heidi Howard has several amazing papers about how the differences between Raft and Multi-Paxos are very surface level and that Raft's key contribution is its presentation as well as being a more "complete" presentation since there are so many fragmented different presentations of Multi-Paxos.
As a bonus, one of my favorite papers I have read recently is Compartmentalized Paxos: https://vldb.org/pvldb/vol14/p2203-whittaker.pdf which is just a brilliant piece on how to scale Multi-Paxos
https://paper-notes.zhjwpku.com/assets/pdfs/paxos_for_system...
I'll check out the other two papers though! Also just looking around and I found this paper https://arxiv.org/pdf/1103.2408 [PDF] which looks useful as well.
I took a DS class and (poorly) implemented Paxos a few years ago. I’m curious about how others continue learning about DS.
The teachers provide you with some code templates, a bunch of tests, and a progressive way to implement it all.
This may be a great article, but I'll never know because it's frustrating to try and read.
Raft Consensus Animated (2014) - https://news.ycombinator.com/item?id=32484584 - Aug 2022 (67 comments)
Raft Visualization - https://news.ycombinator.com/item?id=25326645 - Dec 2020 (35 comments)
Raft: Understandable Distributed Consensus - https://news.ycombinator.com/item?id=8271957 - Sept 2014 (79 comments)
The other biggest help to me aside from the paper and the thesis was Ongaro's TLA+ spec: https://github.com/ongardie/raft.tla/blob/master/raft.tla. It's the only super concise "implementation" I found that is free of production-grade tricks, optimizations, and abstractions.
And for building an intuition, TigerBeetle's sim.tigerbeetle.com is great. What happens to consensus when there's high latency to disk or network? Or as processes crash more frequently? It demonstrates.
However it's not clear how that log is transmitted. Until this point only heartbeats via append entry were discussed, so it's not clear if the followers pull that information from the leader somehow via a different mechanism, or whether it's the leader's responsibility to detect followers that are left behind and replay everything. That would seem rather error prone and a lot of coordination effort. So how's it actually done?
[0]: https://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf
As for Hedera Hashgraph being the trust layer of the internet, we tend to build the internet through the IETF and standards setting. Unfortunately HH is an endeavour from a private company so isn't especially likely to be taken on in that context.
I'd also wonder what you mean by the trust layer of the internet, what are the use cases that you'd like to see solved with such a trust layer?
The DLT in question - Hedera - is built on the unique consensus algorithm, the "hashgraph". The hashgraph algorithm combines a gossip-about-gossip protocol with virtual voting.
In fact, services development is now in the hands of the largest open source foundation in the world. These implementations are entirely open source [0], and very recently the codebase has been donated in whole to the Linux Foundation.
Furthermore, Hedera is a Pioneer member of the newly founded Linux Foundation Decentralized Trust organization [1] - along with Chainlink, Deloitte, Hitachi, many other major organizations, some of whom are also on the Hedera governing council [2]. This foundation will be a big player in the future of decentralized web, and Hedera is the only L1 that I know of which is both primed for this future and actually scalable.
I understand the IETF and standards approach; and am not aware of a current draft or intention for such a draft. The idea of Hedera being the 'trust layer' of the internet is more about use cases like decentralized recovery, process validation, carbon offsets, extremely granular supply chain auditing, and any other application you might imagine that would benefit from having extremely fast (10k+ TPS), 100% guaranteed aBFT consensus on-chain. I'd love to hear what you might think up or where this could be particularly useful. Strong governance with 39 council members - including Google, IBM, Boeing, Tata, AP+, Hitachi and more... with decentralized network operation and stable fees (essential for enterprise application).
> Additional use cases include, but are not limited to, financial markets, matching engines (like those used in Uber or AirBnb), or supply chain negotiations (e.g., several competing factories bidding on parts from several competing parts suppliers).
So, admittedly the use cases maybe aren't evident or interesting to you and I right now at the TCP/IP layer, but I can certainly say there are a plethora of trust-based problems that could be solved with consensus only needing a few thousand ms. Think digital identity, healthcare, financial markets, IoT, supply chain, real-world asset tokenization... For any real-world, scaled application, a DLT must have very high throughput at high performance. It's the absolute highest performance and security possible in a leaderless consensus-based DLT as far as I know.
Literally carbon neutral or negative because of buybacks but even without Hedera buying carbon credits, it's the single most "green" i.e. power-efficient DLT on the market. Does HN still care about Bitcoin using too much power? They would like Hedera, to that extent. Predictable, very low fixed fees. Long list of the biggest tech players leading the open development process. What's not to love?
I urge you to help me invalidate these claims as it's pretty important I understand the tech here... But I'm very bullish on the token price as the technology is proven, robust, and overall extremely undervalued by retail - in my opinion. NFA.
> The Hashgraph consensus algorithm is an algorithm for asynchronous Byzantine fault tolerance intended for distributed shared ledgers. Its main distinguishing characteristic is it achieves consensus without exchanging any extra messages; each participant’s votes can be determined from public information, so votes need not be transmitted.
For more rigorous explanation, see [3] and the associated Coq proof of the algorithm [4].
[0]: https://github.com/hashgraph/hedera-services
[1]: https://www.lfdecentralizedtrust.org/
[2]: https://hedera.com/ecosystem/governing-council
[3]: https://hedera.com/papers
[4]: https://www.cs.cmu.edu/~crary/papers/2021/hashgraph.pdf
Doing that in a way that's easy to automate, set up, evaluate, and tear down various scenarios seems like the hardest part to me.
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.
When I read these posts, i see things like "timeout", "heartbeat", and I think: timeout according to whom? I read "once the leader has been elected", um, hangon, according to whom? Has node 1 finally agreed on the leader, just while node 3 has given up and started another election? I don't doubt that Raft is correct, but the writing about it seems simple by glossing over details.
Paxos, on the other hand, seems timeless. (And the writing about it doesn't trigger my "distributed system fallacies" reaction)
Whereas I think each line of pseudocode in Paxos is much more motivated.
In other words, if a philosopher had to design a crash-fault protocol from scratch, without having seen any before, I think 80% of the time it would look exactly like Paxos.