research-article

Infrastructureless Spatial Storage Algorithms

Authors:

Jose Luis Fernandez-Marquez,

Giovanna Di Marzo Serugendo,

Josep Lluis ArcosAuthors Info & Claims

ACM Transactions on Autonomous and Adaptive Systems (TAAS), Volume 6, Issue 2

Article No.: 15, Pages 1 - 26

https://doi.org/10.1145/1968513.1968518

Published: 01 June 2011 Publication History

Abstract

This article defines and analyzes a collection of algorithms for persistent storage of data at specific geographical zones exploiting the memory of mobile devices located in these areas. Contrarily to other approaches for data dissemination, our approach uses a viral programming model. Data performs an active role in the storage process. It acts as a virus or a mobile agent, finding its own storage and relocating when necessary. We consider geographical areas of any shape and size. Simulation results show that our algorithms are scalable and converge quickly, even though none of them outperform the others for all performance metrics considered.

Supplementary Material

PDF File (a15-fernandez-marquez_appendix.pdf)

The proof is given in an electronic appendix, available online in the ACM Digital Library.

Download
3.51 MB

References

[1]

Abelson, H., Beal, J., and Sussman, G. J. 2007. Amorphous computing. Tech. rep. MIT-CSAIL-TR-2007-030, Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA.

[2]

Beal, J. 2003. Persistent nodes for reliable memory in geographically local networks. Tech. rep. AI Memo 2003-011, Artificial Intelligence Laboratory, MIT, Cambridge, MA.

[3]

Borcea, C., Intanagonwiwat, C., Kang, P., Kremer, U., and Iftode, L. 2004. Spatial programming using smart messages: Design and implementation. In Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS’04).

Digital Library

[4]

Butera, W. 2007. Text display and graphics control on a paintable computer. In Proceedings of the 1st International Conference on Self-Adaptive and Self-Organizing Systems (SASO’07). IEEE, Los Alamitos, CA, 45--54.

Digital Library

[5]

Cheng, J., Cheng, W., and Nagpal, R. 2005. Robust and self-repairing formation control for swarms of mobile agents. In Proceedings of the 20th National Conference on Artificial Intelligence. AAAI Press, Menlo Park, CA, 59--64.

Digital Library

[6]

Corbet, D. J. and Cutting, D. 2006. Ad loc: Location-based infrastructure-free annotation. In Proceedings of the 3rd International Conference on Mobile Computing and Ubiquitous Networking (ICMU’06).

[7]

Courts, L., Killijian, M.-O., Powell, D., and Roy, M. 2005. Sauvegarde cooprative entre pairs pour dispositifs mobiles. In Proceedings of the 2nd French-Speaking Conference on Mobility and Ubiquity Computing (UbiMob’05). ACM, New York, 97--104.

Digital Library

[8]

Datta, A., Quarteroni, S., and Aberer, K. 2004. Autonomous gossiping: A self-organizing epidemic algorithm for selective information dissemination in mobile ad-hoc networks. In Proceedings of the International Conference on Semantics of a Networked World (IC-SNW’04). Lecture Notes in Computer Science, vol. 3226, Springer, Berlin, 126--143.

[9]

Di Marzo Serugendo, G., Villalba Castro, A., and Konstantas, D. 2007. Dependable requirements for hovering information. In Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN’07). Supplemental vol., 36--39.

[10]

Dolev, S., Gilbert, S., Lynch, N. A., Shvartsman, A. A., and Welch, J. 2003. Geoquorums: Implementing atomic memory in mobile ad hoc networks. In Distributed Computing, Lecture Notes in Computer Science, vol. 2848, Springer, Berlin, 306--320.

[11]

Dolev, S., Gilbert, S., Lynch, N. A., Schiller, E., Shvartsman, A. A., and Welch, J. L. 2004. Virtual mobile nodes for mobile ad hoc networks. In Distributed Computing. Lecture Notes in Computer Science, vol. 3274, Springer, Berlin, 230--244.

[12]

Dolev, S., Gilbert, S., Lahiani, L., Lynch, N. A., and Nolte, T. 2005a. Timed virtual stationary automata for mobile networks. In Principles of Distributed Systems (OPODIS). Lecture Notes in Computer Science, vol. 3974, Springer, Berlin, 130--145.

Digital Library

[13]

Dolev, S., Gilbert, S., Schiller, E., Shvartsman, A. A., and Welch, J. 2005b. Autonomous virtual mobile nodes. In Proceedings of the Joint Workshop on Foundations of Mobile Computing (DIALM-POMC’05). ACM, New York, 62--69.

Digital Library

[14]

