Forming resource-sharing coalitions: a distributed resource allocation mechanism for self-interested agents in computational grids

ABSTRACT

Designing efficient resource allocation mechanism for computational grids is extremely challenging because the effective agents in computational grids are inherently self-interested due to their different ownerships. Providing incentive for agents to share their resource with others is the key to make computational grids realistic. The global efficiency should be generated through the interactions among agents from the bottom up. In game theory, forming coalition is such a cooperative game among self-interested agents. We develop a distributed resource allocation mechanism for computational grids by forming resource-sharing coalitions among self-interested agents through automated multiparty negotiation. This mechanism is based on a task-oriented mechanism for measuring the economic value of computational resource usage. The simulation results show that the self-interests of agents in computational grids have considerable impact on the decisions of each agent about how to allocate their resource to appropriate tasks.

REFERENCES

• 1: Fran Berman , Geoffrey Fox , Anthony J. G. Hey , Tony Hey, Grid Computing: Making the Global Infrastructure a Reality, John Wiley & Sons, Inc., New York, NY, 2003
• 2: Buyya, R. Economic-Based Distributed Resource Management and Scheduling for Grid Computing. Ph.D. Dissertation, 2002.
• 3: Philippe Caillou , Samir Aknine , Suzanne Pinson, A multi-agent method for forming and dynamic restructuring of pareto optimal coalitions, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy [doi>10.1145/545056.545075]
• 4: Scott H. Clearwater, Market-based control: a paradigm for distributed resource allocation, World Scientific Publishing Co., Inc., River Edge, NJ, 1996
• 5: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 6: He, L. and Ioerger, T. R., A Quantitative Model of Capabilities in Multi-Agent Systems, in Proceedings of the International Conference on Artificial Intelligence, 2003.
• 7: Linli He , Thomas R. Ioerger, Combining bundle search with buyer coalition formation in electronic markets: a distributed approach through explicit negotiation, Proceedings of the 6th international conference on Electronic commerce, October 25-27, 2004, Delft, The Netherlands [doi>10.1145/1052220.1052233]
• 8: Kahan, J. P. and Rapoport, A., Theories of Coalition Formation, Lwarence Erlbaum Associates, Inc., London, 1984.
• 9: Sarit Kraus, Strategic negotiation in multiagent environments, MIT Press, Cambridge, MA, 2001
• 10: Zhiling Lan , Valerie E. Taylor , Greg Bryan, A novel dynamic load balancing scheme for parallel systems, Journal of Parallel and Distributed Computing, v.62 n.12, p.1763-1781, December 2002 [doi>10.1016/S0743-7315(02)00008-4]
• 11: 0. Shehory, Coalition Formation for Large-Scale Electronic Markets, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.167, July 10-12, 2000
• 12: Cuihong Li , Katia Sycara, Algorithm for combinatorial coalition formation and payoff division in an electronic marketplace, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544771]
• 13: Proter, M. E., Competitive Strategy, The Free Press, New York, 1980.
• 14: Jeffrey S. Rosenschein , Gilad Zlotkin, Rules of encounter: designing conventions for automated negotiation among computers, MIT Press, Cambridge, MA, 1994
• 15: Sandholm, T. Making Markets and Democracy Work: A Story of Incentives and Computing, in Proceedings of IJCAI, 2003.
• 16: Tuomas Sandholm , Kate Larson , Martin Andersson , Onn Shehory , Fernando Tohmé, Coalition structure generation with worst case guarantees, Artificial Intelligence, v.111 n.1-2, p.209-238, July 1999 [doi>10.1016/S0004-3702(99)00036-3]
• 17: Tuomas Wilhelm Sandholm , Victor R. Lesser, Negotiation among self-interested computationally limited agents, 1996
• 18: Tuomas Sandholm , Victor Lesser, Leveled-commitment contracting: a backtracking instrument for multiagent systems, AI Magazine, v.23 n.3, p.89-100, Fall 2002
• 19: Shehory, O. and Kraus, S., Feasible formation of coalitions among autonomous agents in non-super-additive environments, Computational Intelligence, vol. 15(3), 218--251, 1999.
• 20: Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9]
• 21: Leigh Tesfatsion, Agent-Based Computational Economics: Growing Economies From the Bottom Up, Artificial Life, v.8 n.1, p.55-82, March 2002 [doi>10.1162/106454602753694765]
• 22: Wolski, R., Brevik, J., Plank, J., and Bryan, T., Grid Resource Allocation and Control Using Computational Economies, In Grid Computing: Making the Global Infrastructure a Reality Berman, F, Fox, G., and Hey, T. editors, Wiley and Sons, pp. 747--772, 2003.
• 23: Rich Wolski , James S. Plank , John Brevik , Todd Bryan, Analyzing Market-Based Resource Allocation Strategies for the Computational Grid, International Journal of High Performance Computing Applications, v.15 n.3, p.258-281, August 2001 [doi>10.1177/109434200101500305]

INDEX TERMS

General Terms:
Algorithms, Design, Economics, Measurement

Keywords:
coalition formation, computational grids, self-interested agent