IISc Logo    Title

etd AT Indian Institute of Science >
Division of Electrical Sciences >
Computer Science and Automation (csa) >

Please use this identifier to cite or link to this item: http://etd.iisc.ernet.in/2005/553

Title: A Mechanism Design Approach To Resource Procurement In Computational Grids With Rational Resource Providers
Authors: Prakash, Hastagiri
Advisors: Narahari, Y
Keywords: Computational Grids
Multiprocessing (Electronic Digital Computers)
Grid Computing
Grid Resource Management
Mechanism Design
G-DISC (Grid-Dominant Strategy Incentive Compatible) Mechanism
G-BIC (Grid-Bayesian Nash Incentive Compatible) Mechanism
G-OPT (Grid-Optimal) Mechanism
Incentive Compatibility (IC)
Rational Resource Providers
Grid Resource Procurement
Submitted Date: Oct-2006
Series/Report no.: G20533
Abstract: 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 efficiency of the computational grid in comparison to what can be achieved when the participating users are centrally coordinated . This loss in efficiency 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. Specifically, we follow a game theoretic and mechanism design approach to design three elegant, different 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 payoffs 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.
URI: http://etd.iisc.ernet.in/handle/2005/553
Appears in Collections:Computer Science and Automation (csa)

Files in This Item:

File Description SizeFormat
G20533.pdf986 kBAdobe PDFView/Open

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.


etd@IISc is a joint service of SERC & IISc Library ||
|| Powered by DSpace || Compliant to OAI-PMH V 2.0 and ETD-MS V 1.01