Distances, arrivals, and three clocks

A fixed undirected register graph with positive edge weights has a shortest-path metric

Directed weights instead give an asymmetric extended distance. Weights representing routing cost are not automatically communication times or geometric lengths.

In a timed network, waiting and availability are represented explicitly. The earliest-arrival function is

The value is $+\infty$ if there is no path. On a finite time-expanded DAG, dynamic programming in topological order computes the arrivals exactly.

The three clocks are

A certificate assigns model times to ports and, separately, hardware start and finish times. Reordering independent gates can change depth or hardware time without changing the channel. It need not preserve the assigned model-time embedding.