Analysis of Control Resynchronization

Formally, we say a graph G implements another graph G if it is derived from G by serializing and lengthening, and we state the following key theorem. 

Theorem 9.4.1 Given a well-posed, ordered, elementary graph G with control cost COST. A well-posed segmented graph G can always be found such that COST COST.  

Proof Consider a vertex w V, v yt vo, of the graph G. By Theorem 9.3.2 we know we can lengthen the graph so that all non-prime anchors of v are made redundant. Furthermore, since G is elementary and ordo ed we know that P.4(v) = 1. Let Ao, Ai. Ajt denote the anchor clusters that have been ordered. Since G is elementary, each clusta contains a single atKhor. Consider two consecutive clusters A,- = a and A +i = 6 such that a . 4(w). The length of a longest path Ipfb, v) (if one exists) from 6 to v is denoted by = Mb,v).  

In (x-der to assign v to the link a maximal timing constraint e i, is added. If a path of positive length from 6 to v exists, then w f, = — lp l , w), otherwise Wvi, = —0. The value of the weight ensures that no positive cycle is formed. Note that is bounded, because if kv is unbounded, then a cannot be a prime anchor of v, which contradicts our assumption. Since no forward edges are added, the anchor sets for all vertices remain unchanged. Since G is well-posed, no anchor sets have been modified, and no positive cycles have been introduced, G is well-posed. 

Likewise, consider an anchor c where c . A(a), i.e. c precedes a in the ordering. For the sake of contradiction, assume that has increased. This implies that a vertex w exists such that there is a path p(c, w) from c to w with exactly one unbounded weight (c). Furthermore, p c,w) must contain the newly added edge e b- Since paths from c to a and from a to v exist, it follows that a path p c,a,v,w) exists. This path has at least two unbounded weights (c) and (a). This implies that c is not a prime anchor of w, and by contradiction, cannot increase. 

---