Owner: @Alexander Mozeika

Supporting work of:

NomosDA

Blend

Deterministic random graph topology generation ✅
Disincentivizing Cover Traffic Emission Delay 👥
Minimal Stake Threshold Design ❌
Network Performance Improvements 👥
Resiliency research and improvements ****✅

Latency of broadcast

Use recent Analysis of latency work on as a starting point.
We consider latency of a broadcast on the network of $N$ nodes modelled by a weighted random graph (RG) .
The latency of broadcast is the time it takes for a message sent from a node to be delivered to the other $N-1$ nodes of the network.
If network is modelled by (weighted) RG then latency of broadcast is the diameter of this RG.
We assume that locally RG is tree-like as in the figure below

$A single message is sent from node $1$ to all $N-1$ nodes of the network. The latter has topology of a random regular graph of connectivity $c=3$ which is locally tree-like for large $N$. The total delay of a message sent from node $1$ to node $4$, via the nodes $2$ and $3$, is given by the sum $\sum_{j=2}^4[ r_{j-1j}\Delta_{j-1}+d_{j-1j}]$.$

A single message is sent from node $1$ to all $N-1$ nodes of the network. The latter has topology of a random regular graph of connectivity $c=3$ which is locally tree-like for large $N$. The total delay of a message sent from node $1$ to node $4$, via the nodes $2$ and $3$, is given by the sum $\sum_{j=2}^4[ r_{j-1j}\Delta_{j-1}+d_{j-1j}]$.

We assume that a message sent from node $i$ to node $j$ is delayed by the $r_{ij}\Delta_i+d_{ij}$ amount of time. Here $r_{ij}\Delta_i$ is the delay at node $i$ and $d_{ij}$ is the delay in the communication link between nodes $i$ and $j$.