Random gossip spec update

[morph-dev]

Problem

Current Random Gossip spec indicates that node should gossip content be selecting "random node from a random bucket", repeated n times.

This has a risk of not reliably distributing content to all peers, which is desired property of random gossip.

For example, if I'm the first node that bridge offers the content to, and I randomly select peers that are not in my neighborhood, there is high likelihood that peers from my neighborhood would never actually receive the content (especially if they are new node and not present in buckets of nodes that are far from them, because their buckets were already full when they joined the network).

Some potential solutions

0. Random sampling

I just wanted to list current spec so I can easily reference it later.

I's also worth mentioning that it isn't quite clear which of the following two algorithms are specified:

• select peer at random
• select bucket at random, then select peer from that bucket at random

1. Weighted sampling based on distance

Instead of selecting peers/buckets with unified distribution, we can use weighted sampling such that peers that are closer to nood have higher chance of being selected for gossip. Two ideas:

1.1. Weighted peer sampling

Every peer would have weight assigned to them and n peers would be sampled based on their weights.

• example of the weight could be: $q^{256 - log2\textunderscore distance(peer)}$
• q can be chosen arbitrary (more on this later)

1. 2. Weighted bucket sampling + random peer from a bucket

Every bucket with at least one peer would be assigned a weight (similar to step 1). Then random bucket would be sampled based on their weights. And lastly random peer from selected bucket (uniform distribution) is selected for gossip. This process is repeated n times.

More on choosing parameter q

Selecting q can be tricky because:

• picking too low value would lead to having close to unified distribution
• picking too high value can make it difficult to "escape" neighborhood and propagate content to peers that are far away
  • this is somewhat less of an issue for proposal 1.1. as farther away buckets will have more peers than the one close to us

2. Partial random + partial weighted sampling

One idea that I like is to combine random (unified) sampling and weighted sampling.

For example, something like this:

1. Select n peers based on algorithm 1.2. using q=2
2. Select n peers at randomly

This ensures that peers from both the neighborhood and far away are represented between selected peers.

note: If we want to select the same number of peers, the n in this approach would be half of the n in previous approaches.

[kdeme]

My first very simple thought about this was to do n/2 random and n/2 NHgossip. Which is sort of similar to 2.

[carver]

For example, if I'm the first node that bridge offers the content to, and I randomly select peers that are not in my neighborhood, there is high likelihood that peers from my neighborhood would never actually receive the content (especially if they are new node and not present in buckets of nodes that are far from them, because their buckets were already full when they joined the network).

Thanks for explaining this better than I did in the call. X)

---

The obvious win of a random gossip like 0 is that it's extremely simple. I would love to make our solution as close to that as possible.

One option is basically a refinement of strategy 0:

0.1. peer per bucket

• Uniform-random select n buckets of the peer's k non-empty buckets (if n > k, select all buckets, then repeat with n-k buckets)
• Uniform-random select 1 peer from each selected bucket

There are already more buckets closer to you than further away, which gives you some weighting effect. But maybe it doesn't spread fast enough along the closest neighbors if the network is large.

But I really like that it doesn't have any tunable parameters, besides n.

I asked Gemini to write a simulator, which turned out better than I expected. It probably has some bugs in it, but a quick code-review suggests that it basically did what I asked. (I think the buckets are calculated backwards, but I don't expect that to have any effect)

If each "round" of transmission is 300ms, then we get 99.9% in 3s (ie~ 10 rounds). This assumes everyone has full buckets, no data loss, etc. Is that good enough? Maybe... Or maybe it's important to know what happens with less full buckets.

It shouldn't be terribly difficult to try editing the simulator to use a different propagation strategy, but I think I'm done for now.

[carver]

My first very simple thought about this was to do n/2 random and n/2 NHgossip. Which is sort of similar to 2.

Are you defining NHgossip here to send it to the peers closest to the sending peer node ID, rather than the content ID? That's promising, because it can reuse a good amount of logic (just substituting in the node ID for the content ID)

I haven't had a chance to implement that in the simulation yet, but it's fairly similar to the best strategy I've got in the simulation below.

---

I take back my earlier statement that the random strategy is good enough, I think we can do much better.

I fleshed out the simulator a little bit here: https://github.com/carver/network-propagation-simulator

These are the strategies that I tried out, mostly because they were the quickest to code up:

1. Select N random buckets, select 1 random peer in that bucket (from the screenshot in my previous comment)
2. Select N buckets closest to self, select 1 random peer in that bucket
3. Select 1/2 from first strategy and 1/2 from second strategy
4. Select 1 from first strategy and N-1 from second strategy
5. Select N buckets furthest from self (for laughs)
6. Select N peers closest to self (all from closest bucket, then next closest bucket, etc) (also for laughs)

The most promising strategy in my experiments was strategy 3. All strategies are pretty sensitive to how many peers we gossip to, and the number we need is a bit higher than I expected it to be. (especially to optimize for latency).

I tried with 10k nodes and 2 "Initial Data Holders" (think bridge recipients), started with 4 peers to gossip, and made my way up to 18 peers. Above 18, there was no improvement to latency. I actually haven't made sense of that yet, since there are less than 2^14 nodes in this simulation, so I wouldn't have expected any improvement over ~14.

Other observations during experimentation:

• Strategy 2 would often work very well, except when it didn't. Then it would fail to reach ~1/2 or more of the network
• Strategy 1 would often stall after reaching 99.9% of the network, so some nodes just never received the data (this becomes less and less likely as the number of peers goes up to 18, but is still pretty common at 14)
• Strategy 3 sent the fewest messages per peer, for the same N peers to gossip setting
• 5 Stalls out pretty quickly, leaving a big chunk of the network untouched, usually
• 6 is comically bad, reaching a tiny percent of the network before stalling (as expected)
• Strategy 4 performs about the same as 3, but sends a bit more messages per peer

Strategy 1 stall example at 14:

Strategy 3: example at 14:

At 14, the number of rounds ranges from 7-9. At 18, it's rarely more than 7 rounds.

[carver]

Some updates after the meeting today:

Most importantly: I favor a new simpler strategy now, which is to select all non-empty buckets, and pick one random peer from each of them to gossip

Comparison to strategy 3 from earlier:

• ~same # of rounds to propagate
• gets rid of two different parameters (the 50/50 split between random and closest, and the N number of peers to fan out to)
• As a side effect of getting rid of the fan-out parameter: the number of peers you fan out to scales automatically as the network grows.
• The number of messages is less predictable, at log2(n) of the network size (the downside of an auto-scaling parameter)
• Small increase in the number of messages received (~1 more message per peer)

I think the simplicity win, similar latency success, and small communication cost make this the new leading contender.

---

I added another new strategy: selecting N random peers across the pool of all buckets. We kinda knew it would be bad, but it's fun to test anyway. Yeah, it stalls before reaching everyone fairly often.

---

I also played with increasing the number of starting nodes with data. I was curious if that would improve the "1 peer from each of N random buckets" strategy. With a network of 65k nodes, and 2k initial sources, it was actually fairly common for it to miss a few peers and stall out. But yeah it still is mostly successful:

With the same config, the "All buckets -> 1 peer" strategy never failed in my ~10 simulations, taking 5 rounds usually, and uses slightly fewer messages per peer.

[morph-dev]

I like the simplicity and scaling properties of 1 random peer for each kbucket.