A new class of nature-inspired algorithms for self-adaptive peer-to-peer computing

ABSTRACT

We present, and evaluate benefits of, a design methodology for translating natural phenomena represented as mathematical models, into novel, self-adaptive, peer-to-peer (p2p) distributed computing algorithms (protocols). Concretely, our first contribution is a set of techniques to translate discrete sequence equations (also known as difference equations) into new p2p protocols called sequence protocols. Sequence protocols are self-adaptive, scalable, and fault-tolerant, with applicability in p2p settings like Grids. A sequence protocol is a set of probabilistic local and message-passing actions for each process. These actions are translated from terms in a set of source sequence equations. Individual processes do not simulate the source sequence equations completely. Instead, each process executes probabilistic local and message passing actions, so that the emergent round-to-round behavior of the sequence protocol in a p2p system can be probabilistically predicted by the source sequence equations. The article's second contribution is the design and evaluation of a set of sequence protocols for detection of two global triggers in a distributed system: threshold detection and interval detection. This article's third contribution is a new self-adaptive Grid computing protocol called HoneyAdapt. HoneyAdapt is derived from sequence equations modeling adaptive bee foraging behavior in nature. HoneyAdapt is intended for Grid applications that allow Grid clients, at run-time, a choice of algorithms for executing chunks of the application's dataset. HoneyAdapt tells each Grid client how to adaptively select at run-time, for each chunk it receives, a good algorithm for computing the chunk—this selection is based on continuous feedback from other clients. Finally, we design a variant of HoneyAdapt, called HoneySort, for application to Grid parallelized sorting settings using the master-worker paradigm. Our evaluation of these contributions consists of mathematical analysis, large-scale trace-based simulation results, and experimental results from a HoneySort deployment.

REFERENCES

