Topology Design to Minimize P2P Broadcast Delay
Why Topology Matters for Block Propagation
In blockchain networks, every new block must reach every full node as fast as possible. The faster propagation happens, the lower the chance of accidental forks caused by miners working on stale data. Real networks like Bitcoin already limit each node to a handful of outbound peers (traditionally 8), so the question becomes: given a limited number of connections per node, which specific links should we choose to minimize propagation delay across the whole network?
This is a graph topology design problem. We’re not just measuring propagation time on a fixed network — we’re actively searching for the best set of edges under a degree constraint.
Formulating the Problem
Let $N$ be the number of nodes, each placed in some abstract network-distance space. The one-hop latency between nodes $i$ and $j$ is modeled as:
$$L_{ij} = L_{base} + \alpha \cdot d_{ij} + \epsilon_{ij}$$
where $d_{ij}$ is the Euclidean distance between nodes, $\alpha$ is a propagation-speed factor, and $\epsilon_{ij}$ is random network jitter.
When node $s$ broadcasts a block, it floods it through the topology. The time for the block to reach node $v$ is the shortest-latency path:
$$T(s,v) = \min_{\text{path } s \to v} \sum_{(i,j) \in \text{path}} L_{ij}$$
Our optimization objective is the average propagation delay across all node pairs:
$$\bar{T} = \frac{2}{N(N-1)} \sum_{i<j} T(i,j)$$
We want to find the topology (a set of edges, with each node keeping the same number of connections it started with) that minimizes $\bar{T}$. To search this combinatorial space, we use simulated annealing with a temperature schedule:
$$T_{temp}(t) = T_0 \left(\frac{T_{end}}{T_0}\right)^{t/I}$$
and an acceptance probability for worse solutions:
$$P(\text{accept}) = \exp\left(-\frac{\Delta \bar{T}}{T_{temp}}\right)$$
The Python Implementation
1 | import numpy as np |
Initial average propagation delay : 114.86 ms (worst case: 233.59 ms) Optimized average propagation delay: 113.65 ms (worst case: 219.94 ms) Improvement: 1.05%
Walking Through the Code
Network setup: Thirty nodes are scattered in a 2D coordinate space representing abstract network distance. The latency matrix combines a fixed base latency, a distance-proportional term, and symmetric random jitter — this mimics how real internet paths have both physical-distance costs and unpredictable congestion.
Baseline topology: We start from a k-nearest-neighbor graph, connecting each node to its 6 lowest-latency peers. This is a reasonable, geography-aware starting point — similar to how real P2P clients bias new connections toward low-latency peers.
Propagation calculation: Rather than writing our own Dijkstra loop in pure Python, we hand the whole topology to scipy.sparse.csgraph.dijkstra, which computes all-pairs shortest paths in one call using a compiled C backend. This single design choice is what keeps the whole optimization loop fast — a naive per-node Python Dijkstra implementation would spend most of its time in Python-level loop overhead rather than actual computation. Likewise, connectivity checks use scipy.sparse.csgraph.connected_components, a compiled union-find routine, instead of a manual graph traversal.
Simulated annealing: At each iteration we pick two random edges and perform a double-edge swap — this is important because it automatically preserves every node’s degree, so the “max 6 connections per node” constraint is respected without any extra bookkeeping. We reject swaps that disconnect the graph, evaluate the resulting average delay, and accept improvements always, and occasional worsening moves according to the annealing temperature — this lets the search escape local optima early on while converging tightly by the end.
Output: The script prints the before/after average and worst-case delay along with the percentage improvement, so you can see numerically how much the optimized topology helps.
Reading the Graphs
The 2D topology comparison shows the raw k-NN network on the left and the annealing-optimized network on the right, with edges colored by latency (darker purple = higher latency, bright yellow = lower). Look for whether the optimized graph favors more geographically clustered short links while still keeping a few longer “bridge” links that prevent the network from splitting into slow-to-reach pockets.
The convergence curve tracks the average propagation delay across all 3000 annealing iterations. You should see a fairly sharp initial drop, followed by a long, noisy plateau as the temperature cools — that noise is exactly the annealing process occasionally accepting worse solutions to avoid getting stuck.
The 3D delay map is the most intuitive result: each node’s height represents how long it takes for a block broadcast from the red source node to reach it, using the final optimized topology. Tall bars far from the source indicate the network’s weakest links — nodes an operator might want to add a direct low-latency peer to in a real deployment.
Takeaways
This example shows that block propagation delay isn’t just a function of network size — it’s fundamentally a graph design problem under a degree constraint. Even with the same number of connections per node, the choice of which peers to connect to can meaningfully change how fast a block reaches the entire network. In a live blockchain client, this kind of optimization could inform smarter peer-selection heuristics instead of relying purely on random or purely-nearest-neighbor peer discovery.
