TY - JOUR
T1 - Fault tolerant scheduling of tasks of two sizes under resource augmentation
AU - Kowalski, Dariusz R.
AU - Wong, Prudence W.H.
AU - Zavou, Elli
N1 - Funding Information:
Acknowledgements This research was partially supported by the Cloud4BigData grant (S2013/ICE-2894) from Madrid Regional Government (CM), the HyperAdapt project (TEC2014-55713-R) from the Spanish Ministry of Economy and Competitiveness (MINECO), the NSFC project 61520106005 from the National Science Foundation of China, the FPU12/00505 grant from the Spanish Ministry of Education, Culture and Sports (MECD) and the Polish National Science Centre grant DEC-2012/06/M/ST6/00459. We would like to thank the anonymous reviewers for their constructive comments and suggestions to improve our work.
Publisher Copyright:
© 2017, Springer Science+Business Media, LLC.
PY - 2017/12/1
Y1 - 2017/12/1
N2 - Guaranteeing the eventual execution of tasks in machines that are prone to unpredictable crashes and restarts may be challenging, but is also of high importance. Things become even more complicated when tasks arrive dynamically and have different computational demands, i.e., processing time (or sizes). In this paper, we focus on the online task scheduling in such systems, considering one machine and at least two different task sizes. More specifically, algorithms are designed for two different task sizes while the complementary bounds hold for any number of task sizes bigger than one. We look at the latency and 1-completed load competitiveness properties of deterministic scheduling algorithms under worst-case scenarios. For this, we assume an adversary, that controls the machine crashes and restarts as well as the task arrivals of the system, including their computational demands. More precisely, we investigate the effect of resource augmentation—in the form of processor speedup—in the machine’s performance, by looking at the two efficiency measures for different speedups. We first identify the threshold of the speedup under which competitiveness cannot be achieved by any deterministic algorithm, and above which there exists some deterministic algorithm that is competitive. We then propose an online algorithm, named γ-Burst, that achieves both latency and 1-completed-load competitiveness when the speedup is over the threshold. This also proves that the threshold identified is also sufficient for competitiveness.
AB - Guaranteeing the eventual execution of tasks in machines that are prone to unpredictable crashes and restarts may be challenging, but is also of high importance. Things become even more complicated when tasks arrive dynamically and have different computational demands, i.e., processing time (or sizes). In this paper, we focus on the online task scheduling in such systems, considering one machine and at least two different task sizes. More specifically, algorithms are designed for two different task sizes while the complementary bounds hold for any number of task sizes bigger than one. We look at the latency and 1-completed load competitiveness properties of deterministic scheduling algorithms under worst-case scenarios. For this, we assume an adversary, that controls the machine crashes and restarts as well as the task arrivals of the system, including their computational demands. More precisely, we investigate the effect of resource augmentation—in the form of processor speedup—in the machine’s performance, by looking at the two efficiency measures for different speedups. We first identify the threshold of the speedup under which competitiveness cannot be achieved by any deterministic algorithm, and above which there exists some deterministic algorithm that is competitive. We then propose an online algorithm, named γ-Burst, that achieves both latency and 1-completed-load competitiveness when the speedup is over the threshold. This also proves that the threshold identified is also sufficient for competitiveness.
KW - Adversarial failures
KW - Competitive analysis
KW - Online algorithms
KW - Resource augmentation
KW - Scheduling
KW - Task sizes
UR - http://www.scopus.com/inward/record.url?scp=85028979968&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028979968&partnerID=8YFLogxK
U2 - 10.1007/s10951-017-0541-1
DO - 10.1007/s10951-017-0541-1
M3 - Article
AN - SCOPUS:85028979968
SN - 1094-6136
VL - 20
SP - 695
EP - 711
JO - Journal of Scheduling
JF - Journal of Scheduling
IS - 6
ER -