• 1: Agarwal, R. P. 2000. Difference Equations and Inequalities: Theory, Methods and Applications, second edition. CRC.
• 2: Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M. J., and Peralta, R. 2006. Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18, 4, 235--253.
• 3: Arpaci-Dusseau, R., Arpaci-Dusseau, A., Culler, D. E., Hellerstein, J. M., and Patterson, D. A. 1998. Searching for the sorting record: experience with now-sort. In Proceedings of ACM SIGMETRICS Symposium on Parallel and Distributed Tools. ACM, New York, 124--133.
• 4: Arvind. 2003. Bluespec: A language for hardware design, simulation, synthesis and verification. In Proceedings of ACM-IEEE MEMOCODE. ACM, New York, 249.
• 5: Babaoglu, O., Jelasity, M., Canright, G., Urnes, T., Deutsch, A., Ganguly, N., di Caro, G., Ducatelle, F., Gambardella, L. M., Montemanni, R., and Montresor, A. 2005. Design patterns from biology for distributed computing. In Proceedings of the European Conference on Complex Systems.
• 6: Babaoglu, O., Meling, H., and Montresor, A. 2002. Anthill: A framework for the development of agent-based peer-to-peer systems. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS). IEEE, NY, 15.
• 7: Bhagwan, R., Tati, K., Cheng, Y.-C., Savage, S., and Voelker, G. M. 2004. Total Recall: System support for automated availability management. In Proceedings of the Usenix Symposium on Networked Systems Design and Implementation (NSDI). Usenix, San Francisco, CA, 337--350.
• 8: Bonabeau, E., Dorigo, M., and Theraulaz, G. 1999. Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, Oxford, UK.
• 9: Chandy, K. and Lamport, L. 1985. Distributed snapshots: Determining global states of distributed systems. ACM Trans. Comput. Syst. 3, 63--75.
• 10: Cormen, T., Leiserson, C., Rivest, R., and Stein, C. 2001. Introduction to Algorithms, 2nd Ed. MIT Press, Cambridge, MA.
• 11: di Caro, G. and Dorigo, M. 1998. Antnet: Distributed stigmergic control for communications networks. J. AI Res. 9, 317--365.
• 12: D'Silva, S. 1998. Collective decision making in honeybees. http://www.msu.edu/user/dsilva/beepp2.ps.
• 13: Gray, J. 2005. Sorting benchmark. http://research.microsoft.com/barc/SortBenchmark.
• 14: Guo, H. 2003. Algorithm selection for sorting and probabilistic inference: a machine-learning approach. Phd. Dissertation, Department of Computing and Information Sciences, Kansas State University.
• 15: Gupta, I., Nagda, M., and Devaraj, C. F. 2007. The design of novel distributed protocols from differential equations. Distrib. Comput. 20, 2, 95--114.
• 16: Herbster, M. and Warmuth, M. K. 1995. Tracking the best expert. In Proceedings of International Conference on Machine Learning (ICML). ACM, New York, 286--294.
• 17: Jelasity, M., Voulgaris, S., Guerraoui, R., Kermarrec, A.-M., and Steen, M. 2007. Gossip-based peer sampling. ACM Trans. Comput. Syst. 25, 3, Article 8.
• 18: Kempe, D., Dobra, A., and Gehrke, J. 2003. Computing aggregate information using gossip. In Proceedings of the 44th IEEE Symposiumon on the Foundations of Computer Science (FOCS). IEEE, NY, 482--491.
• 19: Ko, S. Y., Gupta, I., and Jo, Y. 2007. Novel mathematics-inspired algorithms for self-adaptive peer-to-peer computing. In Proceedings of the IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO). IEEE, NY, 3--12.
• 20: Kurtz, T. 1981. Approximation of population processes. In Regional Conference Series in Applied Mathematics. SIAM, Philadelphia, PA.
• 21: Loo, B., Condie, T., Hellerstein, J. M., Maniatis, P., Roscoe, T., and Stoica, I. 2005. Implementing declarative overlays. ACM SIGOPS Oper. Syst. Rev. 39, 5, 75--90.
• 22: Maniezzo, V., Boschetti, M. A., and Jelasity, M. 2004. An ant approach to membership overlay design. In Proceedings of the International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS), Lecture Notes in Computer Science, vol. 3172, 37--48, Springer, Berlin, Germany.
• 23: MathWorld. 2007. Logistic map. http://mathworld.wolfram.com/LogisticMap.html.
• 24: Medina, A., Lakhina, A., Matta, I., and Byers, J. 2001. BRITE: An approach to universal topology generation. In Proceedings of the IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS). IEEE, NY, 346.
• 25: Merritt, M. and Taubenfeld, G. 2000. Computing with infinitely many processes. In Proceedings of the International Conference on Distributed Computing (DISC). Lecture Notes in Computer Science, vol. 1914, Springer Berlin, Germany, 164--178.
• 26: Misra, J. and Chandy, K. M. 1982. Termination detection of diffusing computations in communicating sequential processes. ACM Trans. Prog. Lang. Syst. 4, 1, 37--43.
• 27: Mitzenmacher, M. 2001. The power of two choices in randomized load balancing. IEEE Trans. Para. Distrib. Syst. 12, 10, 1094--1104.
• 28: Rabin, M. O. 1983. Randomized Byzantine generals. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, NY, 403--409.
• 29: Rice, J. R. 1976. The algorithm selection problem. Advances Comput. 15, 65, 118.
• 30: Rohrer, J. 2007. Mute: Simple anonymous file sharing. http://mute-net.sourceforge.net/.
• 31: Schneider, F. 1986. The state machine approach: A tutorial. Tech. rep. TR86-800, Cornell University.
• 32: Seeley, T. 1996. The Wisdom of the Hive. Harvard University Press, Cambridge, MA.
• 33: Strogatz, S. H. 2001. Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry and Engineering, Perseus Book Group, New York, NY.
• 34: Uresin, A. and Dubois, M. 1990. Parallel asynchronous algorithms for discrete data. J. ACM 37, 3, 588--606.
• 35: Voulgaris, S., Gavidia, D., and van Steen, M. 2005. CYCLON: Inexpensive membership management for unstructured P2P overlays. J. Netw. Syst. Manag. 13, 2 (June), 197--217.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.0 General

General Terms:
Algorithms, Design, Performance

Keywords:
Complex adaptive systems, adaptivity, autonomic computing and communication, bio-inspired techniques, convergence, design methodology, difference equations, distributed protocols, grid computing, probabilistic protocols, sequence equations, sequence protocols