I was reading a document that Olivia wrote about estimating queue sizes in the IOTA Congestion Control Algorithm, and she pointed out that the delay is related to the time it takes for the scheduler to complete one DRR round. I realized this seems to have some implications in estimating the delay of a message, and for the behavior of the network. Skip to the conclusions for a TL:DR.
Notation
In the following, we consider the perspective of a fixed node.
- R_N is the reputation (i.e. mana) of node N
- D_N is the deficit awarded to a node in each round of the scheduler. The Deficit is measured in ātransactionsā
- k: By definition, D_N=kR_N for a constant k
- Q_N is the length of nod N's queue measured in transactions.
- \delta_N: Consider the message M at the end of node N's queue. The random variable \delta_N denotes the time it take for M to be scheduled.
- \tau is the time it takes for the scheduler to complete one DRR round. \tau is a random variable.
- \Delta_N is the delay for messages issued by N.
A simple relation
Let M be the message at the end of N's queue. Whenever, the scheduler visits node N's queue, it schedules D_n messages. Thus, scheduling M, and the Q_N messages before it, requires Q_N/D_n visits from the scheduler. Since the scheduler visits each queue once every \tau seconds, we therefore have the following relationship
E \delta_N=\frac{Q_N}{ kR_n} E\tau
Network Delays
This equality is interesting because we can use \delta_N to approximate the network delay of messages issued by N:
\Delta_N\approx(\textrm{Diameter})E\delta_N
This holds because each āhopā in the network experiences a delay of E\delta_N. Thus, the above formula concerns the delay of the entire network.
Also of important, E\delta_N also can estimate the time it can take to schedule a message. Suppose N is our own nodeās ID. Our message factory will contain a queue of payloads waiting to be scheduled. Let M_{\textrm{queue}} be the length of current message factory queue measured in transactions. If a wallet asks our node āhow long till you will schedule this transaction Txā we can reply using the previous logic with the following time:
\frac{Q_N+M_{\textrm{queue}}+\textrm{size}(Tx)}{ kR_n} E\tau
where E\tau is estimated based on recent activity.
Black listing
In ICCA, we black list a node N if its scaled inbox length, \frac{Q_N}{R_N}, is greater than a threshold \theta. We can conclude from our previous work that the black listing threshold implicitly bounds the delay \Delta_N:
\Delta_N\approx (\textrm{Diameter})E\delta_N=(\textrm{Diameter})\frac{Q_N}{ kR_n} E\tau<\frac{\textrm{Diameter}}{k}\theta E\tau
Thus the networking delay is actually bounded by the black listing threshold! This suggests that by dynamically setting the black listing threshold by the estimating \tau:
\theta=\frac{k\Delta_{\textrm{max}}}{(\textrm{Diameter})E\tau}
Where \Delta_{\textrm{max}} is the bound on the delay.
Max Buffer Size
Since our consensus is asynchronous, what bounds do we even need to bound the network delay? If nodes had an infinite sized buffer, then arbitrary delays could be tolerated, and thus so could infinite queues. But the finiteness of the buffer means that we have to cap delays.
Using our previous work, we can actually prove that our black listing policy really does bound the requisite size of the buffer, as we demonstrate below.
Let \delta_{\max} be the maximal size of any \delta_N allowed by the black listing policy. Specifically, set
\delta_{\max}=\frac{\theta}{ k} E\tau=\frac{\Delta_{\max}}{\textrm{Diamter}}
and let B be the size of the buffer. We have then that:
B=\sum_N Q_N=\frac{k}{E\tau} \sum_N R_n E\delta_n<\frac{k}{E\tau} \sum_{\textrm{Active }N} R_n \delta_{\max}=\frac{\delta_{\max}k}{E\tau} \sum_{\textrm{Active }N} R_n =\frac{\delta_{\max}k}{E\tau} (\textrm{Active Mana})
We can simplify further by considering E\tau. In each nonempty queue, the scheduler will be scheduling D_N messages at the scheduling rate \nu. Thus
E\tau=\sum_{\textrm{Active} N} \frac{D_N}{\nu}=\sum_{\textrm{Active} N} \frac{kR_N}{\nu}= \frac{k}{\nu}\sum_{\textrm{Active} N} R_N=\frac{k}{\nu}(\textrm{Active Mana})
Finally, substituting this computation of E\tau into the above inequality yields:
B<\delta_{\max} \nu=\frac{\Delta_{\max}\nu}{\textrm{Diamter}}
Thus the buffer size is bounded!
Moreover, the equality is strict in the case when every active node allows their reputation scaled queue Q_n/R_n to reach \theta. In this extreme scenario, notice then that since all the reputation scaled inboxes are the same length, that the buffer then is allocated according to active mana. This is quite incredible actually, because the allocation adapts (along with the black listing threshold) to the active mana.
Thus, with the dynamic black listing threshold proposed above, the ICCA guarantees that the buffer is finite and space is allocated fairly. However, the buffer will not be fully utilized unless all nodes have maxed out their queues, and thus we do not have min max fairness. Is this ok?
Minimum Mana Threshold
Nodes need some amount of mana to issue messages, but what is the lower bound? Any fixed bound is inherently problematic as it limits functionality, and so its clear to make it dynamic. But based on what?
While we often think of black listing as punishing malicious behavior, what we have seen here is that it really just bounds the network delay. Ultimately the same logic applies to minimal minimal mana: the threshold should be set to prevent intolerable delays. Thus I propose not having a separate minimum mana threshold but just use the black listing.
What would the minimum mana need to send a message, Tx? It would be the amount of mana required such that the queue wont be black listed. Thus mana must satisfy:
\frac{\textrm{Size}(Tx)}{R_n}<\theta
Therefore, the minimum amount of mana to send message Tx must be
\frac{\textrm{Size}(Tx)}{\theta}=\frac{\textrm{Size}(Tx)E\tau}{k\delta_{\max}}
Conclusions
We summarize our thoughts below
- When a wallet is requesting that a node schedule a transaction, a node can estimate the time using the equation E \delta_N=\frac{Q_N}{ kR_n} E\tau
- To bound the network delay, a dynamic blacklisting threshold should be set with the following equation \theta=\frac{k\delta_{\textrm{max}}}{E\tau} where \delta_\max is the max delay devided by the expected diameter.
- With this dynamic black listing threshold, the max size of the buffer is \delta_\max \nu. Moreover, ICCA will always allocate the buffer fairly according to the active mana.
- The minimum amount of mana to required to issue a transaction is \frac{\textrm{Size}(Tx)}{\theta}.
Therefore, by maintaining an estimate of E\tau, and using this value in the message factory and black listing, we can easily solve several problems at once. Unless, of course, there is a problem with my math.
