Earliest-Completion Scheduling of Contract Algorithms with End Guarantees

1 Introduction

One of the central objectives in the design of intelligent systems is the provision for anytime capabilities. In particular, several applications such as medical diagnostic systems and motion planning algorithms require that the system outputs a reasonably efficient solution even if interrupted during its execution. Hence the following problem arises: can we transform a given algorithm to its interruptible equivalent, without compromising the algorithm's performance?

This question has motivated research on interruptible systems based on contract algorithms. A contract algorithm receives, as input parameter, its available computation time (i.e., the intended query time). If queried before this deadline, a contract algorithm may output a meaningless result; in other words, the query deadline must be strictly observed (hence the term "contract"). Thus, contract algorithms inherently lack interruptible capabilities; however, they often use simpler data structures, and thus tend to be easier to implement and maintain than interruptible algorithms [Bernstein et al., 2003].

A general technique for obtaining interruptible systems by means of contract algorithms was first given in [Russell and Zilberstein, 1991], and is based on iteratively doubling the available execution times (i.e., the contract lengths) of the contract algorithm. This can be described as a schedule of executions of the same algorithm in which the i-th execution is run for a time equal to 2i . In this schedule, if an interruption occurs at time t, it is guaranteed that a contract of length at least t/4 has completed its execution. Thus, there is a multiplicative gap of 4 between the interruption t and the largest contract length completed by time t, which is called the acceleration ratio [Russell and Zilberstein, 1991] and is a worst-case measure of the efficiency of the schedule. Furthermore, [Zilberstein et al., 2003] showed that no other schedule can perform better according to this measure.

A generalization of the above setting was studied in [Zilberstein et al., 2003] in which n different instances of an optimization problem are given, and each instance is associated with its own contract algorithm. The objective is to design a schedule of interleaved executions of the n contract algorithms, and the acceleration ratio relates the interruption time t to the contract length of the problem instance that has made the least progress by time t (see Section 2 for a formal definition). Thus, the acceleration ratio can be interpreted as the multiplicative increase in processor speed that is required, in worst-case, to render the schedule as efficient as a contract algorithm with a known, given deadline.

Contract scheduling has been studied in a variety of settings. [Zilberstein et al., 2003] gave an optimal schedule for multiple problem instances and a single processor. Optimal schedules were also shown for a single problem instance in several parallel processors [Bernstein et al., 2002], a result that was later generalized to the multi-processor, multiinstance setting [Bernstein et al., 2003; L´opez-Ortiz et al., 2014]. [Angelopoulos et al., 2008] studied contract scheduling in the presence of soft interruptions, and [Angelopoulos and L´opez-Ortiz, 2009] introduced performance measures alternative to the acceleration ratio.

Contract scheduling can be seen as an application of a broader problem in which we seek an intelligent allocation of resources among tasks under uncertainty. Thus, the optimization aspects of this problem can be of interest to other, seemingly unrelated applications. For example, the basic setting of minimizing the acceleration ratio for a single problem instance is equivalent to the online bidding problem which is used in [Chrobak and Mathieu, 2006] as a framework of efficient algorithms based on iterative doubling for several combinatorial optimization problems. It is also identical to the problem of flood search on the line [Baryshnikov et al., 2004]; thus for all these problems, the same optimal multiplicative guarantee equal to 4 is obtained. Moreover, contract scheduling has interesting parallels to the problem of minimizing the competitive ratio of a search strategy in a star-like environment, as shown first in [Bernstein et al., 2003], and later in [Angelopoulos, 2015].

All previous work on contract scheduling based on the acceleration ratio has assumed that the schedule is unbounded since the interruption may occur arbitrarily far in the future. However, in practice, we expect that the execution of a schedule of contract algorithms will reach a point beyond which any progress over the problem instances will be only marginal. For instance [Boddy and Dean, 1994] show that functions of the form Q(t) = 1 - e-λt can be used to model the expected performance of their anytime planner. This means that beyond a certain t0, Q(t) increases quite slowly (see also the discussion in [Zilberstein, 1996]). Similar sharp thresholds can be observed on the performance profiles of anytime algorithms that relate computation time and precision of output in a medical diagnostic system [Horvitz, 1988], as well as in anytime algorithms for planning and sensing [Zilberstein and Russell, 1993]. Therefore, one can argue that a schedule of contracts may be deemed complete once certain end criteria on the efficiency of completed contracts have been met, in terms of the computational time that has been allotted to the problem instances.

As another example, consider the class of Polynomial Time Approximation Scheme (PTAS) algorithms. The vast majority of such algorithms is based on Dynamic Programming, which means that they are not interruptible [L´opez-Ortiz et al., 2014]. These algorithms take as input a parameter ϵ > 0 and output a solution within a factor of (1 + ϵ) of the optimal. Thus, for a given ϵ, one can find an upper bound of the required time (i.e., contract length) that is required to achieve the desired approximation. This implies that once the target approximation is determined, the designer can know exactly what is the required execution time so as to achieve it.

In our work we study contract scheduling in a setting that is motivated by the above applications. In particular, we seek a finite schedule with the following properties: i) it attains the optimal acceleration ratio, as in the standard model; and ii) it minimizes the time required to satisfy the end guarantees, among all schedules that obey property (i). In other words, if an interruption occurs during the execution of the schedule, the schedule has optimal performance; otherwise, if no interruption has occurred, it outputs a solution that meets the end guarantees the earliest possible, among all schedules optimal with respect to the acceleration ratio.

We adopt the following definition of end guarantees, which is in line with the worst-case nature of the acceleration ratio as well as the previous observation on the performance profiles of typical contract algorithms: we allow the schedule to complete once each problem instance has finished a contract of length at least a target value L. In particular, L can be defined in terms of the problem instance whose contract algorithm requires the largest deadline in order to achieve a satisfactory performance, among all instances.

1.1 Contribution

Our contribution is an optimal schedule for the problem described above, namely for earliest completion scheduling of contract algorithms with end guarantees. We propose a schedule that is theoretically optimal, and can be computed in time polynomial in the size of the end guarantee L (and thus in the size of the input, under the reasonable assumption that the number of problem instances n is constant, independent of L). In addition, we present computational results on its implementation which demonstrate that it achieves a considerable improvement over the known schedule that optimizes the acceleration ratio, but is oblivious of L.

The paper is structured as follows: We begin in Section 3 by showing that there exist optimal schedules for our problem that are cyclic, i.e., contracts are assigned to problems in round-robin fashion. This allows us to formulate our setting by means of a linear program (LP). Section 4 describes the main technical steps in the design and analysis of our schedule. More specifically, we prove that an optimal cyclic strategy saturates the constraints of the LP. In turn, this allows us to define an appropriate recurrence relation over the contract lengths, which yields the optimal schedule. Section 5 provides a computational evaluation of the schedule. Last, in Section 6 we show how to solve optimally a "dual" problem in which the interruptible system is given a deadline, and the objective is to maximize the worst-case performance among all problem instances while maintaining optimality according to the acceleration ratio. We illustrate an application of this setting in the context of online bidding with budget.

This work demonstrates that techniques based on linear programming, which have not been explored in previous work, can be very useful. Indeed, to our knowledge, all previous work is based on a variant of iterative doubling; in contrast, we use the structure of optimal LP solutions in order to obtain schedules that are described by more complex, yet still efficiently computable recurrence relations. A main technical obstacle one has to overcome is to derive the recurrence relations from the saturated LP constraints. We emphasize that we do not need to solve any linear program, and that it is used only as a guide in the design and analysis of the schedule. Due to space limitations some proofs are omitted or only sketched.

2 Preliminaries

We assume a single processor and n problem instances or simply problems, numbered 0, . . . , n - 1. A schedule X of m contracts can be described as a sequence of the form ((xi, pi))i∈[1,m], meaning that the i-th scheduled contract in X has length xi and is assigned to problem pi ∈ {0, . . . , n - 1}. For interruption time t, let ℓp,t(X) denote the length (duration) of the longest execution of a contract algorithm for problem p that has completed by time t in X. Then the acceleration ratio of X [Russell and Zilberstein, 1991] is defined

