TY - JOUR
TI - Probabilistic flooding for efficient information dissemination in random graph topologies
AU - Oikonomou, K.
AU - Kogias, D.
AU - Stavrakakis, I.
JO - Computer Networks
PY - 2010
VL - 54
TODO - 10
SP - 1615-1629
PB - 
SN - 1389-1286
TODO - 10.1016/j.comnet.2010.01.007
TODO - Analytical results;  Asymptotic expressions;  Asymptotic values;  Average numbers;  Complete networks;  Global networks;  Message overhead;  Parameterized;  Probabilistic flooding;  Random graph theory;  Random graph topology;  Random graphs;  Simulation result;  Unstructured peer-to-peer, Asymptotic analysis;  Distributed computer systems;  Graph theory;  Information dissemination, Peer to peer networks
TODO - Probabilistic flooding has been frequently considered as a suitable dissemination information approach for limiting the large message overhead associated with traditional (full) flooding approaches that are used to disseminate globally information in unstructured peer-to-peer and other networks. A key challenge in using probabilistic flooding is the determination of the forwarding probability so that global network outreach is achieved while keeping the message overhead as low as possible. In this paper, by showing that a probabilistic flooding network, generated by applying probabilistic flooding to a connected random graph network, can be (asymptotically) "bounded" by properly parameterized random graph networks and by invoking random graph theory results, asymptotic values of the forwarding probability are derived guaranteeing (probabilistically) successful coverage, while significantly reducing the message overhead with respect to traditional flooding. Asymptotic expressions with respect to the average number of messages and the average time required to complete network coverage are also derived, illustrating the benefits of the properly parameterized probabilistic flooding scheme. Simulation results support the claims and expectations of the analytical results and reveal certain aspects of probabilistic flooding not covered by the analysis. © 2009 Elsevier B.V. All rights reserved.
ER -