×

An analytical model for multi-epidemic information dissemination. (English) Zbl 1219.68034

Summary: Contemporary distributed systems usually involve the spreading of information by means of ad-hoc dialogs between nodes (peers). This paradigm resembles the spreading of a virus in the biological perspective (epidemics). Such abstraction allows us to design and implement information dissemination schemes with increased efficiency. In addition, elementary information generated at a certain node can be further processed to obtain more specific, higher-level and more valuable information. Such information carries specific semantic value that can be further interpreted and exploited throughout the network. This is also reflected in the epidemical framework through the idea of virus transmutation which is a key component in our model. We establish an analytical framework for the study of a multi-epidemical information dissemination scheme in which diverse ‘transmuted epidemics’ are spread. We validate our analytical model through simulations. Key outcomes of this study include the assessment of the efficiency of the proposed scheme and the prediction of the characteristics of the spreading process (multi-epidemical prevalence and decay).

MSC:

68M14 Distributed systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akdere, M.; Cagatay, C.; Gerdaneri, O.; Korpeoglu, I.; Ulusoy, O.; Cetintemel, U.: A comparison of epidemic algorithms in wireless sensor networks, Elsevier computer communications journal 29, No. 13, 2450-2557 (2006)
[2] Albert, R.; Barabási, A-L.: Statistical mechanics of complex networks, Reviews of modern physics 74, No. 1, 47-94 (2002) · Zbl 1205.82086
[3] Anagnostopoulos, C.; Hadjiefthymiades, S.: On the application of epidemical spreading in collaborative context–aware computing, ACM SIGMOBILE mobile computing and communications review 12, No. 4, 43-55 (2009)
[4] Anagnostopoulos, C.; Hadjiefthymiades, S.; Ntarladimas, Y.; Zervas, E.: On the use of epidemical information spreading in mobile computing environments, Mediterranean journal of computers and networks 4, No. 3, 91-98 (2008)
[5] M. Boguna, R. Pastor-Satorras, A. Vespignani, Epidemic spreading in complex networks with degree correlations, in: Sitges Conf. on Statistical Mechanics of Complex Networks, 2003, pp. 127–147. · Zbl 1132.92338
[6] Boyd, S.; Ghosh, A.; Prabhakar, B.; Shah, D.: Randomized gossip algorithms, IEEE transactions on information theory and IEEE/ACM transactions on networking 52, No. 6, 2508-2530 (2006) · Zbl 1283.94005
[7] Comellas, F.; Sampels, M.: Deterministic small-world networks, Physica A 309, No. 1–2, 231-235 (2002) · Zbl 0995.60103
[8] A. Datta, S. Quarteroni, K. Aberer, Autonomous gossiping: a self-organizing epidemic algorithm for selective information dissemination in wireless mobile ad-hoc networks, in: IFIP Int. Conf. on Semantics of a Networked World, 2004, pp. 126–143.
[9] U. Feige, D. Peleg, P. Raghavan, E. Upfal, Randomized broadcast in networks, in: Proc. of the International Symposium on Algorithms, NY, 1990, pp. 128–137. · Zbl 0712.68011
[10] Kempe, D.; Kleinberg, J.; Demers, A.: Spatial gossip and resource location protocols, Journal of the ACM 51, No. 6, 943-967 (2004) · Zbl 1125.68326
[11] J. Kephart, S. White, Directed-graph epidemiological models of computer viruses, in: IEEE Int. Symp. on Research in Security and Privacy, 1991, pp. 343–359.
[12] Kermarrec, A.; Ganesh, A.; Massoulie, L.: Probabilistic reliable dissemination in large-scale systems, IEEE transactions on parallel and distributed systems 14, No. 3, 248-258 (2003)
[13] A. Khelil, C. Becker, J. Tian, K. Rothermel, An epidemic model for information diffusion in MANETs, in: ACM Workshop on Modelling Analysis and Simulation of Wireless and Mobile Systems, 2002, pp. 54–60.
[14] Küpper, A.: Location–based services: fundamentals and operation, (2005)
[15] Leibnitz, K.; Hossfeld, T.; Wakamiya, N.; Murata, M.: Modeling of epidemic diffusion in peer-to-peer file-sharing networks, Lncs 3853, 322-329 (2006)
[16] Mantyjarvi, J.; Huuskonen, P.; Himberg, J.: Collaborative context determination to support mobile terminal applications, IEEE wireless communications magazine 9, No. 5, 39-45 (2002)
[17] Newman, M.: The structure and function of complex networks, Society of industrial and applied mathematics review journal 45, No. 2, 167-256 (2003) · Zbl 1029.68010
[18] V. Papataxiarhis, V. Riga, V. Nomikos, O. Sekkas, K. Kolomvatsos, V. Tsetsos, P. Papageorgas, S. Vourakis, S. Hadjiefthymiades, G. Kouroupetroglou, MNISIKLIS: Indoor location based services for all, in: Proc. of the 5th International Symposium on LBS & TeleCartography, Salzburg, Austria, November 2008.
[19] A. Salkham, R. Cunningham, A. Cahill, A taxonomy of collaborative context-aware systems, in: Ubiquitous Mobile Information and Collaboration Systems Workshop, 2006, pp. 899–911.
[20] P. Tennert, M. Hall, B. Brown, M. Chalmers, S. Sherwood, Three applications for mobile epidemic algorithms, in: ACM Int. Conf. on Human Computer Interaction with Mobile Devices and Services, 2005, pp. 223–226.
[21] V. Tsetsos, S. Hadjiefthymiades, An innovative architecture for context foraging, in: Proc. of Intl. ACM Workshop on Data Engineering for Wireless and Mobile Access (MobiDE, in conjunction with SIGMOD/PODS 2009), Providence, RI, 2009.
[22] Y. Wang, D. Chakrabarti, C. Wang, C. Faloutsos, Epidemic spreading in real networks: an eigenvalue viewpoint, in: Int. Symposium of Reliable and Distributed Systems, 2003, pp. 25–34.
[23] Watts, D.; Strogatz, D.: Collective dynamics of small-world networks, Nature 393, No. 6684, 440-442 (1998) · Zbl 1368.05139
[24] L. Xiao, S. Boyd, S. Lall, A space–time diffusion scheme for peer-to-peer least-squares estimation, in: Proc. of the Fifth International Symposium on Information Processing in Sensor Networks, 2006, pp. 168–176.
[25] Zesheng, C.; Chuanyi, J.: Spatial–temporal modelling of malware propagation in networks, IEEE transactions on neural networks 16, No. 5, 1291-1303 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.