We denote by Tj(X) the completion time of the j-th contract in X and by T(X) the completion time of X (i.e., of its last contract). It is not hard to see that the worst-case interruptions occur infinitesimally prior to the completion of a contract, hence the following useful formula for a schedule of m contracts:

where T - j (X) denotes a time right before Tj(X). We also make the standard assumption that no interruption occurs unless each problem instance has completed a contract in the schedule, and assume, without loss of generality, that X does not schedule a contract of length l for problem p if it has already finished a contract for p of length at least l by that time.

A schedule is called cyclic if its i-th contract is assigned to problem i mod n, and monotone if xi+1 ≥ xi, for all i. The optimal acceleration ratio, denoted by ρ∗n , can be attained by a cyclic (and monotone) strategy such that xi = bi , with b = n+1 n [Zilberstein et al., 2003], from which it follows that ρ∗n = n ( n+1 n )n+1 . We will denote by S∗n the set of all schedules of optimal acceleration ratio ρ∗n .

Given a schedule X, and an end guarantee L ∈ R+, we say that X is feasible for L if for each problem p there is a contract for p in X that has length at least L. A schedule X that is feasible for L is called earliest for L if for any other schedule X′ feasible for L, T(X) ≤ T(X′ ). Using this notation, we can state our problem as follows: Find schedule X∗ (feasible for L) such that X∗ ∈ S∗n , and for every X′ ∈ S∗n , T(X) ≤ T(X′ ). We call such a schedule optimal.

Example 1. Consider the simple case n = 1, and L = 30. An example of a schedule feasible for L is a schedule X with contract lengths 1, 2, 4, 8, 16, 30, which has completion time T(X) = 61. Note also that X is in S∗ 1 , since it has optimal acceleration ratio equal to 4.

3 Cyclic Schedules and the LP Formulation

In this section we show that for a given end guarantee L, there is a cyclic schedule that is optimal for L. This will allow us to focus exclusively on this class of schedules, which we will later analyze by means of an LP. To this end, we first define a property that will be instrumental in the proof.

Definition 2. A schedule X = ((xi, pi))mi=1 is called normalized if for each i ∈ [1,m], ℓpi,Ti-1(X)(X) ≤ ℓq,Ti-1(X)(X), for all q ̸= pi.

Informally, a normalized schedule X assigns, at each time, a contract to the problem that has been worked the least among all problems up to that time. The following lemma shows that for every L there exists an optimal normalized schedule. Its proof expands the property that is already known, namely that there exists a normalized schedule that has optimal acceleration ratio [L´opez-Ortiz et al., 2014].

Lemma 3. For every schedule X feasible for L, there exists a normalized schedule X′ feasible for L such that ρ(X′ ) ≤ ρ(X) and T (X′ ) ≤ T (X).

The following property follows easily from the definition of a normalized schedule.

Lemma 4. Any optimal normalized schedule X is such that for every problem p, X schedules at most one contract for p of length at least L.

Proof. By way of contradiction, suppose that there is a problem p for which X schedules two contracts of length at least L. Let C1, C2 denote these contracts, in the order they appear in the schedule. Since X is normalized, at the moment C2 is about to start, every other problem in X has completed a contract of length at least the length of C1, and thus at least L. Thus, at that moment, X has met the end guarantee. One could then obtain a schedule X′ that is identical to X up to, but not including C2. X′ is also feasible for L; moreover, ρ(X′ ) ≤ ρ(X). However, T(X′ ) < T(X), a contradiction.

The next theorem is central in that it allows us to obtain an LP formulation from the problem. The theorem implies that optimal schedules can be found in the space of cyclic and monotone schedules.

Theorem 5. Given the end guarantee L, there is a cyclic and monotone schedule that is optimal.

