Game Theoretical Model Applied to Scheduling in Grid Computing

• Autorzy: Świtalski P. , Seredyński F.
• Języki publikacji: EN

Abstrakty

EN

We consider a grid computational model which consist of a number of computation nodes and a number of users. Each user generates a computation load (jobs) requesting computational and communication resources. A deadline for each job is also defined. We propose a scheduling algorithm which is based on Iterated Prisoner's Dilemma (IPD) under the Random Pairing game, where nodes (players) of the grid system decide about their behavior: cooperate or defect. In this game players play a game with randomly chosen players and receive payoffs. Each player has strategies which define its decision. Genetic algorithm (GA) is used to evolve strategies to optimize a criterion related to scheduling problem. In this paper we show that GA is able to discover a strategy in the IPD model providing a cooperation between node-players, which permits to solve scheduling problem in grid.

Słowa kluczowe

EN

scheduling; game theory; prisoner's dilemma; genetic algorithm; grid; task; job

• Wydawca: Wydawnictwo Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach
• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2007
• Tom: Vol. 2(9)
• Strony: 19--27
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Świtalski P.

• The University of Podlasie, Computer Science Department, ul. Sienkiewicza 51, 08-110 Siedlce, Poland

autor

Seredyński F.

• The University of Warmia and Mazury, ul. Oczapowskiego 2, 10-719 Olsztyn, Poland
• Institute of Computer Science, Polish Academy of Sciences, ul. Ordona 21, 01-237 Warsaw, Poland

Bibliografia

• 1. Foster I. and Kesselman C. (ed.), (1999). The Grid: Blueprint for a Future Computing Infrastructure, Morgan Kaufmann Publishers, USA.
• 2. Foster I., Kesselman C., Tuecke S., (2001). The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal Supercomputer Applications, 15(3).
• 3. Ferguson D., Nikolaou C., Sairamesh J., Yemini Y., (1996). Economic models for allocating resources in computer systems. Market-Based Control: A Paradigm for Distributed Resource Allocation, World Scientific Press: Singapore.
• 4. SETI@home: http://setiathome.ssl.berkeley.edu
• 5. Forghanizadeh S., (2005). Grid Processor Scheduling based on Game Theoretic Approach, CPSC532A Final Project.
• 6. Buyya R., Abramson D., Giddy J. and Stockinger H., (2002). Economic Models for Resource Management and Scheduling in Grid Computing, Special Issue on Grid Computing Environments, The Journal of Concurrency and Computation: Practice and Experience (CCPE), Wiley Press, USA.
• 7. Ygge F., (1998). Market-Oriented Programming and its Application to Power Load Management, Ph.D. Thesis, Lund University.
• 8. Wellman M.P., Walsh W.E., Wurman P.R., MacKie-Mason J.K., (2001). Auction Protocols for Decentralized Scheduling, Games and Economic Behavior, 35: 271-303.
• 9. Wilson L.A., (2008). Distributed, heterogeneous resource management using artificial immune systems, International Parallel and Distributed Processing Symposium (IPDPS '08), NIDISC.
• 10. Switalski P., Seredynski F., Hertel P., (2006). GAVis System Supporting Visualization, Analysis and Solving Combinatorial Optimization Problems Using Evolutionary Algorithms, Intelligent Information Processing And Web Mining: Proceedings of the International IIS, 75-84.
• 11. Wikipedia: http://en.wikipedia.org
• 12. Marsh S.P., (1994). Formalising Trust as a Computational Concept. PhD Thesis, University of Stirling, UK.
• 13. Camerer C.F., (2003). Behavioral Game Theory: Experiments in Strategic Interaction, Princeton University Press.
• 14. Namikawa N., Ishibuchi H., (2005). Evolution of Cooperative Behavior in the Iterated Prisoner’s Dilemma under Random Pairing in Game Playing, Proceedings of the Congress on Evolutionary Computation, IEEE Press, 2637-2644.
• 15. Lijuan X., Yanmin Z., Lionel N. and Zhiwei X., (2005). GridlS: An Incentive- based Grid Scheduling, Proceedings of the International Parallel & Distributed Processing Symposium, Denver, Colorado.