9 ms·

A Review of Consensus Protocols

121 points by tcgv 6y ago

tilt_error 6y ago
Raft? The two most prominent consensus algorithms that I usually come across in 'the wild', are Paxos and Raft. Am I missing something -- or is the article missing something?
- johnnyAghands 6y ago
  Yeah I was kinda wondering that too
  - EGreg 6y ago
    There are others too. Proof of Work consensus, etc. Or this: https://ripple.com/files/ripple_consensus_whitepaper.pdf https://ripple.com/files/ripple_consensus_whitepaper.pdf
- rubiquity 6y ago
  As it pertains to reaching consensus, everything in the "Basic Paxos" section of the article is the same for Raft as it is Paxos. Raft can be seen as instance of Paxos with different terminology and prescribed solutions for leader elections, solving dueling leader issues, and persisting past outcomes. Here's a nice paper on this that dives deeper into the matter and also shows how Paxos can be just as "understandable" as Raft with a few vocabulary changes: https://arxiv.org/pdf/2004.05074.pdf https://arxiv.org/pdf/2004.05074.pdf
  - infogulch 6y ago
    So could you say that the Raft spec is an opinionated implementation of Paxos?
    - rubiquity 6y ago
      Some people don’t like it when you say that, but yes. I don’t mean to downplay Raft’s significance because its better perceived understandability helped bring a good algorithm to much more popularity, maybe even nudged future researchers to think about the “user experience” of their discoveries (not to say that Leslie Lamport wasn’t, he did try very hard with metaphors in The Part-time Parliament).
    - jasonwatkinspdx 6y ago
      Yes. Raft is in the basic category called Multi-Paxos, but with specific choices intended to make the algorithm more comprehensible and less error prone to implement. Looks like there's substance to that view as well, looking at both the literature and practice. A more recent development is Heidi Howard's work, which provides a framework for thinking about the whole category of Paxos algorithms that many of us find a lot more approachable.
      - poooogles 6y ago
        >A more recent development is Heidi Howard's work Glad someone has mentioned her here. This talk helped me greatly https://www.youtube.com/watch?v=KTHOwgpMIiU https://www.youtube.com/watch?v=KTHOwgpMIiU.
        cmckn 6y ago
        Seconded, her videos and papers are fantastic. Previous discussion here: https://news.ycombinator.com/item?id=22994420 https://news.ycombinator.com/item?id=22994420
iambvk 6y ago
On Paxos: The following already seems wrong. AFAIK the proposal number space must be divided across proposers. If all proposers use minNumber+1 replicas will diverge on the chosen value. protected override void Propose(Instance r) { proposalNumber = minNumber + 1; Broadcast(r, MessageType.Propose, proposalNumber); }
- rubiquity 6y ago
  Using incrementing ballot numbers is fine. If you have multiple Proposers all sending the same ballot number in Phase 1 (Prepare & Promise) the Acceptors will reject any ballot number less than the highest ballot number they have received. In order to move to Phase 2, the Proposer needs to receive the thumbs up from a majority of the Acceptors, which means only one Proposer can ever win. If you were to divide the ballot number space, in the event that the owner of the highest values in that space won, every other proposer would immediately need to increase their ballot numbers for all future rounds and so on and so forth or else they would always get rejected.
  - iambvk 6y ago
    The problem is on the recovery path. Recovery path needs to identify if there was a chosen value only from F+1 nodes (out of 2*F+1 nodes total). When two proposers with same proposal-number, but different values have partially executed the protocol before the crash, then you would end up with all F+1 nodes with same proposal number indicating successful consensus previously, but with divergent values.
    - rubiquity 6y ago
      I'm not sure what you mean by "recovery path" or "partially executed the protocol before the crash." Paxos has specific terminology for each of the phases. Can you be more precise?
      - iambvk 6y ago
        Sure, imagine all nodes are crashed (due to poweroff) in the middle of two proposers A and B doing Phase2 with the same proposal-number, but different values. Remember, they can go to Phase2 cause their proposal-number is the largest ever seen when they are the first. Proposer-A received Phase2 votes from nodes n_1,...n_f and Proposer-B received one vote from n_f+1 when power is off and other nodes n_f+2, n_f+3...n_2f+1 don't know anything about the Phase2. Now, consider the case when power is back and only the first F+1 nodes came back online. System is expected to continue with F+1 live nodes. Proposer-C now does Phase-1 with the same proposal-number. He is expected to pick the already voted value associated with the max proposal-number from the Phase-1 responses, but there are two different values and he can't determine what to pick.