Proof. Let X = ((xi, pi))mi=1 denote an optimal schedule given L. From Lemma 3 and 4, we can assume that X is normalized, and that for every problem p, it schedules at most one contract of length at least L. For each problem p ∈ [0, n-1], define by Cp the contract of longest length for p in X, and let C = ∪p{Cp}. We denote by C = X \ C the set of all remaining contracts in X. Note that |C| = n, and |C| = m-n. Let the permutation π : [1,m-n] → [1,m-n] describe the contract lengths of C in increasing order, namely xπ(i) ≤ xπ(i+1) for all i ∈ [1,m-n].

We define a cyclic schedule X′ that is derived from X as follows. X′ is produced by assigning the following m contract lengths to problem instances, in a cyclic manner:

In words, X′ is by construction cyclic, in that we assign length xπ(i) to problem π(i) mod n. The same rule is applied to to the last n contracts of length L. Note that X′ is feasible for L, since it completes a contract of length L for each problem. Moreover, T(X′ ) ≤ T(X), since each contract in X′ can be mapped bijectively to a contract of no great length in X. By definition, xπ(i) < L, for all i ∈ [1,m- n], since X schedules at most one contract of length at least L per problem. Hence, X′ is also monotone.

It remains then to show that ρ(X′ ) ≤ ρ(X). We partition the interruptions for X′ into two classes: Those occurring right before the length xπ(j) contracts, and those occurring right before the length L contracts. Let Tm-n = ∑m-n i=1 xπ(i). Then we can express the acceleration ratio of X′ as the maximum among these types of interruptions by applying (2), which gives

Next, we will lower-bound ρ(X). For j ∈ [1,m- n] let pj denote the problem to which xπ(j) is assigned in X. Since xπ(j) ∈ C, by definition there is another contract in X for problem pj that is executed after xπ(j) inX; let ˜ cj denote the first such contract. Since X is monotone, it follows that right at the moment ˜ cj is to be scheduled in X, all contracts xπ(i), with i ≤ j have already been executed, as well as n contracts that are at least as long as xπ(j). We will consider two cases:

Case 1: j ∈ [1,m- 2n]. In this case ˜ cj completes at time at least ∑j+n i=1 xπ(i) in X, and since the largest contract completed for pj right before ˜ cj terminates is xπ(j) it follows that

Case 2: j ∈ [m-2n+1,m-n]. In this case, ˜ cj completes at time at least Tm-n +(j -(m-2n))L in X, and since the largest contract completed for pj right before ˜ cj terminates is xπ(j), we have that

Combining (3), (4), and (5), shows that ρ(X′ ) ≤ ρ(X), which completes the proof.

Theorem 5 allows us to formulate our problem using an LP. More precisely, it suffices to show that there exists a cyclic schedule X∗ of m∗ contracts of the form X∗ = (x∗1 , . . . , x∗m∗) whose contracts lengths are the optimal solution to the following LP, which we denote by Pm.

Here, constraints (Fi) model the feasibility of X for L; constraints (Ci) imply that X has optimal acceleration ratio, using (2); and constraints (Mi) model the monotonicity of X. Last, we need an initialization constraint for x1, namely (I), which states that x1 has length at most a fixed number τ, which is a constant that does not depend on other parameters. This is a reasonable assumption, but is also required in order to exclude some unacceptable solutions. Otherwise, a cyclic schedule that starts with n contracts of length L would be feasible and optimal for the LP, but this is by no means an interruptible schedule.

4 Obtaining an Optimal Schedule

We will show how to obtain an optimal schedule given L. We will denote by T ∗ (L) the completion time of an optimal schedule. Let C ∗m denote the class of all cyclic schedules with m contracts that have optimal acceleration ratio ρ∗n . For simplicity we denote Ti(X) by Ti when X is clear from context, with T0 = 0.

We first give a road map of our approach. We begin by showing a lower bound on the lengths xi of any schedule of optimal acceleration ratio (Lemma 7). This lower bound is expressed inductively in terms of Ti and two sequences a, b, which are defined appropriately in order to satisfy the inductive arguments. Next, we need to find the best value of m. To this end, we first show that if Pm is feasible, then the lower bounds on the xi's hold with equality. This allows us to express the objective in terms of the parameters n, L and the sequences a, b (Lemma 8). Finally, to find the best value of m, we argue that it suffices to identify the smallest m for which Pm is feasible (Lemma 9).

