discv5: topic index design thread

In order to register a node for a certain topic, it must place ads for itself on other nodes. In the current version of the spec, the process of registering with a single node is very well described, but distributing ads among registrar nodes is still unsolved.

There are two sub-problems here: (1) is HOW MANY ads a single node should place, (2) is WHERE they should be placed.

For (1), what we need is an algorithm that places ads such that the node can be 'found enough', where the notion of 'enough' is application-specific.

Intuitively, if every registrant node was targeting a fixed number of live ads, the odds of finding any particular node would be the same and the system would stay balanced. Unfortunately, this can be gamed too easily by simply registering on more nodes than everyone else.

Our current best guess for doing this better is to compute the notion of 'found enough' based on
peer activity outside of the discovery protocol. We can assume that every participant is able decide whether the current amount of incoming useful peer connections is too high or too low. If the incoming peer connection rate is too low, we can simply increase the number of live ads we target. This can still be gamed, but ensures that nodes will correct for imbalances automatically. The remaining issue here is to find out how this measurement can be implemented in practice. If an application uses multiple topics, it might not be possible to attribute incoming connections to a particular topic, for example.

For problem (2), which is where ads should be placed, we want the algorithm to pick registrars such that the set of considered registrar nodes shrinks and grows according to some estimation of topic size, i.e. popular topics provided by many participants should use a larger subset of the whole network to store ads.

To do this, we decided early on that ad distribution should use Kademlia distance to determine a subset of all nodes, the size of which we called the 'topic radius'. The radius was to be estimated by checking ticket waiting times, but then we found multiple issues (#111, #112) and concluded that using the waiting time is a dead end because it can vary for reasons other than topic popularity.

Instead, it seems that the number of nodes in the topic queue of each registrar is a better indicator. If registrants could obtain this number in some way, they could walk the network for a while to find registrars which have space available and fill it. How exactly this should happen, and whether this approach will converge on a good distribution ads is still an open question.