  We study the problem of disseminating a piece of information through all the
nodes of a network, given that it is known originally only to a single node. In
the absence of any structural knowledge on the network other than the nodes'
neighborhoods, this problem is traditionally solved by flooding all the
network's edges. We analyze a recently introduced probabilistic algorithm for
flooding and give an alternative probabilistic heuristic that can lead to some
cost-effective improvements, like better trade-offs between the message and
time complexities involved. We analyze the two algorithms both mathematically
and by means of simulations, always within a random-graph framework and
considering relevant node-degree distributions.
