Ozalp Babaoglu
Geoffrey Canright
Alberto Montresor
Skip Abstract Section
Abstract
Recent developments in information technology have brought about important changes in distributed computing. New environments such as massively large-scale, wide-area computer networks and mobile ad hoc networks have emerged. Common characteristics of these environments include extreme dynamicity, unreliability, and large scale. Traditional approaches to designing distributed applications in these environments based on central control, small scale, or strong reliability assumptions are not suitable for exploiting their enormous potential. Based on the observation that living organisms can effectively organize large numbers of unreliable and dynamically-changing components (cells, molecules, individuals, etc.) into robust and adaptive structures, it has long been a research challenge to characterize the key ideas and mechanisms that make biological systems work and to apply them to distributed systems engineering. In this article we propose a conceptual framework that captures several basic biological processes in the form of a family of design patterns. Examples include plain diffusion, replication, chemotaxis, and stigmergy. We show through examples how to implement important functions for distributed computing based on these patterns. Using a common evaluation methodology, we show that our bio-inspired solutions have performance comparable to traditional, state-of-the-art solutions while they inherit desirable properties of biological systems including adaptivity and robustness.
- Abelson, H., Allen, D., Coore, D., Hanson, C., Homsy, G., Thomas F. Knight, J., Nagpal, R., Rauch, E., Sussman, G. J., and Weiss, R. 2000. Amorphous computing. Comm. ACM 43, 5 (May). Google Scholar
- Adamatzky, A., De Lacy Costello, B., and Asai, T. 2005. Reaction-Diffusion Computers. Elsevier. Google Scholar
- Albert, R. and Barabási, A.-L. 2002. Statistical mechanics of complex networks. Rev. Modern Physics 74, 1 (Jan.), 47--97.Google Scholar
- Alexander, C. 1977. A Pattern Language: Towns, Buildings, Construction. Center for Environmental Structure Series. Oxford University Press.Google Scholar
- Arbib, M. A., Érdi, P., and Szentágothai, J. 1997. Neural Organization: Structure, Function and Dynamics. MIT Press., Cambridge MA.Google Scholar
- Bailey, N. T. J. 1975. The Mathematical Theory of Infectious Diseases and Its Applications, 2nd ed. Griffin, London, UK.Google Scholar
- Baras, J. S. and Mehta, H. 2003. A probabilistic emergent routing algorithm for mobile ad hoc networks. In Proceedings of Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'03).Google Scholar
- Bertsekas, D. and Gallager, R. 1992. Data Networks. Prentice--Hall, Englewood Cliffs, NJ. Google Scholar
- Bettstetter, C., Resta, G., and Santi, P. 2003. The node distribution of the random waypoint mobility model for wireless ad hoc networks. IEEE Trans. Mobile Comput. 2, 3, 257--269. Google Scholar
- Boillat, J. 1990. Load balancing and poisson equation on a graph. Concurrency: Pract. Exper. 2, 280--313. Google Scholar
- Camazine, S., Deneubourg, J.-L., Franks, N. R., Sneyd, J., Theraulaz, G., and Bonabeau, E. 2001. Self-Organization in Biological Systems. Princeton University Pres, Princeton, NJ. Google Scholar
- Canright, G., Deutsch, A., and Urnes, T. 2005. Chemotaxis-inspired load balancing. In Proceedings of the European Conference on Complex Systems (ECCS'05).Google Scholar
- Chawathe, Y., Ratnasamy, S., Breslau, L., Lanham, N., and Shenker, S. 2003. Making gnutella-like p2p systems scalable. In Proceedings of ACM SIGCOMM. ACM Press, 407--418. Google Scholar
- Clausen, T., Jacquet, P., Laouiti, A., Muhlethaler, P., Qayyum, A., and Viennot, L. 2001. Optimized link state routing protocol. In Proceedings of IEEE INMIC.Google Scholar
- Cybenko, G. 1989. Dynamic load balancing for distributed memory multiprocessors. J. Parall. Distribut. Comput. 7, 279--301. Google Scholar
- de Castro, L. N. and Timmis, J. 2002. Artificial Immune Systems. Springer Verlag, Berlin, Germany.Google Scholar
- Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., and Terry, D. 1987. Epidemic algorithms for replicated database maintenance. In Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing (PODC'87). Vancouver, British Columbia, Canada. ACM Press, 1--12. Google Scholar
- Deutsch, A., Ganguly, N., Canright, G., Jelasity, M., and Engø-Monsen, K. 2003. Models for advanced services in AHN, P2P networks. www.cs.unibo.it/bison/deliverables/D08.pdf.Google Scholar
- Di Caro, G. A. 2003. Analysis of simulation environments for mobile ad hoc networks. Tech. Rep. 24-03 (Dec). IDSIA, Lugano, Switzerland.Google Scholar
- Di Caro, G. A. 2004. Ant colony optimization and its application to adaptive routing in telecommunication networks. Ph.D. thesis, Faculté des Sciences Appliquées, Université Libre de Bruxelles, Brussels, Belgium.Google Scholar
- Di Caro, G. A. and Dorigo, M. 1998. AntNet: Distributed stigmergetic control for communications networks. J. Artificial Intelli. Res. 9, 317--365. Google Scholar
- Di Caro, G. A., Ducatelle, F., and Gambardella, L. M. 2004. AntHocNet: An ant-based hybrid routing algorithm for mobile ad hoc networks. In Proceedings of Parallel Problem Solving from Nature (PPSN) VIII. Lecture Notes in Computer Science, vol. 3242. Springer-Verlag, 461--470.Google Scholar
- Di Caro, G. A., Ducatelle, F., and Gambardella, L. M. 2005a. AntHocNet: An adaptive nature-inspired algorithm for routing in mobile ad hoc networks. European Trans. Telecomm. (Special Issue on Self-Organization in Mobile Networking) 16, 5 (Sept.-Oct.), 443--455.Google Scholar
- Di Caro, G. A., Ducatelle, F., and Gambardella, L. M. 2005b. Swarm intelligence for routing in mobile ad hoc networks. In Proceedings of the IEEE Swarm Intelligence Symposium.Google Scholar
- Di Caro, G. A., Ducatelle, F., and Gambardella, L. M. 2006. Studies of routing performance in a city-like testbed for mobile ad hoc networks. Tech. rep. 07-06 (March). IDSIA, Lugano, Switzerland.Google Scholar
- Di Marzo Serugendo, G., Karageorgos, A., Rana, O. F., and Zambonelli, F., Eds. 2004. Engineering self-organising systems. Lecture Notes in Artificial Intelligence, vol. 2977. Springer, Verlag, Berlin, Germany. Google Scholar
- Dorigo, M., Di Caro, G. A., and Gambardella, L. M. 1999. Ant algorithms for discrete optimization. Artificial Life 5, 2, 137--172. Google Scholar
- Dorigo, M. and Stützle, T. 2004. Ant Colony Optimization. MIT Press, Cambridge, MA. Google Scholar
- Ducatelle, F., Di Caro, G. A., and Gambardella, L. M. 2005b. Ant agents for hybrid multipath routing in mobile ad hoc networks. In Proceedings of the 2nd Annual Conference on Wireless on demand Network Systems and Services (WONS). St. Moritz, Switzerland. Google Scholar
- Ducatelle, F., Di Caro, G. A., and Gambardella, L. M. 2005a. Using ant agents to combine reactive and proactive strategies for routing in mobile ad hoc networks. Int. J. Computat. Intell. Appl. (Special Issue on Nature-Inspired Approaches to Networks and Telecommunications) 5, 2 (June), 169--184.Google Scholar
- Eiben, A. E. and Smith, J. E. 2003. Introduction to Evolutionary Computing. Springer Verlag, Berlin, Germany. Google Scholar
- Elsässer, R. and Monien, B. 2003. Diffusion load balancing in static and dynamic networks. In Proceedings of the International Workshop on Ambient Intelligence Computing. 49--62.Google Scholar
- Fewell, J. H. 2003. Social insect networks. Science 301, 26 (Sept.), 1867--1869.Google Scholar
- Gamma, E., Helm, R., Johnson, R., and Vlissides, J. 1995. Design Patterns. Addison-Wesley.Google Scholar
- Ganguly, N., Brusch, L., and Deutsch, A. 2005. Design and analysis of a bio-inspired search algorithm for peer to peer networks. In Self-Star Properties in Complex Information Systems. Lecture Notes in Computer Science, vol. 3460. Springer-Verlag, Berlin, Germany. Google Scholar
- Ganguly, N., Canright, G., and Deutsch, A. 2004a. Design of a robust search algorithm for p2p networks. In 11th International Conference on High Performance Computing. Google Scholar
- Ganguly, N., Canright, G., and Deutsch, A. 2004b. Design of an efficient search algorithm for p2p networks using concepts from natural immune systems. In 8th International Conference on Parallel Problem Solving from Nature.Google Scholar
- Ganguly, N. and Deutsch, A. 2004a. A cellular automata model for immune based search algorithm. In 6th International Conference on Cellular Automata for Research and Industry.Google Scholar
- Ganguly, N. and Deutsch, A. 2004b. Developing efficient search algorithms for p2p networks using proliferation and mutation. In 3rd International Conference on Artificial Immune Systems.Google Scholar
- Glazier, J. A. and Graner, F. 1993. Simulation of the differential adhesion driven rearrangement of biological cells. Phys. Rev. E 47, 3, 2128--2154.Google Scholar
- Günes, M., Kähmer, M., and Bouazizi, I. 2003. Ant-routing-algorithm (ARA) for mobile multi-hop ad-hoc networks---new features and results. In Proceedings of the 2nd Mediterranean Workshop on Ad-Hoc Networks (Med-Hoc-Net'03). Mahdia, Tunisia.Google Scholar
- H. Van Dyke Parunak, S. B. 2004. Stigmergic learning for self-organizing mobile ad-hoc networks. In Proceedings of AAMAS. Google Scholar
- Haas, Z. J. 1997. A new routing protocol for the reconfigurable wireless networks. In Proceedings of the IEEE International Conference on Universal Personal Communications.Google Scholar
- Haykin, S. 1998. Neural Networks: A Comprehensive Foundation, 2nd ed. Prentice Hall. Google Scholar
- Ilachinski, A. 2001. Cellular Automata: A Discrete Universe. World Scientific. Google Scholar
- Janeway, C. A., Travers, P., Walport, M., and Shlomchik, M. 2001. Immuno Biology: The Immune System in Health and Disease, 5th ed. Garland Publishing.Google Scholar
- Jelasity, M. and Babaoglu, O. 2005. T-Man: Gossip-based overlay topology management. In 3rd International Workshop on Engineering Self-Organising Applications (ESOA'05). Google Scholar
- Jelasity, M., Guerraoui, R., Kermarrec, A.-M., and van Steen, M. 2004. The peer sampling service: Experimental evaluation of unstructured gossip-based implementations. In Middleware 2004, H.-A. Jacobsen, Ed. Lecture Notes in Computer Science, vol. 3231, Springer-Verlag, Berlin, Germany, 79--98. Google Scholar
- Jelasity, M., Montresor, A., and Babaoglu, O. 2004. A modular paradigm for building self-organizing peer-to-peer applications. In Engineering Self-Organising Systems, G. Di Marzo Serugendo, A. Karageorgos, O. F. Rana, and F. Zambonelli, Eds. Lecture Notes in Artificial Intelligence, vol. 2977. Springer-Verlag, Berlin, Germany, 265--282.Google Scholar
- Jelasity, M., Montresor, A., and Babaoglu, O. 2005. Gossip-based aggregation in large dynamic networks. ACM Trans. Comput. Syst. 23, 3 (Aug.), 219--252. Google Scholar
- Johnson, D. and Maltz, D. 1996. Mobile Computing. Kluwer (Chapter Dynamic Source Routing in Ad Hoc Wireless Networks). 153--181.Google Scholar
- Keil, D. and Goldin, D. 2005. Adaptation and evolution in dynamic persistent environments. In Proceedings of the Workshop on the Foundations of Interactive Computation (FInCo'05). To appear in Electronic Notes in Theoretical Computer Science.Google Scholar
- Kempe, D., Dobra, A., and Gehrke, J. 2003. Gossip-based computation of aggregate information. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03). IEEE Computer Society, 482--491. Google Scholar
- Kephart, J. O. and Chess, D. M. 2003. The vision of autonomic computing. IEEE Comput. 36, 1 (Jan.), 41--50. Google Scholar
- Langton, C. G., Ed. 1997. Artificial Life: An Overview. MIT Press, Cambridge, MA. Google Scholar
- Lee, D. L., Chuang, H., and Seamons, K. 1997. Document ranking and the vector-space model. IEEE Softw. 14, 2, 67--75. Google Scholar
- Lodding, K. N. 2004. The hitchhiker's guide to biomorphic software. ACM Queue 2, 4, 66--75. Google Scholar
- Lv, Q., Cao, P., Cohen, E., and Shenker, S. 2002. Search and replication in unstructured peer-to-peer networks. In Proceedings of the 16th ACM International Conference on Supercomputing. Google Scholar
- Mankin, R., Arbogast, R., Kendra, P., and Weaver, D. 1999. Active spaces of pheromone traps for Plodia Interpunctella in enclosed environments. Environmen. Entomol. 28, 4, 557--565.Google Scholar
- Montemanni, R. and Gambardella, L. 2005a. Exact algorithms for the minimum power symmetric connectivity problem in wireless networks. Compute. Oper. Resea. 32, 11 (Nov.), 2891--2904. Google Scholar
- Montemanni, R. and Gambardella, L. 2005b. Power-aware distributed protocol for a connectivity problem in wireless sensor networks. In Self-Star Properties in Complex Information Systems. Lecture Notes in Computer Science, vol. 3460. Springer-Verlag, Berlin, Germany. Google Scholar
- Montemanni, R. and Gambardella, L. 2005c. Swarm approach for a connectivity problem in wireless networks. In Proceedings of the IEEE Swarm Intelligence Symphosium. 265--272.Google Scholar
- Montemanni, R., Gambardella, L., and Das, A. 2006. Models and algorithms for the MPSCP: An overview. In Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, J. Wu, Ed. Auerbach Publications, 133--146.Google Scholar
- Murray, J. D. 1990. Mathematical Biology. Springer-Verlag, Berlin, Germany.Google Scholar
- Ottino, J. M. 2004. Engineering complex systems. Nature 427, 399.Google Scholar
- Parunak, H. V. D., Brueckner, S. A., Sauter, J. A., and Matthews, R. 2005. Global convergence of local agent behaviors. In Proceedings of the 4th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'05). 305--312. Google Scholar
- PeerSim. http://peersim.sourceforge.net/.Google Scholar
- Perkins, C. and Royer, E. 1999. Ad-hoc on-demand distance vector routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications. Google Scholar
- Păun, G. 2002. Computing with Membranes: an Introduction. Springer, Verlag, Berlin, Germany.Google Scholar
- Păun, G., Rozenberg, G., and Salomaa, A. 2005. DNA Computing. Springer, Verlag, Berlin, Germany.Google Scholar
- Risson, J. and Moors, T. 2004. Survey of research towards robust peer-to-peer networks: Search methods. Tech. rep. UNSW-EE-P2P-1-1, (Sept.). University of New South Wales, Sydney, Australia.Google Scholar
- Royer, E. and Toh, C.-K. 1999. A review of current routing protocols for ad hoc mobile wireless networks. IEEE Person. Comm.Google Scholar
- Scalable Network Technologies, Inc. 2005. QualNet Simulator, Version 3.8. Scalable Network Technologies, Inc., Culver City, CA, USA. http://www.scalable-networks.com.Google Scholar
- Schmidt, D. C., Johnson, R. E., and Fayad, M. 1996. Guest editorial for the special issue on patterns and pattern languages. Comm. ACM 39, 10 (Oct.). Google Scholar
- Schoonderwoerd, R., Holland, O., Bruten, J., and Rothkrantz, L. 1996. Ant-based load balancing in telecommunications networks. Adaptive Behavior 5, 2, 169--207. Google Scholar
- Shen, C.-C., Jaikaeo, C., Srisathapornphat, C., Huang, Z., and Rajagopalan, S. 2004. Ad hoc networking with swarm intelligence. In Proceedings of 4th International Workshop on Ant Algorithms. Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany.Google Scholar
- Staab, S., Heylighen, F., Gershenson, C., Flake, G. W., Pennock, D. M., Fain, D. C., De Roure, D., Aberer, K., Shen, W.-M., Dousse, O., and Thiran, P. 2003. Neurons, viscose fluids, freshwater polyp hydra---and self-organizing information systems. IEEE Intelli. Syst. 18, 4, 72--86. Google Scholar
- Sutton, R. and Barto, A. 1998. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA. Google Scholar
- Theraulaz, G. and Bonabeau, E. 1999. A brief history of stigmergy. Artificial Life, Special Issue on Stigmergy 5, 97--116. Google Scholar
- van Renesse, R. 2003. The importance of aggregation. Future Directions in Distributed Computing, A. Schiper, A. A. Shvartsman, H. Weatherspoon, and B. Y. Zhao, Eds. Lecture Notes in Computer Science, vol. 2584. Springer-Verlag, Berlin, Germany, 87--92. Google Scholar
- van Renesse, R., Birman, K. P., and Vogels, W. 2003. Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining. ACM Trans. Comput. Sys. 21, 2 (May), 164--206. Google Scholar
- Yuste, S. B. and Acedo, L. 2000. Number of distinct sites visited by N random walkers on a Euclidean lattice. Physical Review E 61, 6327--34.Google Scholar
- Zipf, G. K. 1935. Psycho- Biology of Languages. Houghton-Mifflin, Boston, MA.Google Scholar
Index Terms
- Design patterns from biology for distributed computing
Recommendations
A Distributed Virtual Backbone Development Scheme for Ad-Hoc Wireless Networks
The virtual backbone is an approach for solving routing problems in ad-hoc wireless networks. The virtual backbone approach features low latency, moderate routing overhead and is a hybrid scheme that uses the table-driven and on-demand routing ...
Performance evaluation of routing protocols in vehicular ad-hoc networks
This paper presents a reactive location routing algorithm that uses cluster-based flooding for Vehicular Ad-hoc Networks (VANET). We compare both position-based and non-position-based routing strategies in typical urban and motorway traffic scenarios. A ...
Modeling the performance of flooding in wireless multi-hop Ad hoc networks
One feature common to most existing routing protocols for wireless mobile ad hoc networks, or MANETs, is the need to flood control messages network-wide during the route acquisition and maintenance process. Flooding of control messages may result in ...
Comments