Analysis of Probabilistic Flooding: How do we Choose the Right Coin?

• Type: Article in International Conference Proceedings Book
• Date: 2009

Authors

Sergio Crisostomo (Author) FCUP; Udo Schilcher (Author) Other; Christian Bettstetter (Author) Other; Joao Barros (Author) FEUP

Conference proceedings International

Title: 2009 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, VOLS 1-8

Pages: 2080-2085

IEEE International Conference on Communications (ICC 2009)

Dresden, GERMANY, JUN 14-18, 2009

Indexing

ISI Web of Knowledge - 1 Citation

ISI Web of Science

Scopus - 10 Citations

Scientific classification

FOS: Engineering and technology > Electrical engineering, Electronic engineering, Information engineering

Other information

Authenticus ID: P-003-SSC

DOI: 10.1109/icc.2009.5198745

Abstract (EN): This paper studies probabilistic information dissemination in random networks. Consider the following scenario: A node intends to deliver a message to all other nodes in the network ("flooding"). It first transmits the message to all its neighboring nodes. Each node forwards a received message with some network-wide probability p(f). A natural question arises: which forwarding probability p(f) should each node use such that a flooded message is obtained by all nodes with high probability? In other words, what is the minimum p(f) to achieve a high global outreach probability? We first present a generic approach to estimate the probability for achieving global outreach. This approach is then employed in Erdos Renyi random graphs, where we derive an upper and a lower bound for the global outreach probability for given random network and flooding parameters. The analysis is complemented with simulation results showing the tightness of both bounds. As a final result, we take a system design perspective to show a number of parameter vectors leading to global outreach.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 6