Optimal Scheduling of Contract Algorithms for Anytime Problems

Alejandro López-Ortiz, Spyros Angelopoulos, Angèle M. Hamel

Abstract

This paper settles a long-standing conjecture in the theory of anytime algorithms by proving the mathematically optimal way to schedule "contract algorithms" to create "interruptible algorithms." The authors demonstrate that a simple round-robin strategy with geometrically increasing contract lengths is the absolute best possible approach across $m$ processors and $n$ problem instances.

Introduction

In AI and real-time systems, "anytime algorithms" are essential for their ability to return valid solutions upon interruption. These algorithms come in two primary forms:

  1. Contract Algorithms: These require a pre-defined deadline $t$ to produce a result. Stopping them early yields no output.
  2. Interruptible Algorithms: These can be stopped at any arbitrary time $t$ and must provide the best current answer.

Interruptible algorithms are typically constructed by simulating a sequence of contracts with increasing lengths. The efficiency of this simulation is measured by the acceleration ratio: the factor by which processors must be sped up to match an "ideal" algorithm that knew the interruption time in advance. This paper provides the missing proof that a specific class of geometric schedules is globally optimal.

Theoretical Framework and Methodology

The authors employ a sophisticated framework to bridge specific scheduling strategies with general lower bounds.

Narrowing the search space of schedules through theoretical lemmas.

The proof relies on three main pillars:

  • Schedule Normalization: The authors prove that any arbitrary schedule can be transformed into a "normalized" version—more structured and predictable—without increasing the acceleration ratio. This reduction allows the proof to focus on a manageable set of well-behaved schedules.
  • Functional Analysis: By defining a mathematical functional for the acceleration ratio and applying search theory techniques, they show that the supremum for any sequence is at least as large as that of a geometric sequence.
  • Geometric Scaling: They demonstrate that optimal contract lengths must follow a geometric progression, where the growth factor depends on the number of problems $n$ and processors $m$.

Key Insights: The Round-Robin Optimality

A significant finding is the link between scheduling and "robot searching on rays." The mathematics required to minimize search time for a target on branching paths is identical to minimizing the acceleration ratio.

Furthermore, the authors show that a simple round-robin strategy—cycling through problem instances with increasing time slices—is actually globally optimal. This generalizes the classic "Four Rule" (where the optimal acceleration ratio for one processor and one problem is 4) to any number of processors and problems. This removes the need for complex dynamic scheduling logic to achieve peak performance.

Results and Conclusion

The paper's primary result is Theorem 3, which establishes the optimal acceleration ratio $R_{m,n}^*$ for $n$ problems and $m$ processors:

$$ R_{m,n}^* = \left( \frac{n}{m} \right) \left( \frac{m + n}{n} \right)^{\frac{m+n}{m}} $$

A multi-processor schedule (top) and its corresponding acceleration ratio over time (bottom).

This formula defines the physical limit of efficiency for simulating interruptible behavior. While this work focuses on deterministic schedules and identical processors, it opens doors for future research into randomized schedules and heterogeneous systems.

Summary updated

Abstract

A contract algorithm is an algorithm which is given, as part of the input, a specified amount of allowable computation time. The algorithm must then compute a solution within the alloted time. An interruptible algorithm, in contrast, can be interrupted at an arbitrary point in time and must produce a solution. It is known that contract algorithms can simulate interruptible algorithms using iterative deepening techniques. This simulation is done at a penalty in the performance of the solution, as measured by the so-called acceleration ratio. In this paper we give matching (i.e. optimal) upper and lower bounds for the acceleration ratio under this simulation. This resolves an open conjecture of Bernstein et al. [IJCAI 2003] who gave an ingenious optimal schedule under the restricted setting of round robin and length-increasing processor schedules, but whose optimality in the general unrestricted case remained open.
BibTeX
@inproceedings{lopezortiz2006optimal,
  author = {Alejandro López-Ortiz and Spyros Angelopoulos and Angèle M. Hamel},
  title = {{Optimal Scheduling of Contract Algorithms for Anytime Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure