Online parallel scheduling of non-uniform tasks: Trading failures for energy
Date
2013ISSN
0302-9743Source
19th International Symposium on Fundamentals of Computation Theory, FCT 2013Volume
8070 LNCSPages
145-158Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
Consider a system in which tasks of different execution times arrive continuously and have to be executed by a set of processors that are prone to crashes and restarts. In this paper we model and study the impact of parallelism and failures on the competitiveness of such an online system. In a fault-free environment, a simple Longest-in-System scheduling policy, enhanced by a redundancy-avoidance mechanism, guarantees optimality in a long-term execution. In the presence of failures though, scheduling becomes a much more challenging task. In particular, no parallel deterministic algorithm can be competitive against an offline optimal solution, even with one single processor and tasks of only two different execution times. We find that when additional energy is provided to the system in the form of processor speedup, the situation changes. Specifically, we identify thresholds on the speedup under which such competitiveness cannot be achieved by any deterministic algorithm, and above which competitive algorithms exist. Finally, we propose algorithms that achieve small bounded competitive ratios when the speedup is over the threshold. © 2013 Springer-Verlag.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Article
Adaptive scheduling over a wireless channel under constrained jamming
Fernández Anta, Antonio; Georgiou, Chryssis; Zavou, Elli (2015)We consider a wireless channel between a single pair of stations (sender and receiver) that is being “watched” and disrupted by a malicious, adversarial jammer. The sender’s objective is to transmit as much useful data as ...
-
Article
Computing Nash equilibria for scheduling on restricted parallel links
Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2010)We consider the problem of routing nusers on m parallel links under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. So, this problem is equivalent to the ...
-
Article
Online parallel scheduling of non-uniform tasks: Trading failures for energy
Fernández Anta, Antonio; Georgiou, Chryssis; Kowalski, D. R.; Zavou, Elli (2015)Consider a system in which tasks of different execution times arrive continuously and have to be executed by a set of machines that are prone to crashes and restarts. In this paper we model and study the impact of parallelism ...