monocasa 6y ago
I'd throw in the "Virtual synchrony" set of protocols in the vein of Horus, Isis, VSync, and Derecho that are similar to Paxos, but older and take a slightly different view. I prefer them a bit from an ergonomic perspective. These formed the basis of the New York stock exchange, the Aegis Combat System, and the French air traffic control system, among other extremely highly available systems. It appears the fantastic Virtual Synchrony wiki page has been unfortunately deleted, and simply replaced with a redirect to a couple sentences on the reliable multicast page (despite not relying on reliable multicast any more than Paxos does) so here's an archive.org capture of the wiki page. https://web.archive.org/web/20181231000827/https://en.wikipedia.org/wiki/Virtual_synchrony https://web.archive.org/web/20181231000827/https://en.wikipe...
- jasonwatkinspdx 6y ago
  VS and Paxos operate at different layers. For VS to provide its guarantees it needs to use true consensus for group membership. You could see it as a more feature expanded version of leases used to optimize away one of the phases of paxos in the common case.
  - monocasa 6y ago
    That's for sure one way to look at it, but I prefer to view VS as looking at the concept of consensus as a spectrum and providing tools in many interesting points on that spectrum. Yes, the question of "who gets to participate in the consensus protocol itself" is itself solved through total consensus in VS (and a total consensus protocol older than Paxos). But the way that is then used to bootstrap looser and more performant views of consensus as a first class concept I believe makes it still interesting to bring up in a discussion of consensus in general.
    - jasonwatkinspdx 6y ago
      Not really. Atomic broadcast is equivalent to the consensus problem. VS itself can be turned into Paxos and vice versa via shuffling of details. All of the performance optimizations the VS sales literature pushes so hard are just as possible atop Paxos, and in fact are done now in practice. It's just a divide of concepts/terminology for the most part.
lomereiter 6y ago
I wish this article had a bit more systematic approach. I've been recently looking into consensus protocols, and there are at least two dimensions to consider: permissioned (participants are known in advance) vs permissionless (anyone can join), and partially synchronous (some guarantees about message delivery time) vs asynchronous (only the delivery is guaranteed, the time can be at any point in the future). There are also some recent developments loosely based on Ben-Or protocol (HoneyBadgerBFT, HashGraph) that look a lot more promising than blockchain-based consensus.
baldo 6y ago
Practical Byzantine Fault Tolerance (PBFT) is a consensus algorithm for permissioned environments that allows a number of faulty nodes f<n/3. It does not rely on synchrony for correctness and it is safe against Byzantine faults (when f<n/3). It is used in BFS (PBFT for NFS) and in hyperledger fabric, to name the first two that came in my mind. http://zoo.cs.yale.edu/classes/cs426/2012/bib/castro02practical.pdf http://zoo.cs.yale.edu/classes/cs426/2012/bib/castro02practi...
miohtama 6y ago
Some new consensus protocols: Avalanche from AVA labs and Nightshade as used in NEAR protocol.
ccktlmazeltov 6y ago
If you want a more theoretical review of byzantine consensus protocols, you need to read through the gossip-based protocol literature, in particular byzantine broadcast protocols[1], where consensus is just one powerful primitive among others. [1]: https://dcl.epfl.ch/site/_media/education/sdc_byzconsensus.pdf https://dcl.epfl.ch/site/_media/education/sdc_byzconsensus.p...
- josh2600 6y ago
  Yeah the broadcast layer is the part where a lot of the byzantine protocols breakdown IMHO. Broadcast storms are very bad. There's also the whole problem of tombstone-ing a proposed block if it doesn't achieve consensus fast enough (which is basically impossible to do as a function of time so you end up doing it as a function of a monotonic counter which has other problems). Anyways, I love all the byzantine stuff but very little of it is actually practical or fast.
  - ccktlmazeltov 6y ago
    depends on your usecases or what throughput you need in your system
