Decentralized job scheduling in the cloud based on a spatially generalized Prisoner’s Dilemma game

Gąsior, J. ; Seredyński, F.

International Journal of Applied Mathematics and Computer Science, Tome 25 (2015) no. 4, pp. 737-751.

Résumé

We present in this paper a novel distributed solution to a security-aware job scheduling problem in cloud computing infrastructures. We assume that the assignment of the available resources is governed exclusively by the specialized brokers assigned to individual users submitting their jobs to the system. The goal of this scheme is allocating a limited quantity of resources to a specific number of jobs minimizing their execution failure probability and total completion time. Our approach is based on the Pareto dominance relationship and implemented at an individual user level. To select the best scheduling strategies from the resulting Pareto frontiers and construct a global scheduling solution, we developed a decision-making mechanism based on the game-theoretic model of Spatial Prisoner’s Dilemma, realized by selfish agents operating in the two-dimensional cellular automata space. Their behavior is conditioned by the objectives of the various entities involved in the scheduling process and driven towards a Nash equilibrium solution by the employed social welfare criteria. The performance of the scheduler applied is verified by a number of numerical experiments. The related results show the effectiveness and scalability of the scheme in the presence of a large number of jobs and resources involved in the scheduling process.

Détail

Keywords: job scheduling, multiobjective optimization, genetic algorithm, prisoner's dilemma, cellular automata
Mots-clés : harmonogramowanie zadań, optymalizacja wielokryterialna, algorytm genetyczny, dylemat więźnia, automat komórkowy

Bibliographie

[1] An, B., Miao, C. and Shen, Z. (2007). Market based resource allocation with incomplete information, in M. Veloso (Ed.), Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAI’07, Morgan Kaufmann Publishers Inc., San Francisco, CA, pp. 1193–1198.

[2] Brandic, I., Pllana, S. and Benkner, S. (2006). An approach for the high-level specification of QoS-aware grid workflows considering location affinity, Workshop on Workflows in Support of Large-Scale Science, WORKS’06, Paris, France, Vol. 14, pp. 231–250.

[3] Christodoulou, G., Koutsoupias, E. and Vidali, A. (2007). A lower bound for scheduling mechanisms, in H. Gabow (Ed.), Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’07, Society for Industrial and Applied Mathematics, Philadelphia, PA, pp. 1163–1170.

[4] Deb, K., Agrawal, S., Pratap, A. and Meyarivan, T. (2000). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimisation: NSGA-II, in M. Schoenauer et al. (Eds.), Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, PPSN VI, Springer-Verlag, London, pp. 849–858.

[5] Even-Dar, E., Kesselman, A. and Mansour, Y. (2007). Convergence time to Nash equilibrium in load balancing, ACM Transactions on Algorithms 3(3): 111–132.

[6] Hwang, S. and Kesselman, C. (2003). A flexible framework for fault tolerance in the grid, Journal of Grid Computing 1(3): 251–272.

[7] Katsumata, Y. and Ishida, Y. (2008). On a membrane formation in a spatio-temporally generalized prisoner’s dilemma, in H. Umeo et al. (Eds.), Proceedings of the 8th International Conference on Cellular Automata for Research and Industry, ACRI’08, Springer-Verlag, Berlin/Heidelberg, pp. 60–66.

[8] Khan, S.U. and Ahmad, I. (2006). Non-cooperative, semi-cooperative, and cooperative games-based grid resource allocation, 20th International Parallel and Distributed Processing Symposium, IPDPS 2006, Rhodes, Greece.

[9] Kolodziej, J. and Xhafa, F. (2011). Meeting security and user behavior requirements in grid scheduling, Simulation Modelling Practice and Theory 19(1): 213–226.

[10] Lee, Y. and Zomaya, A. (2012). Energy efficient utilization of resources in cloud computing systems, The Journal of Supercomputing 60(2): 268–280.

[11] Li, Z.-J., Cheng, C.-T. and Huang, F.-X. (2009). Utility-driven solution for optimal resource allocation in computational grid, Computer Languages, Systems Structures 35(4): 406–421.

[12] Lin, C., Varadharajan, V., Wang, Y. and Pruthi, V. (2004). Enhancing grid security with trust management, in L.-J. Zhang, J. Zhang and H. Cai (Eds.), Proceedings of the 2004 IEEE International Conference on Services Computing, SCC’04, IEEE Computer Society, Washington, DC, pp. 303–310.

[13] Londoño, J., Bestavros, A. and Teng, S.-H. (2009). Collocation games and their application to distributed resource management, Proceedings of the 2009 Conference on Hot Topics in Cloud Computing, HotCloud’09, San Diego, CA, USA.

[14] Nowak, M.A. and May, R.M. (1992). Evolutionary games and spatial chaos, Nature 359: 826.

[15] Palmieri, F., Buonanno, L., Venticinque, S., Aversa, R. and Di Martino, B. (2013). A distributed scheduling framework based on selfish autonomous agents for federated cloud environments, Future Generation Computer Systems 29(6): 1461–1472.

[16] Perc, M. and Szolnoki, A. (2008). Social diversity and promotion of cooperation in the spatial prisoner’s dilemma game, Physical Review E 77: 011904.

[17] Song, S., Hwang, K. and Kwok, Y.-K. (2006). Risk-resilient heuristics and genetic algorithms for security-assured grid job scheduling, IEEE Transactions on Computers 55(6): 703–719.

[18] Sookhak, M., Akhunzada, A., Talebian, H., Gani, A., Khan, S., Buyya, R. and Zomaya, A.Y. (2015). Remote data auditing in cloud computing environments: A survey, taxonomy, and open issues, ACM Computing Surveys 47(4), Article no. 65.

[19] Switalski, P. and Seredynski, F. (2011). An efficient evolutionary scheduling algorithm for parallel job model in grid environment, in V. Malyshkin (Ed.), Proceedings of the 11th International Conference on Parallel Computing Technologies, PaCT’11, Springer-Verlag, Berlin/Heidelberg, pp. 347–357.

[20] Szabó, G., Vukov, J. and Szolnoki, A. (2005). Phase diagrams for Prisoner’s Dilemma game on two-dimensional lattices, Physical Review E 72(4).

[21] Tchernykh, A., Schwiegelshohn, U., Yahyapour, R. and Kuzjurin, N. (2010). On-line hierarchical job scheduling on grids with admissible allocation, Journal of Scheduling 13(5): 545–552.

[22] Tziritas, N., Xu, C.-Z., Loukopoulos, T., Khan, S. and Yu, Z. (2013). Application-aware workload consolidation to minimize both energy consumption and network load in cloud environments, 42nd International Conference on Parallel Processing (ICPP), Lyon, France, pp. 449–457.

[23] Wu, C.-C. and Sun, R.-Y. (2010). An integrated security-aware job scheduling strategy for large-scale computational grids, Future Generation Computer Systems 26(2): 198–206.