Manuscript En06-B@1 · En06-B.tex · lemma · ee886ae8

Lemma: Vanishing slack is sufficient

Local junctions and the global partition schedule › Parallel routes between frames · lines 748–789 · proof included or linked

En06-B@1#lem:slack, En06-B@1#eq:durationmargin

Back to manuscript

For every fixed finite graph, all sufficiently large $n$ satisfy $N_{e} \geq 1$ and the step criterion (eq:stepcriterion) for every edge.

Proof. The rounding in (eq:vertexclock) gives

N_{e} τ_{n} \geq (1 + η_{n}) T_{e} - (B + 1) τ_{n} .

Since the graph is fixed and has finitely many positive-duration edges, for sufficiently large $n$ ,

(B + 1) τ_{n} \leq \frac{η _{n} T _{e}}{2}

simultaneously for all edges. Hence

N_{e} τ_{n} \geq (1 + η_{n} /2) T_{e} .

Causality implies

\frac{∥ x _{w} - x _{v} ∥ _{2}}{N _{e}} \leq \frac{a _{n}}{1 + η _{n} /2} .

The remaining step margin is

a_{n} - \frac{a _{n}}{1 + η _{n} /2} = \frac{a _{n} η _{n}}{2 + η _{n}} .

On the other hand,

\frac{2 b _{n}}{a _{n}} = \frac{D L}{n ^{2}} = o (η_{n}) .

Thus $2 b_{n} \leq a_{n} η_{n} / (2 + η_{n})$ for all sufficiently large $n$ , proving (eq:stepcriterion). Equation (eq:durationmargin) also proves $N_{e} \geq 1$ .

Displayed formulas in this passage

unlabeled · line 757
$N_{e} τ_{n} \geq (1 + η_{n}) T_{e} - (B + 1) τ_{n} .$
unlabeled · line 763
$(B + 1) τ_{n} \leq \frac{η _{n} T _{e}}{2}$
En06-B@1#eq:durationmargin · line 767
$N_{e} τ_{n} \geq (1 + η_{n} /2) T_{e} .$
unlabeled · line 772
$\frac{∥ x _{w} - x _{v} ∥ _{2}}{N _{e}} \leq \frac{a _{n}}{1 + η _{n} /2} .$
unlabeled · line 777
$a_{n} - \frac{a _{n}}{1 + η _{n} /2} = \frac{a _{n} η _{n}}{2 + η _{n}} .$
unlabeled · line 782
$\frac{2 b _{n}}{a _{n}} = \frac{D L}{n ^{2}} = o (η_{n}) .$

Lemma: Vanishing slack is sufficient

Displayed formulas in this passage

Nearby in this section