4 ms·

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.

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.
- DannyBee 8y ago
  "This paper generalizes variants of Paxos - certainly not the class of all consensus algorithms." This is not true. It generalizes quite many more than that. It happens to use PaxOS as examples.
  - Vervious 8y ago
    It generalizes specifically a class of consensus algorithms that write to sequences of registers in a monotonic way, such that if a "previous" register decides v, future "registers" and associated quorums will decide v. This is not a property of all consensus algorithms. Consensus algorithms don't need to behave this way. Paxos and derivatives behave this way, but I'm not sure Raft, etc. slide in as neatly (that would require a substantial analysis). In particular, this generalization does not capture any nondeterministic algorithm, any algorithm tolerating Byzantine faults (or various other consensus problems), any non-quorum based algorithm, Nakamoto style (which is a byzantine consensus algorithm), Ben-Orr, etc. etc. So, my question for you: what other algorithms do you think this paper generalizes, that are useful outside of the narrow scope of optimizing Paxos?
disposablename 8y ago
This is a very techincal topic, of course the vote to comment ratio is going to be very high.
anigbrowl 8y ago
Not really, in fact it's something I've come to expect here. There's a loss in social status for appearing too enthusiastic about a new thing (that might not be so great) and if the new thing replaces a difficult-to-use old thing then the people who invested effort in understanding the old thing don't want to participate in making it obsolete. Don't forget that people often just want to use an algorithm and are not necessarily that interested in the underlying mathematical structure, only in whether it works reliably and does a better job than the existing solution.

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.

DannyBee 8y ago
"This paper generalizes variants of Paxos - certainly not the class of all consensus algorithms." This is not true. It generalizes quite many more than that. It happens to use PaxOS as examples.
- Vervious 8y ago
  It generalizes specifically a class of consensus algorithms that write to sequences of registers in a monotonic way, such that if a "previous" register decides v, future "registers" and associated quorums will decide v. This is not a property of all consensus algorithms. Consensus algorithms don't need to behave this way. Paxos and derivatives behave this way, but I'm not sure Raft, etc. slide in as neatly (that would require a substantial analysis). In particular, this generalization does not capture any nondeterministic algorithm, any algorithm tolerating Byzantine faults (or various other consensus problems), any non-quorum based algorithm, Nakamoto style (which is a byzantine consensus algorithm), Ben-Orr, etc. etc. So, my question for you: what other algorithms do you think this paper generalizes, that are useful outside of the narrow scope of optimizing Paxos?

disposablename 8y ago

This is a very techincal topic, of course the vote to comment ratio is going to be very high.

anigbrowl 8y ago

Not really, in fact it's something I've come to expect here. There's a loss in social status for appearing too enthusiastic about a new thing (that might not be so great) and if the new thing replaces a difficult-to-use old thing then the people who invested effort in understanding the old thing don't want to participate in making it obsolete. Don't forget that people often just want to use an algorithm and are not necessarily that interested in the underlying mathematical structure, only in whether it works reliably and does a better job than the existing solution.