Probabilistic heuristics for disseminating information in networks

A O Stauffer, Valmir C. Barbosa

Research output: Contribution to journalArticle

26 Citations (Scopus)
71 Downloads (Pure)

Abstract

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
Original languageEnglish
Pages (from-to)425-435
JournalIEEE/ACM Transactions on Networking
Volume15
Issue number2
DOIs
Publication statusPublished - 1 Apr 2007

Fingerprint

Costs

Cite this

Probabilistic heuristics for disseminating information in networks. / Stauffer, A O; Barbosa, Valmir C.

In: IEEE/ACM Transactions on Networking, Vol. 15, No. 2, 01.04.2007, p. 425-435.

Research output: Contribution to journalArticle

@article{635dd796e86f4733996617c5b5eeb770,
title = "Probabilistic heuristics for disseminating information in networks",
abstract = "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",
author = "Stauffer, {A O} and Barbosa, {Valmir C.}",
year = "2007",
month = "4",
day = "1",
doi = "10.1109/TNET.2007.892877",
language = "English",
volume = "15",
pages = "425--435",
journal = "IEEE/ACM Transactions on Networking",
issn = "1063-6692",
publisher = "IEEE",
number = "2",

}

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

VL - 15

SP - 425

EP - 435

JO - IEEE/ACM Transactions on Networking

JF - IEEE/ACM Transactions on Networking

SN - 1063-6692

IS - 2

ER -