Abstract
A contract algorithm is an algorithm which is given, as part of its input, a specified amount of allowable computation time. In contrast, interruptible algorithms may be interrupted throughout their execution, at which point they must report their current solution. Simulating interruptible algorithms by means of schedules of executions of contract algorithms in parallel processors is a well-studied problem with significant applications in AI. In the classical case, the interruptions are hard deadlines in which a solution must be reported immediately at the time the interruption occurs. In this paper we study the more general setting of scheduling contract algorithms at the presence of soft deadlines. This is motivated by the observation of practitioners that soft deadlines are as common an occurrence as hard deadlines, if not more common. In our setting, at the time $t$ of interruption the algorithm is given an additional window of time $w(t) \leq c \cdot t$ to continue the contract or, indeed, start a new contract (for some fixed constant $c$). We explore this variation using the acceleration ratio, which is the canonical measure of performance for these schedules, and derive schedules of optimal acceleration ratio for all functions $w$.
Introduction
In the field of artificial intelligence, "anytime algorithms" are essential for systems that must provide a solution even when interrupted unexpectedly. These are broadly categorized into two types: interruptible algorithms, which can be stopped at any point to return their best current result, and contract algorithms, which must be told exactly how long they will run at the start of execution.
While interruptible algorithms offer greater flexibility, contract algorithms are often significantly easier to implement for complex tasks. To bridge this gap, researchers typically schedule a sequence of contracts of increasing lengths. If an interruption occurs, the system returns the result of the longest completed contract. Historically, this problem was studied under "hard deadlines," where a solution must be reported the instant an interruption occurs. However, real-world scenarios often involve "soft deadlines" or grace periods—such as a diagnostic system being given a few extra minutes to refine a result. This paper provides the first formal mathematical treatment of optimal contract scheduling within these grace periods.
Problem Formulation and Metrics
The authors model the grace period as a window function $w(t) \leq \epsilon \cdot t$, where $t$ is the time of interruption and $\epsilon$ is a constant. To evaluate the efficiency of a schedule, the paper employs the Acceleration Ratio ($\beta$). This performance metric compares the length of the best contract completed by the schedule within the grace period to the total time elapsed. Essentially, it represents the "speedup" a processor would require to match an ideal algorithm that knew the deadline in advance.
The Optimal Scheduling Strategy
The core of the research focuses on exponential schedules, where the lengths of contracts increase exponentially (e.g., $b^1, b^2, b^3, \dots$). Through competitive analysis, the authors identify the optimal "base" ($b$) for this exponential growth that minimizes the worst-case acceleration ratio.
The "Wait or Start Over" Trade-off
A key insight of the paper is the decision logic required when a soft deadline is triggered. The system faces two choices:
- Wait: Continue the currently running contract if it is guaranteed to finish within the grace period $w(t)$.
- Start Over: Immediately initiate a new, larger contract designed to fit exactly into the remaining time provided by the window.
Key Results
The paper establishes several landmark results for scheduling theory:
- Optimality of Exponential Growth: The authors prove that even with the flexibility of a grace period, the optimal strategy remains an exponential schedule. The grace period simply allows the scheduler to choose a more efficient growth rate (base $b$) than the hard-deadline version.
- Closed-Form Solutions: The authors provide a closed-form expression for the optimal acceleration ratio $\beta^*$ and prove that no other scheduling strategy—including non-cyclic or non-exponential ones—can achieve a better worst-case ratio.
- Generalization: The findings are shown to hold for $n$ different problem instances being solved across $m$ parallel processors. This generalizes previous work that was limited to single-processor or single-problem scenarios.
Discussion and Future Directions
While this work provides a rigorous foundation for soft-deadline scheduling, it focuses on linear window functions where the grace period grows proportionally with time. The analysis is also strictly "worst-case," suggesting that future research could benefit from average-case analysis, where interruptions follow a known probability distribution.
Additionally, the current model assumes no penalty for utilizing the grace period. Future iterations of this framework could explore models where the "value" of a solution decays the longer the system takes to respond during the soft-deadline window, further aligning the theory with time-sensitive applications in robotics and medical AI.
Summary updated