Improved algorithmic mechanism based on game theory in computational grids
Tóm tắt
Computational grids (CGs) aim to offer pervasive access to a diverse collection of geographically distributed resources owned by different self-interested agents or organizations. These agents may manipulate the resource allocation algorithm in their own benefit, and their selfish behavior may lead to severe performance degradation and poor efficiency. In this paper, game theory is introduced to solve the problem of barging for resource collection in heterogeneous distributed systems. By using the Cournot model that is an important model in static and complete information games, the algorithm is optimized in order to maximize the benefit. It can be seen that the approach is more suitable to the real situation and has practical use. Validity of the solutions is shown.
Tài liệu tham khảo
Foster I, Kesselman C. The Grid: Blueprint for a New Computing Infrastructure[M]. San Francisco: Morgan Kaufman Publishers, 1999.
Roughgarden T, Tardos E. How bad is selfish routing[J]. Journal of the ACM, 2002, 49(2): 236–259.
Osborne M, Rubinstein A. A Course in Game Theory[M]. Cambridge, Mass.: MIT Press, 1994.
Buyya R. Economic-Based Distributed Resource Management and Scheduling for Grid Computing[D]. Doctoral Dissertation, Australia: Monash University, 2002.
Nisan N, Ronen A. Computationally feasible VCG mechanism[C]// Proceedings of 2nd ACM Confences Electronic Commerce. 2000: 242–252.
Archer A, Tardos E. Truthful mechanism for one-parameter agents[C]// Proceedings of 42nd IEEE Symposium Foundations Computer Science, Las Vegas, Nevada. 2001: 482–491.
Tantawi A N, Towsley D. Optimal static load balancing in distributed computer systems[J]. Journal of the ACM, 1985, 32(2): 445–465.
Kim C, Kameda H. An algorithm for optimal static load balancing in distributed computer systems[J]. IEEE Transaction on Computers, 1992, 41(3): 381–384.
Li Jie, Kameda H. A decomposition algorithm for optimal static load balancing in tree hierarchy network configuration[J]. IEEE Transaction on Parallel and Distributed System, 1994, 5(5): 540–548.
Li Jie, Kameda H. Optimal static load balancing in star network configurations with two-way traffic[J]. Journal of Parallel and Distributed Computing, 1994, 23(3): 364–375.
Tang X, Chanson S T. Optimizing static job scheduling in a network of heterogeneous computers[C]// Proceedings of the International Conference on Parallel Processing, Toronto. 2000: 373–382.
Lee H. Optimal static distribution of prioritized customers to heterogeneous parallel servers[J]. Computers and Operations Research, 1995, 22(9): 995–1003.
Li Jie, Kameda H. Load balancing problems for multiclass jobs in distributed/parallel computer systems[J]. IEEE Transaction on Computers, 47(3): 322–332.
Grosu D, Chronopoulos A T, Leung M Y. Load balancing in distributed systems: An approach using cooperative games[C]// Proceedings of 16th IEEE International Parallel Distributed Processing Symposium, Fort Lauderdale. 2002:52–61.
Grosu D, Chronopoulos A T. Algorithmic mechanism design for load balancing in distributed systems[J]. IEEE Transaction on Systems, Man and Cybernetics, Part B: Cybernetics, 2004, 34(1): 77–84.
Cardell J B, Hitt C C, Hogan W W. Market power and strategic interaction in electricity networks[J]. Resources and Energy Economics, 1997, 19(1–2): 109–137.
Bushnell J B. Looking for Trouble: Competition Policy in the US Electricity Industry[M]. University of Berkeley, California Energy Institute, Center for the Study of Energy Markets, 2003.
Chattopadhyay D. Multi-Area Spatial Cournot Model for Generator Bidding Analysis[M]. Wellington, New Zealand: Charles River Associates, 2003.
Chattopadhyay D. A game theoretic model for strategic maintenance and dispatch decisions[J]. IEEE Transaction on Power Systems, 2004, 19(4): 2014–2021.