Title :
A Novel Algorithm for Task Scheduling in Grid Computing Based on Game Theory
Author :
Yao, Lei ; Dai, Guanzhong ; Zhang, Huixiang ; Ren, Shuai ; Niu, Yun
Author_Institution :
Coll. of Autom., Northwestern Polytech Univ., Xi´´an
Abstract :
In the resource-rich grid computing environment, there are plenty of idle resources that compete for similar tasks. In order to make resources gained the maximum benefit, a guarantee of victorious probability algorithm (GVP) based on game theory is presented in this paper. This algorithm predicts the action of adversaries based on historical information, and determines its own action based on the forecast. We use GridSim toolkit to implement a resource-rich environment and verify our algorithm through experiments. The experimental results show that the resources using GVP algorithm can be close to their expectation of victorious probability comparing with the other resources using the random algorithms. The two-player game and multi-player game are discussed and a more in-depth analysis is made. Finally the Nash equilibrium of game among resources is also discussed.
Keywords :
game theory; grid computing; processor scheduling; GridSim toolkit; Nash equilibrium; game theory; grid computing; task scheduling; victorious probability algorithm; Drugs; Educational institutions; Game theory; Grid computing; High performance computing; Nash equilibrium; Prediction algorithms; Processor scheduling; Resource management; Scheduling algorithm; Game Theory; Grid Computing; Nash Equilibrium; Resource-Rich; Task Scheduling;
Conference_Titel :
High Performance Computing and Communications, 2008. HPCC '08. 10th IEEE International Conference on
Conference_Location :
Dalian
Print_ISBN :
978-0-7695-3352-0
DOI :
10.1109/HPCC.2008.74