Abstract

Computational grids are characterized by widely distributed computational resources shared by virtual organizations. Users submit workflows of tasks to be executed, some of which may duplicated because of their shared application domain. The problem of allocating tasks to resources in grids has unique characteristics, governed by three features. First, users are generally interested in workflows, coordinated sets of tasks that together achieve some goal, rather than individual tasks. Good allocations of resources will optimize workflow-centered measures of performance, such as makespan and overall resource use, rather than taskcentered measures. Second, the allocation process is relatively decentralized, with distributed, autonomous agents as opposed to central control. Third, the products of jobs, files, are easy to replicate and share once created, although transfer times must be taken into account. We describe several strategies for resource allocation in Grids that differ in the amount of coordination and make an empirical analysis of their performance using a high-fidelity grid simulation environment. This analysis indicates that some coordination is essential, but the most effective strategies depend on global features such as the temporal spacing of different workflow handlers as well as structural features of workflows. We identify situations under which different strategies are appropriate.

Date

March 16, 2026

Authors

Jim Blythe, Yolanda Gil, Ewa Deelman

Journal

Proc. 14th Int. Conf. Autom. Planning Scheduling