Dynamic scheduling for heterogeneous Desktop Grids

Desktop Grids have emerged as an important method-ology to harness the idle cycles of millions of participant desktop PCs over the Internet. However, to effectively uti-lize 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. Sub-optimal performance would result if the scheduling policy does not take into account information on heterogeneity. In this paper, we suggest and develop several scheduling poli-cies for Desktop Grid systems involving different levels of heterogeneity. In particular, we propose a policy which uti-lizes the solution to a linear programming problem which maximizes system capacity. We consider parallel applica-tions that consist of independent tasks. 1