  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.
