Delays and Blacklisting

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

  1. 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
  2. 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.
  3. 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.
  4. 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.

The node would measure E\tau. Then it would adjust:

  1. \theta the blacklisting threshold
  2. \alpha\theta which would be the back off threshold.
    The minimum mana threshold would also be changing, but this would be handled by the blacklister

Also the minimum mana threshold could be handeled by the rate setter. If the amount of mana you have would make it so that your next message would trigger the back off threshold, then the rate setter should tell you to not issue the message.

It is not clear why this waiting time occurs at every node. Think about crossing the border of two countries and both work at the same rate. Then essentially you only have to queue at the exit of the first country and entering the second country is much faster.

This seems strange. By choosing \theta arbitrarily small you can get the delay down to 0?

I did not follow all the arguments, but all arguments are in expectation, so the result should be like the expected buffer size is bounded.

This last term is a constant. But B is random.

Thats true. In the previous section Q_n is not a random variable but a fixed quantity. But in considering the whole network simultaneously, we are actually taking the sum of several non identical random variables.

I think the general point is that \delta_N is related somehow to the global network delay, and bounding it, also caps the network delay too.

Well choosing \theta arbitrarily small means that no one can issue a message because no one has enough mana. Also, we are ignoring that actual communication between nodes.

Actually, $B$ is not random, because we fix our view from a particular view in a particular point in time. In particular we dont treat $Q_N$ as a random variable.

I hope that makes sense mathematically: remember Im just an algebraist :slight_smile:

Again, I play the algebraist card :slight_smile: But the bound is in terms of numbers? If you relate two expectations, you can bound a value, correct?

@sebastian.mueller

Maybe my one caveat is this is more or less a hypothesis. I was hoping this would work as “engineering math”: we do bend some mathematical rules to guess how the system would behave, and then test the behavior in simulations.

I share most of Billy’s thoughts and I’m adding here a few more comments:

  • The analysis does not consider the orderer module (that’s a reasonable assumption, the analysis would get too complicated)
  • ΔN ≈ Diameter * E[δN]. IMO, E[δN] can be considered as an upperbound on the expected scheduling delay. In practice, the first node creates a bottleneck and releases messages at “a correct pace”. What I mean is that messages most likely only accumulate at the issuing node’s buffer.
  • Why do you add size(M) to the scheduling delay of the message factory? Because you consider a new message after QN in the bufferr and Mqueue in the message factory, right? Why don’t you just consider 1 (instead of size(M)) since you assumed same size messages?
  • You mention that the blacklisting threshold introduces an upper bound on the delay. Under normal conditions (i.e., without adversaries), the delay is bounded by the backoff threshold since queues should never grow larger than that. The blacklisting threshold represents the worst case scenario.
  • Your analysis takes E[τ] as a fixed input value. In reality, this depends on a number of things, one of those being the minimum mana threshold.
  • Having a dynamic blacklisting threshold is ideal, but I am not sure how big the discrepancies in the traffic perception would be. I don’t want to end up in a situation where nodes have different perspectives of the congestion and start blacklisting nodes in a different way. That could perhaps affect consistency. The good thing is that I assume this stuff can be tested (easily?) in the DevNet