Analysis of Probabilistic Flooding: How Do We Choose the Right Coin?

This paper studies probabilistic information dissemination in random networks. Consider the following scenario: A node intends to deliver a message to all other nodes in the network ("flooding"). It first transmits the message to all its neighboring nodes. Each node forwards a received message with some network-wide probability p_f. A natural question arises: which forwarding probability p_f should each node use such that a flooded message is obtained by all nodes with high probability? In other words, what is the minimum p_f to achieve a high global outreach probability? We first present a generic approach to estimate the probability for achieving global outreach. This approach is then employed in Erdos Renyi random graphs, where we derive an upper and a lower bound for the global outreach probability for given random network and flooding parameters. The analysis is complemented with simulation results showing the tightness of both bounds. As a final result, we take a system design perspective to show a number of parameter vectors leading to global outreach.