We define the sequence a and b recursively as follows:

and

Lemma 6. For every i ≥ 0, it holds that ai > 0 and bi ∈ [0, 1n ]. In addition, (bi)i≥0 is monotone increasing with limi→+∞ bi = 1n .

The following lemma lower bounds the contract lengths of schedules in C ∗m.

Lemma 7. For any positive integers m, n with m > n and for every schedule X = (x1, . . . , xm), with X ∈ C ∗m, it holds that xi ≥ am-i · xm-n+1 + bm-i · Ti-1 for i ∈ [1,m]. In addition, xi = am-i · xm-n+1 + bm-i · Ti-1 if constraints (Cj) for j ∈ [i,m] and (Mi) for i ∈ [m-n+1,m- 1] are tight.

Proof. The proof is by induction on i, for i ∈ [1,m]. The base cases can be readily verified. For the inductive step, suppose that for i ≤ m- n it holds that xj ≥ am-jxm-n+1 + bm-jTj-1 with j ∈ [i + 1,m]. We will show that xi ≥ am-ixm-n+1 + bm-iTi-1.

Inductively, it follows that

which is equivalent to xi ≥ am-i ·xm-n+1+bm-iTi-1.

Lemma 7 allows us to find the optimal objective value of Pm, for a given m, assuming Pm has a feasible solution. This is shown in the next lemma.

Lemma 8. Given m ≥ n, assuming that Pm has a feasible solution, then the objective value of Pm is minimized if constraints (Fi) for i ∈ [m - n + 1,m], (Mi) for i ∈ [m- n + 1,m- 1] and (Ci) for i ∈ [n + 1,m] are tight. Moreover, the minimum objective value is

Proof. Given m ≥ n, for any feasible solution X = (x1, . . . , xm) of Pm, by Lemma 7, we have

It follows inductively that

We note that this lower bound is attained if constraints (Fi) for i ∈ [m-n+1,m], (Mi) for i ∈ [m-n+1,m-1] and (Ci) for i ∈ [n+1,m] are tight.

From Lemma 7 and 8, it follows that for a given m, under the assumption that Pm has a feasible solution, the optimal solution is derived by means of the recurrence relation

The initial condition on x1 comes from the constraint (Cn+1) in the LP Pm. Note that if am-1L > τ, then Pm is not feasible, from Lemma 7.

Moreover, from the statement of xi, we have that Ti = ρ∗n · xi-n for all i ∈ [n + 1,m], which implies that xi = ρ∗n (xi-n - xi-n-1), for all i ∈ [n + 2,m]. Moreover, from Lemma 7, xi > 0. Therefore, xi-n > xi-n-1 for i ∈ [n + 2,m]. This in turn means that the solution defined above satisfies constraints (Mi) of Pm (since xi = L for i ∈ [m - n + 1, m]).

Lemma 9. The optimal objective value of Pm is monotone increasing in m. Thus, T ∗ (L) is attained by the optimal objective value of PM, where M is the smallest integer m such that Pm has a feasible solution.

Proof. For m ≥ n, by Lemma 8, the optimal objective value of Pm is α(m)·L, with α(m) = n+∑m-1 j=n aj ∏j-1 k=n (bk+1). By Lemma 6, it follows that α(m) is monotone increasing in m. This concludes the proof.

It remains to find the smallest integer m such that Pm has feasible solutions; denote such m by m∗ . To this end, we give an upper bound to m∗ , as follows: we observe that the exponential cyclic strategy in which the i-th contract has length bi-1 , where b = n+1 n has optimal acceleration ratio ρ∗n (see the discussion in Section 2). Thus, there are at most ⌈ log L log b + n⌉ = O(n logL) candidate values for m∗ , and the overall complexity of the algorithm is O(n2 log2 L). Algorithm 1 summarizes the steps needed to obtain the optimal schedule.

