News for hackers. Stuff that matters.
Re:A generalised solution to distributed consensus by karl_gluck on Saturday March 09, 2019 @08:52AM (#19346086)
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.

Re:A generalised solution to distributed consensus by disposablename on Saturday March 09, 2019 @03:10PM (#19348191)
This is a very techincal topic, of course the vote to comment ratio is going to be very high.
Re:A generalised solution to distributed consensus by Vervious on Saturday March 09, 2019 @02:15PM (#19347872)
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.

Re:A generalised solution to distributed consensus by DannyBee on Saturday March 09, 2019 @03:00PM (#19348138)
"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.

Re:A generalised solution to distributed consensus by Vervious on Saturday March 09, 2019 @04:26PM (#19348584)
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?

Re:A generalised solution to distributed consensus by anigbrowl on Saturday March 09, 2019 @03:12PM (#19348198)
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.

Re:A generalised solution to distributed consensus by brighton36 on Saturday March 09, 2019 @09:49AM (#19346353)
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.
Re:A generalised solution to distributed consensus by woah on Saturday March 09, 2019 @11:25AM (#19346837)
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.
Re:A generalised solution to distributed consensus by atombender on Saturday March 09, 2019 @03:10PM (#19348189)
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.
Re:A generalised solution to distributed consensus by eru on Monday March 11, 2019 @10:43AM (#19359322)
Even just something as simple as which of several replicas is supposed to be the master. Not some great external truth about the world.
Re:A generalised solution to distributed consensus by sagichmal on Friday March 08, 2019 @07:40PM (#19343665)
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.
Re:A generalised solution to distributed consensus by pathseeker on Saturday March 09, 2019 @12:47AM (#19344706)
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.
Re:A generalised solution to distributed consensus by DannyBee on Saturday March 09, 2019 @01:51AM (#19344875)
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)

Re:A generalised solution to distributed consensus by DennisP on Saturday March 09, 2019 @09:13AM (#19346169)
Also, from the abstract, "the surprising result of this analysis is a substantial weakening to the quorum requirements of these widely studied algorithms."
Re:A generalised solution to distributed consensus by thethirdwheel on Sunday March 10, 2019 @03:39PM (#19353912)
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.
Re:A generalised solution to distributed consensus by 0xb100db1ade on Saturday March 09, 2019 @12:28AM (#19344657)
Would someone ELI5?
Re:A generalised solution to distributed consensus by cbhl on Saturday March 09, 2019 @02:36AM (#19344975)
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.

Re:A generalised solution to distributed consensus by bch on Saturday March 09, 2019 @01:05AM (#19344753)
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-i...

[1] https://youtu.be/gYkueS5sKqo

Re:A generalised solution to distributed consensus by grogers on Saturday March 09, 2019 @11:31PM (#19350265)
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.
Re:A generalised solution to distributed consensus by ccleve on Saturday March 09, 2019 @05:07PM (#19348811)
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.

Re:A generalised solution to distributed consensus by macintux on Sunday March 10, 2019 @03:51PM (#19353998)
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-t...

Or Howard's blog post: 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

There's a distributed systems theory Google Group, but it appears to have completely died off:

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).

Re:A generalised solution to distributed consensus by jvanderbot on Saturday March 09, 2019 @08:20PM (#19349628)
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.
Re:A generalised solution to distributed consensus by anonymousDan on Saturday March 09, 2019 @05:04AM (#19345431)
My understanding is the cost of all these weaker quorums is reduced fault tolerance. Is that correct?
Re:A generalised solution to distributed consensus by DblPlusUngood on Saturday March 09, 2019 @02:03PM (#19347811)
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.

Re:A generalised solution to distributed consensus by jrootabega on Saturday March 09, 2019 @08:43AM (#19346053)
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.

Re:A generalised solution to distributed consensus by karl_gluck on Saturday March 09, 2019 @08:55AM (#19346098)
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.
Re:A generalised solution to distributed consensus by krastanov on Saturday March 09, 2019 @09:10AM (#19346160)
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.
Re:A generalised solution to distributed consensus by thaumaturgy on Friday March 08, 2019 @07:46PM (#19343698)
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/

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.

Re:A generalised solution to distributed consensus by Vervious on Friday March 08, 2019 @08:42PM (#19343945)
Raft is arguably more difficult to understand at a deep level. After extensive study, I've noticed that Raft hides all of its complexity under its leader election setup. There's nuance after nuance. With Paxos, the complexity is explicit and at the forefront, which is actually better, when trying to reason about a distributed system and its invariants.
Re:A generalised solution to distributed consensus by ccleve on Friday March 08, 2019 @09:04PM (#19344005)
That was my experience as well. The rules around leader election, terms, voting, timeouts and the like are very subtle.
Re:A generalised solution to distributed consensus by pests on Friday March 08, 2019 @10:45PM (#19344314)
Raft is basically a fixed leader elected by a single round of Paxos.
Re:A generalised solution to distributed consensus by zzzcpan on Friday March 08, 2019 @08:32PM (#19343909)
It's not that simple. Here's an overview on paxos/raft consensus algorithms: https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ and even that is incomplete and not necessarily describes trade-offs well. Submitted generalized solution is a better point to start experimenting from.
Re:A generalised solution to distributed consensus by DannyBee on Saturday March 09, 2019 @01:48AM (#19344863)
This paper is deliberately a generalization of all of them, actually. Raft can also be explained in terms of the rules/system she provides.

She happens to use PaxOS as examples to show they are non-optimal, in part because Raft is already deliberately non-optimal.

The other reason is that Raft is completely trivial in her framework.

It is equivalent to only having one thing decide the registers (and all the hard work is in deciding which thing).

Re:A generalised solution to distributed consensus by fanf2 on Sunday March 10, 2019 @07:44AM (#19351560)
By the way, Paxos is the name of a Greek island; it doesn’t have funky capitalisation. The name is from Lamport’s paper “the part-time parliament” which describes the algorithm in the setting of Ancient Greece.
Re:A generalised solution to distributed consensus by thecupisblue on Saturday March 09, 2019 @04:39AM (#19345340)
Exactly this, not sure why people think it's a different thing - just wrap nodes into a higher level of abstraction. I believe Raft might be a better approach to scalable consensus tho but there needs to be more layers to a network so the network can be more self-balancing and localised.

If we we call "heartbeat" the frequency at which a node is synced to the network (achieves consensus) - lower heartbeat nodes need to stay close only to nodes with a "heartbeat" faster than theirs and elect leaders in that group. The leaders in that group are also in a group of other leaders of that layer and listening to their leader, which belongs to a group above (like zooming out from a group and the group becoming a node in a larger graph).

In the end, there is only one state after all and the graph is the ultimate leader with the highest heartbeat. We wouldn't need many layers to cover all nodes, assuming laws of nature and all. Then just go a layer up/down if the network is getting too large, use a karmic system to position new/reactivated nodes. Seems scalable enough.

Sorry OP, it might be too early and I'm just thinking out loud in a comment box.

Re:A generalised solution to distributed consensus by yxhuvud on Saturday March 09, 2019 @05:41AM (#19345555)
Can the framework model the leader election though?
Re:A generalised solution to distributed consensus by DannyBee on Saturday March 09, 2019 @01:43PM (#19347710)
They do, effectively. They show what is necessary for quorums, and show that a large number of algorithms meet these requirements.

Hence, the single leader election is not actually necessary (and this is one of their points - the existing algorithms require much stronger quorum guarantees than are actually necessary for correctness)

Re:A generalised solution to distributed consensus by ccleve on Friday March 08, 2019 @09:02PM (#19344001)
It took me months to do a reliable Raft implementation. The author of the Raft paper, Diego Ongaro, wrote in a comment on a Raft mailing list that it could take weeks.

The Raft paper is really easy to read and understand, but the actual code is very tricky.

Re:A generalised solution to distributed consensus by justinjlynn on Friday March 08, 2019 @09:29PM (#19344091)
What did you find most difficult about the implementation?
Re:A generalised solution to distributed consensus by ccleve on Saturday March 09, 2019 @04:58PM (#19348761)
To make it work with any kind of performance, all message passing needs to be asynchronous, and you need an event loop to process messages one at a time. Things are much simpler if your code is effectively single-threaded when processing an inbound message. That took me a while to figure out. Futures and promises are very helpful.

It took a while to get the building blocks together: the log file, which can be traversed, read, and rolled back/truncated (use a kv store for this, trust me), and the transport mechanism to deal with sending complex objects and handling errors and timeouts.

Tracking terms, states (leader, follower, candidate), rejecting out of date terms, voting, elections -- it's all very complex. You'll have to build some really, really good multi-threaded tests that simulate out-of-order and dropped messages, then really pound away at the system. And good logging to find that odd corner case that keeps coming up and throwing mysterious messages.

I haven't even tried membership changes yet.

Re:A generalised solution to distributed consensus by bch on Saturday March 09, 2019 @09:16PM (#19349785)
> use a kv store for this, trust me

Order is important here - is this inherent in your key?

Re:A generalised solution to distributed consensus by ccleve on Saturday March 09, 2019 @10:48PM (#19350063)
Yes.

I did two implementations, one with plain text files and one with a kv store. For plain text files, I had to maintain file offsets of the records so I could traverse backward and truncate records that had to be replaced, and then break the files into segments so I could retire segments that are no longer needed. It had all kinds of little bugs.

Then I reimplemented using a kv store, and it took a tiny fraction of the time. And surprisingly had better performance.

Just create a good interface at the start, use the kv store underneath, and then later if you don't want the dependency swap it out for the more complicated code.

Re:A generalised solution to distributed consensus by bch on Saturday March 09, 2019 @11:45PM (#19350333)
Cool - I’d like to talk about your design and how you arrived at it if you’re interested.
Re:A generalised solution to distributed consensus by ccleve on Monday March 11, 2019 @11:56AM (#19359903)
Happy to. I just added my email address to my profile.
Re:A generalised solution to distributed consensus by Matheus28 on Friday March 08, 2019 @11:13PM (#19344413)
Not OP, but it is very easy to make mistakes while implementing it and end up with something that is not actually reliable. You have to have the paper opened and write code line by line looking at it. I implemented it a while ago so that's the most I remember, but it did a bit of fuzzing to nail down every bug.
Re:A generalised solution to distributed consensus by karl-police on Friday March 15, 2019 @03:42AM (#19397478)
Or I could ask you here one of the questions.

Do you host diep.io on cloudflare, heroku, linode etc.? or do you have own servers?

Because I'm interested about developing something.

Re:A generalised solution to distributed consensus by isbvhodnvemrwvn on Saturday March 09, 2019 @11:53AM (#19347022)
Also not OP, I think I went through the paper 10 times over during the implementation. There's a lot of cross-references all over the place.
Re:A generalised solution to distributed consensus by karl-police on Wednesday March 13, 2019 @07:45AM (#19377721)
Could I ask you something, or maybe on Steam?
Re:A generalised solution to distributed consensus by killjoywashere on Friday March 08, 2019 @08:32PM (#19343907)
Isn't raft the default for Bitcoin?
Re:A generalised solution to distributed consensus by deathanatos on Friday March 08, 2019 @08:44PM (#19343946)
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:

> 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.

Re:A generalised solution to distributed consensus by narrator on Friday March 08, 2019 @10:12PM (#19344210)
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

Re:A generalised solution to distributed consensus by hugofirth on Saturday March 09, 2019 @05:13AM (#19345454)
True. Though in tradeoff it has massively increased throughput. I'm always frustrated when I see blockchains recommended as a solution for a consensus problem in anything but a zero-trust scenario
Re:A generalised solution to distributed consensus by parasubvert on Saturday March 09, 2019 @11:26AM (#19346841)
Even in a zero trust scenario, you need a majority of nodes to be good faith, non-colluding actors. Even anarchy breaks down in the face of unequal power.
Re:A generalised solution to distributed consensus by RcouF1uZ4gsC on Friday March 08, 2019 @11:00PM (#19344361)
Bitcoin consensus is what is called Byzantine consensus - that is your consensus still has to work with some nodes actively trying to send bad information to mess up the protocol.

Raft and Paxos are non-Byzantine. They assume that the nodes are actively trying to follow the protocol though there me be such things as network partitions and crashes.

Re:A generalised solution to distributed consensus by kccqzy on Friday March 08, 2019 @10:20PM (#19344232)
Bitcoin consensus is extremely simple: the chain with the most accumulated difficulty. Furthermore blocks aren't removed or changed, so consensus is in fact a monotonic process. You don't need either Paxos or Raft or any other sophisticated algorithm; just broadcast every block you believe to be part of the most difficult chain and consensus will be achieved.
Re:A generalised solution to distributed consensus by thecoinrepublic on Saturday March 09, 2019 @01:20AM (#19344796)
The client maintains a decision table with one entry for each quorum of each register set.