Probabilistic heuristics for disseminating information in networks

A O Stauffer, Valmir C. Barbosa

Research output: Contribution to journalArticle

27 Citations (Scopus)
126 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 Dive into the research topics of 'Probabilistic heuristics for disseminating information in networks'. Together they form a unique fingerprint.

  • Cite this