A Market Design for Grid Computing
Authors:
- 1 February 2008
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 20 (1) , 100-111
Abstract
Grid computing uses software to integrate computing resources, such as CPU cycles, storage, network bandwidth, and even applications, across a distributed and heterogeneous set of networked computers. It is now widely deployed by organizations and provides seamless temporary processing-capacity expansion to handle peak-period demand on e-commerce servers, distributed gaming, and content storage and distribution. We develop a market-based resource-allocation model that adds an economic layer to the current approach of treating resource allocation as primarily a scheduling issue. We design a value-elicitation and allocation scheme that provides the economic incentives for buyers and sellers of computing resources to exchange assets. We formulate the problem as a combinatorial call auction and present a portfolio of three solution approaches that trade off economic properties, such as allocative efficiency, incentive compatibility, and fairness in allocation, with computational efficiency. The first of these is an efficient solution that maximizes social welfare and yields incentive-compatible Vickrey-Clarke-Groves prices, but requires solving multiple instances of an NP-hard problem. For markets where having a commodity price is critical, we show how the addition of fairness constraints to the efficient model can somewhat reduce the computational burden and yet preserve incentive compatibility. Finally, for markets that require real-time fast solution techniques, we propose a time-sensitive fair Grid (tsfGRID) heuristic that relaxes the maximal allocation requirement of the welfare-maximizing fair solution. Its solution is not guaranteed to be incentive-compatible, but the heuristic is designed to be fast, maintain fairness in allocations, and yield commodity prices. Notably, while incentive compatibility is not guaranteed by tsfGRID, computational results comparing it with the efficient solution technique indicate that there are no significant differences in the expected-revenue and operational-allocative characteristics.Keywords
This publication has 20 references indexed in Scilit:
- An Efficient Dynamic Auction for Heterogeneous CommoditiesAmerican Economic Review, 2006
- Computational Grids in action: the National Fusion CollaboratoryFuture Generation Computer Systems, 2002
- The GrADS Project: Software Support for High-Level Grid Application DevelopmentThe International Journal of High Performance Computing Applications, 2001
- Analyzing Market-Based Resource Allocation Strategies for the Computational GridThe International Journal of High Performance Computing Applications, 2001
- Predicting application run times using historical information1998
- Utilizing the metaserver architecture in the Ninf global computing system1998
- Spawn: a distributed computational economyIEEE Transactions on Software Engineering, 1992
- Incentives in TeamsEconometrica, 1973
- Multipart pricing of public goodsPublic Choice, 1971
- COUNTERSPECULATION, AUCTIONS, AND COMPETITIVE SEALED TENDERSThe Journal of Finance, 1961