Eugster, P., Felber, P., Guerraoui, R., and Kermarrec, A.-M. 2003. The many faces of publish/subscribe. ACM Comput. Surv. 35, 2, 114--131.

Digital Library

[15]

Eugster, P., Garbinato, G., and Holzer, A. 2005. Location-based publish/subscribe. In Proceedings of the 4th IEEE Symposium on Network Computing and Applications. IEEE, Los Alamitos, CA.

Digital Library

[16]

Eugster, P., Garbinato, G., Holzer, A., and Luo, J. 2009. Effective location-based publish/subscribe in manets. In Proceedings of the IEEE International Conference on Pervasive Computing and Communications (PerCom’09). IEEE, Los Alamitos, CA.

[17]

Fekete, S. P., Schmidt, C., Wegener, A., and Fischer, S. 2006. Hovering data clouds for recognizing traffic jams. In Proceedings of the 2nd International Symposium on Leveraging Applications of Formal Methods, Verification and Validation (IEEE-ISOLA). IEEE, Los Alamitos, CA, 213--218.

Digital Library

[18]

Fernandez-Marquez, J. L. and Arcos, J. L. 2009. Keeping diversity when exploring dynamic environments. In Proceedings of the 24th Annual ACM Symposium on Applied Computing. D. Shin Ed., ACM, New York, 1192--1196.

Digital Library

[19]

Fernandez-Marquez, J. L., Arcos, J. L., and Di Marzo Serugendo, G. 2010. In Proceedings of the ACM Symposium on Applied Computing (SAC’10). ACM, New York.

Digital Library

[20]

Fernandez-Marquez, J. L., Di Marzo Serugendo, G., and Arcos, J. L. 2010. Infrastructureless spatial storage algorithms. Tech. rep. BBKCS-10-05, School of Computer Science and Information Systems, Birkbeck, University of London.

[21]

Killijian, M.-O., Powell, D., Bantre, M., Couderc, P., and Roudier, Y. 2004. Collaborative backup for dependable mobile applications. In Proceedings of the 2nd Workshop on Middleware for Pervasive and Ad-Hoc Computing (MPAC’04). ACM, New York, 146--149.

Digital Library

[22]

Leontiadis, I. and Mascolo, C. 2007a. Geopps: Opportunistic geographical routing for vehicular networks. In Proceedings of the IEEE Workshop on Autonomic and Oportunistic Communications (Colocated with WOWMOM’07). IEEE, Los Alamitos, CA.

[23]

Leontiadis, I. and Mascolo, C. 2007b. Opportunistic spatio-temporal dissemination system for vehicular networks. In Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking (MobiOpp’07). ACM, New York, 39--46.

Digital Library

[24]

Leontiadis, I., Costa, P., and Mascolo, C. 2009. Persistent content-based information dissemination in hybrid vehicular networks. In Proceedings of the IEEE International Conference on Pervasive Computing and Communications (PerCom’09). IEEE, Los Alamitos, CA.

Digital Library

[25]

Maihfer, C. 2004. A survey of geocast routing protocols. In IEEE Communications Surveys and Tutorials, Vol. 6, 32--42.

Digital Library

[26]

Mamei, M. and Zambonelli, F. 2001. Programming pervasive and mobile computing applications: The TOTA approach. ACM Trans. Softw. Eng. Method. 2, 3.

Digital Library

[27]

Mamei, M. and Zambonelli, F. 2005. Programming stigmergic coordination with the tota middleware. In Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS’05). ACM, New York, 415--422.

Digital Library

[28]

Motani, M., Srinivasan, V., and Nuggehalli, P. S. 2005. Peoplenet: Engineering a wireless virtual social network. In Proceedings of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom’05). ACM, New York, 243--257.

Digital Library

[29]

Roth, J. 2003. The critical mass problem of mobile ad-hoc networks. In Proceedings of the IADIS International Conference e-Society. IADIS Press, 243--250.

[30]

Scellato, S., Mascolo, C., Musolesi, M., and Latora, V. 2007. Epcast: Controlled dissemination in human-based wireless networks by means of epidemic spreading models. CoRR abs/0711.2780.

[31]

Villalba Castro, A., Di Marzo Serugendo, G., and Konstantas, D. 2008. Hovering information--self-organising information that finds its own storage. In Proceedings of the International IEEE Conference on Sensor Networks, Ubiquitous and Trustworthy Computing (SUTC’08). IEEE, Los Alamitos, CA, 193--200.

Digital Library

[32]

Villalba Castro, A., Di Marzo Serugendo, G., and Konstantas, D. 2009. Hovering information--self-organising information that finds its own storage. In Autonomic Communications. Springer, Berlin.

