TY - JOUR
T1 - Selfish grids
T2 - Game-theoretic modeling and NAS/PSA benchmark evaluation
AU - Kwok, Yu Kwong
AU - Hwang, Kai
AU - Song, Shan Shan
N1 - Funding Information:
The authors would like to thank the anonymous reviewers (in particular, Reviewers 2 and 3) for their constructive suggestions to improve the quality and presentation of this paper. Thanks are also due to Professor Xiaodong Zhang for his useful suggestions on the final version of the manuscript. Finally, the authors thank the members of the University of Southern California GridSec research team for their inspiring comments about this research. This paper is significantly extended from the conference version submitted to the IEEE/ACM CCCGrid 2005. This research was supported by an NSF ITR Research Grant under contract number ACI-0325409.
PY - 2007/5
Y1 - 2007/5
N2 - Selfish behaviors of individual machines in a Grid can potentially damage the performance of the system as a whole. However, scrutinizing the Grid by taking into account the noncooperativeness of machines is a largely unexplored research problem. In this paper, we first present a new hierarchical game-theoretic model of the Grid that matches well with the physical administrative structure in real-life situations. We then focus on the impact of selfishness in intrasite job execution mechanisms. Based on our novel utility functions, we analytically derive the Nash equilibrium and optimal strategies for the general case. To study the effects of different strategies, we have also performed extensive simulations by using a well-known practical scheduling algorithm over the NAS (Numerical Aerodynamic Simulation) and the PSA (Parameter Sweep Application) workloads. We have studied the overall job execution performance of the Grid system under a wide range of parameters. Specifically, we find that the Optimal selfish strategy significantly outperforms the Nash selfish strategy. Our performance evaluation results can serve as a valuable reference for designing appropriate strategies in a practical Grid.
AB - Selfish behaviors of individual machines in a Grid can potentially damage the performance of the system as a whole. However, scrutinizing the Grid by taking into account the noncooperativeness of machines is a largely unexplored research problem. In this paper, we first present a new hierarchical game-theoretic model of the Grid that matches well with the physical administrative structure in real-life situations. We then focus on the impact of selfishness in intrasite job execution mechanisms. Based on our novel utility functions, we analytically derive the Nash equilibrium and optimal strategies for the general case. To study the effects of different strategies, we have also performed extensive simulations by using a well-known practical scheduling algorithm over the NAS (Numerical Aerodynamic Simulation) and the PSA (Parameter Sweep Application) workloads. We have studied the overall job execution performance of the Grid system under a wide range of parameters. Specifically, we find that the Optimal selfish strategy significantly outperforms the Nash selfish strategy. Our performance evaluation results can serve as a valuable reference for designing appropriate strategies in a practical Grid.
KW - Grid computing
KW - NAS workload
KW - Nash equilibrium
KW - Noncooperative games
KW - Online scheduling
KW - Optimal strategies
KW - Parameter sweep application (PSA)
KW - Performance evaluation
KW - Selfish behaviors
KW - Virtual organizations
UR - http://www.scopus.com/inward/record.url?scp=34247628327&partnerID=8YFLogxK
U2 - 10.1109/TPDS.2007.1013
DO - 10.1109/TPDS.2007.1013
M3 - Article
AN - SCOPUS:34247628327
SN - 1045-9219
VL - 18
SP - 621
EP - 636
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 5
ER -