In real-time artificial intelligence, a fundamental tension exists between the efficiency of an algorithm and its flexibility. Many high-performance computational methods, such as dynamic programming or complex search, are contract algorithms. As defined by Stuart Russell 0001 and Shlomo Zilberstein, these components require a pre-specified execution time to produce a meaningful result. If a contract algorithm is interrupted even a moment before its deadline, it typically fails to provide any usable output.
This rigidity is a liability in dynamic environments where deadlines are unpredictable. To bridge this gap, researchers develop scheduling strategies that transform these "all-or-nothing" contracts into interruptible algorithms—systems that can be stopped at any time to provide a result that improves monotonically with more computation.
The Mechanism of Iterative Execution
The core intuition for simulating interruptibility is to execute a sequence of contracts with progressively increasing durations. If an interruption occurs, the system returns the result from the most recently completed contract.
As Alejandro López-Ortiz et al. explain, this mechanism ensures that a valid result is always available. For example, in decision tree induction, Saher Esmeir and Shaul Markovitch show that wrapping a fixed-time contract algorithm in an iterative improvement loop allows the model to provide an immediate initial solution that refines continuously as long as resources remain. Similarly, in speech parsing, Gunther Gorz and Marcus Kesseler propose that completing discrete transactions before processing an interrupt allows for "graceful degradation" of results rather than total failure.
The Cost of Uncertainty
Converting a contract algorithm into an interruptible one is not free. There is a performance loss because the system spends time completing shorter contracts that are eventually superseded by longer ones. This loss is often measured by the acceleration ratio—the factor by which the processor must be sped up to guarantee the same quality as a contract algorithm that knew the deadline in advance.
Shlomo Zilberstein et al. proved that for a single processor, the optimal strategy is to execute a sequence of contracts where each duration is double the previous one. This "doubling strategy" ensures that, regardless of when the interruption occurs, the system has completed a contract within a constant factor of 4 of the total available time. Alejandro López-Ortiz et al. later provided the definitive proof that a cyclic, exponential growth strategy is mathematically unbeatable for scheduling $n$ problems across $m$ processors.
Unifying Search and Scheduling
The problem of scheduling contracts bears a surprising mathematical resemblance to physical search problems. Daniel S. Bernstein et al. established a formal equivalence between contract scheduling and the "robots on rays" problem, where multiple robots search for a goal on intersecting paths. In both cases, the agent must decide how far to explore in one direction (or how long to run one contract) before switching to another to minimize the worst-case time to find the goal (or reach a quality threshold).
Learning-Augmented Schedules
While traditional schedules assume a worst-case scenario where the deadline is completely unknown, recent research incorporates "advice" or predictions to improve performance. Spyros Angelopoulos et al. demonstrated that if a system has access to a probability distribution of potential interruption times, the performance loss factor can be reduced from 4 to approximately 2.77.
However, relying on predictions introduces new risks. Spyros Angelopoulos et al. note that contract scheduling is highly sensitive to the timing of interruptions relative to completion boundaries. A slightly more accurate prediction can sometimes lead to worse performance if it causes the schedule to "just miss" the completion of a long contract. Modern frameworks therefore aim for "consistency" (high performance when predictions are right) and "robustness" (a safety net when predictions are wrong).
Key Foundational Work
Composing Real-Time Systems (1991) — contributed 1 concept elements to this direction.
Anytime Algorithms for Speech Parsing? (1994) — contributed 1 concept elements to this direction.