Discourage nodes from re-register attempts

[harnen]

We still have a problem with our waiting time formula described below. Each incoming request is coming from a specific IP address, an ID and is for a specific topic.

• n - capacity of the table
• d - number of entries currently in the table
• d(IP) - number of entries currently in the table with given IP
• d(ID) - number of entries currently in the table with given ID
• d(topic) - number of entries currently in the table with given topic
• a - registration lifetime (time spent in the table)
• w - waiting time

The formula proved to work really well in multiple scenarios. However, when request r1 arrives at time t1 and is given waiting time w1, we cannot guarantee that coming back after t < w1 won't give the registrant a better waiting time.

Consider a request r1 coming at t1=10, based on the entries already in the table, the waiting time is calculated as w1=100s. However, it may happen that at t2=15s a lot of ads will expire and decreasing the waiting time to w2=5s. The registrant thus shouldn't wait for w1, but rather come at t3 = t2 + w2. We can reliably calculate this time, but the complexity is high O(d). What is worse, some ads expiring may actually increase the waiting time, so we cannot optimize it with a binary search and reduce the complexity to O(log(n)).

The tickets issued by the registrar carry the accumulated waiting time. I.e., the total waiting time, the registrant already waited for. It means that the registrant doesn't have any incentive to try to re-register if the decrease in the waiting time is lower than the time between the registration attempts: t2 - t1 < w1 - w2