machawinka 6y ago
Another is The Stellar Consensus Protocol by David Mazières .
hardwaresofton 6y ago
Shameless plug for a similar post I've made, listing all the variations of Paxos (including Raft), etc: https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ No implementations/code but if you've ever wondered what the rest of the research landscape looks like for the paxos family tree of coordination (there's also some mention of stuff like SWIM[0], aka batched & randomized gossip at the end as well) [0]: https://research.cs.cornell.edu/projects/Quicksilver/public_pdfs/SWIM.pdf https://research.cs.cornell.edu/projects/Quicksilver/public_...
- rstuart4133 6y ago
  That's a pretty impressive summary. Thanks for writing it.
  - hardwaresofton 6y ago
    No problem -- I didn't do any of the research so it was very easy. I got a brief intriguing introduction to consensus a long time ago in university but never really appreciated how interesting the space is until much later. I really ought to send an email thanking the professor that taught the class.
waste_monk 6y ago
Can't we just agree to use one consensus protocol?
- nullsense 6y ago
  I concur.

121 points by tcgv 6y ago

Raft? The two most prominent consensus algorithms that I usually come across in 'the wild', are Paxos and Raft. Am I missing something -- or is the article missing something?

johnnyAghands 6y ago
Yeah I was kinda wondering that too
- EGreg 6y ago
  There are others too. Proof of Work consensus, etc. Or this: https://ripple.com/files/ripple_consensus_whitepaper.pdf https://ripple.com/files/ripple_consensus_whitepaper.pdf
rubiquity 6y ago
As it pertains to reaching consensus, everything in the "Basic Paxos" section of the article is the same for Raft as it is Paxos. Raft can be seen as instance of Paxos with different terminology and prescribed solutions for leader elections, solving dueling leader issues, and persisting past outcomes. Here's a nice paper on this that dives deeper into the matter and also shows how Paxos can be just as "understandable" as Raft with a few vocabulary changes: https://arxiv.org/pdf/2004.05074.pdf https://arxiv.org/pdf/2004.05074.pdf
- infogulch 6y ago
  So could you say that the Raft spec is an opinionated implementation of Paxos?
  - rubiquity 6y ago
    Some people don’t like it when you say that, but yes. I don’t mean to downplay Raft’s significance because its better perceived understandability helped bring a good algorithm to much more popularity, maybe even nudged future researchers to think about the “user experience” of their discoveries (not to say that Leslie Lamport wasn’t, he did try very hard with metaphors in The Part-time Parliament).
  - jasonwatkinspdx 6y ago
    Yes. Raft is in the basic category called Multi-Paxos, but with specific choices intended to make the algorithm more comprehensible and less error prone to implement. Looks like there's substance to that view as well, looking at both the literature and practice. A more recent development is Heidi Howard's work, which provides a framework for thinking about the whole category of Paxos algorithms that many of us find a lot more approachable.
    - poooogles 6y ago
      >A more recent development is Heidi Howard's work Glad someone has mentioned her here. This talk helped me greatly https://www.youtube.com/watch?v=KTHOwgpMIiU https://www.youtube.com/watch?v=KTHOwgpMIiU.
      - cmckn 6y ago
        Seconded, her videos and papers are fantastic. Previous discussion here: https://news.ycombinator.com/item?id=22994420 https://news.ycombinator.com/item?id=22994420

iambvk 6y ago

On Paxos: The following already seems wrong. AFAIK the proposal number space must be divided across proposers. If all proposers use minNumber+1 replicas will diverge on the chosen value. protected override void Propose(Instance r) { proposalNumber = minNumber + 1; Broadcast(r, MessageType.Propose, proposalNumber); }

rubiquity 6y ago
Using incrementing ballot numbers is fine. If you have multiple Proposers all sending the same ballot number in Phase 1 (Prepare & Promise) the Acceptors will reject any ballot number less than the highest ballot number they have received. In order to move to Phase 2, the Proposer needs to receive the thumbs up from a majority of the Acceptors, which means only one Proposer can ever win. If you were to divide the ballot number space, in the event that the owner of the highest values in that space won, every other proposer would immediately need to increase their ballot numbers for all future rounds and so on and so forth or else they would always get rejected.
- iambvk 6y ago
  The problem is on the recovery path. Recovery path needs to identify if there was a chosen value only from F+1 nodes (out of 2*F+1 nodes total). When two proposers with same proposal-number, but different values have partially executed the protocol before the crash, then you would end up with all F+1 nodes with same proposal number indicating successful consensus previously, but with divergent values.
  - rubiquity 6y ago
    I'm not sure what you mean by "recovery path" or "partially executed the protocol before the crash." Paxos has specific terminology for each of the phases. Can you be more precise?
    - iambvk 6y ago
      Sure, imagine all nodes are crashed (due to poweroff) in the middle of two proposers A and B doing Phase2 with the same proposal-number, but different values. Remember, they can go to Phase2 cause their proposal-number is the largest ever seen when they are the first. Proposer-A received Phase2 votes from nodes n_1,...n_f and Proposer-B received one vote from n_f+1 when power is off and other nodes n_f+2, n_f+3...n_2f+1 don't know anything about the Phase2. Now, consider the case when power is back and only the first F+1 nodes came back online. System is expected to continue with F+1 live nodes. Proposer-C now does Phase-1 with the same proposal-number. He is expected to pick the already voted value associated with the max proposal-number from the Phase-1 responses, but there are two different values and he can't determine what to pick.

monocasa 6y ago

I'd throw in the "Virtual synchrony" set of protocols in the vein of Horus, Isis, VSync, and Derecho that are similar to Paxos, but older and take a slightly different view. I prefer them a bit from an ergonomic perspective. These formed the basis of the New York stock exchange, the Aegis Combat System, and the French air traffic control system, among other extremely highly available systems. It appears the fantastic Virtual Synchrony wiki page has been unfortunately deleted, and simply replaced with a redirect to a couple sentences on the reliable multicast page (despite not relying on reliable multicast any more than Paxos does) so here's an archive.org capture of the wiki page. https://web.archive.org/web/20181231000827/https://en.wikipedia.org/wiki/Virtual_synchrony https://web.archive.org/web/20181231000827/https://en.wikipe...

jasonwatkinspdx 6y ago
VS and Paxos operate at different layers. For VS to provide its guarantees it needs to use true consensus for group membership. You could see it as a more feature expanded version of leases used to optimize away one of the phases of paxos in the common case.
- monocasa 6y ago
  That's for sure one way to look at it, but I prefer to view VS as looking at the concept of consensus as a spectrum and providing tools in many interesting points on that spectrum. Yes, the question of "who gets to participate in the consensus protocol itself" is itself solved through total consensus in VS (and a total consensus protocol older than Paxos). But the way that is then used to bootstrap looser and more performant views of consensus as a first class concept I believe makes it still interesting to bring up in a discussion of consensus in general.
  - jasonwatkinspdx 6y ago
    Not really. Atomic broadcast is equivalent to the consensus problem. VS itself can be turned into Paxos and vice versa via shuffling of details. All of the performance optimizations the VS sales literature pushes so hard are just as possible atop Paxos, and in fact are done now in practice. It's just a divide of concepts/terminology for the most part.

lomereiter 6y ago

I wish this article had a bit more systematic approach. I've been recently looking into consensus protocols, and there are at least two dimensions to consider: permissioned (participants are known in advance) vs permissionless (anyone can join), and partially synchronous (some guarantees about message delivery time) vs asynchronous (only the delivery is guaranteed, the time can be at any point in the future). There are also some recent developments loosely based on Ben-Or protocol (HoneyBadgerBFT, HashGraph) that look a lot more promising than blockchain-based consensus.

baldo 6y ago

Practical Byzantine Fault Tolerance (PBFT) is a consensus algorithm for permissioned environments that allows a number of faulty nodes f<n/3. It does not rely on synchrony for correctness and it is safe against Byzantine faults (when f<n/3). It is used in BFS (PBFT for NFS) and in hyperledger fabric, to name the first two that came in my mind. http://zoo.cs.yale.edu/classes/cs426/2012/bib/castro02practical.pdf http://zoo.cs.yale.edu/classes/cs426/2012/bib/castro02practi...

miohtama 6y ago

Some new consensus protocols: Avalanche from AVA labs and Nightshade as used in NEAR protocol.

ccktlmazeltov 6y ago

If you want a more theoretical review of byzantine consensus protocols, you need to read through the gossip-based protocol literature, in particular byzantine broadcast protocols[1], where consensus is just one powerful primitive among others. [1]: https://dcl.epfl.ch/site/_media/education/sdc_byzconsensus.pdf https://dcl.epfl.ch/site/_media/education/sdc_byzconsensus.p...

josh2600 6y ago
Yeah the broadcast layer is the part where a lot of the byzantine protocols breakdown IMHO. Broadcast storms are very bad. There's also the whole problem of tombstone-ing a proposed block if it doesn't achieve consensus fast enough (which is basically impossible to do as a function of time so you end up doing it as a function of a monotonic counter which has other problems). Anyways, I love all the byzantine stuff but very little of it is actually practical or fast.
- ccktlmazeltov 6y ago
  depends on your usecases or what throughput you need in your system

machawinka 6y ago

Another is The Stellar Consensus Protocol by David Mazières .

hardwaresofton 6y ago

Shameless plug for a similar post I've made, listing all the variations of Paxos (including Raft), etc: https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ No implementations/code but if you've ever wondered what the rest of the research landscape looks like for the paxos family tree of coordination (there's also some mention of stuff like SWIM[0], aka batched & randomized gossip at the end as well) [0]: https://research.cs.cornell.edu/projects/Quicksilver/public_pdfs/SWIM.pdf https://research.cs.cornell.edu/projects/Quicksilver/public_...

rstuart4133 6y ago
That's a pretty impressive summary. Thanks for writing it.
- hardwaresofton 6y ago
  No problem -- I didn't do any of the research so it was very easy. I got a brief intriguing introduction to consensus a long time ago in university but never really appreciated how interesting the space is until much later. I really ought to send an email thanking the professor that taught the class.

waste_monk 6y ago

Can't we just agree to use one consensus protocol?

nullsense 6y ago
I concur.