# Scheduling Contract Algorithms on Multiple Processors

Daniel S. Bernstein, Theodore J. Perkins, Shlomo Zilberstein, and Lev Finkelstein.
Scheduling Contract Algorithms on Multiple Processors.
*Proceedings of the Eighteenth National Conference on Artificial Intelligence*
(AAAI), 702-706, Edmonton, Alberta, 2002.

## Abstract

Anytime algorithms offer a tradeoff between computation time and the
quality of the result returned. They can be divided into two classes:
contract algorithms, for which the total run time must be specified in
advance, and interruptible algorithms, which can be queried at any time for
a solution. An interruptible algorithm can be constructed from a contract
algorithm by repeatedly activating the contract algorithm with increasing
run times. The acceleration ratio of a run-time schedule is a worst-case
measure of how inefficient the constructed interruptible algorithm is
compared to the contract algorithm. The smallest acceleration ratio
achievable on a single processor is known. Using multiple processors,
smaller acceleration ratios are possible. In this paper, we provide a
schedule for *m* processors and prove that it is optimal for all
*m*. Our results provide general guidelines for the use of parallel
processors in the design of real-time systems.

### Bibtex entry:

@inproceedings{BPZFaaai02, author = {Daniel S. Bernstein and Theodore J. Perkins and Shlomo Zilberstein and Lev Finkelstein}, title = {Scheduling Contract Algorithms on Multiple Processors}, booktitle = {Proceedings of the Eighteenth National Conference on Artificial Intelligence}, year = {2002}, pages = {702-706}, address = {Edmonton, Alberta}, url = {http://rbr.cs.umass.edu/shlomo/papers/BPZFaaai02.html} }shlomo@cs.umass.edu