A Mechanism Design Approach To Resource Procurement In Computational Grids With Rational Resource Providers
MetadataShow full item record
A computational grid is a hardware and software infrastructure that provides dependable, consistent, pervasive, and inexpensive access to high-end computational capabilities. In the presence of grid users who are autonomous, rational, and intelligent, there is an overall degradation of the total eﬃciency of the computational grid in comparison to what can be achieved when the participating users are centrally coordinated . This loss in eﬃciency might arise due to an unwillingness on the part of some of the grid resource providers to either not perform completely or not perform to the fullest capability, the computational jobs of other users in the grid. In this thesis, our attention is focused on designing grid resource procurement mechanisms which a grid user can use for procuring resources in a computational grid based on bids submitted by autonomous, rational, and intelligent resource providers. Speciﬁcally, we follow a game theoretic and mechanism design approach to design three elegant, diﬀerent incentive compatible procurement mechanisms for this purpose: G-DSIC (Grid-Dominant Strategy Incentive Compatible) mechanism which guarantees that truthful bidding is a best response for each resource provider, irrespective of what the other resource providers bid G-BIC (Grid-Bayesian Nash Incentive Compatible) mechanism which only guarantees that truthful bidding is a best response for each resource provider whenever all other resource providers also bid truthfully G-OPT (Grid-Optimal) mechanism which minimizes the cost to the grid user, satisfying at the same time, (1) Bayesian Incentive Compatibility (which guarantees that truthful bidding is a best response for each resource provider whenever all other resource providers also bid truthfully) and (2) Individual Rationality (which guarantees that the resource providers have non-negative payoﬀs if they participate in the bidding process). We evaluate the relative merits and demerits of the above three mechanisms using game theoretical analysis and numerical experiments. The mechanisms developed in this thesis are in the context of parameter sweep type of jobs, which consist of multiple homogeneous and independent tasks. We believe the use of the mechanisms proposed transcends beyond parameter sweep type of jobs and in general, the proposed mechanisms could be extended to provide a robust way of procuring resources in a computational grid where the resource providers exhibit rational and strategic behavior.
Showing items related by title, author, creator and subject.
Roy, Sharmili (2011-02-25)The aim of the work is to examine the issue of pricing network resources so as to ensure fair and efficient resource-sharing among users. The basic question we address is: Do there exist simple pricing schemes such that ...
Hiremath, Rahul B (2010-02-18)The energy-planning involves finding a set of sources and conversion devices so as to meet the energy requirements/demands of all the activities in an optimal manner. This could occur at centralized or decentralized level. ...
Swarm Intelligence And Evolutionary Computation For Single And Multiobjective Optimization In Water Resource Systems Reddy, Manne Janga (2008-10-03)Most of the real world problems in water resources involve nonlinear formulations in their solution construction. Obtaining optimal solutions for large scale nonlinear optimization problems is always a challenging task. ...