Online parallel scheduling of non-uniform tasks: Trading failures for energy
Date
2015Source
Theoretical Computer ScienceVolume
590Pages
129-146Google 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 machines 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 off-line optimal solution, even with one single machine and tasks of only two different execution times. We find that when additional energy is provided to the system in the form of processing 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. © 2015 Elsevier B.V.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Conference Object
A neural-type parallel algorithm for fast matrix inversion
Polycarpou, Marios M.; Ioannou, P. A. (1991)
-
Article
Max-product algorithms for the generalized multiple-fault diagnosis problem
Le, T.; Hadjicostis, Christoforos N. (2007)In this paper, we study the application of the max-product algorithm (MPA) to the generalized multiple-fault diagnosis (GMFD) problem, which consists of components (to be diagnosed) and alarms/connections that can be ...
-
Article
Distributed matrix scaling and application to average consensus in directed graphs
Domínguez-Garcia, A. D.; Hadjicostis, Christoforos N. (2013)We propose a class of distributed iterative algorithms that enable the asymptotic scaling of a primitive column stochastic matrix, with a given sparsity structure, to a doubly stochastic form. We also demonstrate the ...