PDF《A Game-Theoretic Approach》

Formation of Virtual Organizations in Grids: A Game-Theoretic Approach Thomas E.

Carroll

1 , Daniel Grosu

2 Dept. of Computer Science, Wayne State University

5143 Cass Avenue, Detroit, Michigan

48202 USA

1 [email protected]

2 [email protected] Abstract― Applications require the composition of resources to execute in a grid computing environment. The Grid Service Providers (GSPs), the owners of the computational resources, must form Virtual Organizations (VOs) to be able to provide the composite resource. We consider grids as self-organizing systems composed of autonomous, self-interested GSPs that will organize themselves into VOs with every GSP having the objective of max- imizing its pro?t. Using game theory, we formulate the resource composition among GSPs as a coalition formation problem and propose a framework based on cooperation structures to model it. Using this framework, we propose a resource management system that supports the VO formation among GSPs in a grid computing system. I. INTRODUCTION Grid computing is the preferred computational platform of choice for collaborative, resource intensive applications which are typical in the domains of science and engineering [1]. There are two classes of participants in the grid, the users and the service providers. The users submit applications to be executed. The service providers, who are geographically distributed over the world, provide and operate resources to execute programs. Each provider has its own administrative domain and thus it is largely autonomous. Applications require the composition of resources owned by several Grid Service Providers (GSPs). Service providers will form Virtual Organizations (VOs) [1] to provide the necessary resources on a dynamic, per application basis. The VO may dissolve as soon as the application has completed execution. Execution results in the service providers incurring costs (e.g., power, administrators wages and time). If we assume that the service providers are rational (self-interested and welfare- maximizing), they will refuse to offer their resources unless they can recover their costs. The rationality assumption permits analysis by economic models. Of particular interest are coalitional games, which are studied in game theory. Coalitional games model the interactions between groups of decision-makers. In this case the decision-makers are the service providers. The service providers form VOs in such a way that each provider maxi- mizes its own pro?t. The VOs provide the composite resource needed to execute applications. A VO is traditionally conceived for the sharing of resources, but it can also represent a business model [1]. In this work, a VO is a coalition of GSPs who desire to maximize their individual pro?ts and are largely indifferent about the global welfare. In this paper we examine VO formation using models from coalitional game theory. We assume that a grid user submits a program and a speci?cation consisting of a deadline and payment. A VO will form and execute the program. If the VO completes the program before the deadline, the VO will be paid;

otherwise, the VO incurs the cost of execution. A GSP attempts to form a VO with other GSPs that maximizes its pro?t. But this is not simple as for n service providers, there are 2n potential VOs in which a GSP can be part of. Further complicating the matter is that computing the worth of a coalition of GSPs requires determining a mapping that assigns application tasks to providers. This problem is known to be NP-hard. This process clearly takes an exponential amount of time and it makes completing the application before its deadline dif?cult. Consequently, a service provider cannot possibly compute the worth of all coalitions and thus has limited information to base its decision. It is likely that service providers will employ heuristics to expedite the process. These heuristics would be held private as they give providers signif- icant economic advantages over the others. The advantage is only gained though, if others can be convinced to form the preferred coalition. This can be readily done by disclosing the coalition and its mapping. Using the model that we developed, we propose a resource management system, the Virtual Organization Formation Man- ager (VOFM), to support VO formation among GSPs. The system is a middleware component which is supported by the grid implementation. The VOFM would be replicated across the grid, allowing users and GSPs to interact with local copies. The VOFM provides support for exchanging mappings and other information between GSPs to facilitate the VO formation process. Out of the set of resulting VOs, it selects the one that will execute the program. A. Our Contributions We model the Virtual Organization (VO) formation as a coalition formation problem. We use Myerson'