Algorithm 1: Earliest-completion scheduling of contract algorithms with end guarantee L

• 1 Input: n ≥ 1,L > 0 and τ > 0
• 2 U ← ⌈ logL log b +n⌉
• 3 Compute (ai)i∈[1,U], (bi)i∈[1,U] using the recurrence relations (6) and (7)
• 4 for m= n+1 . . .U do
• 5 if am-1L ≤ τ then 6 Output xi, using the recurrence relation xi = am-iL + bm-iTi-1(X), and stop. 7 end 8 end

5 Computational Evaluation

In this section we present computational results on the implementation of our schedule, whose completion time recall we denote by T ∗ (L). In particular, we compare T ∗ (L) to the completion time of the exponential cyclic schedule with base b = n+1 n , whose completion time we denote by Texp(L). Recall that the latter is the known strategy with optimal acceleration ratio, which, however is oblivious of L. We choose τ to be equal to 1, and L to be integral in the range [1, 106 ].

Figure 1 illustrates the completion times of the two schedules for n = 5. We observe that T ∗ (L) is almost linear, unlike Texp(L) which is a step function. Similar almost-linear shapes were observed for T ∗ (L) for the values of n for which we evaluated our schedule, with slopes increasing in n.

Figure 2 illustrates the ratio Texp(L)/T ∗ (L) for n ∈ {1, 2, 20}. We observe that the fluctuations of the ratio, as function of L, tend to decrease in n.

Figure 2 motivates the evaluation of the ratio Texp(L)/T ∗ (L), for large L. This is shown in Figure 3. The experiments suggest that a constant multiplicative gain is achieved by the optimal schedule, and for L = 106 the ratio tends to approximately 1.65, for large n.

We conclude this section with an observation on the run time of the implementation. In our computational evaluation, we observed that the values (ai) described by (6) appear to be monotone decreasing in i, although this is hard to prove analytically. If this indeed holds, then one can show the following fact concerning the LP: If there exists m such that Pm has a feasible solution, then so does Pm+1. This implies a heuristic in which instead of O(n logL) candidate values for m, one needs to check only O(logn + log logL) values, using binary search, which improves the complexity to O(n log(log n + log log L)).

6 Extensions and Further Applications

Consider the following problem, which can be seen as the "dual" of earliest-completion scheduling with end guarantees. Suppose we are given a deadline D, and we would like to obtain a schedule X of contract algorithms for n problems with the following properties: i) T(X) ≤ D, namely the schedule respects the deadline; ii) ρ(X) = ρ∗n ; and iii) X maximizes the parameter minp ℓ(p, D), among all problems p. In words, we seek an interruptible system which has optimal interruptible behavior up to the deadline, and which maximizes the progress that has been made by the deadline among all problem instances. This formulation can be useful in the context of medical diagnostic systems, in which the deadline models the absolute time by which a diagnosis needs to be procured. To solve this dual problem, one can apply Algorithm 1 in combination with binary search over the space of end guarantees, namely with O(logD) applications of our algorithm.

For the special case n = 1, this problem has an equivalent statement, which we call the online bidding problem with budget D. In the online bidding problem [Chrobak and Mathieu, 2006], there is some hidden value u, and a player submits a sequence (xi) of bids until a bid is greater than or equal to u. The player pays the sum of the bids, and the efficiency of the sequence is measured in terms of the competitive ratio, which is the worst-case ratio of the cost paid by the player over the value u. It is known that a simple doubling bidding strategy is competitively optimal, but the setting does not take into account the budget of the bidder. In contrast, our solution provides a competitively optimal bidding strategy with overall cost that does not exceed the bidder's budget D.

7 Conclusion

We studied contract scheduling in a model in which the interruptible system is deemed complete once certain performance guarantee has been reached on all problem instances. In future work we would like to consider more general models of end guarantees. For instance, each problem instance p may be associated with its own end guarantee Lp. We also believe that our approach can be applicable to other budgeted optimization problems. More precisely, we would like to study the setting in which the searcher has a budget in terms of the total area it can cover.