7 ms·

Swarm consensus [pdf]

122 points by gritzko 5y ago

erpellan 5y ago
Interesting! How does this compare to Serf / SWIM? https://www.serf.io/docs/internals/gossip.html https://www.serf.io/docs/internals/gossip.html https://www.cs.cornell.edu/projects/Quicksilver/public_pdfs/SWIM.pdf https://www.cs.cornell.edu/projects/Quicksilver/public_pdfs/...
- gritzko 5y ago
  In a fundamental way: a node is not tracking all other nodes. The number of nodes may be unknown. A node only tracks its adjacent nodes.
isaacimagine 5y ago
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? 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?
- gritzko 5y ago
  Very good question. The article clearly lacks a section on that. This form of consensus is made for a different set of trade-offs than Raft or Paxos or blockchains. It implies a swarm of participants of an unknown size and, mainly, CRDT data structures. That subject deserves an article of its own though. Swarm consensus does not seek quorums, it has no knowledge of the number of nodes. It assumes there is a way to connect to the "giant cluster" in a highly redundant way. On the other hand, if disconnected (blackout etc), islands of consensus can progress despite that. So it is more on the AP side, like everything CRDT.
- colinmhayes 5y ago
  Doesn't seek quorums, so it's not consistent in the face of partitions.
saurik 5y ago
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.) 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).
- gritzko 5y ago
  On the formal side, SC is deterministic and nodes only talk to their friends, which is the opposite of Avalanche. The article has some calculations for the case of real-world time, but in the end it is always a question of acceptable timeouts. In a fully asynchronous system, deterministic consensus is impossible. What does it mean practically is a different story though. Regarding distance effects, if node clocks are well synchronized (like, NTP well, not TrueTime well) and the time step is long enough, then the heartbeat should work fine, I believe.
judofyr 5y ago
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. This algorithm requires a lot 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 15 messages (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). In addition this is heavily round-based (the nodes only progress once they've received responses from all neighbors) which means that one slow node ("straggler") can stall everything. I'm super interested if it's possible to expand on the ideas in the paper though!
- gritzko 5y ago
  Thanks, we will address that.
- DarylZero 5y ago
  Have you looked at Stellar at all? https://www.stellar.org/papers/stellar-consensus-protocol https://www.stellar.org/papers/stellar-consensus-protocol https://medium.com/interstellar/understanding-the-stellar-consensus-protocol-423409aad32e https://medium.com/interstellar/understanding-the-stellar-co...
- gritzko 5y ago
  Actually, I may address it here. > This algorithm requires a lot of messages The algorithm requires (1) data propagation (proposal) messages and (2) heartbeat messages that confirm progress similar to TCP ACKs. The amount of heartbeat messages is not dependent on the presence/absence/number of proposals. Both types of messages are more or less unavoidable. > one slow node ("straggler") can stall everything In fully asynchronous systems, consensus is impossible anyway. Hence, there is always some turn duration/timeout value.
DarylZero 5y ago
How does this compare to Stellar? https://www.stellar.org/papers/stellar-consensus-protocol https://www.stellar.org/papers/stellar-consensus-protocol https://medium.com/interstellar/understanding-the-stellar-consensus-protocol-423409aad32e https://medium.com/interstellar/understanding-the-stellar-co...
- gritzko 5y ago
  If I understand correctly, Stellar assumes there is some core of the network where quorum slices intersect?
  - noxer 5y ago
    Don't know about Stellar but the original XRPL consensus which Stellar is based on requires each validator "node" (nodes that participate in consensus finding) to define which other nodes it listens to (This list of other nodes doesn't have to be public.) But if you would make all the lists public the most overlapped nodes would be the core. A common misconception is however that nodes in this core somehow have more rights or can somehow affect the outcome of the consensus. Which is not the case. Each node enforces all rules. The overlap is only requires in the sense of that it prevents forking. I.e. if there would be 2 loosely connected "cores" the same size and they get disconnected form each other, both sides could keep going which is objectively worse than if the system halts until the problem is resolved. This "emergency halting" is only guaranteed if there is one core that is overlapped enough so that no 2 separated parts or the network could reach the 80% quorum.
  - DarylZero 5y ago
    As I understand it, the protocol doesn't assume that. It's just an assumption of the payment processing network built on top, that there will be some "strong set" or whatever of nodes that includes big banking institutions and that actual human beings will recognize as canonical.
rileyphone 5y ago
Some background https://m.youtube.com/watch?v=sSYeqZYgSUk https://m.youtube.com/watch?v=sSYeqZYgSUk
api 5y ago
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." 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 efficient general solution with no subjectivity and no assumption of a sentient or AI operator who can intervene is possible. 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.
- noxer 5y ago
  FBA does not require to know who your friends are you just need to know enough nodes. If some of the nodes are not your friend aka they lie to you, you would know as soon as they lie and you can simply stop listen to them. This however requires identities. You cant just listen to anyone because someone could simply fire up 1000 lying nodes and if you pick 100 at random you'd have mostly lying nodes. You would figure out if they lie but then you have to stop listen to them all and you are offline. In practice this is not a real problem because obvious you would pick old nodes and not the 1000 freshly generated "identities". The assumption that you know nothing about any other node is a more or less made up thing for theoretical analysis that has no relevance in the real world. You dont start a network form zero you just want to join an existing one and you know its there so you might as well know who is there.
  - api 5y ago
    Ahh, okay, but requiring identities means you must have a central authority to issue them or they must be extremely costly (proof of work or similar). Of course this doesn't make this useless. If identities are all you need then you've devolved the role of the central authority to nothing more than something that says who you are. If there is no provision for centralized identity revocation then you don't have a censorship problem because once you have an identity you have it forever. Identities could also be anonymized keys where only the central authority knows the true identity, minimizing privacy exposure surface area. Decentralization isn't boolean. This is more decentralized than Raft. Edit: I suppose proof of work for identities could be less costly than continuous PoW. The work required just has to be high enough to make sybil attacks expensive enough to meet your threat model threshold.
davidrusu 5y ago
> 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). > 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 If I understand this correctly, a single node crashing would stall it's entire neighbourhood. @gritzko, can you confirm?
- gritzko 5y ago
  Nope. Missed a heartbeat means gone. We discuss churn later in the article. Its effects are complicated, but as long as d holds, everything else holds.
  - davidrusu 5y ago
    Ok, the red flag to me is the reliance on all neighbours responding to a proposal. Suppose we have a faulty node heart-beating correctly but not responding to proposals, or selectively responding to proposals. This would seem to imply that dishonest nodes have full control over which decisions are made.
    - gritzko 5y ago
      see later in the article, Ctrl+F "mushrooms"
      - davidrusu 5y ago
        I will stop looking into this now, I have to get back to my work. The colorful language doesn't make it easy for someone who follows the literature to review your idea. I still have doubts that you can handle a dropped message or how much control a faulty node has over decisions, but I'll leave that to you to work out.
crawfordcomeaux 5y ago
How might this look if implemented by a group of people, instead of a group of computers?

122 points by gritzko 5y ago

Interesting! How does this compare to Serf / SWIM? https://www.serf.io/docs/internals/gossip.html https://www.serf.io/docs/internals/gossip.html https://www.cs.cornell.edu/projects/Quicksilver/public_pdfs/SWIM.pdf https://www.cs.cornell.edu/projects/Quicksilver/public_pdfs/...

gritzko 5y ago
In a fundamental way: a node is not tracking all other nodes. The number of nodes may be unknown. A node only tracks its adjacent nodes.

isaacimagine 5y ago

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

gritzko 5y ago
Very good question. The article clearly lacks a section on that. This form of consensus is made for a different set of trade-offs than Raft or Paxos or blockchains. It implies a swarm of participants of an unknown size and, mainly, CRDT data structures. That subject deserves an article of its own though. Swarm consensus does not seek quorums, it has no knowledge of the number of nodes. It assumes there is a way to connect to the "giant cluster" in a highly redundant way. On the other hand, if disconnected (blackout etc), islands of consensus can progress despite that. So it is more on the AP side, like everything CRDT.
colinmhayes 5y ago
Doesn't seek quorums, so it's not consistent in the face of partitions.

saurik 5y ago

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

gritzko 5y ago
On the formal side, SC is deterministic and nodes only talk to their friends, which is the opposite of Avalanche. The article has some calculations for the case of real-world time, but in the end it is always a question of acceptable timeouts. In a fully asynchronous system, deterministic consensus is impossible. What does it mean practically is a different story though. Regarding distance effects, if node clocks are well synchronized (like, NTP well, not TrueTime well) and the time step is long enough, then the heartbeat should work fine, I believe.

judofyr 5y ago

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. This algorithm requires a lot 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 15 messages (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). In addition this is heavily round-based (the nodes only progress once they've received responses from all neighbors) which means that one slow node ("straggler") can stall everything. I'm super interested if it's possible to expand on the ideas in the paper though!

gritzko 5y ago
Thanks, we will address that.
DarylZero 5y ago
Have you looked at Stellar at all? https://www.stellar.org/papers/stellar-consensus-protocol https://www.stellar.org/papers/stellar-consensus-protocol https://medium.com/interstellar/understanding-the-stellar-consensus-protocol-423409aad32e https://medium.com/interstellar/understanding-the-stellar-co...
gritzko 5y ago
Actually, I may address it here. > This algorithm requires a lot of messages The algorithm requires (1) data propagation (proposal) messages and (2) heartbeat messages that confirm progress similar to TCP ACKs. The amount of heartbeat messages is not dependent on the presence/absence/number of proposals. Both types of messages are more or less unavoidable. > one slow node ("straggler") can stall everything In fully asynchronous systems, consensus is impossible anyway. Hence, there is always some turn duration/timeout value.

DarylZero 5y ago

How does this compare to Stellar? https://www.stellar.org/papers/stellar-consensus-protocol https://www.stellar.org/papers/stellar-consensus-protocol https://medium.com/interstellar/understanding-the-stellar-consensus-protocol-423409aad32e https://medium.com/interstellar/understanding-the-stellar-co...

gritzko 5y ago
If I understand correctly, Stellar assumes there is some core of the network where quorum slices intersect?
- noxer 5y ago
  Don't know about Stellar but the original XRPL consensus which Stellar is based on requires each validator "node" (nodes that participate in consensus finding) to define which other nodes it listens to (This list of other nodes doesn't have to be public.) But if you would make all the lists public the most overlapped nodes would be the core. A common misconception is however that nodes in this core somehow have more rights or can somehow affect the outcome of the consensus. Which is not the case. Each node enforces all rules. The overlap is only requires in the sense of that it prevents forking. I.e. if there would be 2 loosely connected "cores" the same size and they get disconnected form each other, both sides could keep going which is objectively worse than if the system halts until the problem is resolved. This "emergency halting" is only guaranteed if there is one core that is overlapped enough so that no 2 separated parts or the network could reach the 80% quorum.
- DarylZero 5y ago
  As I understand it, the protocol doesn't assume that. It's just an assumption of the payment processing network built on top, that there will be some "strong set" or whatever of nodes that includes big banking institutions and that actual human beings will recognize as canonical.

rileyphone 5y ago

Some background https://m.youtube.com/watch?v=sSYeqZYgSUk https://m.youtube.com/watch?v=sSYeqZYgSUk

api 5y ago

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." 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 efficient general solution with no subjectivity and no assumption of a sentient or AI operator who can intervene is possible. 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.

noxer 5y ago
FBA does not require to know who your friends are you just need to know enough nodes. If some of the nodes are not your friend aka they lie to you, you would know as soon as they lie and you can simply stop listen to them. This however requires identities. You cant just listen to anyone because someone could simply fire up 1000 lying nodes and if you pick 100 at random you'd have mostly lying nodes. You would figure out if they lie but then you have to stop listen to them all and you are offline. In practice this is not a real problem because obvious you would pick old nodes and not the 1000 freshly generated "identities". The assumption that you know nothing about any other node is a more or less made up thing for theoretical analysis that has no relevance in the real world. You dont start a network form zero you just want to join an existing one and you know its there so you might as well know who is there.
- api 5y ago
  Ahh, okay, but requiring identities means you must have a central authority to issue them or they must be extremely costly (proof of work or similar). Of course this doesn't make this useless. If identities are all you need then you've devolved the role of the central authority to nothing more than something that says who you are. If there is no provision for centralized identity revocation then you don't have a censorship problem because once you have an identity you have it forever. Identities could also be anonymized keys where only the central authority knows the true identity, minimizing privacy exposure surface area. Decentralization isn't boolean. This is more decentralized than Raft. Edit: I suppose proof of work for identities could be less costly than continuous PoW. The work required just has to be high enough to make sybil attacks expensive enough to meet your threat model threshold.

davidrusu 5y ago

> 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). > 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 If I understand this correctly, a single node crashing would stall it's entire neighbourhood. @gritzko, can you confirm?

gritzko 5y ago
Nope. Missed a heartbeat means gone. We discuss churn later in the article. Its effects are complicated, but as long as d holds, everything else holds.
- davidrusu 5y ago
  Ok, the red flag to me is the reliance on all neighbours responding to a proposal. Suppose we have a faulty node heart-beating correctly but not responding to proposals, or selectively responding to proposals. This would seem to imply that dishonest nodes have full control over which decisions are made.
  - gritzko 5y ago
    see later in the article, Ctrl+F "mushrooms"
    - davidrusu 5y ago
      I will stop looking into this now, I have to get back to my work. The colorful language doesn't make it easy for someone who follows the literature to review your idea. I still have doubts that you can handle a dropped message or how much control a faulty node has over decisions, but I'll leave that to you to work out.

crawfordcomeaux 5y ago

How might this look if implemented by a group of people, instead of a group of computers?