A FAULT-TOLERANT SCHEDULING ALGORITHM FOR ECONOMY-BASED GRID SYSTEMS

Abstract

Grid computing, emerging as a new paradigm for next-generation computing, enables sharing, selection, and aggregation of geographically distributed heterogeneous resources for solving large-scale and computationally-intensive applications. Bag-of- Tasks applications (those parallel applications whose tasks are independent of each other) are both relevant and adaptable for execution on computational grids, as has been demonstrated by the projects such as SETI@home, MyGrid. With multiple users competing for the same resources, the key challenge is to finish a user application within a specified deadline. But it not only involves the problem of efficient utilization and satisfactory response time but also the problem of fault-tolerance. Typically, the probability of a failure is higher in the grid computing than in a traditional parallel computing and the failure of resources affects job execution significantly. Therefore, as grids are increasingly used for applications requiring high levels of performance and reliability, the ability to tolerate failures while effectively exploiting resources in a scalable and transparent manner must be an integral part of grid computing resource management systems. In this dissertation, a fault-tolerant algorithm for scheduling Bag-of-Tasks applications in economy-based grid systems has been proposed. Bid-based proportional share resource allocation is used to meet user QoS requirement. The allocation system, which is based on proportional share, allows users to bid higher in order to gain more resource share and periodically adjusts user bid to finish the application with in time. Task migration is incorporated into resource allocation which allows users to move some tasks on a busy or slow resource to other resource. Check-pointing approach is used to tolerate failures. Performance comparisons of the proposed fault-tolerant scheduler against a scheduling policy without task migration and check-pointing is presented and shown that the proposed algorithm performs reasonably well.