8 ms·

A generalised solution to distributed consensus

454 points by based2 8y ago

sagichmal 8y ago
Great paper with an incredibly important result. It will take years to shake out in industry and implementations, but should dramatically improve situations where strong consistency is important.
- pathseeker 8y ago
  Can you explain how? In many cases when a "generalized result" comes out there was already a generalized result that covered all but obscure corner cases.
  - DannyBee 8y ago
    This is the first paper i've seen to generalize consensus while only using immutable state. That is, you can describe PaxOS, Raft, etc using the generalization given here. The result is fairly understandable. (Of course, as mentioned, Raft is trivial in her framework because there is only one thing deciding values, Raft is spending it's time in the leader election part to find that one thing)
    - DennisP 8y ago
      Also, from the abstract, "the surprising result of this analysis is a substantial weakening to the quorum requirements of these widely studied algorithms."
  - thethirdwheel 8y ago
    The big thing here is that its analytical framework allows the authors to clearly analyze Paxos and some important variants and identify performance improvements (e.g. steps in the algorithm you can elide) that don't undermine the guarantees provided.
thaumaturgy 8y ago
As an alternative to Paxos-related consensus algorithms, some projects may want to take a look at the Raft consensus protocol: https://www.brianstorti.com/raft/ https://www.brianstorti.com/raft/ Whereas Paxos tries to maintain a fully distributed consensus state, Raft instead proposes a protocol for automatically electing a leader node from a group of follower nodes, and coordinating the replication of the write log through that leader node. I haven't had the pleasure of experimenting with either one though and would love to hear from people who have.
- killjoywashere 8y ago
  Isn't raft the default for Bitcoin?
  - deathanatos 8y ago
    No. Raft and Bitcoin's algorithms for agreeing on what the blockchain is are completely different. AIUI, Bitcoin's "consensus" is just whoever has the longest valid blockchain is the winner. The algorithm tunes the difficulty s.t. it takes ~10 minutes to find a block, so the chance of two blockchains continuing to have the same length for any long amount of time is unlikely. That is, one chain will find the next block before the other, and in the meantime, be able to distribute that fact to the other nodes and thus "win". From https://en.bitcoin.it/wiki/Block_chain https://en.bitcoin.it/wiki/Block_chain: > Honest generators only build onto a block (by referencing it in blocks they create) if it is the latest block in the longest valid chain. "Length" is calculated as total combined difficulty of that chain, not number of blocks, though this distinction is only important in the context of a few potential attacks.
  - narrator 8y ago
    No. Bitcoin uses its own protocol. Raft could not be used for a secure cryptocurrency bevause Raft does not handle byzantine faults[1]. It assumes nodes are not run by malicious actors and messages sent are unaltered in transit. [1] https://en.m.wikipedia.org/wiki/Byzantine_fault https://en.m.wikipedia.org/wiki/Byzantine_fault
0xb100db1ade 8y ago
Would someone ELI5?
- bch 8y ago
  I can’t, but I can say: 1) Heidi Howard’s papers are very fun to read. She’s done lots of work I’ve enjoyed esp wrt Raft 2) She touches on two things in this story’s paper that I first read in another paper of hers that are a joy to realize for two reasons a) She made a practical improvement in the already simple Raft protocol b) quorum != (obvious) majority - in (eg) Raft she identifies that quorum actually spans two states, which are * leader election and * “regular” mode with a leader and requisite # followers Read/watch on and be amazed[0][1] [0] http://hh360.user.srcf.net/blog/2016/08/majority-agreement-is-not-necessary/ http://hh360.user.srcf.net/blog/2016/08/majority-agreement-i... [1] https://youtu.be/gYkueS5sKqo https://youtu.be/gYkueS5sKqo
  - deleted 8y ago
    [deleted]
- cbhl 8y ago
  Here's my attempt: Making multiple computers all store the same thing is hard because they have to send messages between each other, and sometimes messages get lost. Other people have tried to write down how they solved this problem, but their explanations were hard for adults to understand. This person has tried a new way to solve this problem, and a new way to explain their solution that uses ideas that many big kids who go to big kid school to study computers can understand.
- deleted 8y ago
  [deleted]
thecoinrepublic 8y ago
The client maintains a decision table with one entry for each quorum of each register set.
anonymousDan 8y ago
My understanding is the cost of all these weaker quorums is reduced fault tolerance. Is that correct?
- DblPlusUngood 8y ago
  Yes. In theory, maybe it's useful to have more flexibility to trade-off durability for performance (smaller quorum size hopefully reduces deciding latency [unless your small quorum contains the straggler!]) for specific kinds of data in the same replica group. In practice though, it seems easier just to run separate instances of Paxos.
