The DOI matches its Crossref record; 63 of the 63 references it cites were found in a registry or an index.
Design patterns from biology for distributed computing
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Neural Networks: A Comprehensive Foundation
Haykin, S. (1998) · Cited by 30,070
Reinforcement Learning: An Introduction
Sutton, R. S., & Barto, A. G. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.1998.712192 · Cited by 27,225
Reinforcement Learning: An Introduction
(2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2004.842673 · Cited by 24,496
Statistical mechanics of complex networks
Albert, R., & Barabási, A.-L. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.47 · Cited by 20,471
Ad-hoc on-demand distance vector routing
Perkins, C. E., & Royer, E. M. (1999) · Proceedings WMCSA'99. Second IEEE Workshop on Mobile Computing Systems and Applications · doi:10.1109/mcsa.1999.749281 · Cited by 10,313
Dynamic Source Routing in Ad Hoc Wireless Networks
Johnson, D. B., & Maltz, D. A. (2007) · The Kluwer International Series in Engineering and Computer Science · doi:10.1007/978-0-585-29603-6_5 · Cited by 8,518
Introduction to Reinforcement Learning
Sutton, R. S., & Barto, A. G. (1998) · The MIT Press eBooks · Cited by 6,855
Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers
Perkins, C. E., & Bhagwat, P. (1994) · ACM SIGCOMM Computer Communication Review · doi:10.1145/190809.190336 · Cited by 6,678
(2007) · Handbook of Approximation Algorithms and Metaheuristics · doi:10.1201/9781420010749-33 · Cited by 6,607
A Pattern Language: Towns, Buildings, Construction
Alexander, C., Ishikawa, S., Silverstein, M., Jacobson, M., Fiksdahl-King, I., & Angel, S. (1977) · Cited by 6,582
The vision of autonomic computing
Kephart, J. O., & Chess, D. M. (2003) · Computer · doi:10.1109/mc.2003.1160055 · Cited by 6,572
Bertsekas, D. P., & Gallager, R. G. (1987) · Cited by 5,561
A performance comparison of multi-hop wireless ad hoc network routing protocols
Broch, J., Maltz, D. A., Johnson, D. B., Hu, Y.-C., & Jetcheva, J. (1998) · Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking · doi:10.1145/288235.288256 · Cited by 4,673
Introduction to Evolutionary Computing
Eiben, A. E., & Smith, J. E. (2003) · Natural Computing Series · doi:10.1007/978-3-662-05094-1 · Cited by 4,176
Immunobiology: the immune system in health and disease
(1995) · Choice Reviews Online · doi:10.5860/choice.32-3876 · Cited by 4,110
A review of current routing protocols for ad hoc mobile wireless networks
Royer, E. M., & Toh, C.-K. (1999) · IEEE Personal Communications · doi:10.1109/98.760423 · Cited by 3,763
Dorigo, M., & Stützle, T. (2004) · The MIT Press eBooks · doi:10.7551/mitpress/1290.001.0001 · Cited by 3,330
Nazuno, J. F. (2000) · Computación y Sistemas · Cited by 3,201
Self-Organization in Biological Systems
Sneyd, J., Theraula, G., Bonabeau, E., Deneubourg, J.-L., & Franks, N. R. (2001) · doi:10.1515/9780691212920 · Cited by 2,949
Ant Algorithms for Discrete Optimization
Dorigo, M., Caro, G. D., & Gambardella, L. M. (1999) · Artificial Life · doi:10.1162/106454699568728 · Cited by 2,808
Self-citationThe Mathematical Theory of Infectious Diseases and its applications
Ling, N. R. (1978) · Immunology · Cited by 1,934
Optimized Link State Routing Protocol
Jacquet, P., Mühlethaler, P., Qayyum, A., Laouiti, A., Viennot, L., & Clausen, T. (2000) · Cited by 1,907
IMMUNOBIOLOGY : the immunesystem in health and disease
Janeway, C. A. (1994) · Cited by 1,757
Lasater, C. G. (2006) · Cited by 1,682
Epidemic algorithms for replicated database maintenance
Demers, A., Greene, D., Hauser, C., Irish, W., & Larson, J. (1987) · Proceedings of the sixth annual ACM Symposium on Principles of distributed computing - PODC '87 · doi:10.1145/41840.41841 · Cited by 1,673
Search and replication in unstructured peer-to-peer networks
Lv, Q., Cao, P., Cohen, E., Li, K., & Shenker, S. J. (2014) · International Conference on Supercomputing · doi:10.1145/2591635.2667182 · Cited by 1,612
AntNet: Distributed Stigmergetic Control for Communications Networks
Di Caro, G., & Dorigo, M. (1998) · Journal of Artificial Intelligence Research · doi:10.1613/jair.530 · Cited by 1,579
Gossip-based computation of aggregate information
Kempe, D., Dobra, A., & Gehrke, J. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238221 · Cited by 1,480
Making gnutella-like P2P systems scalable
Chawathe, Y., Ratnasamy, S., Breslau, L., Lanham, N., & Shenker, S. (2003) · Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/863955.864000 · Cited by 1,082
Dynamic load balancing for distributed memory multiprocessors
Cybenko, G. (1989) · Journal of Parallel and Distributed Computing · doi:10.1016/0743-7315(89)90021-x · Cited by 997
(1996) · The Kluwer International Series in Engineering and Computer Science · doi:10.1007/b102605 · Cited by 873
Simulation of the differential adhesion driven rearrangement of biological cells
Glazier, J. A., & Graner, F. (1993) · Physical Review E · doi:10.1103/physreve.47.2128 · Cited by 798
Gossip-based aggregation in large dynamic networks
Jelasity, M., Montresor, A., & Babaoğlu, Ö. (2005) · ACM Transactions on Computer Systems · doi:10.1145/1082469.1082470 · Cited by 786
Self-citationAnt-Based Load Balancing in Telecommunications Networks
Schoonderwoerd, R., Holland, O. E., Bruten, J. L., & Rothkrantz, L. J. M. (1997) · Adaptive Behavior · doi:10.1177/105971239700500203 · Cited by 739
The Psycho-Biology of Language
Tinker, M. A., & Zipf, G. K. (1936) · The American Journal of Psychology · doi:10.2307/1415586 · Cited by 728
A new routing protocol for the reconfigurable wireless networks
Haas, Z. J. (2002) · IEEE International Conference on Universal Personal Communications (ICUPC) · doi:10.1109/icupc.1997.627227 · Cited by 695
Theraulaz, G., & Bonabeau, E. (1999) · Artificial Life · doi:10.1162/106454699568700 · Cited by 665 · cited 2×
“It is worth pointing out that in the literature stigmergy is usually described in terms of mobile agents moving through a passive environment, communicating indirectly via modications they make to stigmergic variables distributed in their environment [ Theraulaz and Bonabeau 1999; Keil and Goldin 2005].”
Van Renesse, R., Birman, K. P., & Vogels, W. (2003) · ACM Transactions on Computer Systems · doi:10.1145/762483.762485 · Cited by 645
Langton, C. G. (1995) · Cited by 580
AntHocNet: an adaptive nature‐inspired algorithm for routing in mobile ad hoc networks
Di Caro, G., Ducatelle, F., & Gambardella, L. M. (2005) · European Transactions on Telecommunications · doi:10.1002/ett.1062 · Cited by 579
Self-citationAbelson, H., Allen, D., Coore, D., Hanson, C., Homsy, G., Knight, T. F., Nagpal, R., Rauch, E., Sussman, G. J., & Weiss, R. (2000) · Communications of the ACM · doi:10.1145/332833.332842 · Cited by 521
Cellular Automata: A Discrete Universe
Ilachinski, A. (2001) · WORLD SCIENTIFIC eBooks · doi:10.1142/4702 · Cited by 457
The Mathematical Theory of Infectious Diseases and Its Applications
Giles, P. (1977) · Journal of the Operational Research Society · doi:10.1057/jors.1977.92 · Cited by 421
Survey of research towards robust peer-to-peer networks: Search methods
Risson, J., & Moors, T. (2006) · Computer Networks · doi:10.1016/j.comnet.2006.02.001 · Cited by 386
Ottino, J. M. (2004) · Nature · doi:10.1038/427399a · Cited by 351
The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-Based Implementations
Jelasity, M., Guerraoui, R., Kermarrec, A.-M., & van Steen, M. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30229-2_5 · Cited by 301
Self-citationFewell, J. H. (2003) · Science · doi:10.1126/science.1088945 · Cited by 281
T-Man: Gossip-Based Overlay Topology Management
Jelasity, M., & Babaoğlu, Ö. (2006) · Lecture notes in computer science · doi:10.1007/11734697_1 · Cited by 241
Self-citationEngineering Self-Organising Systems
Brueckner, S. A., Yamins, D. L. K., Jelasity, M., & Hassas, S. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-69868-5 · Cited by 214
Self-citationA Probabilistic Emergent Routing Algorithm for Mobile Ad Hoc Networks
Baras, J. S., & Mehta, H. (2003) · Cited by 188
Prakken, H., Kok, E. M., Meyer, J. C., & Vreeswijk, G. A. W. (2012) · Adaptive Agents and Multi-Agents Systems · Cited by 186
Epidemic-style proactive aggregation in large overlay networks
Jelasity, M., & Montresor, A. (2004) · 24th International Conference on Distributed Computing Systems, 2004. Proceedings. · doi:10.1109/icdcs.2004.1281573 · Cited by 172
Self-citationAnt colony optimization and its application to adaptive routing in telecommunication networks
Di, G. A., & Dorigo, M. (2004) · Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles) · Cited by 166
Neural Organization: Structure, Function, and Dynamics
Arbib, M. A., Érdi, P., & Szentágothai, J. (1997) · Cited by 161
AntHocNet: an Ant-Based Hybrid Routing Algorithm for Mobile Ad HocNetworks.
Di, G. A., Ducatelle, F., & Gambardella, L. M. (2004) · doi:10.71910/supsi.7015 · Cited by 160
Self-citationUSING ANT AGENTS TO COMBINE REACTIVE AND PROACTIVE STRATEGIES FOR ROUTING IN MOBILE AD-HOC NETWORKS
Ducatelle, F., Di, G. A., & Gambardella, L. M. (2005) · International Journal of Computational Intelligence and Applications · doi:10.1142/s1469026805001556 · Cited by 113
Self-citationSwarm intelligence for routing in mobile ad hoc networks
Di, G. A., Ducatelle, F., & Gambardella, L. M. (2005) · IEEE Swarm Intelligence Symposium · doi:10.1109/sis.2005.1501605 · Cited by 110
Self-citationNumber of distinct sites visited by N random walkers
Larralde, H., Trunfio, P. A., Havlin, S., Stanley, E., & Weiss, G. H. (1992) · Physical Review A · doi:10.1103/physreva.45.7128 · Cited by 98
Ant Agents for Hybrid Multipath Routing in Mobile Ad Hoc Networks
Ducatelle, F., Di, G. A., & Gambardella, L. M. (2005) · Annual Conference on Wireless On-demand Network Systems and Services (WONS) · doi:10.1109/wons.2005.3 · Cited by 88
Self-citationMotivated Reinforcement Learning
Dayan, P. (2002) · The MIT Press eBooks · doi:10.7551/mitpress/1120.003.0006 · Cited by 53
van Renesse, R. (2003) · Lecture notes in computer science · doi:10.1007/3-540-37795-6_16 · Cited by 49
Analysis of simulation environments for mobile ad hoc networks.
Di, G. A. (2003) · doi:10.71910/supsi.7045 · Cited by 41
The Hitchhiker’s Guide to Biomorphic Software
Lodding, K. N. (2004) · Queue · doi:10.1145/1016978.1016985 · Cited by 21
Cited by
Self-adaptive software: Landscape and research challenges
Salehie, M., & Tahvildari, L. (2009) · ACM Transactions on Autonomous and Adaptive Systems · doi:10.1145/1516533.1516538 · Cited by 1,266
A survey on engineering approaches for self-adaptive systems
Krupitzer, C., Roth, F. M., VanSyckel, S., Schiele, G., & Becker, C. (2015) · Pervasive and Mobile Computing · doi:10.1016/j.pmcj.2014.09.009 · Cited by 443
On Patterns for Decentralized Control in Self-Adaptive Systems
Weyns, D., Schmerl, B., Grassi, V., Malek, S., Mirandola, R., Prehofer, C., Wuttke, J., Andersson, J., Giese, H., & Göschka, K. M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-35813-5_4 · Cited by 370
Conti, M., Das, S. K., Bisdikian, C., Kumar, M., Ni, L. M., Passarella, A., Roussos, G., Tröster, G., Tsudik, G., & Zambonelli, F. (2012) · Pervasive and Mobile Computing · doi:10.1016/j.pmcj.2011.10.001 · Cited by 275
Developing pervasive multi-agent systems with nature-inspired coordination
Zambonelli, F., Omicini, A., Anzengruber, B., Castelli, G., De Angelis, F. L., Serugendo, G. D. M., Dobson, S., Fernandez-Marquez, J. L., Ferscha, A., Mamei, M., et al. (2015) · Pervasive and Mobile Computing · doi:10.1016/j.pmcj.2014.12.002 · Cited by 96
Metadata
- Authors
- Babaoglu, O., Canright, G., Deutsch, A., Caro, G. A. D., Ducatelle, F., Gambardella, L. M., Ganguly, N., Jelasity, M., Montemanni, R., Montresor, A., & Urnes, T.
- Venue
- ACM Transactions on Autonomous and Adaptive Systems
- Published
- 2006-09
- Volume
- 1
- Issue
- 1
- Pages
- 26-66
- ISSN
- 1556-4665 (ISSN-L)
- 1556-4703
- OpenAlex
- W2124990234
- Cited by
- 302
- References
- 63
- FWCI
- 46.58
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.