Crisostomo, Schilcher, Bettstetter and Barros investigate probabilistic information dissemination in stochastic networks. The following problem is studied: A source node intends to deliver a message to all other network nodes using probabilistic flooding, i.e., each node forwards a received message to all its neighbors with a forwarding probability ϖ. Question is: which minimum ϖ-value needs to be met by each node to ensure receipt of the flooded message by all nodes with high probability?
Their forthcoming article in the journal Computer Networks presents a generic approach to this problem in arbitrary networks and then focuses on Erdős Rényi graphs (ERGs) and random geometric graphs (RGGs). An exact solution is given for ERGs. An asymptotic expression is given for RGGs, which is shown to be an approximation for networks with high node density. In both cases, unreliable links are taken into account.