jrootabega 8y ago
Forgive the tangent, but could quantum entanglement one day provide consensus with trivial (if expensive) complexity? E.g., nodes maintain a supply of preentangled particles, observing them at predetermined timestamps, and using that known shared randomness to make decisions? Edit: ok after that sat there for a while I realized that generating shared pseudorandom bits would be just as effective.
- karl_gluck 8y ago
  If you abstract quantum-entangled particles to a communication channel with zero latency, you still have the consensus problem—you just run into the edge cases less frequently. So it would help, but consensus is still a fundamental challenge with parallel processes.
  - krastanov 8y ago
    Given the handwaviness I might just be misunderstanding what you mean by "zero latency", so I just wanted to clarify: entangled particles do NOT enable FTL communication. Sorry if I am saying something you know, but others might misread your comment.
karl_gluck 8y ago
Is anyone else surprised at the relatively mild reaction to this result here on Hacker News? Only a couple dozen comments, and many are addressing other topics. Can we take a second to appreciate that this result will rapidly become the first thing taught in every single distributed systems class? And if this holds as a generalization of trustful distributed consensus as a field, then she has defined its Turing Machine equivalent. And it is even remarkably easy to understand! That is wild!! Props to the authors. Personally, this is going on the top of my “to memorize” list.
- brighton36 8y ago
  I'm very skeptical that many people will want this. Data misrepresentation is rarely (never?) due to a fault in the persistence medium. Its usually a political reason, or human error that perverts consensus.
  - woah 8y ago
    What? Consensus algorithms in this class are used everywhere in web programming, from MySQL to AWS. Ironic that your comment may very well have touched several consensus algorithms on its way to my eyes. The fact that you remain blissfully unaware of them is a testament to their power.
  - atombender 8y ago
    This has nothing to do with "data misrepresentation". It's about distributed consensus. It's not even really about storage, but about multiple parties agreeing on a single truth.
    - eru 8y ago
      Even just something as simple as which of several replicas is supposed to be the master. Not some great external truth about the world.
- Vervious 8y ago
  I disagree. This paper generalizes variants of Paxos - certainly not the class of all consensus algorithms. Moreoever, it generalizes Paxos variants, with different requirements - weaker quorums are always a tradeoff with liveness in the presense of faults. tldr; I don't see world-changing novelty here, theoretically. There are dozens of other consensus algorithms in the world, some randomized, some not quorum based, etc. This is interesting if you're in Paxos land, trying to tune your Paxos for different fault-tolerance requirements. It's no way comparable to a computational model.
ccleve 8y ago
I have a lot of questions about this paper. Parts of it aren't clear to me. Is anyone aware of a forum where consensus algorithms are discussed? A mailing list, subreddit, or website? I found a Raft mailing list a while ago, but I'm looking for a place for a more general discussion, where real experts hang out.
- jvanderbot 8y ago
  I believe you have to go through literature to get this kind of back-and-forth. At least, that's how I manage, even if that feels slow and opinionated.
- macintux 8y ago
  For questions specifically about this paper, you might have luck with Adrian Colyer's take on it: https://blog.acolyer.org/2019/03/08/a-generalised-solution-to-distributed-consensus/ https://blog.acolyer.org/2019/03/08/a-generalised-solution-t... Or Howard's blog post: https://hh360.user.srcf.net/blog/2019/02/towards-an-intuitive-high-performance-consensus-algorithm/ https://hh360.user.srcf.net/blog/2019/02/towards-an-intuitiv... Twitter used to be a useful place for general distsys discussions, but I haven't been around for a few years now so I'm not certain how much still takes place. This tweet, for example, I would have expected to see more people chime in on. https://twitter.com/adriancolyer/status/1103935905948028928 https://twitter.com/adriancolyer/status/1103935905948028928 There's a distributed systems theory Google Group, but it appears to have completely died off: https://groups.google.com/forum/#!forum/distsys-discuss https://groups.google.com/forum/#!forum/distsys-discuss To inquire what avenues for theoretical discussion are currently active, I would suggest reaching out on Twitter to Chris Meiklejohn (cmeik), Michael Bernstein (mrb_bk) or Kyle Kingsbury (aphyr).
grogers 8y ago
Really cool result and a very readable paper. I'm struggling to figure out how this would be applicable to iterated consensus (i.e. logs). It seems like the extension examples are focused on reducing the message round trips for specific cases that don't matter when applied to muti-paxos or raft.

454 points by based2 8y ago

Great paper with an incredibly important result. It will take years to shake out in industry and implementations, but should dramatically improve situations where strong consistency is important.

pathseeker 8y ago
Can you explain how? In many cases when a "generalized result" comes out there was already a generalized result that covered all but obscure corner cases.
- DannyBee 8y ago
  This is the first paper i've seen to generalize consensus while only using immutable state. That is, you can describe PaxOS, Raft, etc using the generalization given here. The result is fairly understandable. (Of course, as mentioned, Raft is trivial in her framework because there is only one thing deciding values, Raft is spending it's time in the leader election part to find that one thing)
  - DennisP 8y ago
    Also, from the abstract, "the surprising result of this analysis is a substantial weakening to the quorum requirements of these widely studied algorithms."
- thethirdwheel 8y ago
  The big thing here is that its analytical framework allows the authors to clearly analyze Paxos and some important variants and identify performance improvements (e.g. steps in the algorithm you can elide) that don't undermine the guarantees provided.

thaumaturgy 8y ago

As an alternative to Paxos-related consensus algorithms, some projects may want to take a look at the Raft consensus protocol: https://www.brianstorti.com/raft/ https://www.brianstorti.com/raft/ Whereas Paxos tries to maintain a fully distributed consensus state, Raft instead proposes a protocol for automatically electing a leader node from a group of follower nodes, and coordinating the replication of the write log through that leader node. I haven't had the pleasure of experimenting with either one though and would love to hear from people who have.

killjoywashere 8y ago
Isn't raft the default for Bitcoin?
- deathanatos 8y ago
  No. Raft and Bitcoin's algorithms for agreeing on what the blockchain is are completely different. AIUI, Bitcoin's "consensus" is just whoever has the longest valid blockchain is the winner. The algorithm tunes the difficulty s.t. it takes ~10 minutes to find a block, so the chance of two blockchains continuing to have the same length for any long amount of time is unlikely. That is, one chain will find the next block before the other, and in the meantime, be able to distribute that fact to the other nodes and thus "win". From https://en.bitcoin.it/wiki/Block_chain https://en.bitcoin.it/wiki/Block_chain: > Honest generators only build onto a block (by referencing it in blocks they create) if it is the latest block in the longest valid chain. "Length" is calculated as total combined difficulty of that chain, not number of blocks, though this distinction is only important in the context of a few potential attacks.
- narrator 8y ago
  No. Bitcoin uses its own protocol. Raft could not be used for a secure cryptocurrency bevause Raft does not handle byzantine faults[1]. It assumes nodes are not run by malicious actors and messages sent are unaltered in transit. [1] https://en.m.wikipedia.org/wiki/Byzantine_fault https://en.m.wikipedia.org/wiki/Byzantine_fault

0xb100db1ade 8y ago

Would someone ELI5?

bch 8y ago
I can’t, but I can say: 1) Heidi Howard’s papers are very fun to read. She’s done lots of work I’ve enjoyed esp wrt Raft 2) She touches on two things in this story’s paper that I first read in another paper of hers that are a joy to realize for two reasons a) She made a practical improvement in the already simple Raft protocol b) quorum != (obvious) majority - in (eg) Raft she identifies that quorum actually spans two states, which are * leader election and * “regular” mode with a leader and requisite # followers Read/watch on and be amazed[0][1] [0] http://hh360.user.srcf.net/blog/2016/08/majority-agreement-is-not-necessary/ http://hh360.user.srcf.net/blog/2016/08/majority-agreement-i... [1] https://youtu.be/gYkueS5sKqo https://youtu.be/gYkueS5sKqo
- deleted 8y ago
  [deleted]
cbhl 8y ago
Here's my attempt: Making multiple computers all store the same thing is hard because they have to send messages between each other, and sometimes messages get lost. Other people have tried to write down how they solved this problem, but their explanations were hard for adults to understand. This person has tried a new way to solve this problem, and a new way to explain their solution that uses ideas that many big kids who go to big kid school to study computers can understand.
deleted 8y ago
[deleted]

thecoinrepublic 8y ago

The client maintains a decision table with one entry for each quorum of each register set.

anonymousDan 8y ago

My understanding is the cost of all these weaker quorums is reduced fault tolerance. Is that correct?

DblPlusUngood 8y ago
Yes. In theory, maybe it's useful to have more flexibility to trade-off durability for performance (smaller quorum size hopefully reduces deciding latency [unless your small quorum contains the straggler!]) for specific kinds of data in the same replica group. In practice though, it seems easier just to run separate instances of Paxos.

jrootabega 8y ago

Forgive the tangent, but could quantum entanglement one day provide consensus with trivial (if expensive) complexity? E.g., nodes maintain a supply of preentangled particles, observing them at predetermined timestamps, and using that known shared randomness to make decisions? Edit: ok after that sat there for a while I realized that generating shared pseudorandom bits would be just as effective.

karl_gluck 8y ago
If you abstract quantum-entangled particles to a communication channel with zero latency, you still have the consensus problem—you just run into the edge cases less frequently. So it would help, but consensus is still a fundamental challenge with parallel processes.
- krastanov 8y ago
  Given the handwaviness I might just be misunderstanding what you mean by "zero latency", so I just wanted to clarify: entangled particles do NOT enable FTL communication. Sorry if I am saying something you know, but others might misread your comment.

karl_gluck 8y ago

Is anyone else surprised at the relatively mild reaction to this result here on Hacker News? Only a couple dozen comments, and many are addressing other topics. Can we take a second to appreciate that this result will rapidly become the first thing taught in every single distributed systems class? And if this holds as a generalization of trustful distributed consensus as a field, then she has defined its Turing Machine equivalent. And it is even remarkably easy to understand! That is wild!! Props to the authors. Personally, this is going on the top of my “to memorize” list.

brighton36 8y ago
I'm very skeptical that many people will want this. Data misrepresentation is rarely (never?) due to a fault in the persistence medium. Its usually a political reason, or human error that perverts consensus.
- woah 8y ago
  What? Consensus algorithms in this class are used everywhere in web programming, from MySQL to AWS. Ironic that your comment may very well have touched several consensus algorithms on its way to my eyes. The fact that you remain blissfully unaware of them is a testament to their power.
- atombender 8y ago
  This has nothing to do with "data misrepresentation". It's about distributed consensus. It's not even really about storage, but about multiple parties agreeing on a single truth.
  - eru 8y ago
    Even just something as simple as which of several replicas is supposed to be the master. Not some great external truth about the world.
Vervious 8y ago
I disagree. This paper generalizes variants of Paxos - certainly not the class of all consensus algorithms. Moreoever, it generalizes Paxos variants, with different requirements - weaker quorums are always a tradeoff with liveness in the presense of faults. tldr; I don't see world-changing novelty here, theoretically. There are dozens of other consensus algorithms in the world, some randomized, some not quorum based, etc. This is interesting if you're in Paxos land, trying to tune your Paxos for different fault-tolerance requirements. It's no way comparable to a computational model.

ccleve 8y ago

I have a lot of questions about this paper. Parts of it aren't clear to me. Is anyone aware of a forum where consensus algorithms are discussed? A mailing list, subreddit, or website? I found a Raft mailing list a while ago, but I'm looking for a place for a more general discussion, where real experts hang out.

jvanderbot 8y ago
I believe you have to go through literature to get this kind of back-and-forth. At least, that's how I manage, even if that feels slow and opinionated.
macintux 8y ago
For questions specifically about this paper, you might have luck with Adrian Colyer's take on it: https://blog.acolyer.org/2019/03/08/a-generalised-solution-to-distributed-consensus/ https://blog.acolyer.org/2019/03/08/a-generalised-solution-t... Or Howard's blog post: https://hh360.user.srcf.net/blog/2019/02/towards-an-intuitive-high-performance-consensus-algorithm/ https://hh360.user.srcf.net/blog/2019/02/towards-an-intuitiv... Twitter used to be a useful place for general distsys discussions, but I haven't been around for a few years now so I'm not certain how much still takes place. This tweet, for example, I would have expected to see more people chime in on. https://twitter.com/adriancolyer/status/1103935905948028928 https://twitter.com/adriancolyer/status/1103935905948028928 There's a distributed systems theory Google Group, but it appears to have completely died off: https://groups.google.com/forum/#!forum/distsys-discuss https://groups.google.com/forum/#!forum/distsys-discuss To inquire what avenues for theoretical discussion are currently active, I would suggest reaching out on Twitter to Chris Meiklejohn (cmeik), Michael Bernstein (mrb_bk) or Kyle Kingsbury (aphyr).

grogers 8y ago

Really cool result and a very readable paper. I'm struggling to figure out how this would be applicable to iterated consensus (i.e. logs). It seems like the extension examples are focused on reducing the message round trips for specific cases that don't matter when applied to muti-paxos or raft.