International Journal of Grid and Utility Computing (9 papers in press)

• Reverse Combinatorial Auction Based Protocols for Resource Selection in Grids
  by Radhani kanth Guturi, Narahari Y 
  Abstract: Grid computing provides an extremely promising distributed paradigm for executing large scale resource intensive applications. Given a distributed pool of resources, a grid user who wishes to execute a job comprising a large number of tasks on the grid, is faced with the problem of selecting an optimal set of resources. We call this problem the "resource selection problem" and our approach to modeling and solving this problem is through a reverse combinatorial auction. In the proposed auction, the grid user is the buyer and the resource owners are the sellers. The resource owners submit bids on combinations of resources or tasks in response to the grid user's request for a bundle of resources. The objective of the grid user is to minimize an appropriately defined cost function based on these bids. The resource selection problem therefore becomes the winner determination problem of the reverse combinatorial auction. Two variants of the problem are considered: (1) resource selection with task level trading and (2) resource selection with resource level trading. In both the cases, the resource selection problem turns out to be an integer linear programming problem. To investigate the performance of the proposed resource selection protocols, NAS grid benchmarks are run using SimGrid and the performance is compared against that of a cost optimization protocol and a time optimization protocol which are part of the Nimrod-G resource broker. The protocols proposed are found to have superior overall performance in terms of turn around time and total cost.
  Keywords: Grid computing; auction based resource allocation; resource selection with task level trading; resource selection with resource level trading; reverse auction; reverse combinatorial auction; integer linear programs
   
• Performance Evaluation of Different Replica Placement Algorithms
  by Mohammad Rahman, Ken Barker, Reda Alhajj 
  Abstract: Data Grid technology is developed to permit data sharing across many organizations in different geographically disperse locations. Replication of data to different sites will help the researchers around the world to analyze and initiate future experiments. The general idea of replication is to store copies of data in different locations so that data can be easily recovered if one copy at one location is lost or unavailable. Moreover, if data can be kept close to users via replication, data access performance can be improved dramatically. One of the challenges for data replication is to select the candidate sites that will host the replicas of datasets. In our earlier research (Rahman et al., 2006, 2007) we propose different replica placement algorithms based on three mathematical models, i.e., p-center, p-median and a multi-objective model. We also present a replica maintenance algorithm to relocate replicas to different sites if the performance of the replica host sites degrades significantly. In this research, we validate our replica placement algorithms with different performance metrics, e.g., total file transfer time, the number of local and remote file access, and with accuracy. To evaluate our replica placement algorithms we use a Data Grid simulator called OptorSim (Bell et al., 2003). This paper presents detailed execution flows of the replication algorithms in the simulator. The study of our replica placement algorithms is carried out using a model of the EU Data Grid Testbed 1 (Bell et al., 2003) sites and their associated network geometry. Jobs are based on the CDF use-case as described in (Huffman et al., 2002).
  Keywords: data grid, replication, network latency, dynamic allocation, distributed environment
   
• Resolution of large symmetric eigenproblems on a world-wide grid
  by Laurent Choy, Serge G. Petiton, Mitsuhisa Sato 
  Abstract: We propose a parallel and distributed application for the resolution of the large real symmetric eigenproblem on world-wide heterogeneous grids. It is based on the explicit restarted Lanczos algorithm which is a Krylov subspace method. We take into account the specificities of computational resources and deal with communication constraints over the Internet. We propose techniques such as out-of-core and data persistence. We also show that a restarted algorithm and the combination of several paradigms of parallelism are relevant in this context. The results of the experiments stress the impact of the main numerical parameters of the Lanczos method. We also compare many platform configurations built on top of two complementary experimental environments. We first use a realistic world-wide grid harnessing 2 geographic sites, in France and in Japan, interconnected by the Internet. Then, we use the French national testbed Grid5000. We conclude on the scalability of our application and we forecast the next bounding factor of the implementation. It can be solved by means of a dedicated data management layer such as OmniStorage.
  Keywords: Global Computing; GRID5000; OmniRPC; Eigenproblem; Lanczos; Bisection.
   
• Adaptive Approaches for Efficient Parallel Algorithms on Cluster-based Systems
  by Wahid Nasri, Luiz Angelo Steffenel, Denis Trystram 
  Abstract: Few years ago, there was a huge development of new parallel and distributed systems. Due to many reasons, such as the inherent heterogeneity, the diversity, and the continuous evolution of such computational supports, it is very hard to solve efficiently a target problem by using a single algorithm or to write portable programs that perform well on any architecture. Toward this goal, we propose a generic framework combining communication models and adaptive approaches to deal with the performance modeling problem associated to the design of efficient parallel algorithms on grid computing environments, and we apply this methodology on collective communication operations. Experiments performed on a grid platform prove that the framework provides significant performances while determining the best combination model-algorithm depending on the problem and architecture parameters.
  Keywords: Cluster computing; Performance modeling; Adaptive approaches; Poly- models of communications
   
