I read through the paper when the first draft was published on Arxiv a few weeks ago. It's a very neat algorithm and there seems to be a cool underlying concept here, but I wasn't quite able to make it practical.<p>This algorithm requires a <i>lot</i> of messages. E.g. if you have four nodes positioned in a line and an action is starting at the end, it will need in total <i>15 messages</i> (A sends 4 messages to B; B sends 3 messages to both A+C; C sends 2 messages to both B+D; D sends one message to C). And in general what happens is that as the action is being propagated to the boundary of the graph, the current nodes keep "heart beating" to each other: They continue sending messages to each other which doesn't contribute to any specific exchange of information (other than staying in sync).<p>In addition this is heavily round-based (the nodes only progress once they've received responses from <i>all</i> neighbors) which means that one slow node ("straggler") can stall everything.<p>I'm super interested if it's possible to expand on the ideas in the paper though!
At least at a high level, this sounds a lot like Avalanche? Each node tells their neighbors about something and eventually a phase transition is passed that makes it super difficult for anyone to convince anyone something different happened? (Which itself claims to be revolutionary but has always felt like an example of an Ising model to me, which others have used for consensus.)<p>My biggest concern, at a lower level, is the mechanism used to try to get away from this algorithm having "turns"--which the real world does not have as there is no shared clock due to distance effects (which is made all the worse due to the Internet not satisfying triangle inequality)--seems to rely on a fixed diameter and some timing assumptions that squick me (as someone who always wants to find asynchronous solutions).
How does this compare to Stellar?<p><a href="https://www.stellar.org/papers/stellar-consensus-protocol" rel="nofollow">https://www.stellar.org/papers/stellar-consensus-protocol</a><p><a href="https://medium.com/interstellar/understanding-the-stellar-consensus-protocol-423409aad32e" rel="nofollow">https://medium.com/interstellar/understanding-the-stellar-co...</a>
Neat paper, but: "Gnomes know each other, to start with, so the problem itself is non-existant, not to mention the price of the solution. Similarly, the Byzantine generals problem was found to be irrelevant at first. Gnomes know who their friends are."<p>That makes it useless for real world coordination outside of systems run by closed vertically integrated organizations like companies, governments, etc. In the real world you don't know who your friends are. That's the point of Nakamoto consensus, which is AFAIK the only known partial real world solution to this problem. Unfortunately it's grotesquely inefficient and still has failure modes when you assume "irrational" actors willing to burn resources just to destroy the system. That's why I called it a partial solution. I still wonder if an <i>efficient</i> general solution with no subjectivity and no assumption of a sentient or AI operator who can intervene is possible.<p>This could potentially be better than Raft and friends for geographically distributed consensus or extreme scalability. Raft based systems ultimately end up being limited by the ability of the leader to lead a sufficiently large cluster. In practice with modern server-grade hardware this limit is quite high but it still exists.
Interesting! How does this compare to Serf / SWIM?<p><a href="https://www.serf.io/docs/internals/gossip.html" rel="nofollow">https://www.serf.io/docs/internals/gossip.html</a><p><a href="https://www.cs.cornell.edu/projects/Quicksilver/public_pdfs/SWIM.pdf" rel="nofollow">https://www.cs.cornell.edu/projects/Quicksilver/public_pdfs/...</a>
What are the use cases of swarm consensus? Is it byzantine fault tolerant? (I think so?) If so, what component of the CAP theorem does it sacrifice? It it suitable for use in federated/distributed contexts (e.g. resistant to Sybil attacks), or is it more a replacement for PAXOS or Raft?<p>I bring up the last point because these algorithms (e.g. Raft) require knowledge of the full quorum, whereas Swarm seems to work on a slice of the full quorum. If it is suitable for distributed use, how does it compare to constructions of FBA such as SCP?
> n ∈ N (p), where N (g) is the set of gnomes who can hear g, including himself. Note that h ∈ N (g) ⇐⇒ g ∈ N (h).<p>> Each gnome g tracks the spread of the proposal in the following way: once all his neighbors n ∈ N (g) say their k-neighborhood (or bigger) is aware of the proposal<p>If I understand this correctly, a single node crashing would stall it's entire neighbourhood. @gritzko, can you confirm?
Some background <a href="https://m.youtube.com/watch?v=sSYeqZYgSUk" rel="nofollow">https://m.youtube.com/watch?v=sSYeqZYgSUk</a>