Design patterns from biology for distributed computing

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Harold Abelson , Don Allen , Daniel Coore , Chris Hanson , George Homsy , Thomas F. Knight, Jr. , Radhika Nagpal , Erik Rauch , Gerald Jay Sussman , Ron Weiss, Amorphous computing, Communications of the ACM, v.43 n.5, p.74-82, May 2000 [doi>10.1145/332833.332842]
	2	Andrew Adamatzky , Benjamin De Lacy Costello , Tetsuya Asai, Reaction-Diffusion Computers, Elsevier Science Inc., New York, NY, 2005
	3	Albert, R. and Barabási, A.-L. 2002. Statistical mechanics of complex networks. Rev. Modern Physics 74, 1 (Jan.), 47--97.
	4	Alexander, C. 1977. A Pattern Language: Towns, Buildings, Construction. Center for Environmental Structure Series. Oxford University Press.
	5	Arbib, M. A., Érdi, P., and Szentágothai, J. 1997. Neural Organization: Structure, Function and Dynamics. MIT Press., Cambridge MA.
	6	Bailey, N. T. J. 1975. The Mathematical Theory of Infectious Diseases and Its Applications, 2nd ed. Griffin, London, UK.
	7	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).
	8	Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
	9	Christian Bettstetter , Giovanni Resta , Paolo Santi, The Node Distribution of the Random Waypoint Mobility Model for Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.3, p.257-269, March 2003 [doi>10.1109/TMC.2003.1233531]
	10	J. E. Boillat, Load balancing and Poisson equation in a graph, Concurrency: Practice and Experience, v.2 n.4, p.289-313, Dec. 1990 [doi>10.1002/cpe.4330020403]
	11	Scott Camazine , Nigel R. Franks , James Sneyd , Eric Bonabeau , Jean-Louis Deneubourg , Guy Theraula, Self-Organization in Biological Systems, Princeton University Press, Princeton, NJ, 2001
	12	Canright, G., Deutsch, A., and Urnes, T. 2005. Chemotaxis-inspired load balancing. In Proceedings of the European Conference on Complex Systems (ECCS'05).
	13	Yatin Chawathe , Sylvia Ratnasamy , Lee Breslau , Nick Lanham , Scott Shenker, Making gnutella-like P2P systems scalable, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.864000]
	14	Clausen, T., Jacquet, P., Laouiti, A., Muhlethaler, P., Qayyum, A., and Viennot, L. 2001. Optimized link state routing protocol. In Proceedings of IEEE INMIC.
	15	G. Cybenko, Dynamic load balancing for distributed memory multiprocessors, Journal of Parallel and Distributed Computing, v.7 n.2, p.279-301, October 1989 [doi>10.1016/0743-7315(89)90021-X]
	16	de Castro, L. N. and Timmis, J. 2002. Artificial Immune Systems. Springer Verlag, Berlin, Germany.
	17	Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
	18	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.
	19	Di Caro, G. A. 2003. Analysis of simulation environments for mobile ad hoc networks. Tech. Rep. 24-03 (Dec). IDSIA, Lugano, Switzerland.
	20	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.
	21	Di Caro, G. A. and Dorigo, M. 1998. AntNet: Distributed stigmergetic control for communications networks. J. Artificial Intelli. Res. 9, 317--365.
	22	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.
	23	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.
	24	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.
	25	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.
	26	Giovanna Di Marzo Serugendo , Anthony Karageorgos , Omer F. Rana , Franco Zambonelli, Engineering Self-Organising Systems, SpringerVerlag, 2004
	27	Marco Dorigo , Gianni Di Caro , Luca M. Gambardella, Ant algorithms for discrete optimization, Artificial Life, v.5 n.2, p.137-172, April 1999 [doi>10.1162/106454699568728]
	28	Marco Dorigo , Thomas Stützle, Ant Colony Optimization, Bradford Book, 2004
	29	Frederick Ducatelle , Gianni Di Caro , Luca Maria Gambardella, Ant Agents for Hybrid Multipath Routing in Mobile Ad Hoc Networks, Proceedings of the Second Annual Conference on Wireless On-demand Network Systems and Services (WONS'05), p.44-53, January 19-21, 2005 [doi>10.1109/WONS.2005.3]
	30	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.
	31	Agoston E. Eiben , J. E. Smith, Introduction to Evolutionary Computing, SpringerVerlag, 2003
	32	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.
	33	Fewell, J. H. 2003. Social insect networks. Science 301, 26 (Sept.), 1867--1869.
	34	Gamma, E., Helm, R., Johnson, R., and Vlissides, J. 1995. Design Patterns. Addison-Wesley.
	35	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.
	36	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.
	37	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.
	38	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.
	39	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.
	40	Glazier, J. A. and Graner, F. 1993. Simulation of the differential adhesion driven rearrangement of biological cells. Phys. Rev. E 47, 3, 2128--2154.
	41	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.
	42	H. Van Dyke Parunak , Sven A. Brueckner, Stigmergic Learning for Self-Organizing Mobile Ad-Hoc Networks (MANET's), Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1324-1325, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.253]
	43	Haas, Z. J. 1997. A new routing protocol for the reconfigurable wireless networks. In Proceedings of the IEEE International Conference on Universal Personal Communications.
	44	Simon Haykin, Neural Networks: A Comprehensive Foundation, Prentice Hall PTR, Upper Saddle River, NJ, 1998
	45	Andrew Ilachinski , Zane, Cellular Automata: A Discrete Universe, World Scientific Publishing Co., Inc., River Edge, NJ, 2001
	46	Janeway, C. A., Travers, P., Walport, M., and Shlomchik, M. 2001. Immuno Biology: The Immune System in Health and Disease, 5th ed. Garland Publishing.
	47	Jelasity, M. and Babaoglu, O. 2005. T-Man: Gossip-based overlay topology management. In 3rd International Workshop on Engineering Self-Organising Applications (ESOA'05).
	48	Márk Jelasity , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, The peer sampling service: experimental evaluation of unstructured gossip-based implementations, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
	49	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.
	50	Márk Jelasity , Alberto Montresor , Ozalp Babaoglu, Gossip-based aggregation in large dynamic networks, ACM Transactions on Computer Systems (TOCS), v.23 n.3, p.219-252, August 2005 [doi>10.1145/1082469.1082470]
	51	Johnson, D. and Maltz, D. 1996. Mobile Computing. Kluwer (Chapter Dynamic Source Routing in Ad Hoc Wireless Networks). 153--181.
	52	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.
	53	David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
	54	Jeffrey O. Kephart , David M. Chess, The Vision of Autonomic Computing, Computer, v.36 n.1, p.41-50, January 2003 [doi>10.1109/MC.2003.1160055]
	55	Christopher G. Langton, Artificial Life, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
	56	Dik L. Lee , Huei Chuang , Kent Seamons, Document Ranking and the Vector-Space Model, IEEE Software, v.14 n.2, p.67-75, March 1997 [doi>10.1109/52.582976]
	57	Kenneth N Lodding, The Hitchhiker's Guide to Biomorphic Software, Queue, v.2 n.4, June 2004 [doi>10.1145/1016978.1016985]
	58	Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
	59	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.
	60	R. Montemanni , L. M. Gambardella, Exact algorithms for the minimum power symmetric connectivity problem in wireless networks, Computers and Operations Research, v.32 n.11, p.2891-2904, November 2005 [doi>10.1016/j.cor.2004.04.017]
	61	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.
	62	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.
	63	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.
	64	Murray, J. D. 1990. Mathematical Biology. Springer-Verlag, Berlin, Germany.
	65	Ottino, J. M. 2004. Engineering complex systems. Nature 427, 399.
	66	H. Van Dyke Parunak , Sven A. Brueckner , John A. Sauter , Robert Matthews, Global convergence of local agent behaviors, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082520]
	67	PeerSim. http://peersim.sourceforge.net/.
	68	Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
	69	Păun, G. 2002. Computing with Membranes: an Introduction. Springer, Verlag, Berlin, Germany.
	70	Păun, G., Rozenberg, G., and Salomaa, A. 2005. DNA Computing. Springer, Verlag, Berlin, Germany.
	71	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.
	72	Royer, E. and Toh, C.-K. 1999. A review of current routing protocols for ad hoc mobile wireless networks. IEEE Person. Comm.
	73	Scalable Network Technologies, Inc. 2005. QualNet Simulator, Version 3.8. Scalable Network Technologies, Inc., Culver City, CA, USA. http://www.scalable-networks.com.
	74	Douglas C. Schmidt , Mohamed Fayad , Ralph E. Johnson, Software patterns, Communications of the ACM, v.39 n.10, p.37-39, Oct. 1996 [doi>10.1145/236156.236164]
	75	Ruud Schoonderwoerd , Janet L. Bruten , Owen E. Holland , Leon J. M. Rothkrantz, Ant-based load balancing in telecommunications networks, Adaptive Behavior, v.5 n.2, p.169-207, Fall 1996 [doi>10.1177/105971239700500203]
	76	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.
	77	Steffen Staab , Francis Heylighen , Carlos Gershenson , Gary William Flake , David M. Pennock , Daniel C. Fain , David De Roure , Karl Aberer , Wei-Min Shen , Olivier Dousse , Patrick Thiran, Neurons, Viscose Fluids, Freshwater Polyp Hydra-and Self-Organizing Information Systems, IEEE Intelligent Systems, v.18 n.4, p.72-86, July/August 2003 [doi>10.1109/MIS.2003.1217631]
	78	Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
	79	Guy Theraulaz , Eric Bonbeau, A brief history of stigmergy, Artificial Life, v.5 n.2, p.97-116, April 1999 [doi>10.1162/106454699568700]
	80	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.
	81	Robbert Van Renesse , Kenneth P. Birman , Werner Vogels, Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.164-206, May 2003 [doi>10.1145/762483.762485]
	82	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.
	83	Zipf, G. K. 1935. Psycho- Biology of Languages. Houghton-Mifflin, Boston, MA.

Collaborative Colleagues:

Ozalp Babaoglu: colleagues

Geoffrey Canright: colleagues

Andreas Deutsch: colleagues

Gianni A. Di Caro: colleagues

Frederick Ducatelle: colleagues

Luca M. Gambardella: colleagues

Niloy Ganguly: colleagues

Márk Jelasity: colleagues

Roberto Montemanni: colleagues

Alberto Montresor: colleagues

Tore Urnes: colleagues