Fault Tolerant Scheduling of Non-uniform Tasks under Resource Augmentation
Dariusz Rafal Kowalski, Prudence W. H. Wong, Elli Zavou · 2015
Dealing with computationally intensive jobs is becoming a necessity rather than an additional advantage of new computational systems. Some of the multiple challenges that appear with the complexity of such systems include the dynamicity of job (or task) arrivals, the diversity of their computational demands (e.g. different processing times), the unpredictable machine failures, as well as the preservation of power consumption. In this work we focus on the simple model of one single machine prone to unpredictable crashes and restarts, and tasks of sizes c ∈ [cmin, cmax] arriving dynamically in the system. Values cmin and cmax represent the smallest and largest processing times a task may need respectively, when executed by the machine running without additional resource augmentation. We consider a parameter s representing speedup; the amount of resource augmentation added to the machine, such that the processing time of a task of size c becomes c/s. We apply resource augmentation to overcome the machine failures, as an alternative to using more processing entities (e.g. multiprocessor systems). Due to the unpredictable nature of the machine and the dynamicity of task arrivals, we consider crash, restart and injection patterns to be controlled by an adversarial entity A, and perform worst-case competitive analysis for the performance of online scheduling algorithms. We focus on two efficiency measures: the completed time, which is the aggregate size of all tasks that have been completely executed, and latency, which is the longest time a task spends in the system. In some sense, the former corresponds to the utilization of the machine, while the latter on the fairness of the scheduling algorithm. In a previous work, Fernandez Anta et al. [2] looked at the pending time competitiveness of a similar system of multiple machines and showed that in order to achieve competitiveness, it is necessary to use speedup. They proved the NP-hardness of the offline version of the problem and gave lower bounds on speedup, under which no competitiveness can be achieved. These were given by conditions C1: s 0 a parameter that represents the number of cmin tasks that a machine with speedup s can complete in addition to a cmax task, in an interval of length (γ + 1)cmin. In a different line of work and environment, Fernandez Anta et al. [1] have shown that even with no speedup, an algorithm that gives priority to the shortest tasks can achieve