Introduction

We consider latency of a broadcast on the network constructed from mix nodes which use queues to store in-coming and out-going messages. A message is removed from the queue with probability $q$ which delays messages by a random amount of time governed by the Geometric distribution with parameter $q$. The other source of message delays are due to the latency in communication links which we assume to be “frozen”, i.e. not changing with time. We show that for a single path constructed from $k$ mix nodes the average message latency is proportional to $k/q$ and we estimate the probability of latency being greater than the average. Furthermore, we consider latency of a broadcast on the network with topology of random regular graph with connectivity $c$. Here we find that latency of broadcast, divided by $\log(N)$, is approaching $\frac{2(c-1)}{c(c-2)}\frac{1}{\log(1+q)}$ for a small probability of message removal $q$ as the number of nodes in the network $N$ is growing. However, for finite $N$ the distribution of latency can have long tails. We note that the latter result is established semi-analytically and only for trees we managed to develop a complete analytical framework which can be used to compute the latency of a broadcast. Finally, in this document we propose a simple model of communication latency in consensus.

Analysis

Single node

Assuming that a message is removed from the queue of a node with probability $q$ (see the document), a message in node $i$ is delayed by (at most) $r_i\Delta_i$, where $r_i$ is a random variable from the Geometric distribution with parameter $q$ and $\Delta_i$ is a “cost” of one attempt of removing a message.
Assuming that node $i$ has $c$ connections and it puts a message into all out-queues associated with these connections, i.e. the node $i$ is sending a message. The message will be delayed by (at most) $r_i(1)\Delta_i$ in the queue $1$, by $r_i(2)\Delta_i$ in the queue $2$, etc., where $r_i(1),\ldots,r_i(c)$ is sample from the Geometric distr. with parameter $q$.
Assuming that node $i$ has $c$ connections and it puts a message into all out-queues but not the queue associated with the connection labelled by $c$, i.e. the node is relaying a message, the message will be delayed by (at most) $r_i(1)\Delta_i$ in the queue $1$, by $r_i(2)\Delta_i$ in the queue $2$, etc., where $r_i(1),\ldots,r_i(c-1)$ is sample from the Geometric distr. with parameter $q$.

Single path

Without loss of generality, we consider a message traveling from node $1$ to node $k$. A message is delayed at the node $1$ by $r_1\Delta_1$, at the node $2$ by $r_2\Delta_2$, etc. For node $i$ we assume that $r_i$ is random variable from the Geometric distribution with parameter $q$ and that $\Delta_i>0$. The latter is prop. to a max. time elapsed between attempts to “flip a coin”. Furthermore, a message traveling between the nodes $i$ and $j$ is delayed by $d_{ij}$.

Using above the total delay is given by $\sum_{i=1}^kr_i\Delta_i+ \sum_{i=1}^{k-1}d_{ii+1}$. We note that for $\Delta=\max_{i\in[k]}\Delta_i$ and $d=\max_{i\in[k-1]}d_{ii+1}$ we have

$$ \sum_{i=1}^kr_i\Delta_i+ \sum_{i=1}^{k-1}d_{ii+1}\leq \Delta\sum_{i=1}^kr_i+ (k-1)d $$

The sum $r=\sum_{i=1}^kr_i$ is random variable from the negative binomial distribution

$$ P_{k,q}(r)={r-1\choose k-1}q^k(1-q)^{r-k},\mathrm{where}\,\, r\in\{k,k+1,\ldots\}. $$

Using that $r_i$ is a random variable from the Geometric distribution with parameter $q$ the average and variance of the total delay $\sum_{i=1}^kr_i\Delta_i+ \sum_{i=1}^{k-1}d_{ii+1}$ is given, respectively, by $\sum_{i=1}^k\Delta_i/q+ \sum_{i=1}^{k-1}d_{ii+1}$ and $\frac{1-q}{q^2}\sum_{i=1}^k\Delta^2_i$. The latter, for $\Delta=\Delta_i$ and $d=d_{ii+1}$ , is simplifies to $k\Delta/q+ (k-1)d$ and $\frac{1-q}{q^2}k\Delta^2$.

$The histogram of delays $\sum_{i=1}^kr_i\Delta_i+ \sum_{i=1}^{k-1}d_{ii+1}$ of $N_m=10^6$ messages traveling through $k=5$ nodes (red histogram bars) is compared with negative binomial (o symbols) with parameters $k=5$ and $q=1/2$. Here we assumed that $\Delta_i=1$ and $d_{ii+1}=0$.$

The histogram of delays $\sum_{i=1}^kr_i\Delta_i+ \sum_{i=1}^{k-1}d_{ii+1}$ of $N_m=10^6$ messages traveling through $k=5$ nodes (red histogram bars) is compared with negative binomial (o symbols) with parameters $k=5$ and $q=1/2$. Here we assumed that $\Delta_i=1$ and $d_{ii+1}=0$.

The mean of sum $\sum_{i=1}^kr_i$ is equals to $k/q$. For $\epsilon>0$ the probability $\mathrm{P}\left(\sum_{i=1}^kr_i\geq (1+\epsilon)k/q\right)$ can bounded from above as follows

$$ \mathrm{P}\left(\sum_{i=1}^kr_i\geq (1+\epsilon)k/q\right)\leq\left(\frac{q \left(\epsilon -1\right)+1}{1-q}\right)^{k} \left(\frac{q \left(\epsilon -1\right)+1}{\left(1-q \right) \left(\epsilon q +1\right)}\right)^{-\frac{k \left(1+\epsilon \right)}{q}} $$