TY - JOUR
T1 - Probabilistic heuristics for disseminating information in networks
AU - Stauffer, A O
AU - Barbosa, Valmir C.
PY - 2007/4/1
Y1 - 2007/4/1
N2 - 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
AB - 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
UR - http://dx.doi.org/10.1109/TNET.2007.892877
U2 - 10.1109/TNET.2007.892877
DO - 10.1109/TNET.2007.892877
M3 - Article
SN - 1063-6692
VL - 15
SP - 425
EP - 435
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 2
ER -