Alexandre O. Stauffer
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.
- {1} A. Segall, "Distributed network protocols," IEEE Trans. Inf. Theory, vol. IT-29, no. 1, pp. 23-35, Jan. 1983.Google Scholar
- {2} V. C. Barbosa, An Introduction to Distributed Algorithms. Cambridge, MA: MIT Press, 1996. Google Scholar
- {3} F. Banaei-Kashani and C. Shahabi, "Criticality-based analysis and design of unstructured peer-to-peer networks as "complex systems"," in Proc. IEEE CCGRID, 2003, pp. 351-358. Google Scholar
- {4} I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan, "Chord: A scalable peer-to-peer lookup protocol for internet applications," IEEE/ACM Trans. Netw., vol. 11, no. 1, pp. 17-32, Feb. 2003. Google Scholar
- {5} B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz, "Tapestry: A resilient global-scale overlay for service deployment," IEEE J. Sel. Areas Commun., vol. 22, no. 1, pp. 41-53, Jan. 2004. Google Scholar
- {6} W. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, "Search and replication in unstructured peer-to-peer networks," in Proc. ACM ICS, 2002, pp. 84-95. Google Scholar
- {7} L. A. Adamic, R. M. Lukose, and B. A. Huberman, "Local search in unstructured networks," in Handbook of Graphs and Networks, S. Bornholdt and H. G. Schuster, Eds. Weinheim, Germany: Wiley-VCH, 2003, pp. 295-317.Google Scholar
- {8} M. E. J. Newman, S. H. Strogatz, and D. J. Watts, "Random graphs with arbitrary degree distributions and their applications," Phys. Rev. E, vol. 64, 2001, paper no. 026118.Google Scholar
- {9} R. Albert and A.-L. Barabási, "Statistical mechanics of complex networks," Rev. Modern Phys., vol. 74, pp. 47-97, 2002.Google Scholar
- {10} P. Erdös and A. Rényi, "On random graphs," Publ. Math., vol. 6, pp. 290-297, 1959.Google Scholar
- {11} M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the Internet topology," in Proc. ACM SIGCOMM, 1999, pp. 251-262. Google Scholar
- {12} A. Medina, I. Matta, and J. Byers, "On the origin of power laws in Internet topologies," Comput. Commun. Rev., vol. 30, no. 2, pp. 18-28, 2000. Google Scholar
- {13} A. Lakhina, J. W. Byers, M. Crovella, and P. Xie, "Sampling biases in IP topology measurements," in Proc. IEEE INFOCOM, 2003, pp. 332-341.Google Scholar
- {14} D. Achlioptas, A. Clauset, D. Kempe, and C. Moore, "On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs," in Proc. ACM STOC, 2005, pp. 694-703. Google Scholar
- {15} M. Molloy and B. Reed, "A critical point for random graphs with a given degree sequence," Random Struct. Alg., vol. 6, pp. 161-180, 1995. Google Scholar
- {16} R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, "Resilience of the Internet to random breakdowns," Phys. Rev. Lett., vol. 85, pp. 4626-4628, 2000.Google Scholar
- {17} S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin, "Giant strongly connected component of directed networks," Phys. Rev. E, vol. 64, 2001, paper no. 025101.Google Scholar
- {18} R. M. Karp, "The transitive closure of a random digraph," Random Struct. Alg., vol. 1, pp. 73-93, 1990.Google Scholar
- {19} B. Bollobás, Random Graphs, 2nd ed. Cambridge, U.K.: Cambridge Univ. Press, 2001.Google Scholar
- {20} S. Y. Yan, Number Theory for Computing, 2nd ed. Berlin, Germany: Springer-Verlag, 2002. Google Scholar
- {21} W. Aiello, F. Chung, and L. Lu, "A random graph model for power law graphs," Exp. Math., vol. 10, pp. 53-66, 2001.Google Scholar
- {22} C. Gkantsidis, M. Mihail, and E. Zegura, "The Markov chain simulation method for generating connected power law random graphs," presented at the ALENEX Conf., 2003.Google Scholar
- {23} Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu, "The broadcast storm problem in a mobile ad hoc network," Wireless Netw., vol. 8, pp. 153-167, 2002. Google Scholar
- {24} C. Avin and C. Brito, "Efficient and robust query processing in dynamic environments using random walk techniques," in Proc. IPSN, 2004, pp. 277-286. Google Scholar
- {25} M. Sheng, J. Li, and Y. Shi, "Relative degree adaptive flooding broadcast algorithm for ad hoc networks," IEEE Trans. Broadcast., vol. 51, no. 2, pp. 216-222, Jun. 2005.Google Scholar
Index Terms
- Probabilistic heuristics for disseminating information in networks
Recommendations
Probabilistic flooding for efficient information dissemination in random graph topologies
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 ...
Analysis of probabilistic flooding: how do we choose the right coin?
ICC'09: Proceedings of the 2009 IEEE international conference on CommunicationsThis 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 ...
Probabilistic flooding in stochastic networks: Analysis of global information outreach
This article investigates probabilistic information dissemination in stochastic networks. The following problem is studied: A source node intends to deliver a message to all other network nodes using probabilistic flooding, i.e., each node forwards a ...
Comments