[33]

Wegener, A., Schiller, E.M., Hellbrck, H., Fekete, S.P., and Fischer, S. 2006. Hovering data clouds: A decentralized and self-organizing information system. In Proceedings of the International Workshop on Self-Organizing Systems. Lecture Notes in Computer Science, vol. 4124, Springer, Berlin, 243--247.

Digital Library

Cited By

Bellman KBotev JDiaconescu AEsterle LGruhl CLandauer CLewis PNelson PPournaras EStein ATomforde S(2020)Self-improving system integration: Mastering continuous changeFuture Generation Computer Systems10.1016/j.future.2020.11.019Online publication date: Nov-2020
https://doi.org/10.1016/j.future.2020.11.019
Fernandez-Marquez JMarzo Serugendo GMontagna SViroli MArcos J(2018)Description and composition of bio-inspired design patternsNatural Computing: an international journal10.1007/s11047-012-9324-y12:1(43-67)Online publication date: 19-Dec-2018
https://dl.acm.org/doi/10.1007/s11047-012-9324-y
Mariani SMariani S(2016)Coordination of Self-organising SystemsCoordination of Complex Sociotechnical Systems10.1007/978-3-319-47109-9_3(25-75)Online publication date: 24-Nov-2016
https://doi.org/10.1007/978-3-319-47109-9_3
Show More Cited By

Index Terms

Infrastructureless Spatial Storage Algorithms

Recommendations

Infrastructureless storage in dynamic environments
SAC '10: Proceedings of the 2010 ACM Symposium on Applied Computing

This paper studies the use of highly dynamic networks as infrastructures for persistent storage of data that offer services at specific geographical zones in a decentralized and distributed way. We propose a new algorithm, based on repulsion techniques, ...
An Efficient Data Dissemination Method over Wireless Ad-Hoc Networks

Recently, mobile data is increased sharply with the rapid development of mobile devices such as smart phone, tablet, and pocket computer. Due to mobile devices are becoming more ubiquitous and most of the mobile devices are equipped with short range ...
An efficient and robust data dissemination protocol for vehicular ad hoc networks
PE-WASUN '12: Proceedings of the 9th ACM symposium on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks

Vehicular Ad Hoc Networks (VANETs) have emerged as an exciting research and application area. The envisioned applications, as well as some inherent VANET characteristics such as highly dynamic topology, frequently disconnected network, and different and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Autonomous and Adaptive Systems

ACM Transactions on Autonomous and Adaptive Systems Volume 6, Issue 2

June 2011

106 pages

ISSN:1556-4665

EISSN:1556-4703

DOI:10.1145/1968513

Issue’s Table of Contents

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2011

Accepted: 01 June 2010

Revised: 01 April 2010

Received: 01 August 2009

Published in TAAS Volume 6, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

EVE
Agreement Technologies
Generalitat de Catalunya
IEA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
279
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bellman KBotev JDiaconescu AEsterle LGruhl CLandauer CLewis PNelson PPournaras EStein ATomforde S(2020)Self-improving system integration: Mastering continuous changeFuture Generation Computer Systems10.1016/j.future.2020.11.019Online publication date: Nov-2020
https://doi.org/10.1016/j.future.2020.11.019
Fernandez-Marquez JMarzo Serugendo GMontagna SViroli MArcos J(2018)Description and composition of bio-inspired design patternsNatural Computing: an international journal10.1007/s11047-012-9324-y12:1(43-67)Online publication date: 19-Dec-2018
https://dl.acm.org/doi/10.1007/s11047-012-9324-y
Mariani SMariani S(2016)Coordination of Self-organising SystemsCoordination of Complex Sociotechnical Systems10.1007/978-3-319-47109-9_3(25-75)Online publication date: 24-Nov-2016
https://doi.org/10.1007/978-3-319-47109-9_3
Mariani S(2014)On the "Local-to-Global" Issue in Self-OrganisationProceedings of the 2014 IEEE Eighth International Conference on Self-Adaptive and Self-Organizing Systems Workshops10.1109/SASOW.2014.14(61-67)Online publication date: 8-Sep-2014
https://dl.acm.org/doi/10.1109/SASOW.2014.14
Fernandez-Marquez JArcos JDi Marzo Serugendo GCasadei M(2011)Description and Composition of Bio-inspired Design PatternsProceedings of the 2011 Eighth IEEE International Conference and Workshops on Engineering of Autonomic and Autonomous Systems10.1109/EASe.2011.15(87-96)Online publication date: 27-Apr-2011
https://dl.acm.org/doi/10.1109/EASe.2011.15

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents