You are reading content from Scuttlebutt
User has not chosen to be hosted publicly
@Rabble %B9BEH/0FS3Sq7H/4dMQSRWIfx93Ne066d6GCgbRm9uQ=.sha256
Voted # Planetary Go Dev Diary During previous dev updates I described our work
User has not chosen to be hosted publicly
@aljoscha %kHH2B9NHcqjQ0aU7YYtVYXJ8ZZ/h2+5unn5+5KbC1PU=.sha256

@moid

My intuition tells me spanning trees are involved.

The nice thing about ebt though is that the spanning tree are a purely global phenomenon, an individual node isn't aware of what those trees look like beyond its neighbors.

@boreq

I cannot speak about the network protocol details in ssb's flavor of ebt, but the conceptual idea (see the paper @moid mentioned) is quite simple: consider a network of nodes, where every node is only connected to a small number of other nodes; different connections may incur different delays when sending a message. One of the nodes produces a sequence of messages, the goal is to broadcast this sequence of messages to all nodes.

We want to optimize three metrics: total number of bits transmitted, latency until the message has reached every node if no connection failures occur, and the impact of connection failures. There are three basic strategies:

  • eager flooding (push): When receiving a message for the first time , send it to every neighbor. This has minimal latency, cannot fail if the network stays connected, but has to transfer many bits.
  • lazy flooding (pull): When receiving a message for the first time, notify every neighbor. They can then request the message from you. This is more efficient in terms of bits transferred, as every message is transmitted only once per node. The resistance to connection failures is the same as that of eager flooding. The latency is however three times as high as the optimum.
  • push along a minimum-weight spending tree: Globally compute a minum-weight (the weight of a connection is its latency) spanning tree over the network, perform eager push along this spanning tree only. Results in minimum latency and minimum number of bits transmitted, but vulnerable to connection failures on the tree.

Each of the three basic strategies is optimal with respect to two of the metrics but pretty bad with respect to the third. EBT is a more complex strategy that strikes a better balance: Perform eager push along a minimum spanning tree, but also perform lazy flooding on all the other connections. If you receive a lazy notification faster than the eager push of the corresponding message (up to a grace period to avoid triggering this case too many times), the spanning tree is apparently not optimal anymore. Notify the node that gave you the fast lazy notification to eagerly push to you in the future (also ask it for the message in question, in case your old eager supplier will take too long to transmit the message to you), and tell your previous eager neighbor to switch to lazy mode.

With this, latency is still optimal, and only a small number of non-optimal bits are transferred (we assume lazy notifications to be almost negligible in their size), yet the system is highly resistant to connection failures: when an eager connection breaks, the receiving node will receive a lazy notification at some point over a different connection and thus change the tree to not contain the broken connection anymore.

So we get a very efficient, self-healing system, but the local operations of every node are fairly simple.

User has not chosen to be hosted publicly
@Sebastian Heit iOS %mksuisBoJYxNO0OXj6nOf0Rqn3rXY3qwtYw281WzHDk=.sha256
Voted # Planetary Go Dev Diary During previous dev updates I described our work
Join Scuttlebutt now