Robust task scheduling for volunteer computing systems

Young Choon Lee, Albert Y. Zomaya, Howard Jay Siegel

Research output: Contribution to journalArticle

14 Citations (Scopus)

Abstract

Performance perturbations are a natural phenomenon in volunteer computing systems. Scheduling parallel applications with precedence-constraints is emerging as a new challenge in these systems. In this paper, we propose two novel robust task scheduling heuristics, which identify best task-resource matches in terms of makespan and robustness. Our approach for both heuristics is based on a proactive reallocation (or schedule expansion) scheme enabling output schedules to tolerate a certain degree of performance degradation. Schedules are initially generated by focusing on their makespan. These schedules are scrutinized for possible rescheduling using additional volunteer computing resources to increase their robustness. Specifically, their robustness is improved by maximizing either the total allowable delay time or the minimum relative allowable delay time over all allocated volunteer resources. Allowable delay times may occur due to precedence constraints. In this paper, two proposed heuristics are evaluated with an extensive set of simulations. Based on simulation results, our approach significantly contributes to improving the robustness of the resulting schedules.

Original languageEnglish
Pages (from-to)163-181
Number of pages19
JournalJournal of Supercomputing
Volume53
Issue number1
DOIs
Publication statusPublished - Jul 2010
Externally publishedYes

Fingerprint Dive into the research topics of 'Robust task scheduling for volunteer computing systems'. Together they form a unique fingerprint.

Cite this