Name
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/TNET.2007.892877 | IEEE/ACM Transactions on Networking (TON) |
Keywords | Field | DocType |
computational complexity,graph theory,information dissemination,cost-effective improvement,network information dissemination,node-degree distributions,probabilistic heuristics,random-graph framework,structural knowledge,time complexity,Heuristic flooding,probabilistic flooding,random networks | Graph theory,Randomized algorithm,Heuristic,Computer science,Computer network,Theoretical computer science,Dissemination,Heuristics,Probabilistic logic,Time complexity,Computational complexity theory,Distributed computing | Journal |
Volume | Issue | ISSN |
15 | 2 | 1063-6692 |
Citations | PageRank | References |
19 | 0.95 | 19 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandre O. Stauffer | 1 | 130 | 11.34 |
| Valmir C. Barbosa | 2 | 350 | 56.76 |