Dynamic Scheduling for Heterogeneous Desktop Grids

Desktop Grids have emerged as an important methodology to harness the idle cycles of millions of participant desktop PCs over the Internet. However, to effectively utilize the resources of a Desktop Grid, it is necessary to use scheduling policies suitable for such systems. A scheduling policy must be applicable to large-scale systems involving large numbers of machines. Also, the policy must be fault-aware in the sense that it copes with resource volatility. Further adding to the complexity of scheduling for Desktop Grids is the inherent heterogeneity of such systems. Suboptimal performance would result if the scheduling policy does not take into account information on heterogeneity. In this paper, we suggest and develop several scheduling policies for Desktop Grid systems involving different levels of heterogeneity. In particular, we propose a policy which utilizes the solution to a linear programming problem which maximizes system capacity. We consider parallel applications that consist of independent tasks.