Summary of Relative Scheduling

For an anchor a, at most La + 1 iterations are needed to find the minimum relative schedule because = 0, k La. For all anchors, the algorithm will give the minimum relative schedule with at most L + 1 iterations.  

Corollary 6.4.1 If the constraints implied by the constraint graph G are inconsistent, then the algorithm will detect the inconsistency and terminate after +i iterations. 

Proof Assume the consfraints are inconsistent, implying a positive cycle exists in the graph. Consider the offset To(wi) wj.L an anchor a G A(v,) for a vertex v, on the positive cycle, denoted by ra(t)j). As IncrementalOffset incrementally tries to increase the offsets in order to meet the constraints implied by the forward edges, the readjustment strategy will always increase the value of (Ta(vi). At least one inequality implied by the backward edges will not be satisfied at each iteration. Thus, the algorithm will continue until the( +l) iteration, whereupon the algorithm terminates and returns no schedule.  

In relative scheduling, the start time of an operation is defined as time offsets with respect to the completion of anchors. Constraints are feasible or well-posed depending on whether they can be satisfied under restricted or general input conditions, respectively. Redundancy of anchors was introduced to simplify the start time of operations by removing redundant anchor dependencies. This can lead to a more efficient control implementation because operations need to be synchronized to a fewer number of signals. Analysis of these properties was presented in this chapter. 

---