In this paper we address the problem of designing an interruptible system in
a setting in which $n$ problem instances, all equally important, must be solved
concurrently. The system involves scheduling executions of contract algorithms
(which offer a trade-off between allowable computation time and quality of the
solution) in m identical parallel processors. When an interruption occurs, the
system must report a solution to each of the $n$ problem instances. The quality
of this output is then compared to the best-possible algorithm that has
foreknowledge of the interruption time and must, likewise, produce solutions to
all $n$ problem instances. This extends the well-studied setting in which only
one problem instance is queried at interruption time.
In this work we first introduce new measures for evaluating the performance
of interruptible systems in this setting. In particular, we propose the
deficiency of a schedule as a performance measure that meets the requirements
of the problem at hand. We then present a schedule whose performance we prove
that is within a small factor from optimal in the general, multiprocessor
setting. We also show several lower bounds on the deficiency of schedules on a
single processor. More precisely, we prove a general lower bound of (n+1)/n, an
improved lower bound for the two-problem setting (n=2), and a tight lower bound
for the class of round-robin schedules. Our techniques can also yield a
simpler, alternative proof of the main result of [Bernstein et al, IJCAI 2003]
concerning the performance of cyclic schedules in multiprocessor environments.

设计并行处理的可中断系统，采用合同算法进行调度，并提出新的性能评价指标，证明在一般的多处理器环境中存在一种调度算法，其性能接近最优，同时找到了单处理器的若干种最小系统缺陷下界的限制。