Optimal Scheduling of Contract Algorithms with Soft Deadlines
[.pdf]
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.
%It is well-known that contract algorithms can simulate interruptible
%algorithms using iterative deepening techniques.
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)≤ c 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.
Bibtex Entry
