Abstract
Tasks scheduling and resource allocation are crucial issues in hierarchic Computational Grid (CG) systems. The Grid users usually belong to different administrative domains with a various communication protocols, the access to the resources, the resource usage policies. In such a complex large-scale environment the game theory has shown to be an effective tool for modelling the Grid users’ decision process, the multi-criteria users’ requirements and the task and resource allocation strategies. In this chapter, we firstly highlight the main Grid users types, their relationships, resource access and usage scenarios in CGs. Then, we identify and analyze some fundamental features arising in the users’ behavior in Grid scheduling. We present a concept of the non-cooperative asymmetric Stackelberg game as a case study of the Grid users behavior decision process, under new requirements arising in allocation problems, such as asymmetric users relations, security and reliability restrictions. We also discuss how computational economy-based approaches, such as market mechanisms, and computational paradigms, such as Neural Networks and Markov decision processes, can be used to model the users’ decisions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abraham, A., Buyya, R., Nath, B.: Nature’s heuristics for scheduling jobs on computational grids. In: Proc. of the 8th IEEE International Conference on Advanced Computing and Communications, pp. 45–52 (2000)
Abraham, A., Jainb, R., Thomasc, J., Hana, S.Y.: D-SCIDS: Distributed soft computing intrusion detection system. Journal of Network and Computer Applications 30(1), 81–98 (2007)
Ali, S., Siegel, H.J., Maheswaran, M., Hensgen, D.: Task execution time modeling for heterogeneous computing systems. In: Proceedings of Heterogeneous Computing Workshop, pp. 185–199 (2000)
Baçsar, T., Olsder, G.J.: Dynamic Non-cooperative Game Theory, 2nd edn. Academic Press, London (1995)
Bonet, B.: An Epsilon-Optimal Grid-Based Algorithm for Partially Observable Markov Decision Processes. In: Proc. of International Conference on Machine Learning - ICML 2002, pp. 51–58 (2002)
Buyya, R., Bubendorfer, K.: Market Oriented Grid and Utility Computing. Wiley Press, Chichester (2009)
Garg, S.K., Buyya, R., Segel, H.J.: Scheduling Parallel Aplications on Utility Grids: Time and Cost Trade-off Management. In: Mans, B. (ed.) Proc. of the 32nd ACSC, vol. 91, pp. 139–147. ACS (2009)
Ghosh, P., Roy, N., Basu, K., Das, S.K.: A Game Theory based Pricing Strategy for Job Allocation in Mobile Grids. In: Proc. of the 18th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2004), Santa Fe, New Mexico (2004)
Khan, S.U., Ahmad, I.: Non-cooperative, semi-cooperative, and cooperative games-based grid resource allocation. In: Proceedings of International Parallel and Distributed Proceedings Symposium (IPDPS 2006), pp. 101–104 (2006)
Kołodziej, J., Xhafa, F.: A game-theoretic and hybrid genetic meta-heuristic model for security-assured scheduling of independent jobs in computational grids. In: Barolli, L., Xhafa, F., Venticinque, S. (eds.) Proc. of CISIS 2010, pp. 93–100. IEEE Press, Los Alamitos (2010)
Kołodziej, J., Xhafa, F., Kolanko, Ł.: Hierarchic genetic scheduler of independent jobs in computational grid environment. In: Otamendi, J., Bargieł, A. (eds.) Proc. of 23rd ECMS, Madrid, June 9-12, pp. 108–115. IEEE Press, Los Alamitos (2009)
Kwok, Y.-K., Hwang, K., Song, S.: Selfish Grids: Game-Theoretic Modeling and NAS/PSA Benchmark Evaluation. IEEE Transactions on Parallel and Distributing Systems 18(5), 1–16 (2007)
Mesghouni, K., Hammadi, S., Borne, P.: Evolutionary alogorithms for job-shop scheduling. Int. J. Appl. Math. Comput. Sci. 14(1), 91–103 (2004)
Montana, D., Zinky, J.: Optimizing Routing and Backlogs for Job Flows in a Distributed Computing Environment. In: Xhafa, F., Abraham, A. (eds.) Meta-heuristics for Scheduling in Distributed Computing Environments, Springer, Heidelberg (2008)
Norman, M.: Types of grid users and the Customer-Service Provider relationship: a future picture of grid use. In: Cox, J. (ed.) Proc. of the UK e-Science All Hands Meeting, Nottingham, September 18-21, pp. 37–44 (2006)
Ritchie, G., Levine, J.: A fast effective local search for scheduling independent jobs in heterogeneous computing environments, Technical Report, Centre for Intelligent System and their Applications, School of Informatics, University of Edinburgh (2003)
Roughgarden, T.: Stackelberg scheduling strategies. SIAM Journal on Computing 2, 332–350 (2004)
Shelestov, A., Skakun, S., Kussul, O.: Intelligent Model of user Behavior in Distributed Systems. Int. Journal on “Information Theories and Applications” 15, 70–75 (2008)
Subrata, R., Zomaya, A.Y., Landfeldt, B.: Cooperative power-aware scheduling in grid computing environments. J. Parallel Distrib. Comput. 70, 84–91 (2010)
Wang, L., Wei, L., Liao, X.-K., Wang, H.: AT-RBAC: An Authentication Trustworthiness-Based RBAC Model. In: Jin, H., Pan, Y., Xiao, N., Sun, J. (eds.) GCC 2004. LNCS, vol. 3252, pp. 343–350. Springer, Heidelberg (2004)
Xhafa, F., Abraham, A.: Computational models and heuristic methods for grid scheduling problems. Future Generation Computer Systems 26, 608–621 (2010)
Xhafa, F., Carretero, J., Abraham, A.: Genetic Algorithm Based Schedulers for Grid Computing Systems. International Journal of Innovative Computing, Information and Control 3(5), 1–19 (2007)
Xhafa, F., Gonzalez, J.A., Dahal, K.P., Abraham, A.: A GA(TS) hybrid algorithm for scheduling in computational grids. In: Corchado, E., Wu, X., Oja, E., Herrero, Á., Baruque, B. (eds.) HAIS 2009. LNCS, vol. 5572, pp. 285–292. Springer, Heidelberg (2009)
Zhang, G., Sun, J.: Grid intrusion detection based on soft computing by modeling real-user’s normal behaviors. In: Proc. of IEEE International Conference on Granular Computing 2006, pp. 558–561 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Kołodziej, J., Xhafa, F. (2011). Task Allocation Oriented Users Decisions in Computational Grid. In: Bouvry, P., González-Vélez, H., Kołodziej, J. (eds) Intelligent Decision Systems in Large-Scale Distributed Environments. Studies in Computational Intelligence, vol 362. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21271-0_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-21271-0_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21270-3
Online ISBN: 978-3-642-21271-0
eBook Packages: EngineeringEngineering (R0)