Well-Posedness of timing constraints

We extend the analysis in order to consider graphs with data-dependent delay vertices. We first define the notion of feasible constraints as follows. 

Definition 6.2.5 A timing constraint is feasible if it can be satisfied when all data-dependent delays are equal to zero, i.e. 6(a) = 0, Va A. Otherwise, it is unfeasible. 

A constraint graph is feasible if every constraint in the graph is feasible. Feasibility is a necessary condition for the existence of a schedule. For the special case of no data-dependent delay vertices, the concept of feasibility is also sufficient to ensure that a schedule for the constraint graph exists. We state the necessary and sufficient condition for feasible constraints in the following theorem. 

Theorem 6.2.1 A constraint graph G V, E) is feasible if and only if no positive cycle exists in G, assuming data-dependent delays in G are set to zero. 

Proof Let Go(V, E) denote the constraint graph G(V, E) where all the data-dependent delays are set to zero. We prove first the necessary condition. If the constraint graph G is feasible, then all constraints in ( o must be consistent Let n = r(t i) Vt)j G V denote a schedule of the constraint graph Go V, E) satisfying the constraints. Consider now a cycle in the graph, denoted 

---