Resource bartering in data grids

Article type: Research Article

Authors: Özturan, Can

Affiliations: Department of Computer Engineering, Bogazici University, Istanbul, Turkey. Tel.: +90 212 359 7225; Fax: +90 212 287 2461; E-mail: ozturaca@boun.edu.tr

Abstract: We present models for bartering of resources on grids. Bartering models can be useful for making resource allocation decisions in grids and perhaps even for building a so called barter grid whereby distributed resources such as electronic media can be bartered. Grids allow various resources to be shared among many users. This sharing however definitely does not mean that everyone will have unrestricted use of the resources. Some mechanism such as pricing or quotas can be employed in order to enforce controlled sharing of resources. A barter model for resource sharing can enable people or computer centers to directly get something in return for letting their resources to be used by others. We utilize directed hypergraphs to develop a barter model in which multiple resources can be traded. We prove that the decision version of the multi-resource bartering problem is NP-complete. We present an integer programming formulation for the bartering problem. We also present a linear time algorithm to compute components that may contain feasible bartering solutions. We generalize our multi-resource bartering formulation to the case where multiple instances of resources are present. Finally, we present various computational results from our software that makes use of LP_SOLVE and CPLEX mixed integer programming libraries to solve example bartering problems.

Keywords: grid, resource management, barter, auction

Journal: Scientific Programming, vol. 12, no. 3, pp. 155-168, 2004