Probabilistic heuristics for disseminating information in networks
<|reference_start|>Probabilistic heuristics for disseminating information in networks: 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.<|reference_end|>
@article{stauffer2004probabilistic,
    title={Probabilistic heuristics for disseminating information in networks},
    author={A. O. Stauffer, V. C. Barbosa},
    journal={IEEE/ACM Transactions on Networking 15 (2007), 425-435},
    year={2004},
    doi={10.1109/TNET.2007.892877},
    number={ES-660/04},
    archivePrefix={arXiv},
    eprint={cs/0409001},
    primaryClass={cs.NI cs.DC}
}