A Markov-Chain-Based Model for Group Message Distribution in Connected Networks

The authors introduce a stochastic Markov-chain-based model for the recursive distribution of a message from the source node to all remaining nodes. This recursive message distribution process produces a spanning tree topology over the connected network of nodes. The model has five input parameters: (1) the number of nodes n in the group, (2) the maximum number of child nodes, (3) the number of sub-message components needed to transfer a single message, (4) the probability p1 that two adjacent nodes in a network initiate a connection (edge) in the spanning tree, and (5) the probability p2 that each sub-message component is transferred correctly between nodes. The authors derive a closed-form expression for the expected group message distribution time, measured in discrete-time epochs, that is verified via Monte Carlo simulations. Since both the closed-form formulas and the Monte Carlo simulations are computationally intensive for networks with a large number of nodes n, this paper derives a reliable approximate formula for the expected distribution time for networks as large as n = 1000.