Fault tolerant scheduling of tasks of two sizes under resource augmentation

Dariusz R. Kowalski, Prudence W. H. Wong and Elli Zavou ()
Additional contact information
Dariusz R. Kowalski: University of Liverpool
Prudence W. H. Wong: University of Liverpool
Elli Zavou: Universidad Carlos III de Madrid and IMDEA Networks Institute

Journal of Scheduling, 2017, vol. 20, issue 6, No 11, 695-711

Abstract: Abstract 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 $$\gamma \text{-Burst } $$ γ -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.

Keywords: Scheduling; Online algorithms; Task sizes; Adversarial failures; Resource augmentation; Competitive analysis (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-017-0541-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:20:y:2017:i:6:d:10.1007_s10951-017-0541-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-017-0541-1

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().