Impact of Network Topology on the Distribution of Broadcast Times: A Mathematical Analysis
摘要
In Web3 and other decentralized systems, a large and indeterminate number of independently operated nodes autonomously configure a peer-to-peer network, where blocks and transactions are frequently broadcast to achieve consensus over a distributed ledger. The latency of these broadcast operations is potentially influenced by the underlying network topology formed among the participating nodes. In this paper, we present a mathematical analysis to investigate how network structure affects the statistical distribution of broadcast time. We demonstrate that, in a special case, when the validator network forms a path graph, the broadcast time follows an Erlang (or Gamma) distribution, whereas prior studies found it better characterized by a Gumbel distribution. Additionally, we find that in a star topology, the mean and standard deviation of the Gumbel distribution depend on the parallel processing capacity of the hub node. Our findings provide theoretical evidence that network topology can considerably influence the distribution of broadcast latency. These results offer important insights for the design and optimization of peer-to-peer networks aimed at building scalable Web3 systems.