A survey of bargaining models for grid resource allocation

ABSTRACT

Whereas it is noted that various types of auctions, commodity market models, and contract-net (tendering) model are more widely used for managing Grid resources, this paper focuses on discussing bargaining (negotiation) models for Grid resource management. To this end, this survey supplements and complements existing surveys by reviewing, comparing, and highlighting the very few extant research initiatives on applying bargaining as a mechanism for managing Grid resources. The contributions of this paper are (i) discussing the motivations for considering bargaining models for Grid resource management, (ii) discussing the issues in building bargaining mechanisms for Grid resource management, (iii) comparing the strategies and protocols of state-of-the-art bargaining models for Grid resources, and (iv) discussing possible new directions.

REFERENCES

• 1: A taxonomy and survey of grid resource management systems for distributed computing, Software—Practice & Experience, v.32 n.2, p.135-164, February 2002 [doi>10.1002/spe.432]
• 2: Kwang Mong Sim, From market-driven agents to market-oriented grids (position paper), ACM SIGecom Exchanges, v.5 n.2, p.45-53, November, 2004 [doi>10.1145/1120687.1120693]
• 3: {3} R. Buyya, D. Abramson, and S. Venugopal. The Grid Economy. Proceedings of the IEEE, Volume 93, Issue 3, pp. 698-714, IEEE Press, New York, USA, March 2005.
• 4: {4} R. Buyya et al. Economic models for resource management and scheduling in Grid computing. Concurrency and computation: practice and experience. Vol. 14, p1507-1542, 2002.
• 5: {5} R. Wolski, J. Brevik, J. Plank, and T. Bryan. Grid Resource Allocation and Control Using Computational Economies. In F. Berman, A. Hey, and G. Fox (eds.): Grid Computing - Making the Global Infrastructure a Reality, 2003, J. Wiley, NY.
• 6: 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]
• 7: {7} R. Wolski, J. Plank, and J. Brevik. G-Commerce -- Building Computational Marketplaces for the Computational Grid (UT Tech. Rep. #CS-00-439), 2001, http://www.cs.ucsb.edu/~rich/publications/.
• 8: Rajkumar Buyya , Sudharshan Vazhkudai, Compute Power Market: Towards a Market-Oriented Grid, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.574, May 15-18, 2001
• 9: Karl Czajkowski , Ian T. Foster , Carl Kesselman , Volker Sander , Steven Tuecke, SNAP: A Protocol for Negotiating Service Level Agreements and Coordinating Resource Management in Distributed Systems, Revised Papers from the 8th International Workshop on Job Scheduling Strategies for Parallel Processing, p.153-183, July 24, 2002
• 10: {10} K. Drexler and M. Miller. Incentive Engineering for Computational Resource Management. In B. Huberman (ed.): The Ecology of Computation, Elsevier Science, 1988, pp. 231-266.
• 11: {11} H. Gimpel et. Al. PANDA: Specifying Policies for Automated Negotiations of Service Contracts In ICSOC 2003, LNCS 2910, pp. 287-302, 2003, Springer-Verlag.
• 12: {12} F. Lang. Developing Dynamic Strategies for Multi-Issue Automated Contracting in the Agent Based Commercial Grid. In Workshop on Agent-based Grid Economics, held in conjunction with the IEEE Int. Sym. on Cluster Computing and the Grid, May 9 - 12, 2005, Cardiff, UK.
• 13: {13} P. Faratin, C. Sierra, N. R. Jennings, Negotiation Decision Functions for Autonomous Agents. Int. J. Robotics and Autonomous System. Vol. 24, No. 3: 159-182.
• 14: {14} R. Lawley et. Al. Automated Negotiation between publishers and consumers of grid notifications. Parallel Processing Letters, 13(4): pp. 537-548, 2003.
• 15: Kwang Mong Sim, From Market-Driven e-Negotiation to Market-Driven G-Negotiation, Proceedings of the 2005 IEEE International Conference on e-Technology, e-Commerce and e-Service (EEE'05) on e-Technology, e-Commerce and e-Service, p.408-413, March 29-April 01, 2005 [doi>10.1109/EEE.2005.78]
• 16: {16} K. M. Sim. A Market-driven Model for Designing Negotiation Agents. In Computational Intelligence, Special issue in Agent Tech. for E-commerce, vol. 18, no. 4, 2002, pp. 618-637.
• 17: {17} K. M. Sim and C. Y. Choi. Agents that React to Changing Market Situations. IEEE Trans. Syst., Man Cybern B: Cybernetics, Vol. 33, No. 2, April 2003, pp. 188-201.
• 18: {18} K. M. Sim. Equilibria, Prudent Compromises, and the "Waiting" Game. IEEE Trans. on Systems, Man and Cybernetics, Part B: Cybernetics, Vol. 35, No. 4, Aug. 2005, pp. 712-724.
• 19: {19} K. M. Sim. Negotiation agents that make prudent compromises and are slightly flexible in reaching consensus. Computational intelligence, Vol. 20, No. 4, 2004, pp. 643-662.
• 20: {20} K. M. Sim. and S. Y. Wang. Flexible Negotiation Agent with Relaxed Decision Rules. IEEE Trans. on Systems, Man & Cybernetics, Part B, Vol. 34, No. 3, Jun. 2004, pp. 1602-1608.
• 21: {21} P. Ghosh, N. Roy, S. K. Das, and K. Basu, "A Game Theory Based Pricing Strategy for Job Allocation in Mobile Grids," Proc. Int. Parallel and Distributed Processing Sym., 2004.
• 22: {22} G. Kennedy, Field Guide to Negotiation. Cambridge, MA: Harvard Business Sch. Press, 1994.
• 23: K.-M. Chao , R. Anane , J.-H. Chen , R. Gatward, Negotiating Agents in a Market-Oriented Grid, Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, p.436, May 21-24, 2002
• 24: Junwei Cao , Darren J. Kerbyson , Graham R. Nudd, Performance Evaluation of an Agent-Based Resource Management Infrastructure for Grid Computing, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.311, May 15-18, 2001
• 25: {25} B. Schnizler, D. Neumann, C. Weinhardt. Resource Allocation in Computational Grids - A Market Engineering Approach http://www.iw.unikarlsruhe.de/Publications/SchnizlerNeumannWeinhardt_04_ResourceAllocation.pdf In Proceedings of the WeB 2004, Washington.
• 26: T. Eymann , M. Reinicke , O. Ardaiz , P. Artigas , F. Freitag , L. Navarro, Decentralized Resource Allocation in Application Layer Networks, Proceedings of the 3st International Symposium on Cluster Computing and the Grid, p.645, May 12-15, 2003
• 27: Tuomas W. Sandholm, Distributed rational decision making, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, Cambridge, MA, 1999
• 28: {28} A. Rubinstein, "Perfect equilibrium in a bargaining model," Econometrica, 50 (1), pp. 97-109.
• 29: Shaheen S. Fatima , Michael Wooldridge , Nicholas R. Jennings, Bargaining with incomplete information, Annals of Mathematics and Artificial Intelligence, v.44 n.3, p.207-232, July 2005 [doi>10.1007/s10472-005-4688-7]
• 30: {30} A. R. Lomuscio, M. Wooldridge, and N. R. Jennings, "A classification scheme for negotiation in electronic commerce," Int. J. Group Decision Negotiation, vol. 12, no. 1, pp. 31-56, 2003.
• 31: {31} J. C. Harsanyi 1989. Bargaining, In The New Palgrave: Game Theory, edited by John Eatwell, Murray Milgate, and Peter Newman, 1st edition, The Macmillan Press Limited, 1989.
• 32: {32} K. M. Sim (P.I.). Grid Commerce, Market-driven G-Negotiation, and Grid Resource Allocation. Project funded by the Faculty of Science in the Hong Kong Baptist University (project number: FRG/04-05/II-65).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

General Terms:
Design, Documentation, Economics

Keywords:
automated negotiation, bargaining, computational economy, grid resource allocation, grid resource management