Abstract
To improve the resource utilization and satisfy more users, a Greedy Double Auction Mechanism(GDAM) is proposed to allocate resources in grid environments. GDAM trades resources at discriminatory price instead of uniform price, reflecting the variance in requirements for profits and quantities. Moreover, GDAM applies different auction rules to different cases, over-demand, over-supply and equilibrium of demand and supply. As a new mechanism for grid resource allocation, GDAM is proved to be strategy-proof, economically efficient, weakly budget-balanced and individual rational. Simulation results also confirm that GDAM outperforms the traditional one on both the total trade amount and the user satisfaction percentage, specially as more users are involved in the auction market.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Buyya, R., Abramson, D., Giddy, J.: A case for economy grid architecture for service oriented grid computing. In: IPDPS 2001: Proceedings of the 15th International Parallel & Distributed Processing Symposium, Washington, DC, USA, p. 83. IEEE Computer Society, Los Alamitos (2001)
Buyya, R., Abramson, D., Venugopal, S.: The grid economy. Proceedings of the IEEE, 698–714 (2005)
Sutherland, I.E.: A futures market in computer time. Communications of the ACM 11(6), 449–451 (1968)
Buyya, R.: Economic-based distributed resource management and scheduling for grid computing. PhD thesis, Monash University, Melbourne, Australia (2002)
Regev, O., Nisan, N.: The popcorn market - an online markets for computational resources. In: ICE 1998: Proceedings of the First International Conference on Information and Computation Economies, pp. 148–157. ACM, New York (1998)
Waldspurger, C.A., Hogg, T., Huberman, B.A., Kephart, J.O., Stornetta, S.W.: Spawn: A distributed computational economy. IEEE Transactions on Software Engineering 18(2), 103–117 (1992)
Bubendorfer, K.: Fine grained resource reservation in open grid economies. In: E-SCIENCE 2006: Proceedings of the Second IEEE International Conference on e-Science and Grid Computing, p. 81. IEEE Computer Society, Los Alamitos (2006)
Lalis, S., Karipidis, A.: Jaws: An open market-based framework for distributed computing over the internet. In: GRID 2000: Proceedings of the First IEEE/ACM International Workshop on Grid Computing, London, UK, pp. 36–46. Springer, Heidelberg (2000)
Lai, K., Rasmusson, L., Adar, E., Sorkin, S., Zhang, L., Huberman, B.A.: Tycoon: an implemention of a distributed market-based resource allocation system. Technical report, HP Labs (2004)
Satterthwaite, M.A., Williams, S.R.: The rate of convergence to efficiency in the buyer’s bid double auction as the market becomes large. The Review of Economic Studies 54(6), 477–498 (1989)
Williams, S.R.: Existence and convergence of equilibria in the buyer’s bid double auction. The Review of Economic Studies 58(2), 351–374 (1991)
Yokoo, M., Sakurai, Y., Matsubara, S.: Robust double auction protocol against false-name bids. In: ICDCS 2001: Proceedings of the The 21st International Conference on Distributed Computing Systems, Washington, DC, USA, pp. 137–145. IEEE Computer Society, Los Alamitos (2001)
Huang, P., Scheller-wolf, A., Sycara, K.: Design of a multiunit double auction e-market. Computational Intelligence 18(4), 596–617 (2002)
Kant, U., Grosu, D.: Double auction protocols for resource allocation in grids. In: ITCC 2005: Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC 2005), Washington, DC, USA, vol. I, pp. 366–371. IEEE Computer Society, Los Alamitos (2005)
Liu, Y., He, H.C.: Multi-unit combinatorial auction based grid resource co-allocation approach. In: SKG 2007: Proceedings of the Third International Conference on Semantics, Knowledge and Grid, Washington, DC, USA, pp. 290–293. IEEE Computer Society, Los Alamitos (2007)
Gonen, R., Lehmann, D.: Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics. In: EC 2000: Proceedings of the 2nd ACM Conference on Electronic Commerce, pp. 13–20. ACM, New York (2000)
Chien, C.H., Chang, P.H.M., Soo, V.W.: Market-oriented multiple resource scheduling in grid computing environments. In: AINA 2005: Proceedings of the 19th International Conference on Advanced Information Networking and Applications, Washington, DC, USA, pp. 867–872. IEEE Computer Society, Los Alamitos (2005)
Wieczorek, M., Podlipnig, S., Prodan, R., Fahringer, T.: Applying double auctions for scheduling of workflows on the grid. In: SC 2008: Proceedings of the 2008 ACM/IEEE Conference on Supercomputing, Piscataway, NJ, USA, pp. 1–11. IEEE Press, Los Alamitos (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ding, D., Luo, S., Gao, Z. (2010). A Greedy Double Auction Mechanism for Grid Resource Allocation. In: Frachtenberg, E., Schwiegelshohn, U. (eds) Job Scheduling Strategies for Parallel Processing. JSSPP 2010. Lecture Notes in Computer Science, vol 6253. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16505-4_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-16505-4_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16504-7
Online ISBN: 978-3-642-16505-4
eBook Packages: Computer ScienceComputer Science (R0)