Accepted Papers

An Autonomic Network-Aware Scheduling Architecture for Grid Computing
Agustin Caminero, Omer Rana, Maria Caminero and Carmen Carrion

Abstract: Grid technologies have enabled the aggregation of geographically distributed resources, in the context of a particular application. The network remains an important requirement for any Grid application, as entities involved in a Grid system (such as users, services, and data) need to communicate with each other over a network. The performance of the network must therefore be considered when carrying out tasks such as scheduling, migration or monitoring of jobs. Surprisingly, many existing QoS efforts ignore the network and focus instead on processor workload and disk access. Making use of the network in an efficient and fault tolerance manner, in the context of such existing research, leads to a significant number of research challenges. One way to address these problems is to make Grid middleware incorporate the concept of autonomic systems. Such a change would involve the development of ``self-configuring" systems that are able to make decisions autonomously, and adapt themselves as the system status changes. We propose an autonomic network-aware scheduling infrastructure that is capable of adapting its behavior to the current status of the environment.



Using Checkpointing to Recover from Poor Multi-site Parallel Job Scheduling Decisions
William Jones

Abstract: Recent research in multi-site parallel job scheduling leverages user-provided estimates of job communication characteristics to effectively partition the job across cluster boundaries. Previous research addressed the impact of inaccuracies in these estimates on overall system performance and found that multi-site scheduling techniques benefit from these estimates, even in the presence of considerable inaccuracy. While these results are encouraging, there are many instances where these errors result in poor scheduling decisions that cause network over-subscription. This situation can lead to significantly degraded application runtime performance and turnaround time.



Multiobjective Differential Evolution for Workflow Execution on Grids
AKM Khaled Talukder, Michael Kirley and Rajkumar Buyya

Abstract: Most algorithms developed for scheduling applications on global Grids focus on a single Quality of Service (QoS) parameter such as execution time, cost or total data transmission time. However, if we consider more than one QoS parameter (eg. execution cost and time may be in conflict) then the problem becomes more challenging. To handle such scenarios, it is convenient to use heuristics rather than a deterministic algorithm. In this paper we have proposed a workflow execution planning approach using Mutliobjective Differential Evolution (MODE). Our goal was to generate a set of trade-off schedule according to two user specified QoS requirements (time and cost). The alternative trade-off solutions offer more flexibility to users when estimating their QoS requirements of workflow executions. We have compared our results with two baseline multiobjective evolutionary algorithms. Simulation results show that our modified Multiobjective Differential Evolution is able to find comparatively better spread of compromise solutions.



A Pricing Information Service for Grid Computing
Alexandru Caracas and Jon Altmann

Abstract: This paper addresses two shortcomings that exist in the area of pricing of Grid services in an economic Grid environment. The first shortcoming is that there are no standards for pricing schemes, caused by the quite large difference between the units of trade (e.g. CPU cycles and virtual clusters) in Grid computing. The second shortcoming is the lack of a model for managing the pricing of informational elements (e.g. software applications) and computational elements (e.g. virtual machines, which comprise resources such as CPU, memory, disk space, network bandwidth). This paper presents a pricing service for Grid computing services, which resolves the shortcomings by introducing a general pricing scheme for informational and computational elements. We describe the functional requirements, architecture, and the interfaces of the pricing service. The pricing service allows expressing the proposed general pricing scheme as an XML document, which can be linked to service level agreements. Contrary to other proposals on pricing, the pricing service is separated from the functionality of metering, accounting, and payment. To validate the concept of a pricing information service we portray two Utility Computing scenarios.



A Multi-Commodity Flow Approach to Maximising Utility in Linked Market-Based Grids
James Broberg and Rajkumar Buyya

Abstract: In this paper we consider the problem of maximising utility in linked market-driven distributed and Grid systems. In such systems, users submit jobs through brokers who can virtualise and make available the resources of multiple service providers, achieving greater economies of scale, improving throughput and potentially reducing cost. Customers compete against each other by assigning a utility value or function to the successful processing of their jobs in an effort to have them prioritised in the face of contested and constrained resources. Brokers and service providers also attempt to maximise the utility they gain, choosing to process jobs that will earn them the highest profit with respect to the resources required. For this to be effective over many linked computing marketplaces highly distributed resource allocation is needed, where each participant can operate independently using only local information, and ideally reach a global state where all participants are satisfied. We model such a system by adapting the classical multi-commodity flow problem to the market-based, utility driven distributed systems, where all participants selfishly attempt to maximise their own gain. We then obtain a utility-aware distributed algorithm that generates increased utility for participants in such systems, especially under scenarios of high contention.