• P2P Design and Implementation of a Parallel Branch and Bound Algorithm for Grids
  by Ahcène Bendjoudi, Nouredine Melab, El-Ghazali Talbi 
  Abstract: Solving optimally large instances of combinatorial optimization problems using Branch and Bound (B&B) Algorithms is CPU-time intensive and requires a large number of computational resources. To harness such huge amount of resources peer-to-peer (P2P) communications must be allowed between resources, and adaptive load balancing and fault-tolerance have to be dealt with when designing and implementing a B&B algorithm. In this paper, we propose a P2P design and implementation of a parallel B&B algorithm on top of the ProActive grid middleware. Load distribution and fault-tolerance strategies are proposed to deal with the dynamic and heterogeneous characteristics of the computational grid. The approach has been promisingly applied to the Flow-Shop scheduling problem and experimented on a computational pool of 1500 CPUs from the GRID'5000 Nation-wide experimental Grid.
  Keywords: Combinatorial optimization, Permutation Flow-shop problem, Parallel Branch and Bound, Peer-to-Peer Computing, ProActive
   
• Ontology-based semantic integration scheme for medical image grid
  by Hai Jin, Aobing Sun, Ran Zheng, Ruhan He, Qin Zhang 
  Abstract: Ontology is becoming a key for grid platform to support the integration of heterogeneous resources by means of processing resource description and enactment. MedImGrid (Medical Image Grid) aims to access, archive and analyze medical data from distributed healthcare information systems to adapt to the development of healthcare information infrastructure. But the heterogeneities of those systems, especially the semantic gulfs hamper their interoperations even encapsulated as web services in grid environment. In this paper, we propose an OSIS (Ontology-based Semantic Integration Scheme) for MedImGrid, which adopts a hybrid method to create MedImGrid semantic environment and unifies its information exchange model with HL7 (Health Level 7) v3 protocol. The MedImGrid ontologies share the same lexicon to simplify the semantic transformation within distributed environment. The ontology based semantic integration components are also designed to support the semantic interoperations of MedImGrid. We test the performances of our scheme with simulation experiments to evaluate the feasibility of our approaches.
  Keywords: semantic integration; medical image grid; hybrid ontologies; HL7 protocol.
   
• Standardized Job Submission and Control in Cluster and Grid Environments
  by Peter Tröger, Hrabri Rajic, Andreas Haas, Piotr Domagalski 
  Abstract: Cluster and Grid environments mostly required the use of product-specific APIs to submit, control and monitor computational jobs in the past. The Open Grid Forum (OGF) standardization body therefore has developed several specifications to fill the gap and enable developers to code to few standardized APIs. This article discusses the details of one of these specifications, the Distributed Resource Management Application API (DRMAA) Grid recommendation. We compare the basic concepts of the finalized API to other specifications from the same area and explain issues and findings uncovered during the standardization of such unified interface.
  Keywords: job submission; job monitoring; job control; cluster system; array job; IDL; API; standardization; Open Grid Forum; DRM system; DRMS; DRMAA.
   
• Cooperative Caching for Grid-Enabled OLAP
  by Frank Dehne, M. Lawrence, A. Rau-Chaplin 
  Abstract: In this paper we propose a grid-based OLAP application which distributes query computation across an enterprise grid. Our application follows a two-tiered process for answering queries based on sharing cached OLAP data between the users at the local grid site, and using grid scheduling approaches to execute the remaining parts of a query amongst a distributed set of OLAP servers. A new technique for extraction and aggregation of shared cached OLAP data is proposed, along with an efficient, aggregate-aware cache controller. An experimental evaluation of the proposed query processing and cooperative caching methods shows a significant reduction in query times compared to previously proposed methods.
  Keywords: OLAP; grid; caching
   
• SecGRID: Model for Maintaining Trust in Large Scale Dynamic Environments
  by Roman Špánek 
  Abstract: The paper describes a new model for treating trust in reconfigurable groups of users with special accent on maintaining trust in the next generations of applications. The proposed model uses properties of weighted hypergraphs for description of possibly complicated trust relationships between and within groups of users. The model flexibility enables description of the relations such that these relations are preserved under frequent changes in their structure or trust. The presented ideas can be for their generality straightforwardly generalized to other concepts describable by weighted hypergraphs. The consistency of the proposal was verified in a couple of experiments with our pilot implementation SecGRID.
  Keywords: trust management; security; hypergraphs; distributed systems.