Extremal search of decision policies for scalable distributed applications

ABSTRACT

The ongoing trend of constructing open, scalable distributed systems such as peer-to-peer (P2P) systems demands for effective tools to manage the interactions between constituent entities (or nodes). One such tool is through imposing decision policies at the network level. However very few techniques are available to allow computers autonomously identify good policies with limited human intervention. In this paper, we propose an Extremal Programming (EP) algorithm to achieve automatic policy identification. The algorithm is inspired by recent advances in understanding far from equilibrium phenomena in terms of self-organized criticality (SOC). The effectiveness of EP is evaluated through a P2P application called location-aware video streaming (LAVS). The simulation studies in LAVS demonstrate that with EP, the fast and effective sharing of video streams is achieved.

REFERENCES

• 1: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 2: S. Boettcher and A. G. Percus. Optimization with extremal dynamics. Physics Review Letter, 23(4):5211--5214, 2001.
• 3: S. Boettcher and A. G. Percus. Extremal optimization: an evolutionary local-search algorithm. In H. K. Bhargava and N. Ye, editors, Computational Modeling and Problem Solving in the Networked World: Interfaces in Computer Science and Operations Research, pages 61--77. Kluwer Academic Publisher, 2003.
• 4: Bengt Carlsson , Rune Gustavsson, The Rise and Fall of Napster - An Evolutionary Approach, Proceedings of the 6th International Computer Science Conference on Active Media Technology, p.347-354, December 18-20, 2001
• 5: A. J. Chakravarti, G. Baumgartner, and M. Lauria. The organic grid: self-organizing computation on a peer-to-peer network. IEEE Transactions on Systems, Man, and Cybernetics, 35(3):373--384, 2005.
• 6: H. S. Chang, H. G. Lee, M. C. Fu, and S. I. Marcus. Evolutionary policy iteration for solving markov decision processes. IEEE Transactions on Automatic Control, 50(11):1804--1808, 2005.
• 7: I. Cloete and J. V. Zyl. Fuzzy rule induction in a set covering framework. IEEE Transactions on Fuzzy Systems, 14(1):93--110, 2006.
• 8: J. R. Koza. Hierarchical genetic algorithms operating on populations of computer programs. In Proceedings of the 11th International Joint Conference on Artificial Intelligence, pages 768--774, 1989.
• 9: J. R. Koza and J. P. Rice. Automatic programming of robots using genetic programming. In Proceedings of the 10th National Conference on Artificial Intelligence, pages 194--201, 1992.
• 10: Wojciech Kwedlo , Marek Kretowski, Discovery of Decision Rules from Databases: An Evolutionary Approach, Proceedings of the Second European Symposium on Principles of Data Mining and Knowledge Discovery, p.370-378, September 23-26, 1998
• 11: E. K. Lua, J. Crowcroft, M. Pias, R. Sharma, and S. Lim. A survey and comparison of peer-to-peer overlay network schemes. IEEE Communications Surveys and Tutorials, 7(2):72--93, 2005.
• 12: Andy Oram, Peer-to-Peer: Harnessing the Power of Disruptive Technologies, O'Reilly & Associates, Inc., Sebastopol, CA, 2001
• 13: P. Bak. How Nature Works: The Science of Self-Organized Criticality. Springer-Verlag Telos, 1999.
• 14: J. R. Quinlan. Decision trees and decision making. IEEE Transactions on System, Man, and Cybernetics, 20:339--346, 1990.
• 15: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 16: Olga Ratsimor , Dipanjan Chakraborty , Anupam Joshi , Timothy Finin , Yelena Yesha, Service discovery in agent-based pervasive computing environments, Mobile Networks and Applications, v.9 n.6, p.679-692, December 2004 [doi>10.1145/1035715.1035728]
• 17: Ion Stoica , Robert Morris , David Liben-Nowell , David R. Karger , M. Frans Kaashoek , Frank Dabek , Hari Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.17-32, February 2003 [doi>10.1109/TNET.2002.808407]
• 18: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 19: W. T. Tsai , Xinxin Liu , Yinong Chen, Distributed Policy Specification and Enforcement in Service-Oriented Business Systems, Proceedings of the IEEE International Conference on e-Business Engineering, p.10-17, October 12-18, 2005 [doi>10.1109/ICEBE.2005.52]
• 20: C. J. C. H. Watkins. Q-learning. Machine Learning, 8:1804--1808, 1992.
• 21: B. Yang and H. Garcia-Monlina. Efficient search in peer-to-peer networks. In Proceedings of the 22nd IEEE International Conference on Distributed Computing Systems (ICDCS), 2002.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search