WSPE: A Peer-to-Peer Programming Environment for Grid-Unaware Applications
Romulo Rosinha, Patricia Kayser Vargas and Claudio Geyer

Abstract: Grid programming environments are tools designed to isolate users from issues like heterogeneity, scalability, and adaptability, thus simplifying the use of Grid infrastructure. This paper presents WSPE, a Grid programming environment for Grid-unaware applications. WSPE consists of a simple programming interface and a fully decentralized runtime system following a peer-to-peer organization. WSPE's runtime system employs a new scheduling mechanism, called Round Stealing, inspired on the idea of work stealing. The main focus of this work is to research methods to achieve efficient execution of parallel applications in a Grid computing infrastructure. By simulation, we show that our scheduling mechanism outperforms a more traditional mechanism, in a Grid environment. We also demonstrate how an appropriate choice for a network overlay mechanism can further improve execution efficiency.



Semantics-Based Grid Resource Management
Alexandre Vidal, Sergio Kofuji, Francisco da Silva e Silva and Fabio Kon

Abstract: Scheduling parallel and distributed applications efficiently onto grid environments is a difficult task and a great variety of scheduling heuristics have been developed aiming to address this issue. A successful grid resource allocation depends, among other things, on the quality of the available information about software artifacts and grid resources. In this paper, we propose a semantic approach to integrate selection of equivalent resources and selection of equivalent software artifacts in order to improve the schedule of resources suitable for a given set of application execution requirements. We also describe a prototype implementation of our approach based on the Integrade grid middleware and experimental results that indicate its benefits.



Fair Access to Scarce Resources in Ad-hoc Grids using an Economic-based Approach
Behnaz Pourebrahimi and Koen Bertels

Abstract: In ad-hoc Grids where the availability of resources and tasks changes over the time, distributing the tasks among the scarce resources in a balanced way is a challenging task. In this paper, we present how using an economic-based approach, the tasks can be distributed evenly among the scarce resources. Such that all nodes which have tasks to be executed, receive more or less equal utilization from the Grid resources. We consider a continuous double auction protocol as the economic approach to share idle cpu cycles among the nodes in a local ad-hoc Grid. Each node is given a limited budget when joining the Grid. The node can use it to buy required resources or increases its budget by selling idle resources. Consumers and producers of resources determine their bid and ask prices using a dynamic pricing strategy and the auctioneer adopts a discriminatory pricing policy which sets the transaction price individually for each matched buyer-seller pair. We experiment in a network where the resources are scarce and the tasks outnumber the resources. The spread of task utilization at individual nodes and the level of load balancing are measured and compared with a non-economic approach. The results show that economic-based approach provides a fair and balanced basis for access to Grid resources for everyone while in the same time gives a satisfactory level of system performance.



Removing the Need for State Dissemination in Grid Resource Brokering
Peer Hasselmeyer

Abstract: Resource brokering in Grids is nowadays handled by resource brokers that require detailed knowledge of the state of the resources that they broker. In business settings, surrendering internal information on resources to an outside party is not an option. The traditional resource brokering method based on intimate resource knowledge is therefore not a viable possibility. This paper argues that the publication of resource state data is not needed for resource brokering. Instead, we advocate the use of service level agreements (SLAs). The use of SLAs for brokering lets providers keep state information internal and at the same time provides customers with guarantees on the used services.The proposed model has been implemented in the form of a resource broker that is based on Web Service technology. It shows that the approach of using SLAs for scheduling is a possible solution to keeping resource state private.



On the Management of Grid Credentials
Luiz Gadelha and Bruno Schulze

Abstract: In this work we provide some insights about the problem of managing credentials in grid environments. Since user mobility is a very common requirement in grid implementations, centralized credential servers are frequently used to store their cryptographic keys. We study some possible solutions for environments with stronger requirements regarding non-repudiation, where the use of credential servers may not be acceptable.



Invited Talk:
Google Infrastructure for Massively Parallel Processing
Walfredo Cirne

Abstract: Google provides a large number of services that are both computationally and data intensive. As a result, the use of massively parallel computing is the norm at Google. However, developing parallel and distributed software is notoriously harder than developing plain sequential software. This talk addresses how we have leveraged expertise of some engineers with deep knowledge in distributed and parallel system to ease everybody else's life, allowing people without strong training in the area to write robust and efficient distributed systems. In particular, we are going to present MapReduce, a framework for parallel applications that process large amounts of data, as a case-study to show how this can be done.