Gradient clock synchronization (GCS) algorithms minimize the worst-case clock offset between the nodes in a distributed network of diameter $D$ and size $n$. They achieve optimal offsets of $\Theta(\log D)$ locally, i.e. between adjacent nodes <cit.>, and $\Theta(D)$ globally <cit.>. As demonstrated in <cit.>, this is a highly promising approach for improved clocking schemes for large-scale synchronous Systems-on-Chip (SoC). Unfortunately, in large systems, faults hinder their practical use. State of the art fault-tolerant GCS <cit.> has a drawback that is fatal in this setting: It relies on node and edge replication. For $f=1$, this translates to at least $16$-fold edge replication and high degree nodes, far from the optimum of $2f+1=3$ for tolerating up to $f$ faulty neighbors.

In this work, we present a self-stabilizing GCS algorithm for a grid-like directed graph with optimal node in- and out-degrees of $3$ that tolerates $1$ faulty in-neighbor.
If nodes fail with independent probability $p\in o(n^{-1/2})$, it achieves asymptotically optimal local skew of $\Theta(\log D)$ with probability $1-o(1)$; this holds under general worst-case assumptions on link delay and clock speed variations, provided they change slowly relative to the speed of the system. The failure probability is the largest possible ensuring that with probabity $1-o(1)$ for each node at most one in-neighbor fails. As modern hardware is clocked at gigahertz speeds and the algorithm can simultaneously sustain a constant number of arbitrary changes due to faults in each clock cycle, this results in sufficient robustness to dramatically increase the size of reliable synchronously clocked SoCs.

<concept_desc>Hardware Very large scale integration design</concept_desc>
<concept_desc>Computing methodologies Distributed algorithms</concept_desc>

[500]Hardware Very large scale integration design
[500]Computing methodologies Distributed algorithms

[500]Hardware Very large scale integration design

§ INTRODUCTION

In their seminal work from 2004 <cit.>, Fan and Lynch introduced the task of Gradient Clock Synchronization (GCS).
In a network of nodes that synchronize their clocks, it requires to minimize the worst-case clock offset between neighbors.
Two key insights motivate minimizing this local skew:

* In many applications the skew between adjacent nodes is the appropriate measure of quality.

* The global skew, the maximum clock offset between any pair of nodes in the network, grows linearly with the diameter $D$ of the network <cit.>.

Defying the intuition of many, Fan and Lynch proved a lower bound of $\Omega(\log D/\log \log D)$ on the local skew.
Follow-up work then established that this bound was very close to the mark: the best local skew that can be achieved is $\Theta(\log D)$ <cit.>.
This exponential gap between global and local skew strongly suggests better scalability of systems employing this approach to synchronization.

Yet, more than a decade after these results have been published, we know of no efforts to apply these techniques in products.
This is not for want of demand!
To drive this point home, consider the case of clocking synchronous hardware.
Conceptually speaking, state of the art hardware that operates synchronously distributes a clock signal from a single source using a tree network, see e.g. <cit.>.
However, for any tree spanning a square grid, there will be adjacent grid points whose distance in the tree is proportional to the side length of the grid <cit.>.
Hence, the worst-case local skew on a computer chip clocked by a clock tree must grow linearly with the side length of the chip <cit.>.
Indeed, these theoretical results are reflected in the reality of hardware suppliers.
Modern systems gave up on maintaining globally synchronous operation, instead communicating asynchronously between multiple clock islands <cit.>.
This comes at a steep cost, both in terms of communication latency <cit.> and ease of design.

So, which obstacle prevents application?
At least in the above setting, neither large hidden constants nor an overly complex algorithm get in the way.
On the contrary, recent work demonstrates that implementation effort is easily managable and pays off already for moderately-sized systems <cit.>.
Instead, the main obstacle are faults.
To see that this is the key issue, recall that today's hardware comprises an enourmous number of individual components.
Recent off-the-shelf hardware has transistor counts beyond the 10 billion mark <cit.>, requiring either incredibly low fault rates or some degree of fault-tolerance.
In a system composed of multiple clock islands that interact asynchronously, these islands are canonical choices for fault-containment regions.
Thus, one can get away with using a clocking scheme in each island that cannot sustain faults, interpreting a fault of the clocking subsystem as a fault of the respective island.
In contrast, when the clocking subsystems of the islands interact with each other via a clock synchronization algorithm, we must ensure that a clock fault in a single island does not bring down the entire system!

§.§.§ Fault-Tolerant Clocking

When clocking hardware, high connectivity networks are not scalable.
This limits the number of concurrent faults that can be sustained, as tolerating up to $f$ faults requires a node connectivity of $2f+1$.
In <cit.>, this bound is matched asymptotically by augmenting an arbitrary network such that the GCS algorithm from <cit.> is simulated in a fault-tolerant way.
Here, augmentation means to replace each node in the original network by a clique of size $3f+1$ and each edge by a biclique.
The clique then synchronizes internally using the classic Lynch-Welch algorithm <cit.>, and the resulting local outputs are interpreted as (an approximation of) a joint cluster clock on which the (non-tolerant) GCS algorithm from <cit.> is simulated.

Unfortunately, this approach is impractical due to the large overhead in terms of edges.
Leaving asymptotics aside – the edge overhead compared to the original graph is $\Theta(f^2)$ rather than $O(f)$ – even for the important special case of $f=1$ node degrees will be at least $15$.
This is a far cry from the simplicity of current distribution techniques, and factor $5$ beyond the minimum node degree of $2f+1=3$.
What might look like a “moderate constant” to a theoretician will not only cause a headache to the engineer trying to route all of these edges with few layers and precise timing, it will also substantially increase communication delay uncertainty.
This, in turn, directly translates into an increased skew, placing the break-even point with prior art beyond relevant limits.

In summary, it is essential to get as close as possible to the minimum required connectivity.
This train of thought led to the study of fault-tolerant clock distribution in low-degree networks <cit.>.
Both of these works have in common that they assume that the clock signal is generated at a central location.
This enables these approaches to achieve self-stabilization and tolerance to isolated faults with very simple pulse forwarding schemes.
The basic idea is to propagate the signal from layer to layer, having each node wait for two nodes signaling a clock pulse before locally generating and forwarding their own pulse.
Moreover, it is assumed that in absence of faults delays are changing only slowly over time.
Thus, matching the input frequency to the expected delay between grid layers results in clock pulses that are well-synchronized between adjacent layers.

The above works differ in the grid structure they use (<Ref>) and the skew bounds they provide:

* Denoting by $d-u$ and $d$ the minimum and maximum end-to-end communication delay, in a grid of width $D$ <cit.> bounds the local skew by $d+O(u^2 D/d)$. Since in practice $d\gg u$, this is a non-trivial bound. Unfortunately, the fact that $d\gg u$ also means that this bound is too large for applications. Even worse, for each fault this bound increases by $d$.

* In <cit.>, each fault adds at most $u$ to the local skew. Observe that the used grid also has the minimum required connectivity, as each node has only $3$ incoming and outgoing edges each. Alas, these advantages come at the expense of poor scaling of worst-case skews with the number of layers: on layer $\ell$, adjacent nodes may pulse up to $u\ell$ time apart.

TRIX <cit.> (top) and HEX <cit.> (bottom) grids. TRIX uses the naive pulse forwarding scheme of waiting for the second copy of each pulse before forwarding it. We see how the TRIX grid can accumulate a skew of $\Theta(uD)$. In the HEX grid, each node waits for two copies of a pulse from in-neighbours. However, $2$ of the $4$ in-neighbors are on the same layer, causing a skew of $d$ if a neighbor on the preceding layer crashes.
[Previous grid structures: TRIX and HEX]TRIX (top) and HEX (bottom) grids. TRIX uses the naive pulse forwarding scheme of waiting for the second copy of each pulse before forwarding it. We see how the TRIX grid can accumulate a skew of $\Theta(uD)$. In the HEX grid, each node waits for two copies of a pulse from in-neighbours. However, $2$ of the $4$ in-neighbors are on the same layer, causing a skew of $d$ if a neighbor on the preceding layer crashes.

Note that in order to tolerate failure of an arbitrary component, also the clock source has to be replicated and the replicas to be synchronized in a fault-tolerant and self-stabilizing manner.
However, here one can employ techniques for fully connected networks <cit.>;
using them in a single location for $f=1$ does not constitute a scalability issue.

In light of the above, in this work we ask the question

“Can a small local skew be achieved in a fault-tolerant way at minimal connectivity?”

§.§ Our Contribution

We provide a positive answer to the above question for the special case of $f=1$.
This is achieved by using the same grid as in <cit.>, but with a different rule for forwarding pulses.
Our novel algorithm is designed as a discrete and fault-tolerant counterpart to the GCS algorithm from <cit.>.

Making this work requires substantial conceptual innovation and technical novelty.
On the conceptual level, our algorithm simulates a discretized variant of the (non-fault-tolerant!) GCS algorithm from <cit.> on an arbitrary base graph of minimum degree $2$.
In more detail, each copy of the graph, referred to as layer, represents a “time step” of the GCS algorithm.
For each node, there is an edge from its copy on a given layer to the copies of itself and its neighbors on the next layer.
The forwarded pulses along these edges serve two very different functions:

* The pulse messages sent to copies of neigbhors correspond to the GCS algorithm's messages for estimating clock offsets to neighbors.

* The pulse messages sent between copies of the same node convey its local time from one of its copies to the next.

Note that this turns a permanently faulty node in the grid into a simulated node being faulty in a single time step only.
This is of vital importance, because it enables us to rely on the self-stabilization properties of the GCS algorithm from <cit.>.
These are implicitly shown in <cit.>;
we prove them explicitly in the different setting of this work.

However, by itself this does not guarantee bounded skew between correct nodes, since we also need to contain the effect of such a “transient” fault on the state of the simulated algorithm.
Otherwise, a fault would increase skews arbitrarily, effectively corrupting downstream nodes:
at any given node, the smallest or largest time at which a pulse from neighbors on the preceding layer is received could be determined by a faulty node.
We can overcome this issue if there is at most one faulty in-neighbor.
The key observation to controlling the impact of a faulty node on the pulse time lies in that it can indeed affect only one of three times:
the smallest or largest time at which a pulse from copies of neighbors on the previous layer is received, or the time at which the pulse from the copy of the node itself is received.
In particular, the median of these three times lies within the interval spanned by the correct in-neighbors' pulse times.
By imposing the additional constraint to always tie the time at which a pulse is generated closely to this median, we can limit the local impact of a fault on skews.

In summary, we seek to simultaneously simulate a time-discrete variant of the GCS algorithm from <cit.>, while also guaranteeing that pulse forwarding times are, up to a sufficiently small deviation, identical to median reception times plus a fixed offset.
Unfortunately, no existing GCS algorithm that achieves a small local skew <cit.> can be used for this purpose as-is, since their decision rules are in conflict with the above “stick to the median” requirement.

As our main technical contribution, we resolve this conflict, simultaneously adapting the resulting algorithm to the discrete setting.
To do so, we determine suitably weakened discrete variants of the slow and fast conditions introduced in <cit.>.
In essence, we allow that a simulated node whose pulse time is ahead all of its neighbors' pulse times to delay its next pulse by the difference to the fastest neighbor;
an analogous rule applies to nodes pulsing later than all of their neighbors.
From the perspective of the GCS algorithm in <cit.>, this constitutes a potentially arbitrarily large clock “jump,” which we leverage to implement the stick-to-the-median requirement despite the arbitrary changes in timing faulty nodes may apply to their pulse messages.
To prevent uncontrolled oscillatory behavior arising from adjacent nodes “jumping” in opposite directions, we introduce an additional condition, which we refer to as jump condition.
Essentially, it slightly reduces how large jumps are to avoid that uncertainty in message delays and local clock speeds cause nodes to “overswing,” potentially resulting in arbitrarily large skews, cf. <Ref>.

Turning so many knobs at once meant that it was not clear that such a scheme would work.
Indeed, bounding the skew of this novel algorithm turned out to be highly challenging, as jumps that delay pulses rather than speeding them up invalidate the fundamental assumption that clocks progress at rate at least $1$ present in all prior work <cit.>.
As a result, the main technical hurdle and contribution turned out to be proving a bound on the local skew $\localskew_{\ell}$ between neighbors in the same layer $\ell$ for the fault-free case.
If there are no faults, then $\localskew_{\ell}\le 4\kappa (2+\log D)$ for all $\ell\in \N$.

Here, choosing the input clock frequency to be $1/(2d)$ results in $\kappa\in \Theta(u+(\vartheta-1)d)$, where it is assumed that local clocks run at rates between $1$ and $\vartheta>1$.
All of our results require that $d\gg u+(\vartheta-1)d$, or equivalently, that the local skew remains small compared to $d$.
Note that if this condition does not hold, we are outside the parameter range of interest: then skews become large compared to the length of a clock cycle under ideal conditions and clock frequency has to be reduced substantially.

To address faults, we bound by how much faults can affect timing.
Due to the aforementioned stick to the median rule, we can bound the local impact of a fault on timing in terms of the local skew.
However, applying this argument repeatedly, skews would grow exponentially in the number of faults.
While tolerating a constant number of faults is certainly better than tolerating none, this is unsatisfactory, since the requirement of one faulty in-neighbor holds with probability $1-o(1)$ for a fairly high independent probability of $p\in o(1/\sqrt{n})$.
Given that the topology we are most interested in is roughly a square grid, i.e., there are roughly $\sqrt{n}$ layers, the naive approach outlined above does not result in a non-trivial bound on the skew unless $p$ is very close to $1/n$.

We provide an improved analysis exploiting that our base graph is almost a line.
Hence, the $d$-hop neighborhood grows linearly with $d$ and hence the number of nodes in layers $\ell'\in [\ell-n^{1/12},\ell]$ that affect the pulse time of a node in layer $\ell$ is in $\Theta(n^{1/6})$.
Thus, if nodes fail with probability $p\in o(1/\sqrt{n})$, the probability that there are more than $2$ faulty nodes within distance $n^{1/12}$ that affect a given node is $o(1/n)$.
Intuitively, this buys enough time for the self-stabilization properties of the simulated algorithm to reduce its local skew again before it spirals out of control.
With probability $1-o(1)$, $\localskew_{\ell}\in O(\kappa \log D)$ for all $\ell \in \N$.

The final step is to extend this bound on the local skew within a layer to one that includes adjacent nodes in different layers.
As we propagate pulses layer by layer, we cannot hope to match pulse times of the $k$-th pulse between different layers.
Instead, we match the input period to the nominal time a pulse spends on each layer.
This works neatly so long as there are no changes in message delay, clock speed, and behavior of faulty nodes between consecutive pulses.
If faulty nodes do not change the timing of their output pulses, then $\localskew\in O(\kappa \log D)$ with probability $1-o(1)$.

To a large extent, this strong assumption is justified in our specific context.
Clock speeds of modern systems are in the gigahertz range, and the amount of change in timing that occurs within a single clock cycle is much smaller than over the lifetime of a system <cit.>.
Similarly, the by far most common timing faults are stuck-at faults, i.e., the signal observed by downstream nodes remains constant logical $0$ or $1$, and broken connections.
From the point of view of the receiving node, this is equivalent to an early or late pulse, respectively, without any change between pulses.

Of course, timing will still change slowly, the above benign faults will occur at some point, before which the nodes worked correctly, and some faults may be more severe.
Using once more that faulty nodes' impact on timing is bounded by the local skew, the bound from <Ref> extends to a constant number of arbitrary faults in each pulse alongside small changes in delays and hardware clock speeds.
With probability $1-o(1)$, $\localskew \in O(\kappa \log D)$ even when in each pulse (i) a constant number of faulty nodes change their output behavior and timing, (ii) link delays vary by up to $n^{-1/2}u \log D$, and (iii) hardware clock speeds vary by up to $n^{-1/2}(\vartheta-1)\log D$.

Finally, if all else fails, we can fall back on the ability of the pulse progation algorithm to recover from arbitrary transient faults.
In constrast to the simulated GCS algorithm, achieving self-stabilization of the pulse propagation scheme itself is straightforward due to the directionality of the propagation.

The pulse propagation algorithm can be implemented in a self-stabilizing way.
It stabilizes within $O(\sqrt{n})$ pulses.

In light of these results, we view this work as a major step towards simultaneously achieving high performance and strong robustness in the practical setting of clock distribution in hardware.
In alignment with the theoretical question motivating this work, we achieve an asymptotically optimal local skew at the minimum possible node degree under the assumption of node failures with probability $o(n^{-1/2})$.

§.§.§ Organization of this Article

In <Ref>, we discuss the system model, introduce the graph on which we run our synchronization algorithm, and motivate our modeling choices, including its non-standard aspects.
We then present a simplified version of the algorithm that better highlights the conceptual approach in <Ref>; the full algorithm and its equivalence without faulty predecessors is shown in <Ref>.
We follow with the formal derivation of the skew bounds in <Ref>.

§ MODELING

The model we use is non-standard, as it is tailored to the specific setting outlined in the introduction.
Accordingly, we will emphasize and discuss model choices where this seems prudent.

§.§.§ Setting

Recall that our goal is to provide a synchronized clock signal to a large System-on-Chip.
Physically, this means that we need to provide the clock signal to a rectangular area; for simplicity, we will assume it to be square.
We want to supply a uniform grid of nodes in the square area with this signal, which then will serve as roots of relatively small local clock trees supplying the low-level components with the clock signal.
If these trees contribute a maximum clock skew of $\Delta$ and the skew between adjacent grid points is at most $\localskew$, the triangle inequality guarantees a worst-case skew of $\localskew + 2\Delta$ between adjacent components of the System-on-Chip.
The local clock trees can be designed using standard methodology.
Therefore, in the following we will focus exclusively on the grid of their roots.

A key assumption we make is that communication delay between correct adjacent nodes changes only slowly with time.
This enables us to generate synchronized pulses at all grid nodes by matching the input frequency with the (inverse) propagation time between consecutive layers.
This is justified for two reasons:

* The dominant sources of uncertainty in propagation delay are inaccuracies in component fabrication, aging, and temperature and frequency variations that are slow relative to the time it takes to propagate an input clock pulse across even a large System-on-Chip <cit.>

* Changing delays of all links between a pair of adjacent layers by up to $\delta$ increases skew bounds by at most $\delta$, cf. <Ref>.

In order to generate sufficiently synchronized pulses at the nodes of layer $0$, a straightforward solution is to use a redundant path, i.e., a path of $3$-cliques in which adjacent cliques are fully bipartitely connected, to propagate pulses from the clock reference along an edge of the chip.
As we show in <Ref>, this results in input pulses of small enough local skew.
For each clique, one of the nodes will be the layer-$0$ node providing its output pulse to close-by nodes of layer $1$.

In a perfect grid, all layers would consist of a path.
Unfortunately, this results in the issue that the endpoints of the path, lacking one neighbor, would have only two adjacent nodes in the preceding and subsequent layer.
A naive solution is to insert a additional edges between the boundary nodes, turning the layer into a cycle and the entire graph into a cylinder (with some special treatment of layer $0$).
However, realizing such a solution on the square would result in far too long edges between boundary nodes or require to, essentially, replicate each layer, effectively doubling the number of nodes and edges in the graph.

Instead, we choose to replicate the boundary nodes only, which then provides the “missing” input to the next layer.
Note that this increases the degree of the nodes next to the boundary nodes by one.
We cope with this by a general analysis allowing for the layers to be copies of an arbitrary base graph of minimum degree $2$.

In <Ref> and <Ref>, we show the base graph and the connectivity of nodes between adjacent layers of our synchronization network in our assumed setting.

§.§.§ Network Graph

Base graph $H$ used in this work. Rather than using a cycle, which would result in a TRIX grid, we replicate the end nodes of a line to ensure a minimum degree of $2$. Alternatively, one could use a line and exploit that the probability that one of the $O(\sqrt{n})$ boundary nodes fails is $o(1)$.
[Base Graph $H$ of our grid]

We are given a simple connected base graph $H=(V,E)$ of minimum degree $2$ and diameter $D\in \N_{>0}$.
For $v,w\in V$, denote by $d(v,w)\le D$ the distance from $v$ to $w$ in $H$.
To derive the graph $G=(V_G,E_G)$ we use for synchronization, for each $\ell\in \N$ we create a copy $V_{\ell}$ of $V$.
Denoting by $(v,\ell)$ the copy of $v\in V$ in $V_{\ell}$, we define $E_{\ell}:=\{((v,\ell),(w,\ell+1))\,|\,\{v,w\}\in E \vee v=w\}$.
We now obtain $G$ by setting $V_G:=\bigcup_{\ell \in \N}V_{\ell}$ and $E_G:=\bigcup_{\ell \in \N} E_{\ell}$.
That is, for each layer $\ell\in \N$ we have a copy of $v\in V$, which has outgoing edges to the copies of itself and all its neighbors on layer $\ell+1$.[This is an abuse of notation, since in a (roughly) square grid of $n:=|V_G|$ nodes, we have $\Theta(\sqrt{n})$ layers. Since $n$, i.e., the size of the grid, will only play a role when making probabilistic statements, we opted for this more convenient notation.]
Sine $V_G$ is a DAG, we refer to out-neighbors as successors and in-neighbors as predecessors.

Layer structure of $G$ resulting from our choice of $H$. Most nodes have in- and out-degree $3$, some $4$.
[Connectivity between adjacent layers of our grid]

§.§.§ Fault Model

An unknown subset $F\subset V_G$ is Byzantine faulty, meaning that these nodes may violate the protocol arbitrarily.
Edge faults are mapped to node faults, i.e., if edge $((v,\ell),(w,\ell+1))$ is faulty, we instead consider $(v,\ell)$ faulty.
We impose the constraint that no node has two faulty predecessors.
Formally, for all $\ell\in \N$ and $v\in V$, $|(\{(v,\ell)\}\cup \bigcup_{\{v,w\}\in E}\{(w,\ell)\})\cap F|\le 1$.
When analyzing the system under random faults, we will assume that each node fails independently with probability $p\in o(1/\sqrt{n})$, which ensures that the above constraint is met with probability $1-o(1)$.
In addition, we impose the restriction that at most a constant number of such faulty nodes change their timing behavior between consecutive pulses.

§.§.§ Communication

Each node has the ability to broadcast pulse messages on its outgoing edges.
If node $v_{\ell}\in V_{\ell}$ broadcasts at time $t_{v,\ell}$, its successors receive its message at a (potentially different) time from $[t_{v,\ell}+d-u,t_{v,\ell}+d]$.
The maximum end-to-end delay $d$ includes any delay caused by computation.
Typically, the delay uncertainty $u$ is much smaller than $d$.
As discussed above, we assume delays to be static, i.e., each edge $e=((v,\ell),(w,\ell+1))$ has an unknown, but fixed associated delay $\delta_e\in [d-u,d]$ applied to each pulse sent from $(v,\ell)$ to $(w,\ell+1)$.

Note that faulty nodes can send pulses at arbitrary times, without being required to broadcast;
even if physical node implementations disallow point-to-point communication, edge faults could still result in this behavior.

§.§.§ Local Clocks and Computations

Each node is able to approximately measure the progress of time by means of a local time reference.
We model this by node $(v,\ell)$ having query access to a hardware clock $H_{v,\ell}\colon \Rpositive\to \Rpositive$ satisfying

\begin{align*}
\forall t < t'\in \Rpositive,\ t'-t\leq H_{v,\ell}(t') - H_{v,\ell}(t) \leq \vartheta(t' - t).
\end{align*}

for some $\vartheta>1$.
No known phase relation is assumed between the hardware clocks.
The algorithm will use them exclusively to measure how much time passes between local events.
Analogous to delays, we assume that hardware clock speeds are static.
This is justified in the same way as for delays.

Computations are deterministic.
However, in addition to receiving a message, the hardware clock reaching a time value previously determined by the algorithm can also trigger computations and possibly broadcasting a pulse.

§.§.§ Output and Skew

The goal of the algorithm is to synchronize the pulses generated by correct nodes.
We assume that correct nodes on layer $0$ generate well-synchronized pulses at times $t_{v,0}^k$ for $k\in \N_{>0}$ at a frequency we control.
In <Ref>, we discuss how to realize this assumption in detail.
All other correct nodes generate pulses $t_{v,\ell}^k$, $k\in \N_{>0}$, based on the pulse messages received from their predecessors.

Our measure of quality is the worst-case local skew the algorithm guarantees.
We define the local skew as the largest offset between the $k$-th pulses of adjacent nodes on the same layer or pulses $k$ and $k+1$ of adjacent nodes on layers $\ell$ and $\ell+1$, whichever is larger.
Formally, for $\ell \in \N$ we define

\begin{equation*}
\localskew_{\ell}:=\sup_{k\in \N}\max_{\substack{\{v,w\}\in E\\ (v,\ell),(w,\ell)\notin F}}\{|t_{v,\ell}^k-t_{w,\ell}^k|\},\quad
\localskew_{\ell,\ell+1}:=\sup_{k\in \N}\max_{\substack{((v,\ell),(w,\ell+1))\in E_{\ell}\\ (v,\ell),(w,\ell+1)\notin F}}\{|t_{v,\ell}^k-t_{w,\ell+1}^{k+1}|\},
\end{equation*}

and $\localskew :=\sup_{\ell \in \N}\max\{\localskew_{\ell},\localskew_{\ell,\ell+1}\}$.
This deviates from the standard definition of the local skew:

* The definition is adjusted to pulse synchronization, which can be viewed as an essentially equivalent time-discrete variant of clock synchronization <cit.>.

* Between consecutive layers, we synchronize consecutive pulses. After initialization, which is complete once the first pulse propagated through the (in practice finite) grid, this is equivalent to a layer-dependent index shift of pulse numbers.

§ ALGORITHM

In this section, we discuss the pulse forwarding algorithm.
We provide a simplified version of the algorithm that behaves identical so long as the predecessors of the executing node are correct.
The full algorithm needs to handle the possibility that faulty nodes send multiple messages or none at all.
This complicates bookkeeping and loop control, distracting from the principles underlying the algorithm's operation.
Accordingly, we defer the full algorithm to <Ref>, where we show the equivalence to the simplified variant when there are no faulty predecessors.

§.§ Simplified Pulse Forwarding Algorithm

The algorithm proceeds in iterations corresponding to pulses.
In each iteration, node $(v,\ell)$

* timestamps the arrival times of the pulses of its predecessors using its hardware clock,

* determines a correction value $\Cor_{v,\ell}$ based on these timestamps, and

* forwards the pulse $\Lambda-d-\Cor_{v,\ell}$ time after receiving the pulse from $v_{\ell-1}$, measured by its hardware clock.

If all reception times are close to each other, then $\Cor_{v,\ell}$ will be small.
Recalling that messages are in transit for roughly $d$ time, this translates to $\Lambda$ being the nominal time for a pulse to propagate from layer $\ell-1$ to layer $\ell$.
We need to choose $\Lambda$ large enough such that the above sequence can be always realized.
That is, we need to consider how far apart the reception times of messages from the previous layer can be, and ensure that $\Lambda-d$ exceeds this value plus the resulting $\Cor_{v,\ell}$.

Simplified pseudocode for discrete GCS at node $(v,\ell)$, $\ell>0$. As shown in <Ref>, this code is equivalent to <Ref> in the absence of faults. The parameters $\Lambda$ and $\kappa$ will be determined later, based on the analysis.

$H_{\own},H_{\min},H_{\max} := \infty$
received pulse from $(v,\ell-1)$
$H_{\own} := H_{v,\ell}(t)$
received pulse from first $(w,\ell-1)$, $\{v,w\}\in E$
received pulse from last $(w,\ell-1)$, $\{v,w\}\in E$
$H_{\own}, H_{\min}, H_{\max}<\infty$
$\Cor_{v,\ell}:=\min_{s\in \N}\{\max\{H_{\own}-H_{\max}+4s\kappa,H_{\own}-H_{\min}-4 s\kappa \}\}-\kappa/2$
$\Cor_{v,\ell}:=\min\{H_{\own}-H_{\min} -\kappa/2+2\kappa,0\}$
$\Cor_{v,\ell}:=\max\{H_{\own}-H_{\max} -\kappa/2-\kappa,\vartheta\kappa\}$
wait until $H_{v,\ell}(t) = H_{\own} + \Lambda - d - \Cor_{v,\ell}$
broadcast pulse

Assuming that this precondition holds, <Ref> implements the above approach.
In each loop iteration, it initializes three reception times to $\infty$:

* $H_{\own}$, which stores the arrival time of the pulse from $(v,\ell-1)$. From the perspective of the simulated GCS algorithm, this reflects the state of the node $v\in V$ simulated by $(v,\ell)$, $\ell\in \N$.

* $H_{\min}$, which stores the minimum arrival time of a pulse from a neighbor $w_{\ell-1}$, $w\neq v$. This corresponds to the first pulse received from a neighbor $w$ of $v$ in $G$ in this iteration.

* $H_{\max}$, which stores the maximum arrival time of a pulse from a neighbor $w_{\ell-1}$, $w\neq v$. This corresponds to the last pulse received from a neighbor $w$ of $v$ in $G$ in this iteration.

The do-until loop fills these variables with the correct values.
At the heart of the algorithm lies the computation of $C_{v,\ell}$.
If there were no faults, one could always compute

\begin{equation*}
\Delta:=\min_{s\in \N}\left\{\max\{H_{\own}-H_{\max}+4s\kappa,H_{\own}-H_{\min}-4 s\kappa \}\right\}-\frac{\kappa}{2}
\end{equation*}

and then choose the closest value from the range $[0,\vartheta \kappa]$, i.e., set

\begin{equation*}
\Cor_{v,\ell}:=\begin{cases}
\Delta & \mbox{if $\Delta \in [0,\vartheta \kappa]$,}\\
0 & \mbox{if $\Delta <0$, and}\\
\vartheta \kappa & \mbox{if $\Delta > \vartheta \kappa$.}
\end{cases}
\end{equation*}

To get intuition on this choice, observe that $\min_{x\in \R}\{\max\{H_{\own}-H_{\min}-x,H_{\own}-H_{\max}+x\}\}$ is attained when $H_{\own}-H_{\max}+x=H_{\own}-H_{\min}-x$, which is equivalent to $x=(H_{\max}-H_{\min})/2$, i.e., $H_{\own}-\Delta=(H_{\max}-H_{\min})/2$.
If timing was perfectly accurate, the reception times of the pulse messages could serve as exact proxies for the actual pulse forwarding times of the nodes on layer $\ell-1$.
In iteration $k$, this would mean to generate the pulse at $(v,\ell)$ faster if $(v,\ell-1)$ generated its pulse later than the average of $\min_{\{v,w\}\in E}\{t_{w,\ell-1}^k\}$ and $\max_{\{v,w\}\in E}\{t_{w,\ell-1}^k\}$.
Thus, any $(v,\ell)$ for which $t_{v,\ell-1}^k-\min_{\{v,w\}\in E}\{t_{w,\ell-1}^k\}>\max_{\{v,w\}\in E}\{t_{w,\ell-1}^k\}-t_{v,\ell-1}^k$ would choose $C_{v,\ell}>0$, attempting to reduce $\max_{\{v,w\}\in E}\{|t_{v,\ell}^k-t_{w,\ell}^k|\}$ compared to $\max_{\{v,w\}\in E}\{|t_{v,\ell-1}^k-t_{w,\ell-1}^k|\}$.
This can be viewed as trying to reduce the local skew by a greedy strategy.

Unfortunately, this naive strategy fails to account for inaccuracies due to message delay uncertainty and drifting hardware clocks.
Nonetheless, we follow this strategy up to deviations of $O(\kappa)$.
The additional terms serve the following purposes:

* Considering only discrete choices for $x\in 4\kappa \N$ rather than arbitrary $x\in \R$ is the key ingredient that makes the algorithmic approach succeed, cf. <cit.>. Essentially, this is necessary because there is no way to determine $t_{v_{\ell-1},k}-t_{w_{\ell-1},k}$ precisely. Discretizing observed skews in units of $\kappa\in \Theta(u+(\vartheta-1)(\Lambda-d))$ enables a delicate strategy that alternates between overestimating skews to locally generate the next pulse earlier for the sake of “catching up” with others and underestimating skews to “wait” for others catch up.

* Substracting $\kappa/2$ accounts for errors in measuring skews, which are caused by uncertainty in message delay and hardware clock speed.

* To limit the damage that a faulty predecessor of $(v,\ell)$ can do, we ensure that $(v,\ell)$ generates its pulse without too large of a deviation from the median of $t_{v,\ell-1}$, $\min_{\{v,w\}\in E}\{t_{w,\ell-1}^k\}$, and $\max_{\{v,w\}\in E}\{t_{w,\ell-1}^k\}$ (plus the nominal offset of $\Lambda$). This is achieved by permitting corrections $C_{v,\ell}<0$ if $(v,\ell-1)$ clearly generated its pulse earlier than $\min_{\{v,w\}\in E}\{t_{w,\ell-1}^k\}$ and $C_{v,\ell}>\vartheta \kappa$ if it clearly generated its pulse later than $\max_{\{v,w\}\in E}\{t_{w,\ell-1}^k\}$, respectively.

To further motivate the last point, recall that there can be at most one fault among the predecessors of $(v,\ell)$.
A single faulty predecessor can only affect only one of the three values $H_{\own}$, $H_{\min}$, and $H_{\max}$: control $H_{\own}$ arbitrarily, $H_{\min}$ to be smaller than the minimum reception time from a correct node $(w,\ell-1)$, $\{v,w\}\in E$, or $H_{\max}$ to exceed the maximum reception time from correct nodes $(w,\ell-1)$, $\{v,w\}\in E$.
Hence, ensuring that pulses are generated with only a small offset relative to $\median{H_{\own}, H_{\min}, H_{\max}}+\Lambda-d$ indeed limits the damage that a fault can do.

Achieving all of the desired properties is non-trivial, leading to the fairly involved choice of $\Cor_{v,\ell}$.
It can be viewed as simultaneously implementing relaxed fast and slow conditions (as introduced in <cit.>), an additional jump condition required to make the GCS algorithm work under these relaxed fast and slow conditions, and the requirement to stick close to the median of predecessors' pulse times.
In <Ref>, we specify the (relaxed) slow and fast condition, as well as the jump condition, and show that the algorithm implements them.
<Ref> show that the algorithm also enforces deviates little from the time interval spanned by correct predecessors (offset by $\Lambda$).

There is some freedom in the choice of parameters.
For simplicity, we fix a good choice of $\kappa$ and note that $d$ must satisfy a lower bound $B\in O(\sup_{\ell\in \N}\{\localskew_{\ell}\}+\kappa)$.
Observe that this constraint simply means that the skew bounds are useful, as a skew that is of similar size as the maximum end-to-end delay requires to slow the system down substantially.
Finally, $\Lambda$ must be at least $d+O(\sup_{\ell\in \N}\{\localskew_{\ell}\})$, which due to the previous constraint holds e.g. for the choice $\Lambda=2d$.
Formally, for a sufficiently large constant $C$,[We do not attempt to optimize constants in this work.]

\begin{align}
\kappa & := 2\left(u+\left(1-\frac{1}{\vartheta}\right)(\Lambda-d)\right),\label{eq:kappa}\\
\Lambda &\ge C\vartheta(\sup_{\ell\in \N}\{\localskew_{\ell}\} + u) + d,\mbox{ and}\label{eq:Lambda}\\
d &\ge C(\vartheta(\sup_{\ell\in \N}\{\localskew_{\ell}\} + u)+\kappa).\label{eq:d}
\end{align}

§.§.§ Complete Algorithm

The complete algorithm cannot wait for messages from all predecessors to determine when to send its pulse, as a faulty node not sending its pulse then would deadlock all its descendants.
As discussed above, the hardware clock time of the next pulse time does not deviate much from $\median{H_{\own}, H_{\min}, H_{\max}}+\Lambda-d$, but does depend on $\max\{H_{\min},H_{\own},H_{\max}\}$ in some cases.
However, we will prove that $\localskew_{\ell-1}$ is small enough such that all pulse messages from correct nodes will be received in time.
Hence, it is sufficient to wait until $\median{H_{\own}, H_{\min}, H_{\max}}+\vartheta \localskew_{\ell-1}$ (or later) according to $H_{v,\ell}$.
Provided that $\Lambda-d$ is large enough, this implies that any message for computing $\Cor_{v,\ell}$ missing is due to a fault;
in fact, at the point in time when this becomes clear, $\Cor_{v,\ell}$ is already determined, regardless of how late the message would arrive.

The complete algorithm differs from <Ref> by covering the case that a signal does not arrive in time.
Intuitively, one can treat the respective message arrival time ($H_{\own}$ or $H_{\max}$, $H_{\min}$ is not possible) as $\infty$, while allowing such an $\infty$ to cancel out in substraction:

* If $H_{\own}=\infty$, then $C_{v,\ell}\in H_{\own}-H_{\max}-O(\kappa)$, and $(v,\ell)$ will generate its pulse at local time $H_{\own}+\Lambda-d-C_{v,\ell}\in H_{\max}+\Lambda-d+O(\kappa)$.

* If $H_{\max}=\infty$ and $H_{\own}\ge H_{\min}$, then $C_{v,\ell}\in H_{\own}-H_{\min}\pm \Theta(\kappa)$ and $(v,\ell)$ will generate its pulse at local time $H_{\own}+\Lambda-d-C_{v,\ell}\in H_{\min}+\Lambda-d\pm O(\kappa)$.

* If $H_{\max}=\infty$ and $H_{\own}< H_{\min}$, then $C_{v,\ell}\in [0,2\kappa]$ and $(v,\ell)$ will generate its pulse at local time $H_{\own}+\Lambda-d-C_{v,\ell}\in H_{\own}+\Lambda-d-O(\kappa)$.

Note that in all cases, the pulse is generated with an offset of $\Lambda-d-\Theta(\kappa)$ from the median reception time.
The complete algorithm follows the above intuition, leveraging the fact that there is no need to wait indefinitely to determine that the third signal is late, and is given in <Ref>.

Last, but not least, it is of interest to make the pulse forwarding algorithm self-stabilizing <cit.>.
Due to the design choice of propagating the clock signal from a single source along a DAG, this will immediately translate to the overall scheme being self-stabilizing, so long as the clock generation is self-stabilizing, too.
This is straightforward, because one can assume that the signals from the previous layer are already well-synchronized.
Thus, all that nodes need to do is to detect when all but possibly one (faulty) pulse signal arrive in close temporal proximity to determine when to clear their memory and start a new iteration of the main loop.
In <Ref>, we sketch how this can be achieved using standard techniques.

§ ANALYSIS

We now analyze the pulse progagation scheme under the assumption that layer $0$ generates well-synchronized pulses.
We discuss a suitable method for achieving this in <Ref>.
Our analysis proceeds along the following lines:

* We show that, if the local skew is small enough compared to $\Lambda$, i.e., <Ref> holds, all correct nodes execute their iterations as intended. That is, each correct node on layer $\ell>0$ receives the $k$-th pulses of its correct predecessors in its $k$-th loop iteration. This is deferred to <Ref>. We then proceed under the assumption that this holds true, which will be justified retroactively once we establish that the local skew is bounded.

* Since delays and hardware clock speeds are (approximated as being) static, any (substantial) change in relative timing of consecutive pulses is due to faulty nodes. Thus, the task of bounding the local skew reduces to bounding the intra-layer skew $\localskew_{\ell}$ for a single pulse, since such a bound must take into account the full variability introduced by faulty nodes. This reasoning is deferred to <Ref>.

* Based on potential functions, we analyze $\localskew_{\ell}$ in the absence of faults. The results entail not only bounded skew, but also that the potentials recover if they become unexpectedly large.

* We show that faulty nodes have limited impact on the potentials. From this and the above recovery property, we conclude that skews behave favorably also when there are faults.

As stated above, the first two steps of our line of reasoning are deferred to the appendix.
The main challenge is to bound $\localskew_{\ell}$ for a single pulse.
Due to the first step, we know that the $k$-th pulse at correct nodes depends only on the $k$-th pulses of their predecessors (<Ref>).
Therefore, in the following fix $k$ and denote the $k$-th pulse time of correct $(v,\ell)\in V_G$ by $t_{v,\ell}$.

Recall that for $v,w\in V$, we denote by $d(v,w)$ their distance in the base graph $H$.
Our analysis is built around the following potential functions.

Let $v,w\in V$ and $s,\ell\in \N$.
We define

\begin{align*}
\psi^s_{v,w}(\ell) &:= t_{v,\ell} - t_{w,\ell} - 4s\kappa d(v,w),\\
\Psi^s(\ell) &:= \max_{v,w\in V}\{\psi^s_{v,w}(\ell)\},\\
\xi^s_{v,w}(\ell) &:= t_{v,\ell} - t_{w,\ell} - (4s-2)\kappa d(v,w),~\mbox{and}\\
\Xi^s(\ell) &:= \max_{v,w\in V}\{\Xi^s_{v,w}(\ell)\}.
\end{align*}

Bounding $\Psi^s(\ell)$ readily translates to bounding $\localskew_{\ell}$.

If for $s,\ell\in \N$ and some $\Psi^s\in \Rpositive$ it holds that $\Psi^s(\ell)\le \Psi^s$, then $\localskew_{\ell}\le \Psi^s+4s\kappa$.

Fix $k\in \N$ and suppose that $\{v,w\}\in E$ maximizes $|t_{v,\ell} - t_{w,\ell}|$.
W.l.o.g., assume that $t_{v,\ell}\ge t_{w,\ell}$.
Since $\{v,w\}\in E$, we have that $d(v,w)=1$.

\begin{equation*}
|t_{v,\ell} - t_{w,\ell}|=t_{v,\ell} - t_{w,\ell}=\psi^s_{v,w}(\ell)+4s\kappa\le \Psi^s(\ell)+4s\kappa\le \Psi^s+4s\kappa.
\end{equation*}

Since $k\in \N$ is arbitrary, it follows that $\localskew_{\ell}\le \Psi^s+4s\kappa$.

In summary, the goal of our analysis will be to bound $\Psi^s(\ell)$ by a small value for some $s$ satisfying $4s\kappa\in O(u\log D)$.

We first study the behavior of the algorithm if there are no faults.
Accordingly, this will be tacitly assumed in all statements of this section, with the expection of <Ref>.
Note that by <Ref>, this means that we may also tacitly assume that <Ref> is run by all nodes in layers $\ell\in \N_{>0}$.
In <Ref>, we will then bound the impact of faulty layers on the potential.

§.§ Basic Statements

We first show three basic lemmas.
The first relates the local reception times of pulses to the actual sending times, bounding the error by $\kappa$.

For $(v,\ell)\in V_{\ell}$, $\ell\in \N_{>0}$, set $t_{\min}:=\min_{\{v,w\}\in E}\{t_{w,\ell-1}\}$ and $t_{\max}:=\min_{\{v,w\}\in E}\{t_{w,\ell-1}\}$.

\begin{align*}
t_{v,\ell-1}-t_{\max}-\kappa &\le H_{\own}-H_{\max}-\frac{\kappa}{2} \le t_{v,\ell-1}-t_{\max}\\
t_{v,\ell-1}-t_{\min}-\kappa &\le H_{\own}-H_{\min}-\frac{\kappa}{2} \le t_{v,\ell-1}-t_{\min}.
\end{align*}

We prove the first inequality; the second is shown analogously. Let $t'_{v,\ell-1}$ and $t'_{\max}$ denote the times when the pulse messages sent at time $t_{v,\ell-1}$ and $t_{\max}$ are received at $v_{\ell}$, respectively. From the bounds on message delays, it follows that

\begin{align*}
t_{v,\ell-1} + d-u &\leq t'_{v,\ell-1} \leq t_{v,\ell-1} + d\mbox{ and}\\
t_{\max} + d - u&\leq t'_{\max} \leq t_{\max} + d.
\end{align*}

\begin{align*}
t_{v,\ell-1} - t_{\max} - u\leq t'_{v,\ell-1} - t'_{\max} \leq t_{v,\ell-1} - t_{\max} + u.
\end{align*}

Using the bounds on hardware clock rates, we get that

\begin{equation*}
|t_{v,\ell-1}' - t_{\max}' -(H_{\own} - H_{\max})|\le (\vartheta-1)|t_{v,\ell-1}' - t_{\max}'|\le (\vartheta-1)(|t_{v,\ell-1} - t_{\max}|+u).
\end{equation*}

Applying <Ref>, we infer that

\begin{align*}
|t_{v,\ell-1} - t_{\max} -(H_{\own} - H_{\max})| &\le |t_{v,\ell-1}' - t_{\max}' -(H_{\own} - H_{\max})|+u\\
&\le (\vartheta-1)|t_{v,\ell-1} - t_{\max}| + \vartheta u\\
&\le (\vartheta-1)\localskew_{\ell-1} + \vartheta u\\
&\le (\vartheta-1)\left(\frac{\Lambda-d}{\vartheta}-u\right)+\vartheta u\\
&=\left(1-\frac{1}{\vartheta}\right)(\Lambda-d)+ u.
\end{align*}

Finally, using <Ref>, we conclude that

\begin{align*}
t_{v,\ell-1}-t_{\max}-\kappa &\le t_{v,\ell-1}-t_{\max}-2\left(\left(1-\frac{1}{\vartheta}\right)(\Lambda-d)+ u\right)\\
&\le H_{\own}-H_{\max}-\frac{\kappa}{2}\\
& \le t_{v,\ell-1}-t_{\max}.\qedhere
\end{align*}

The second lemma shows that corrections are not too large.

For all $v\in V$ and $\ell\in \N_{>0}$, $\Cor_{v,\ell} \le \Lambda - d$.

\begin{equation*}
\Delta=\min_{s\in \N}\left\{\max\{H_{\own}-H_{\max}+4s\kappa,H_{\own}-H_{\min}-4 s\kappa \}\right\}-\frac{\kappa}{2}.
\end{equation*}

We distinguish three cases.

* $\Delta<0$. Then <Ref> sets

\begin{equation*}
\Cor_{v,\ell}\le \min\left\{H_{\own}-H_{\min}-\frac{\kappa}{2}+2\kappa,0\right\}\le 0.
\end{equation*}

As $\Lambda\ge d$ by <Ref>, the claim of the lemma holds in this case.

* $0\le \Delta\le \vartheta \kappa$. Then, using the notation of <Ref>,

\begin{align*}
\Cor_{v,\ell}=\Delta &<\min_{s\in \N}\left\{\max\{H_{\own}-H_{\max}+4s\kappa,H_{\own}-H_{\min}-4 s\kappa \}\right\}-\frac{\kappa}{2}\\
&\le \min_{s\in \N}\left\{\max\{t_{v,\ell-1}-t_{\max}+4s\kappa,t_{v,\ell-1}-t_{\min}-4 s\kappa \}\right\}\\
&\le \min_{s\in \N}\left\{\max\{\localskew_{\ell-1}+4s\kappa,\localskew_{\ell-1} -4s\kappa \}\right\}\\
\end{align*}

which is smaller than $\Lambda-d$ by <Ref>.

* $\Delta>\vartheta \kappa$. Note that then

\begin{equation*}
\vartheta\kappa<\Delta \le \max\{H_{\own}-H_{\max},H_{\own}-H_{\min}\}-\frac{\kappa}{2}\\
\end{equation*}

as $H_{\max}\ge H_{\min}$. Therefore, applying <Ref>,

\begin{align*}
\Cor_{v,\ell}&=\max\left\{H_{\own}-H_{\max}-\frac{\kappa}{2}-\kappa,\vartheta\kappa\right\}\\
&\le H_{\own}-H_{\max}-\frac{\kappa}{2}\\
&\le t_{v,\ell-1}-t_{\max}\\
&\le \localskew_{\ell-1}\\
\end{align*}

The third lemma bounds the time difference between the pulses of $(v,\ell-1)$ and $(v,\ell)$.

For all $v\in V$ and $\ell\in \N_{>0}$ it holds that

\begin{align*}
d-u+\frac{\Lambda-d-\Cor_{v,\ell}}{\vartheta} \le t_{v,\ell}-t_{v,\ell-1} \le \Lambda-\Cor_{v,\ell}.
\end{align*}

Let $t'_{v,\ell-1}$ denote the time at which $(v,\ell)$ receives the pulse sent by $(v,\ell-1)$ at time $t_{v,\ell-1}$.
Inspecting the code of <Ref>, we see that

\begin{equation*}
H_{v,\ell}(t_{v,\ell})=H_{\own}+\Lambda -d - \Cor_{v,\ell}=H_{v,\ell}(t'_{v,\ell-1})+\Lambda -d - \Cor_{v,\ell}.
\end{equation*}

Since $\Cor_{v,\ell}\le \Lambda-d$ by <Ref>, it follows that $H_{v,\ell}(t'_{v,\ell-1})\ge H_{v,\ell}(t_{v,\ell})$ and hence $t_{v,\ell}\ge t'_{v,\ell-1}$.
Using the bounds on message delays and hardware clock speeds, we get that

\begin{align*}
&\le H_{v,\ell}(t_{v,\ell})-H_{v,\ell}(t'_{v,\ell-1})+d\\
&=\Lambda - \Cor_{v,\ell}
\end{align*}

\begin{align*}
&\ge \frac{H_{v,\ell}(t_{v,\ell})-H_{v,\ell}(t'_{v,\ell-1})}{\vartheta}+d-u\\
\end{align*}

which can be rearranged into the claimed inequalities.

§.§ The Slow, Fast, and Jump Conditions

The key to bounding the local skew without faults is to find the right balance between two conflicting goals:
choosing $\Cor_{v,\ell}$ large enough to “catch up” to predecessors $w_{\ell-1}\neq v_{\ell-1}$ that generated their pulse earlier than $v_{\ell-1}$, but small enough to “wait” for predecessors $w_{\ell-1}\neq v_{\ell-1}$ that generated their pulse later than $v_{\ell-1}$.
The following condition captures what we need regarding the latter.

For all $s\in \N$, correct layers $\ell-1\in \N$, and $v_{\ell}\in V_{\ell}\setminus F$, we require the slow condition $\operatorname{\SC}(s):=\SCone(s) \lor \SCtwo(s) \lor \SCthree$ to hold, where

\begin{align*}
\SCone(s)\colon & \frac{\Cor_{v,\ell}}{\vartheta}\le t_{v,\ell-1} - \max_{\{v,w\}\in E}\{t_{w,\ell-1}\}+4s\kappa\\
\SCtwo(s)\colon & \frac{\Cor_{v,\ell}}{\vartheta}\le t_{v,\ell-1} - \min_{\{v,w\}\in E}\{t_{w,\ell-1}\}-4s\kappa\\
\SCthree\colon &  \Cor_{v,\ell} \le 0.
\end{align*}

This can be viewed as a variant of the slow condition from <cit.>, adjusted to our setting by quantifying by how much $v_{\ell}$ may safely shift the timing of its pulse.
The main conceptual difference to <cit.> is that we relax the slow condition by adding $\SCthree$.
In what follows, we drop $s$ from the notation when it is clear from context.

For all $s\in \N$ and $(v,\ell)\in V_{\ell}$, $\ell\in \N_{>0}$, $\SC(s)$ holds at $(v,\ell)$.

Using <Ref>, we prove the claim for <Ref>.
Set $t_{\min}:=\min_{\{v,w\}\in E}\{t_{w,\ell-1}\}$ and $t_{\max}:=\min_{\{v,w\}\in E}\{t_{w,\ell-1}\}$.
If $\Cor_{v,\ell}\le 0$, $\SCthree$ is trivially satisfied.
Hence, assume that $\Cor_{v,\ell}> 0$.

\begin{align*}
\Delta=\min_{s\in \N}\left\{\max\{H_{\own}-H_{\max}+4s\kappa,H_{\own}-H_{\min}-4s\kappa \}\right\}-\frac{\kappa}{2}\\
=\max\{H_{\own}-H_{\max}+4s_{\min}\kappa,H_{\own}-H_{\min}-4 s_{\min}\kappa \}-\frac{\kappa}{2},
\end{align*}

where $s_{\min}\in \N$ is an index for which the minimum is attained.

If $\Delta\le \vartheta \kappa$, then $\Cor_{v,\ell}=\Delta$.

\begin{equation*}
\Cor_{v,\ell}= \max\left\{H_{\own}-H_{\max}-\frac{\kappa}{2}-\kappa,\vartheta\kappa\right\}\le \max\{\Delta,\vartheta \kappa\}=\Delta.
\end{equation*}

Either way, we get that $\Cor_{v,\ell}/\vartheta<\Cor_{v,\ell}\le \Delta$.

We distinguish two cases.

* $H_{\own}-H_{\max}+4s_{\min}\kappa\ge H_{\own}-H_{\min}-4 s_{\min}\kappa$. Then for $s\in \N$, $s\ge s_{\min}$, by <Ref> we have that

\begin{equation*}
\Delta\le H_{\own}-H_{\max}+4s_{\min}\kappa-\frac{\kappa}{2}\le t_{v,\ell-1}-t_{\max}+4s \kappa,
\end{equation*}

i.e., $\SCone$ holds. Now consider $s\in \N$, $s<s_{\min}$. Since $H_{\own}-H_{\max}-\vartheta u+4s\kappa <H_{\own}-H_{\max}-\vartheta u+4s_{\min}\kappa\le \Delta$, but the minimum is attained at index $s_{\min}$, we must have that

\begin{equation*}
\Delta\le H_{\own}-H_{\min}-4s\kappa-\frac{\kappa}{2}
\le t_{v,\ell-1}-t_{\min}-4s\kappa,
\end{equation*}

where the second step again applies <Ref>.
Thus, $\SCtwo$ holds.

* $H_{\own}-H_{\max}+4s_{\min}\kappa < H_{\own}-H_{\min}-4 s_{\min}\kappa$. In this case, we analogously infer that $\SCone$ holds for $s>s_{\min}$ and $\SCtwo$ holds for $s\le s_{\min}$.

The fast condition is the counterpart to <Ref> addressing the need to “catch up” to neighbors that are ahead.

For all $s\in \N_{>0}$, correct layers $\ell-1\in \N_{>0}$, and $v_{\ell}\in V_{\ell}\setminus F$, we require the fast condition $\FC(s):=\FCone(s) \lor \FCtwo(s) \lor \FCthree$ to hold, where

\begin{align*}
\FCone(s)\colon & \Cor_{v,\ell}\ge t_{v,\ell-1} - \max_{\{v,w\}\in E}\{t_{w,\ell-1}\}+(4s-2)\kappa+\kappa\\
\FCtwo(s)\colon & \Cor_{v,\ell}\ge t_{v,\ell-1} - \min_{\{v,w\}\in E}\{t_{w,\ell-1}\}-(4s-2)\kappa+\kappa\\
\FCthree\colon &  \Cor_{v,\ell} \ge \kappa.
\end{align*}

This can be viewed as a variant of the fast condition from <cit.>, adjusted to our setting by quantifying by how much $v_{\ell}$ may safely shift the timing of its pulse.
The main conceptual difference to <cit.> is that we relax the fast condition by adding $\FCthree$.

In addition, note that there is an additive term of $\kappa$ that does not change sign.
Its purpose is to account for the fact that our simulation of the GCS algorithm from <cit.> operates in discrete time steps corresponding to the layers.
The continuous versions of the GCS algorithm in <cit.> can choose this term arbitrarily small.
In contrast, we need it to exceed the maximum error in time measurement accumulated in a step.
We remark that, in principle, one could choose this term different from $\kappa$.
However, since both need to meet the same lower bound of $u+(1-1/\vartheta)(\Lambda-d)$, there is no asymptotic gain in introducing a separate parameter.

For all $s\in \N$ and $(v,\ell)\in V_{\ell}$, $\ell\in \N_{>0}$, $\FC(s)$ holds at $(v,\ell)$.

Using <Ref>, we prove the claim for <Ref>.
Set $t_{\min}:=\min_{\{v,w\}\in E}\{t_{w,\ell-1}\}$ and $t_{\max}:=\min_{\{v,w\}\in E}\{t_{w,\ell-1}\}$.
If $\Cor_{v,\ell}\ge \vartheta\kappa$, trivially $\FCthree$ is satisfied.
Hence, assume that $\Cor_{v,\ell}<\vartheta\kappa$.

\begin{align*}
\Delta=\min_{s\in \N}\left\{\max\{H_{\own}-H_{\max}+4s\kappa,H_{\own}-H_{\min}-4s\kappa \}\right\}-\frac{\kappa}{2}\\
=\max\{H_{\own}-H_{\max}+4s_{\min}\kappa,H_{\own}-H_{\min}-4 s_{\min}\kappa \}-\frac{\kappa}{2},
\end{align*}

where $s_{\min}\in \N$ is an index for which the minimum is attained.

If $\Delta\ge 0$, then $\Cor_{v,\ell}=\Delta$.

\begin{equation*}
\Cor_{v,\ell}= \min\left\{H_{\own}-H_{\min}-\frac{\kappa}{2}+2\kappa,0\right\}\ge \Delta.
\end{equation*}

Either way, we get that $\Cor_{v,\ell}\ge \Delta$.

For $s\in \N$, $s\le s_{\min}$, by <Ref> and <Ref> it holds that

\begin{equation*}
\Delta\ge H_{\own}-H_{\max}+4s\kappa -\frac{\kappa}{2}\ge t_{v,\ell-1}-t_{\max}+(4s-2)\kappa+\kappa,
\end{equation*}

proving that $\FCone$ holds.
For $s\in \N$, $s> s_{\min}$, by <Ref> and <Ref> we get that

\begin{equation*}
\Delta\ge H_{\own}-H_{\min}-4(s-1)\kappa -\frac{\kappa}{2}\ge t_{v,\ell-1}-t_{\min}-(4s-2)\kappa+\kappa,
\end{equation*}

showing that $\FCtwo$ holds.

Slow condition (left) and fast condition (right). $\SC(s)$ is tailored to ensuring that $\max_{w\in V}\{\psi_{v,w}^s(\ell)\}$ (the length of the green arrow) cannot grow quickly. Nodes $w$ with $\Cor_{w,\ell}\le 0$ ($\SCthree$ holds) cannot apply a correction pushing them below the red line. If $\Cor_{w,\ell}>0$, then both $\SCone$ and $\SCtwo$ will ensure that there is a neighbor $x$ of $w$ such that the offset of $t_{w,\ell-1}-\Cor_{w,\ell}/\vartheta$ to the black line does not exceed the one of $t_{x,\ell-1}$. In other words, $\SC$ ensures that the blue arrows indicating $\Cor_{w,\ell}/\vartheta$ do not reach below the red line. This means that any increase of $\max_{w\in V}\{\psi_{v,w}^s(\ell)\}$ is caused by delay and clock speed variation, which in turn is bounded by $\kappa/2$ per layer. Similarly, $\FC(s)$ is tailored to ensuring that $\max_{v\in V}\{\xi_{v,w}^s(\ell)\}$ (the length of the green arrow), if positive, decreases by at least $\kappa/2$. To ensure this, $\Cor_{w,\ell}$ (indicated by blue arrows) must be large enough to reach below the red line. This is achieved by $\FC(s)$ having an additional “slack” term of $\kappa$, which overcomes the “loss” of $\kappa/2$ due to uncertainty.
[Illustrating the Slow and Fast Conditions]Slow condition (left) and fast condition (right). $\SC(s)$ is tailored to ensuring that $\max_{w\in V}\{\psi_{v,w}^s(\ell)\}$ (the length of the green arrow) cannot grow quickly. Nodes $w$ with $\Cor_{w,\ell}\le 0$ ($\SCthree$ holds) cannot apply a correction pushing them below the red line. If $\Cor_{w,\ell}>0$, then both $\SCone$ and $\SCtwo$ will ensure that there is a neighbor $x$ of $w$ such that the offset of $t_{w,\ell-1}-\Cor_{w,\ell}/\vartheta$ to the black line does not exceed the one of $t_{x,\ell-1}$. In other words, $\SC$ ensures that the blue arrows indicating $\Cor_{w,\ell}/\vartheta$ do not reach below the red line. This means that any increase of $\max_{w\in V}\{\psi_{v,w}^s(\ell)\}$ is caused by delay and clock speed variation, which in turn is bounded by $\kappa/2$ per layer. Similarly, $\FC(s)$ is tailored to ensuring that $\max_{v\in V}\{\xi_{v,w}^s(\ell)\}$ (the length of the green arrow), if positive, decreases by at least $\kappa/2$. To ensure this, $\Cor_{w,\ell}$ (indicated by blue arrows) must be large enough to reach below the red line. This is achieved by $\FC(s)$ having an additional “slack” term of $\kappa$, which overcomes the “loss” of $\kappa/2$ due to uncertainty.
[Illustrating the Slow and Fast Conditions]

On the left, it is shown how skews increase without $\JC$. While $\SC(0)$ disallows that $(v,\ell)$ speeds up its pulse by more than the equivalent of $(v,\ell-1)$ matching the earliest pulse of any $(w,\ell-1)$, $\{v,w\}\in E$, $\FC$ permits that a node $(v,\ell)$ with slow $(v,\ell-1)$ to “overshoot,” i.e., $\Cor_{v,\ell}$ (shown as blue arrow) gets large. This results in an amplifying oscillatory behavior. On the right, the same scenario is shown with $\JC$ in effect. $\JC$ forces the corrections to stop $\kappa$ before the earliest or latest neighbor, respectively, resulting in a dampened oscillation.
[Illustrating the need for a Jump Condition]On the left, it is shown how skews increase without $\JC$. While $\SC(0)$ disallows that $(v,\ell)$ speeds up its pulse by more than the equivalent of $(v,\ell-1)$ matching the earliest pulse of any $(w,\ell-1)$, $\{v,w\}\in E$, $\FC$ permits that a node $(v,\ell)$ with slow $(v,\ell-1)$ to “overshoot,” i.e., $\Cor_{v,\ell}$ (shown as blue arrow) gets large. This results in an amplifying oscillatory behavior. On the right, the same scenario is shown with $\JC$ in effect. $\JC$ forces the corrections to stop $\kappa$ before the earliest or latest neighbor, respectively, resulting in a dampened oscillation.

Our relaxation of the slow and fast conditions adds a substantial complication.
From the perspective of the time-continuous variant of the algorithm in <cit.>, we now allow for arbitrarily large clock “jumps,” rather than bounded clock rates.
In our discrete version, the rate bound from <cit.> corresponds to $\Cor_{v,\ell}\in [0,\vartheta \kappa]$.
Without this additional constraint, the slow and fast conditions are insufficient to bound skews.

This is illustrated in <Ref>, showing an execution that satisfies $\SC$ and $\FC$, but suffers from skews that grow without bound.
The key issue is that adjacent nodes could “jump” in opposite directions, resulting in an oscillatory behavior in which measurement errors accumulate indefinitely.
To avoid this kind of behavior, we add an additional condition that “dampens” such oscillations, yet limits by how much a faulty predecessor can cause an increase in skew.

For all correct layers $\ell-1\in \N_{>0}$ and $v_{\ell}\in V_{\ell}\setminus F$, we require the jump condition $\JC:=\JCone \lor \JCtwo\lor \JCthree$ to hold, where

\begin{align*}
\JCone\colon & \kappa<\frac{\Cor_{v,\ell}}{\vartheta}\le t_{v,\ell-1} - \max_{\{v,w\}\in E}\{t_{w,\ell-1}\}-\kappa\\
\JCtwo\colon & 0>\Cor_{v,\ell}\ge t_{v,\ell-1} - \min_{\{v,w\}\in E}\{t_{w,\ell-1}\}+\kappa\\
\JCthree\colon & 0\le \frac{\Cor_{v,\ell}}{\vartheta}\le \kappa.
\end{align*}

Suppose that layer $\ell-1\in \N$ and $v_{\ell}\in V_{\ell}$ are correct.
Then $\JC$ holds at $v_{\ell}$.

Using <Ref>, we prove the claim for <Ref>.
Set $t_{\min}:=\min_{\{v,w\}\in E}\{t_{w,\ell-1}\}$ and $t_{\max}:=\min_{\{v,w\}\in E}\{t_{w,\ell-1}\}$.
We distinguish three cases.

* $0\le \Cor_{v,\ell}\le \vartheta\kappa$. Then $\JCthree$ is satisfied trivially.

* $\Cor_{v,\ell}<0$. By <Ref> and <Ref>, then

\begin{equation*}
\Cor_{v,\ell}=H_{\own}-H_{\min} -\frac{\kappa}{2}+2\kappa
\ge t_{v,\ell-1}-t_{\min}+\kappa,
\end{equation*}

i.e., $\JCtwo$ holds.

* $\Cor_{v,\ell}>\vartheta \kappa$. By <Ref>, then

\begin{equation*}
\Cor_{v,\ell}=H_{\own}-H_{\max} -\frac{\kappa}{2}-\kappa
\le t_{v,\ell-1}-t_{\max}-\kappa,
\end{equation*}

i.e., $\JCthree$ holds.

§.§ Bounding Psi in the Absence of Faults

With the conditions established, we are ready to study how $\Psi^s(\ell)$ evolves in the fault-free setting.
The main technical challenge in bounding $\Psi^s$ lies in performing the induction step from $s-1\in \N$ to $s$.
We will argue that for $\Psi^s(\bar{\ell}\,)$ to be large for some $\bar{\ell}$, $\Xi^s(\underline{\ell}\,)$ must have been large for some $\underline{\ell} < \bar{\ell}$, with an additive term growing with $\bar{\ell}-\underline{\ell}$.

For $s\in \N_{>0}$ and layers $\underline{\ell}\le \bar{\ell}$, it holds that

\begin{equation*}
\Psi^s(\bar{\ell}\,)\le \max\set{0,\Xi^s(\underline{\ell}\,)-(\bar{\ell}-\underline{\ell}+1)\kappa}+(\bar{\ell}-\underline{\ell}\,)\cdot\frac{\kappa}{2}.
\end{equation*}

Intuitively, we intend to argue that if $\Psi^s(\bar{\ell}\,)$ is large, so must be $\Xi^s(\underline{\ell}\,)$.
Tracing back the cause for this, we show that in every step, we have that $\Xi^s(\ell-1)$ is larger than $\Xi^s(\ell)$ by at least $\kappa/2$.
Since $\Xi^s(\bar{\ell}\,)\ge \Psi^s(\bar{\ell}\,)$, as $\psi^s_{v,w}(\ell)\ge \xi^s_{v,w}(\ell)$ for all $v$, $w$, $s$, and $\ell$, this yields the claim.
To formalize that $\Xi^s(\ell)$ must have been decreasing steadily, we seek to show that the minimal layer $\ell$ for which there are nodes $v^{\ell},w^{\ell}\in V$ satisfying that $\xi^s_{v^{\ell},w^{\ell}}(\ell)$ is large enough is $\underline{\ell}$.
To this end, we identify nodes $w$ and $v$ – either $w^{\ell}$ and $v^{\ell}$ themselves or neighbors of them – which cause the large skew on layer $\ell$ by a having a large skew on layer $\ell-1$.
This is done based on $\SC(s)$ and $\FC(s)$, with $\JC$ kicking in for the special case that $w=v^{\ell}$ and $v=w^{\ell}$.

A key obstacle is that if $w$ is a neighbor of $w^{\ell}$, this results in a larger difference in skew than if $v$ is a neighbor of $v^{\ell}$, namely $4s\kappa$ versus $(4s-2)\kappa$.
Thus, when $w$ is closer to $v^{\ell}$ than $w^{\ell}$, we “lose” $2\kappa$ relative to the skew bound on layer $\ell$.
For $d(v^{\bar{\ell}},w^{\bar{\ell}})$ many steps, we can compensate for this based on the initial skew between $v^{\bar{\ell}}$ and $w^{\bar{\ell}}$, but not more.
To address this, essentially we need to show that for any additional steps “towards” $v^{\ell}$ there will be a corresponding step “away” from $v^{\ell}$, on which we “gain” additional $2\kappa$ relative to the skew bound on the layer $\ell$.

If corrections were always positive, this would be straightforward:
Steps towards $v^{\ell}$ would also be steps towards $v^{\bar{\ell}}$, and upon $w^{\ell}=v^{\bar{\ell}}$ we would reach a contradiction to the skew bounds shown.
Unfortunately, negative corrections foreclose this simple argument.
To address this, we introduce a third “prover” node $p^{\ell}$, where $p^{\bar{\ell}}=v^{\bar{\ell}}$, which never increases its distance to $w^{\ell}$;
if $p^{\ell}$ performs a negative correction, then $p$ is a neighbor of $p^{\ell}$ that is closer to $w^{\ell}$.
We then can infer that $p\neq w$ from the skew bounds.

A major complication this approach faces is the special case $p=w^{\ell}$ and $w=p^{\ell}$.
Again, $\JC$ kicks in to show that we have sufficiently large skew between $p$ and $w$.
However, now $p$ lies “behind” $w$ from the perspective of $v$.
A later reversal of this situation by repeating the case that $p=w^{\ell}$ and $w=p^{\ell}$ results in $w$ being farther away from $v^{\ell}$, yet $d(p,w)=d(p^{\ell},w^{\ell})$.
The proof covers this case by adding an additional $(4s-2)\kappa$ to the skew bound if the above situation occured an odd number of times.

Finally, we seek to avoid the case that $v=p^{\ell}$ and $p=v^{\ell}$ for analogous reasons.
Fortunately, here we can exploit that the skew bound between $v^{\ell}$ and $w^{\ell}$ is stronger than the one between $p^{\ell}$ and $w^{\ell}$, meaning that we can simply choose $p=v$ instead in this situation.
In the proof, we do so whenever $v$ lies on the path connecting $p^{\ell}$ and $w^{\ell}$ that we maintain to keep track of hop counts in the construction.

Assume towards a contradiction that the statement of <Ref> is false for minimal $\bar{\ell}$, i.e., there are $v^{\bar{\ell}}$ and $w^{\bar{\ell}}$ such that

\begin{align}
\psi^s_{v^{\bar{\ell}},w^{\bar{\ell}}} &> (\bar{\ell}-\underline{\ell}\ )\cdot\frac{\kappa}{2}\label{eq:contra1}\\
\mbox{and}\quad \psi^s_{v^{\bar{\ell}},w^{\bar{\ell}}}&>\Xi^s(\underline{\ell}\,)-(\bar{\ell}-\underline{\ell}\,)\cdot\frac{\kappa}{2}-\kappa\label{eq:contra2}
\end{align}

and there is no smaller $\bar{\ell}'$ for which this applies for some pair of nodes.

Let $\ell \in [\underline{\ell},\bar{\ell}]$ be minimal such that are $v^{\ell},p^{\ell},w^{\ell}\in V$, a path $Q^{\ell}$ in $H$ from $p^{\ell}$ to $v^{\ell}$, and a path $P^{\ell}$ in $H$ from $p^{\ell}$ to $w^{\ell}$ with the following properties:

$w^{\ell}\neq p^{\ell}$.

$w^{\ell}\neq v^{\ell}$.

\begin{align*}
t_{p^{\ell},\ell}-t_{w^{\ell},\ell}-4s\kappa |P^{\ell}|\ge \psi_{v^{\bar{\ell}},w^{\bar{\ell}}}^s(\bar{\ell}\,)-(\bar{\ell}-\ell)\cdot\frac{\kappa}{2}>0.
\end{align*}

Denote by $|P^{\ell}|$ and $|Q^{\ell}|$ the length of $P^{\ell}$ and $Q^{\ell}$, respectively.
With the shorthand

\begin{align*}
\Delta^{\ell}:=\begin{cases}
|P^{\ell}|+|Q^{\ell}| - 1 & \mbox{if } P^{\ell} \mbox{ and } Q^{\ell} \mbox{ have the same first edge}\\
|P^{\ell}|+|Q^{\ell}| & \mbox{else,}
\end{cases}
\end{align*}

it holds that

\begin{align*}
t_{v^{\ell},\ell}-t_{w^{\ell},\ell}-(4s-2)\kappa \Delta^{\ell}\ge \psi_{v^{\bar{\ell}},w^{\bar{\ell}}}^s(\bar{\ell}\,)+(\bar{\ell}-\ell)\cdot\frac{\kappa}{2}+2\kappa |P^{\ell}|.
\end{align*}

If $v^{\ell}\in P^{\ell}$, then $p^{\ell}=v^{\ell}$.

To see that such an index must indeed exist, let

* $p^{\bar{\ell}}:=v^{\bar{\ell}}$,

* $P^{\bar{\ell}}$ be a shortest path in $H$ from $p^{\bar{\ell}}$ to $w^{\bar{\ell}}$, and

* $Q^{\bar{\ell}}:=(p^{\bar{\ell}})=(v^{\bar{\ell}})$, i.e., the $0$-length path from $p^{\bar{\ell}}$ to $v^{\bar{\ell}}$.

This choice satisfies

* and , because $\Psi^s_{v^{\bar{\ell}},w^{\bar{\ell}}}(\bar{\ell}\,)\neq 0$ implies that $v^{\bar{\ell}}\neq w^{\bar{\ell}}$;

* , because

\begin{equation*}
t_{v^{\bar{\ell}},\bar{\ell}}-t_{w^{\bar{\ell}},\bar{\ell}}-(4s-2)\kappa \Delta^{\ell}=t_{v^{\bar{\ell}},\bar{\ell}}-t_{w^{\bar{\ell}},\bar{\ell}}-(4s-2)\kappa |P^{\bar{\ell}}|
= \psi_{v^{\bar{\ell}},w^{\bar{\ell}}}+2\kappa |P^{\bar{\ell}}|;~\mbox{and}
\end{equation*}

* and , because $p^{\bar{\ell}}=v^{\bar{\ell}}$ (i.e., $t_{p^{\bar{\ell}},\bar{\ell}}=t_{v^{\bar{\ell}},\bar{\ell}}$ and $\Delta^{\bar{\ell}}=|P^{\bar{\ell}}|$) and holds.

<Ref> proves that in fact $\ell=\underline{\ell}$.
Note that

\begin{align*}
d(v^{\underline{\ell}},w^{\underline{\ell}})&\le \begin{cases}
|P^{\underline{\ell}}|+|Q^{\underline{\ell}}|-2 & \mbox{if $P^{\underline{\ell}}$ and $Q^{\underline{\ell}}$ share the first edge}\\
|P^{\underline{\ell}}|+|Q^{\underline{\ell}}| & \mbox{else}
\end{cases}\\
&\le \Delta^{\underline{\ell}}
\end{align*}

and that $|P^{\underline{\ell}}|\ge 1$ due to .
Therefore, yields that

\begin{align*}
\Xi^s(\underline{\ell}\,)
&\ge t_{v^{\underline{\ell}},\underline{\ell}}-t_{w^{\underline{\ell}},\underline{\ell}}-(4s-2)\kappa d(v^{\underline{\ell}},w^{\underline{\ell}})\\
&\ge t_{v^{\underline{\ell}},\underline{\ell}}-t_{w^{\underline{\ell}},\underline{\ell}}-(4s-2)\kappa\Delta^{\underline{\ell}}\\
&\ge \psi_{v^{\bar{\ell}},w^{\bar{\ell}}}^s(\bar{\ell}\,)+(\bar{\ell}-\underline{\ell})\cdot\frac{\kappa}{2}+2\kappa |P^{\underline{\ell}}|\\
&\ge \psi_{v^{\bar{\ell}},w^{\bar{\ell}}}^s(\bar{\ell}\,)+(\bar{\ell}-\underline{\ell})\cdot\frac{\kappa}{2}+2\kappa,
\end{align*}

contradicting <Ref> and completing the proof.

The remainder of <Ref> is dedicated to proving <Ref>, which is the missing step in the proof of <Ref>.
To this end, until the end of <Ref> we consider the setting of the proof of <Ref> and assume for contradiction that $\ell>\underline{\ell}$.
We take note of some straightforward implications.

For any fixed index $\ell$, we have the following implications:

* $\Rightarrow$
* $\Rightarrow$
* ($v^{\ell}=p^{\ell} \land$ ) $\Rightarrow$ .

\begin{equation*}
\psi^s_{v^\ell,w^{\ell}}(\ell)-(\bar{\ell}-\ell)\cdot\frac{\kappa}{2}>0.
\end{equation*}

We prove each implication separately.

* From , $t_{p^\ell,\ell}- t_{w^{\ell},\ell} > 4s\kappa |P^\ell| \geq 0$. This implies $t_{p^\ell,\ell}> t_{w^{\ell},\ell}$ and hence $w^\ell \neq p^\ell$, i.e., .

* Note that $\Delta^{\ell}\ge 0$, $|P^{\ell}|\ge 0$, and $4s-2>0$. Hence, (P4) and <Ref> imply that

\begin{equation*}
t_{v^\ell,\ell}-t_{w^{\ell},\ell}\geq \psi^s_{v^{\ell},w^{\ell}}(\bar{\ell}\,) >0.
\end{equation*}

It follows that $w^{\ell}\neq v^{\ell}$, i.e., (P2).

* If $v^\ell = p^\ell$, then $t_{v^{\ell},\ell}=t_{p^{\ell},\ell}$, $|Q^\ell| = 0$, and $\Delta^{\ell}=|P^{\ell}|$. Thus, implies that

\begin{align*}
t_{p^{\ell},\ell}-t_{w^{\ell},\ell} -(4s-2)\kappa|P^{\ell}| &\geq \psi^s_{v^{\ell},w^{\ell}}(\bar{l}) + (\bar{\ell} - \ell)\cdot\frac{\kappa}{2} + 2\kappa|P^{\ell}|\ge \psi^s_{v^{\ell},w^{\ell}}(\bar{l}) - (\bar{\ell} - \ell)\cdot\frac{\kappa}{2} + 2\kappa|P^{\ell}|,
\end{align*}

which can be rearranged to yield .

§.§.§ A Step in the Construction

We now identify nodes that are suitable for taking the role of $v^{\ell}$, $p^{\ell}$, and $w^{\ell}$ on layer $\ell-1$.
These are either the nodes themselves or neighbors of them in $H$, where $\FC(s)$, $\SC(s)$, and $\JC$ serve to relate respective pulse times.

There is a node $v\in V$ such that

\begin{equation*}
t_{v^{\ell},\ell-1}-\Cor_{v^{\ell},\ell}\le t_{v,\ell-1}-(4s-2)\kappa\Delta_v-\kappa,
\end{equation*}

\begin{equation*}
\Delta_v = \begin{cases}
0 & \mbox{and }v=v^{\ell},\\
-1 & \mbox{and $\{v,v^{\ell}\}$ is the last edge of $Q^{\ell}$ or the first edge of $P^{\ell}$, or}\\
1 & \mbox{and $\{v^{\ell},v\}\in E$.}
\end{cases}
\end{equation*}

By <Ref>, $v^\ell$ obeys the fast condition. Thus one of three things is true for $v^\ell$.

* $\FCone(s)$ holds. In this case, let $v=\arg\max_{\set{x,v^\ell}\in E}\{t_{x,\ell-1}\}$ and bound

\begin{equation*}
t_{v^{\ell},\ell-1} - \Cor_{v^{\ell},\ell} \leq  \max_{\{x,v^\ell\}\in E}\set{t_{x,\ell-1}} - (4s-2)\kappa - \kappa= t_{v,\ell-1} - (4s-2)\kappa - \kappa,
\end{equation*}

i.e., the claim of the lemma holds with $\Delta_v=1$.

* $\FCtwo(s)$ holds. In this case, let $\{v,v^{\ell}\}$ be the last edge of $Q^{\ell}$ if $|Q^{\ell}|\neq 0$ or the first edge of $P^{\ell}$ otherwise; the latter is feasible, because then $v^{\ell}=p^{\ell}$, and $|P^{\ell}|\neq 0$ due to (P1). We get that

\begin{equation*}
t_{v^{\ell},\ell-1} -  \Cor_{v^{\ell},\ell} \leq \min_{\{x,v^\ell\}\in E}\set{t_{x,\ell-1}} + (4s-2)\kappa - \kappa \leq t_{v,\ell-1} + (4s-2)\kappa - \kappa.
\end{equation*}

Thus, the claim of the lemma holds with $\Delta_v = -1$.

* $\FCthree$ holds. In this case,

\begin{equation*}
t_{v^{\ell},\ell-1} - \Cor_{v^{\ell},\ell} \leq t_{v^{\ell},\ell-1} - \kappa,
\end{equation*}

i.e., the claim of the lemma holds with $\Delta_v = 0$.

There is a node $w\in V$ such that

\begin{equation*}
t_{w^{\ell},\ell-1}-\frac{\Cor_{w^{\ell},\ell}}{\vartheta}\ge t_{w,\ell-1}+4s\kappa\Delta_w,
\end{equation*}

\begin{equation*}
\Delta_w= \begin{cases}
0 & \mbox{and }w=w^{\ell},\\
-1 & \mbox{and $\{w,w^{\ell}\}$ is the last edge of $P^{\ell}$, or}\\
1 & \mbox{and $\{w^{\ell},w\}\in E$.}
\end{cases}
\end{equation*}

By <Ref>, $w^{\ell}$ satisfies $\SC$.
We make a case distinction based on which one of $\SCone$, $\SCtwo$, and $\SCthree$ applies.

* $\SCone(s)$ holds. Let $\{w,w^{\ell}\}$ be the last edge of $P^\ell$; by (P1), $|P^{\ell}|\neq 0$, i.e., this edge exists. Then

\begin{equation*}
t_{w^\ell,\ell-1} - \frac{\Cor_{w^{\ell},l}}{\vartheta}\geq  \max_{\{x,w^{\ell}\}\in E}\{t_{x,\ell-1}\} - 4s\kappa
\geq t_{w,\ell-1} - 4s\kappa,
\end{equation*}

i.e., the claim of the lemma holds with $\Delta_w=-1$.

* $\SCtwo(s)$ holds. In this case, let $w=\arg\min_{{\set{x,v^\ell}\in E}}\{t_{x,\ell-1}\}$ and bound

\begin{align*}
t_{w^\ell,\ell-1} - \frac{\Cor{w^{\ell},\ell}}{\vartheta}\geq  \min_{\set{x,w^{\ell}}\in E}\{t_{x,\ell-1}\} + 4s\kappa = t_{w,\ell-1} + 4s\kappa.
\end{align*}

Thus, the lemma holds with $\Delta_w = 1$.

* $\SCthree$ holds. Then

\begin{equation*}
t_{w^\ell,\ell-1} - \Cor_{w,\ell} \geq t_{w^\ell,\ell-1},
\end{equation*}

i.e., the claim of the lemma holds with $\Delta_w=0$.

There is a node $p\in V$ such that

\begin{align*}
t_{p^{\ell},\ell-1}-\Cor_{p^{\ell},\ell}\le \begin{cases}
t_{p,\ell-1}& \mbox{and $p=p^{\ell}$, or}\\
t_{p,\ell-1}-\kappa & \mbox{and $\{p^{\ell},p\}$ is the first edge of $P^{\ell}$.}
\end{cases}
\end{align*}

If $\Cor_{p^{\ell},\ell}\ge 0$, the claim holds with $p=p^{\ell}$.
Hence, suppose that $\Cor_{p^{\ell},\ell}< 0$.
Let $\{p^{\ell},p\}$ be the first edge of $P^\ell$; such an edge exists, as by (P1) we have that $p^{\ell}\neq w^{\ell}$ and hence $|P^{\ell}|\neq 0$.
By <Ref>, $p^\ell$ satisfies $\JC$.
As $\Cor_{p^{\ell},\ell}< 0$, $\JCtwo$ must apply.
We conclude that

\begin{equation*}
\Cor_{p^\ell,\ell} \geq t_{p^\ell,\ell-1} - \min_{\set{x,p^\ell}\in E}\set{t_{x,\ell-1}} + \kappa
\ge t_{p^\ell,\ell-1} - t_{p,\ell-1} + \kappa.
\end{equation*}

Rearranging terms, the desired inequality follows.

In the following, let $(v,p,w)$ be the triple of nodes guaranteed by <Ref>.
Denote by $\circ$ concatenation of paths, by $\prefix(R,x)$ the prefix of path $R$ ending at node $x\in R$, and by $\suffix(R,x)$ the suffix of path $R$ starting at node $x\in R$.

\begin{align*}
v & \mbox{if $v$ lies on $\suffix(P^{\ell},p)$},\\
p & \mbox{else,}
\end{cases}\\
\prefix(P^{\ell},w) & \mbox{if $w$ lies on $P^{\ell}$},\\
P^{\ell}\circ (w^{\ell},w) & \mbox{else,}
\end{cases}\\
\suffix(P,p') &\mbox{if $p'$ lies on $P$},\\
(p',w) & \mbox{else,}
\end{cases}\\
\prefix(Q^{\ell},v) & \mbox{if $v$ lies on $Q^{\ell}$},\\
Q^{\ell}\circ \{v^{\ell},v\} & \mbox{else,}
\end{cases}\\
\suffix(Q,p') & \mbox{if $p'$ lies on $Q$},\\
(p',p^{\ell})\circ Q & \mbox{else.}
\end{cases}
\end{align*}

For notational convenience, in analogy to $\Delta^{\ell}$ we also define

\begin{equation*}
\Delta:=\begin{cases}
|P'|+|Q'| - 1 & \mbox{if } P' \mbox{ and } Q' \mbox{ have the same first edge}\\
|P'|+|Q'| & \mbox{else.}
\end{cases}
\end{equation*}

We will show that this construction satisfies properties (P1) to (P5) for layer $\ell-1$ with $v^{\ell-1}=v$, $p^{\ell-1}=p'$, $w^{\ell-1}=w$, $P^{\ell-1}=P'$, and $Q^{\ell-1}=Q'$;
this will constitute the desired contradiction.

However, we first point out that indeed $P'$ and $Q'$ are paths in $H$ from $p'$ to $w$ and $v$, respectively.
To this end, we first cover the special case that $p'$ does not lie on $P$.

If $p'$ does not lie on $P$, then $p'=w^{\ell}$ and either $w=p^{\ell}$ or $p'=v$.

By <Ref>, $p$ lies on the first edge of $P^{\ell}$.
Hence, if $p'=p$, $p'$ lies on $P$ unless $\prefix(P^{\ell},w)$ does not contain this edge.
By <Ref>, this can only happen if the first edge of $P^{\ell}$ is also the last edge, i.e., $P^{\ell}=(p^{\ell},w^{\ell})=(w,p')$.

It remains to consider the case that $p'\neq p$, i.e., $p'=v$.
Again, we use that all edges but the last of $P^{\ell}$ are also contained in $P$ by <Ref>.
Thus, $p'=v=w^{\ell}$.

$P'$ is a path in $H$ from $p'$ to $w$ and $Q'$ is a path in $H$ from $p'$ to $v$.

To show that $P'$ is a path from $p'$ to $w$, note that by <Ref>, $P$ is a path in $H$, which by definition ends at $w$.
Thus, if $P'=\suffix(P,p')$, $P'$ is a path from $p'$ to $w$ in $H$.
Otherwise, by <Ref>, $p'=w^{\ell}$, and $\{p',w\}=\{w^{\ell},w\}\in E$ by <Ref>.

To show that $Q'$ is a path from $p'$ to $v$, note that by <Ref>, $Q$ is a path in $H$, which by definition ends at $v$.
If $p'=p$, by <Ref> $Q'$ is also a path in $H$, which by definition begins at $p'$ and has the same endpoint as $Q$, which is $v$.
On the other hand, if $p'=v$, $\suffix(Q,p')=\suffix(Q,v)=(v)$, which is the $0$-length path from $p'=v$ to itself.

§.§.§ Proving the Properties

To prove <Ref>, we establish that the tuple $(v,p',w,P',Q')$ satisfies properties to for layer $\ell-1$, contradicting the minimality of $\ell$.
By <Ref>, indeed $P'$ and $Q'$ are paths from $v$ to $w$ and $p'$, respectively.
In the following, we will repeatedly use this fact and the property that $\{x^{\ell},x\}\in E$ for $x\in \{v,w,p\}$ whenever $x\neq x^{\ell}$, without explicitly invoking <Ref> and <Ref>.

We first rule out the special case that $v=w^{\ell}$ and $w=v^{\ell}$.

The case that $v=w^{\ell}$ and $w=v^{\ell}$ is not possible.

Assume towards a contradiction that $v=w^{\ell}$ and $w=v^{\ell}$.
We use , <Ref>, and <Ref> to bound

\begin{align*}
-\Cor_{w,\ell} &\ge t_{w,\ell}-t_{w,\ell-1}-\Lambda\\
&= t_{v^{\ell},\ell}-(t_{w,\ell-1}-4s\kappa)-\Lambda-4s\kappa\\
& \ge t_{v^{\ell},\ell}-\left(t_{w^{\ell},\ell-1}-\frac{\Cor_{w^{\ell},\ell}}{\vartheta}\right)-\Lambda-4s\kappa\\
& = t_{v^{\ell},\ell}-\left(t_{w^{\ell},\ell-1}+d-u+\frac{\Lambda-d-\Cor_{w^{\ell},\ell}}{\vartheta}\right)-\frac{\kappa}{2}-4s\kappa\\
& \ge t_{v^{\ell},\ell}-t_{w^{\ell},\ell}-4s\kappa-\frac{\kappa}{2}\\
& \ge \psi_{v^{\bar{\ell}},w^{\bar{\ell}}}(\bar{\ell}\,)-(\bar{\ell}-\ell+1)\frac{\kappa}{2}\\
& > 0.
\end{align*}

Thus, by $\JC$, it holds that

\begin{equation*}
t_{w,\ell-1} \le t_{w^{\ell},\ell-1}+\Cor_{w,\ell}-\kappa.
\end{equation*}

Note that by , $|P^{\ell}|\neq 0$ and hence $|P^{\ell}|,\Delta^{\ell}\ge 1$.
Thus, by and <Ref>

\begin{equation*}
t_{v^{\ell},\ell}-t_{w^{\ell},\ell}-4s\kappa\ge \psi_{v^{\bar{\ell}},w^{\bar{\ell}}}^s(\bar{\ell}\,)+(\bar{\ell}-\ell)\frac{\kappa}{2}\\
\ge \psi_{v^{\bar{\ell}},w^{\bar{\ell}}}^s(\bar{\ell}\,)>0.
\end{equation*}

We distinguish two cases.

* $\Cor_{w^{\ell},\ell}\le \vartheta\kappa$. Then by <Ref>

\begin{align*}
&= t_{w,\ell}-t_{w^{\ell},\ell}\\
&\le t_{w,\ell-1}-\Cor_{w,\ell}-\left(t_{w^{\ell},\ell-1}-\frac{\Cor_{w^{\ell},\ell}}{\vartheta}\right)+u+\left(1-\frac{1}{\vartheta}\right)(\Lambda-d)\\
&\le u+\left(1-\frac{1}{\vartheta}\right)(\Lambda-d)\\
\end{align*}

which is a contradiction, because $s\ge 1$.

* $\Cor_{w^{\ell},\ell}>\vartheta \kappa$. By $\JC$, it follows that

\begin{align*}
t_{w^{\ell},\ell-1} \ge t_{w,\ell-1}+\frac{\Cor_{w^{\ell},\ell}}{\vartheta}+\kappa,
\end{align*}

yielding by <Ref> that

\begin{align*}
t_{v,\ell-1}-t_{w,\ell-1}&= t_{w^{\ell},\ell-1}-t_{w,\ell-1}\\
&\ge t_{w,\ell-1} + \frac{\Cor_{w^{\ell},\ell}}{\vartheta}+\kappa - (t_{w^{\ell},\ell-1}+\Cor_{w,\ell}-\kappa)\\
&= t_{v^{\ell},\ell-1} - \Cor_{v^{\ell},\ell} - \left(t_{w^{\ell},\ell-1}-\frac{\Cor_{w^{\ell},\ell}}{\vartheta}\right)+2\kappa\\
&\ge t_{v^{\ell},\ell}-t_{w^{\ell},\ell}+2\kappa-\frac{\kappa}{2}\\
\end{align*}

Recall that by , $|P^{\ell}|\neq 0$ and hence $|P^{\ell}|,\Delta^{\ell}\ge 1$.
Moreover, $d(v,w)=d(w^{\ell},w)\le 1$, since by <Ref> $w$ is either $w^{\ell}$ or a neighbor of $w^{\ell}$.
Therefore, implies that

\begin{align*}
\psi_{v,w}^s(\ell-1)
&= t_{v,\ell-1}-t_{w,\ell-1}- 4s\kappa d(v,w)\\
&> t_{v^{\ell},\ell}-t_{w^{\ell},\ell} -4s\kappa|P^{\ell}|+\frac{\kappa}{2}\\
&\ge \psi_{v^{\bar{\ell}},w^{\bar{\ell}}}^s(\bar{\ell}\,)+(\bar{\ell}-(\ell-1))\frac{\kappa}{2}.
\end{align*}

Thus, $v$ and $w$ satisfy <Ref> and <Ref> with index $\bar{\ell}$ replaced by index $\ell-1<\bar{\ell}$, contradicting the minimality of $\bar{\ell}$.

Next, we prove a helper lemma relating $t_{w^{\ell},\ell}$ and $t_{w,\ell-1}$ by a stronger bound than <Ref> for the special case that $p'=w^{\ell}$ and $w=p^{\ell}$.
This follows similar reasoning as the previous lemma.
However, it does not yield an immediate contradiction, as we need to rely on the weaker bound provided by .

If $p'=w^{\ell}$ and $w=p^{\ell}$, then

\begin{equation*}
t_{w^{\ell},\ell}-t_{w,\ell-1}> d-u+\frac{\Lambda-d}{\vartheta}.
\end{equation*}

We use and <Ref> to bound

\begin{align*}
-\Cor_{w,\ell} &\ge t_{w,\ell}-t_{w,\ell-1}-\Lambda\\
&= t_{p^{\ell},\ell}-(t_{w,\ell-1}-4s\kappa)-\Lambda-4s\kappa\\
& \ge t_{p^{\ell},\ell}-\left(t_{w^{\ell},\ell-1}-\frac{\Cor_{w^{\ell},\ell}}{\vartheta}\right)-\Lambda-4s\kappa\\
& = t_{p^{\ell},\ell}-\left(t_{w^{\ell},\ell-1}+d-u+\frac{\Lambda-d-\Cor_{w^{\ell},\ell}}{\vartheta}\right)-\frac{\kappa}{2}-4s\kappa\\
& \ge t_{p^{\ell},\ell}-t_{w^{\ell},\ell}-4s\kappa-\frac{\kappa}{2}\\
& \ge \psi_{v^{\bar{\ell}},w^{\bar{\ell}}}(\bar{\ell}\,)-(\bar{\ell}-\ell+1)\frac{\kappa}{2}\\
& > 0.
\end{align*}

Thus, by $\JC$, it holds that

\begin{equation*}
t_{w,\ell-1} \le t_{w^{\ell},\ell-1}-\kappa.
\end{equation*}

We distinguish two cases.

* $\Cor_{w^{\ell},\ell}\le \vartheta\kappa$. Then

\begin{align*}
t_{w^{\ell},\ell}-t_{w,\ell-1}&\ge t_{w^{\ell},\ell}-t_{w^{\ell},\ell-1}+\kappa\\
&\ge d-u+\frac{\Lambda-d-\Cor_{w^{\ell},\ell}}{\vartheta}+\kappa\\
&\ge d-u+\frac{\Lambda-d}{\vartheta}.
\end{align*}

* $\Cor_{w^{\ell},\ell}>\vartheta \kappa$. By $\JC$, it follows that

\begin{align*}
t_{w^{\ell},\ell-1} \ge t_{w,\ell-1}+\frac{\Cor_{w^{\ell},\ell}}{\vartheta}+\kappa,
\end{align*}

yielding that

\begin{align*}
t_{w^{\ell},\ell}-t_{w,\ell-1}&\ge t_{w^{\ell},\ell}-t_{w^{\ell},\ell-1}+\frac{\Cor_{w^{\ell},\ell}}{\vartheta}+\kappa\\
&> d-u+\frac{\Lambda-d}{\vartheta}.\qedhere
\end{align*}

Using <Ref>, we establish for the special case of $p'=w^{\ell}$ and $w=p^{\ell}$.
Note that this entails that $w$ is closer to $p^{\ell}$, yet $P$ is not shorter than $P^{\ell}$.
This is accounted for by the case distinction in the definition of $\Delta^{\ell}$, which covers the difference.

If $p'=w^{\ell}$ and $w=p^{\ell}$, then holds for $v$, $p'$, $w$, $|P'|$, $|Q'|$, and layer $\ell-1$.

Denote by $\Delta_v\in \{-1,0,1\}$ the value such that

\begin{align*}
t_{v^{\ell},\ell-1}-\Cor_{v^{\ell},\ell}&\le t_{v,\ell-1}-(4s-2)\kappa\Delta_v-\kappa
\end{align*}

according to <Ref>.
By <Ref>,

\begin{align*}
>&\, t_{v,\ell-1}-t_{w^{\ell},\ell}+d-u+\frac{\Lambda-d}{\vartheta}\\
\ge &\,t_{v^{\ell},\ell-1}-\Cor_{v^{\ell},\ell}+(4s-2)\kappa \Delta_v+\kappa-t_{w^{\ell},\ell}+d-u+\frac{\Lambda-d}{\vartheta}\\
\ge &\,t_{v^{\ell},\ell}-\Lambda+(4s-2)\kappa \Delta_v+\kappa-t_{w^{\ell},\ell}+d-u+\frac{\Lambda-d}{\vartheta}\\
= &\,t_{v^{\ell},\ell}-t_{w^{\ell},\ell}+(4s-2)\kappa\Delta_v+\frac{\kappa}{2}\\
\ge &\,(4s-2)\kappa(\Delta^{\ell}+\Delta_v)+\psi_{v^{\bar{\ell}},w^{\bar{\ell}}}^s(\bar{\ell}\,)+(\bar{\ell}-(\ell-1))\frac{\kappa}{2}+\kappa_s|P^{\ell}|.
\end{align*}

We claim that $\Delta\le \Delta^{\ell}+\Delta_v$.
Note that plugging this into the above inequality yields

\begin{equation*}
t_{v,\ell-1}-t_{w,\ell-1}\ge (4s-2)\kappa \Delta+\psi_{v^{\bar{\ell}},w^{\bar{\ell}}}^s(\bar{\ell}\,)+(\bar{\ell}-(\ell-1))\frac{\kappa}{2}+\kappa_s|P'|,
\end{equation*}

i.e., for $v$, $p'$, $w$, $|P'|$, $|Q'|$, and layer $\ell-1$, as desired.
Therefore, proving the above claim will complete the proof.

To show the claim, we first note that $P'=(p',w)=(w^{\ell},p^{\ell})$.
Since $w=p^{\ell}$, by <Ref> we also have that $P^{\ell}=(p^{\ell},w^{\ell})=(w,p')$.
In particular, $|P^{\ell}|=|P'|$.
We distinguish two cases.

* $P^{\ell}$ and $Q^{\ell}$ share the first edge. It follows that $|Q^{\ell}|\ge 2$, as otherwise $v^{\ell}=w^{\ell}$, contradicting . If $v=p'$, then

\begin{equation*}
|Q'|=|Q|=|(v)|=0\le |Q^{\ell}|-2\le |Q^{\ell}|+\Delta_v-1.
\end{equation*}

Otherwise, the first edge of $Q$ is the first edge of $Q^{\ell}$ and thus $P^{\ell}$. This edge is $\{p^{\ell},w^{\ell}\}=\{p^{\ell},p'\}$. Hence, $|Q'|=|\suffix(Q,p')|\le |Q|-1=|Q^{\ell}|+\Delta_v-1$. Either way, we get that

\begin{equation*}
\Delta\le |P'|+|Q'| \le |P^{\ell}|+|Q^{\ell}|+\Delta_v-1 = \Delta^{\ell}+\Delta_v.
\end{equation*}

* $P^{\ell}$ and $Q^{\ell}$ do not share the first edge, but $P'$ and $Q'$ do. Then

\begin{equation*}
\Delta= |P'|+|Q'|-1 \le |P^{\ell}|+|Q^{\ell}|+\Delta_v-1 = \Delta^{\ell}+\Delta_v.
\end{equation*}

* $P^{\ell}$ and $Q^{\ell}$ do not share the first edge and neither do $P'$ and $Q'$. As the first (and only) edge of $P'$ is $\{p',w\}=\{p',p^{\ell}\}$, this entails that $Q'=\suffix(Q,p')$. We distinguish two subcases.

* $|\suffix(Q,p')|\le |Q|-1$. Then

\begin{equation*}
\Delta= |P'|+|Q'| \le |P^{\ell}|+|Q|-1\le |P^{\ell}|+|Q^{\ell}|+\Delta_v = \Delta^{\ell}+\Delta_v.
\end{equation*}

* $|\suffix(Q,p')|=|Q|$ and $v^{\ell}\neq w$. Then $p'$ is the last node on $Q$, i.e., $v=p'$. As by <Ref> $Q'$ is a path from $p'$ to $v$, it follows that $|Q'|=0<|Q^{\ell}|$. We conclude that

\begin{equation*}
\Delta= |P'|+|Q'| \le |P^{\ell}|+|Q^{\ell}|+\Delta_v = \Delta^{\ell}+\Delta_v.
\end{equation*}

* $|\suffix(Q,p')|=|Q|$ and $v^{\ell}= w$. As $w=p^{\ell}$ and $p'=v=w^{\ell}$ as in the previous subcase, this contradicts <Ref>.

Before proceeding to the case that $v\neq w^{\ell}$ or $w\neq v^{\ell}$, we prove another helper statement ruling out the specific case that $v\neq p'=w$.

It is not possible that $v\neq p'=w$.

Assume towards a contradiction that $v\neq p'=w$.
Thus, $p'=p$. <Ref> yield that

\begin{align*}
t_{w^{\ell},\ell-1}-\frac{\Cor_{w^{\ell},\ell}}{\vartheta}&\ge t_{w,\ell-1}-4s\kappa\mbox{ and}\\
t_{p^{\ell},\ell-1}-\Cor_{p^{\ell},\ell}&\le t_{p',\ell-1}.
\end{align*}

Using and <Ref>, it follows that

\begin{align*}
&\ge t_{p^{\ell},\ell-1}-\Cor_{p^{\ell},\ell}-\left(t_{w^{\ell},\ell-1}-\frac{\Cor_{w^{\ell},\ell}}{\vartheta}\right)-4s\kappa\\
&\ge t_{p^{\ell},\ell}-t_{w^{\ell},\ell}-4s\kappa-\frac{\kappa}{2}\\
&\ge \psi^s_{v^{\bar{\ell},w^{\bar{\ell}}}}(\bar{\ell}\,)-(\bar{\ell}-(\ell-1))\frac{\kappa}{2}\\
\end{align*}

arriving at the desired contradiction.

We now establish for the case that $v\neq w^{\ell}$ or $w\neq v^{\ell}$.

If $p'\neq w^{\ell}$ or $w\neq p^{\ell}$, then holds for $v$, $p'$, $w$, $|P'|$, $|Q'|$, and layer $\ell-1$.

Denote by $\Delta_w,\Delta_v\in \{-1,0,1\}$ the values such that

\begin{align*}
t_{w^{\ell},\ell-1}-\Cor_{w^{\ell},\ell}&\ge t_{w,\ell-1}+ 4s\kappa \Delta_w\\
t_{v^{\ell},\ell-1}-\Cor_{v^{\ell},\ell}&\le t_{v,\ell-1}-(4s-2)\kappa \Delta_v -\kappa
\end{align*}

according to <Ref>.
Using and <Ref>, we bound

\begin{align*}
\ge &\,t_{v^{\ell},\ell-1}-\frac{\Cor_{v,\ell}}{\vartheta}+(4s-2)\kappa \Delta_v+\kappa-(t_{w^{\ell},\ell-1}-\Cor_{w,\ell}- 4s\kappa \Delta_w)\\
\ge &\,t_{v^{\ell},\ell}+(4s-2)\kappa\Delta_v+\kappa-t_{w^{\ell},\ell}+ 4s\kappa\Delta_w-\frac{\kappa}{2}\\
\ge &\,(4s-2)\kappa(\Delta^{\ell}+\Delta_v+\Delta_w)+(\bar{\ell}-(\ell-1))\frac{\kappa}{2}+\kappa_s(|P^{\ell}|+\Delta_w)\\
\ge &\,(4s-2)\kappa(\Delta^{\ell}+\Delta_v+\Delta_w)+(\bar{\ell}-(\ell-1))\frac{\kappa}{2}+\kappa_s |P'|,
\end{align*}

where the last step exploits that $|P'|=|\suffix(P,p')|\le |P|\le|P^{\ell}|+\Delta_w$.
We claim that $\Delta\le \Delta^{\ell}+\Delta_v+\Delta_w$.
Proving this claim will complete the proof, as by the above inequality then

\begin{equation*}
t_{v,\ell-1}-t_{w,\ell-1}\ge (4s-2)\kappa\Delta+(\bar{\ell}-(\ell-1))\frac{\kappa}{2}+\kappa_s |P'|,
\end{equation*}

i.e., for $v$, $p'$, $w$, $|P'|$, $|Q'|$, and layer $\ell-1$.

By <Ref> and the prerequisites of the lemma, $P'=\suffix(P,p')$ or $p'=v=w^{\ell}$. To cover the possibility that $P'=\suffix(P,p')$, we distinguish several cases:

* $p'=p^{\ell}$. Then $P'=P$ and $Q'=Q$, as $p'$ is the first node of both $P$ and $Q$. Hence,

\begin{equation*}
\end{equation*}

We distinguish three subcases.

* $P^{\ell}$ and $Q^{\ell}$ do not share their first edge. Then

\begin{equation*}
\Delta\le |P'|+|Q'|=|P^{\ell}|+|Q^{\ell}|+\Delta_w+\Delta_v=\Delta^{\ell}+\Delta_w+\Delta_v.
\end{equation*}

* $P^{\ell}$, $Q^{\ell}$, and $Q'$ share the same first edge. By <Ref>, $w\neq p'$. Therefore, $P'=P\neq (p')$, which means that $P^{\ell}$ and $P'$ have the same first edge, too. Thus, $Q'$ and $P'$ have the same first edge as well, and

\begin{equation*}
\Delta= |P'|+|Q'|-1=|P^{\ell}|+|Q^{\ell}|-1+\Delta_w+\Delta_v=\Delta^{\ell}+\Delta_w+\Delta_v.
\end{equation*}

* $P^{\ell}$ and $Q^{\ell}$ have the same first edge, but $Q'$ does not. Since $Q^{\ell}\neq (p^{\ell})$, we have that $v^{\ell}\neq p^{\ell}$. By , this implies that $v^{\ell}\notin P^{\ell}$. In particular, $v^{\ell}$ cannot be part of the first edge of $Q^{\ell}$ and $|Q^{\ell}|\ge 2$. As $p'=p^{\ell}$, $Q$ and $Q'$ both start with $p'$. Therefore, $Q'$ is a prefix of $Q^{\ell}$. However, $Q^{\ell}$ has the same first edge as $P^{\ell}$, while $Q'$ does not. Thus, $|Q'|=0\le |Q^{\ell}|+\Delta_v-1$. We conclude that

\begin{equation*}
\Delta= |P'|+|Q'|\le |P^{\ell}|+|Q^{\ell}|-1+\Delta_w+\Delta_v=\Delta^{\ell}+\Delta_w+\Delta_v.
\end{equation*}

* $v=p'\neq p^{\ell}$. Then $Q'=(p')$. Moreover, by the prerequisites of the lemma, $P'=\suffix(P,p')$. Since $p'\neq p^{\ell}$, we have that $|\suffix(P,p')|\le |P|-1$. By construction, $|Q'|\le |Q|+1$. Overall,

\begin{equation*}
\Delta\le |P'|+|Q'|\le |P|-1+|Q|+1=|P^{\ell}|+\Delta_w+|Q^{\ell}|+\Delta_v=\Delta^{\ell}+\Delta_w+\Delta_v.
\end{equation*}

* $v\neq p'\neq p^{\ell}$. Thus, $p'=p$ and by <Ref> $\{p^{\ell},p'\}$ is the first edge of $P^{\ell}$. Hence, $|P'|=|\suffix(P,p')|\le |P|-1 \le |P^{\ell}|+\Delta_w-1$. We distinguish two subcases.

* $P^{\ell}$ and $Q^{\ell}$ do not share their first edge. Then

\begin{equation*}
\Delta\le |P'|+|Q'|\le |P^{\ell}|+\Delta_w+|Q^{\ell}|+\Delta_v=\Delta^{\ell}+\Delta_w+\Delta_v.
\end{equation*}

* $P^{\ell}$ and $Q^{\ell}$ share their first edge. As $v\neq p'$, $Q$ has the same first edge as $Q^{\ell}$, i.e., $\{p^{\ell},p'\}$. Hence, $|Q'|=|\suffix(Q,p'|=|Q|-1\le |Q^{\ell}|+\Delta_v-1$. We conclude that

\begin{equation*}
\Delta\le |P'|+|Q'|\le |P^{\ell}|+\Delta_w+|Q^{\ell}|+\Delta_v-2<\Delta^{\ell}+\Delta_w+\Delta_v.
\end{equation*}

It remains to consider the case that $P'\neq \suffix(P,p')$ and $p'=v=w^{\ell}$.
Then $|Q'|=(v)$ and $|P'|=|(p',w)|=1$, implying that $\Delta=1$.
By (P2), $v^{\ell}\neq w^{\ell}=v$.
If $\Delta_v=1$, then

\begin{equation*}
\Delta = 1 \le \Delta^{\ell} \le \Delta^{\ell}+\Delta_w+\Delta_v.
\end{equation*}

By <Ref>, the remaining case is that $\Delta_v=-1$ and $\{v,v^{\ell}\}$ is the last edge of $Q^{\ell}$ or the first edge of $P^{\ell}$.
By <Ref>, it is impossible that $v=w^{\ell}$, so this edge must be the last one of $Q^{\ell}$ and distinct from the first one of $P^{\ell}$.
Moreover, by the prerequisites of the lemma, $p^{\ell}\neq w$, so it must hold that $|P^{\ell}|\ge 2$.
Overall, either

* $|Q^{\ell}|\ge 2$ and

\begin{equation*}
\Delta = 1 \le |P^{\ell}|+|Q^{\ell}|-3 \le \Delta^{\ell}-2=\Delta^{\ell}+\Delta_w+\Delta_v,\mbox{ or}
\end{equation*}

* $|Q^{\ell}|=1$ and $Q^{\ell}$ and $P^{\ell}$ do not share the first edge, yielding

\begin{equation*}
\Delta = 1 \le |P^{\ell}|+|Q^{\ell}|-2 = \Delta^{\ell}-2=\Delta^{\ell}+\Delta_w+\Delta_v.\qedhere
\end{equation*}

and hold for $v$, $p'$, $w$, $|P'|$, $|Q'|$, and layer $\ell-1$.

Follows from <Ref>, <Ref>, and <Ref>.

It remains to prove .

holds for $v$, $p'$, $|P'|$, and layer $\ell-1$.

If $v=p'$, the statement readily follows from <Ref> and <Ref>.
Therefore, assume that $v\neq p'$ and hence $p'=p$ in the following.
Denote by $\Delta_w\in \{-1,0,1\}$ the value such that

\begin{align*}
t_{w^{\ell},\ell-1}-\Cor_{w^{\ell},\ell}&\ge t_{w,\ell-1}+4s\kappa \Delta_w\\
t_{p^{\ell},\ell-1}-\Cor_{p^{\ell},\ell}&\le t_{p',\ell-1}
\end{align*}

according to <Ref>.

Using and <Ref>, it follows that

\begin{align*}
&\ge t_{p^{\ell},\ell-1}-\Cor_{p^{\ell},\ell}-\left(t_{w^{\ell},\ell-1}-\frac{\Cor_{w^{\ell},\ell}}{\vartheta}\right)+\Delta_w 4s\kappa\\
&\ge t_{p^{\ell},\ell}-t_{w^{\ell},\ell}+4s\kappa\Delta_w-\frac{\kappa}{2}\\
&\ge 4s\kappa (|P^{\ell}|+\Delta_w)+\psi^s_{v^{\bar{\ell}},w^{\bar{\ell}}}(\bar{\ell}\,)-(\bar{\ell}-(\ell-1))\frac{\kappa}{2}.
\end{align*}

If $P'=\suffix(P,p')$, then $|P'|\le |P|\le |P^{\ell}|+\Delta_w$ and for $v$, $p'$, $|P'|$, and layer $\ell-1$ readily follows from the above inequality.

Otherwise, by the assumption that $v\neq p'$ and <Ref>, it holds that $p'=w^{\ell}$ and $w=p^{\ell}$, and $|P'|=|P^{\ell}|$.
Using <Ref> together with , we arrive at

\begin{align*}
&\ge t_{p',\ell-1}-t_{w^{\ell},\ell}+\left(d-u+\frac{\Lambda-d}{\vartheta}\right)\\
&\ge t_{p^{\ell},\ell-1}-\Cor_{p^{\ell},\ell}-t_{w^{\ell},\ell}+\left(d-u+\frac{\Lambda-d}{\vartheta}\right)\\
&\ge t_{p^{\ell},\ell}-t_{w^{\ell},\ell}-\frac{\kappa}{2}\\
&\ge 4s\kappa|P^{\ell}|+\psi^s_{v^{\bar{\ell}},w^{\bar{\ell}}}(\bar{\ell}\,)-(\bar{\ell}-(\ell-1))\frac{\kappa}{2}\\
&\ge 4s\kappa|P'|+\psi^s_{v^{\bar{\ell}},w^{\bar{\ell}}}(\bar{\ell}\,)-(\bar{\ell}-(\ell-1))\frac{\kappa}{2},
\end{align*}

i.e., for $v$, $p'$, $|P'|$, and layer $\ell-1$.

Finally, using these results it is not hard to show that is satisfied as well.

holds for $v$, $p'$, $|P'|$, and layer $\ell-1$.

Suppose that $v$ lies on $P'$.
By <Ref>, $v\neq w$.
Thus, if $P'=(p',w)$, $v=p'$, i.e., holds for $v$, $p'$, $|P'|$, and layer $\ell-1$.

Otherwise, $P'=\suffix(P,p')$, implying that $v$ lies on $\suffix(P,p')$.
As $v\neq w$, this implies that $v$ lies on $P^{\ell}$.
Assuming for contradiction that $v\neq p'=p$, by <Ref> we have that $\prefix(P,p')=\prefix(P^{\ell},p')$, which equals either $(p^{\ell})=(p')$ or $(p^{\ell},p')$.
Thus, the above entails that $v$ actually lies on $\suffix(P^{\ell},p')=\suffix(P^{\ell},p)$.
As then $p'=v$, this is a contradiction and we must indeed have that $p'=v$.

In the proof of <Ref>, it must hold that $\ell=\underline{\ell}$.

Assuming for contradiction that $\ell>\underline{\ell}$, <Ref>, <Ref>, and <Ref> show that layer $\ell-1$ also satisfies the properties to for some $v^{\ell-1},p^{\ell-1},w^{\ell-1}$, and paths $P^{\ell-1}$, $Q^{\ell-1}$, contradicting the minimality of $\ell$.

§.§.§ Bounding Skews

With our machinery for bounding $\Psi^s$ in place, it remains to perform the induction on $s\in \N_{>0}$ to wrap things up.
To anchor the induction at $s=1$, we exploit that $\Psi^1(\ell)\le \Xi^1(\ell)+2\kappa D$.

\begin{equation*}
\Psi^1(\ell)\le \begin{cases}
\Xi^1(0) &\mbox{if $\ell <4\Xi^1(0)/\kappa$}\\
4\kappa D & \mbox{else.}
\end{cases}
\end{equation*}

Recall that $\kappa=2(u+(1-1/\vartheta)(\Lambda-d))$.
Note that $\Xi^1(\ell)\le \Psi^1(\ell)+2\kappa D$ for all $\ell\in \N$.
By <Ref>, we thus have for any $\underline{\ell}\le \bar{\ell}$ that

\begin{align*}
\Psi^1(\bar{\ell}\,)&\le \max\left\{0,\Xi^1(\underline{\ell}\,)-(\bar{\ell}-\underline{\ell}+1)\kappa\right\}+(\bar{\ell}-\underline{\ell}\,)\frac{\kappa}{2}\\
&\le \max\left\{0,\Psi^1(\underline{\ell}\,)+2\kappa D-(\bar{\ell}-\underline{\ell}+1)\kappa\right\}+(\bar{\ell}-\underline{\ell}\,)\frac{\kappa}{2}.
\end{align*}

In particular, we have that

\begin{equation*}
\Psi^1(\ell)\le \begin{cases}
\max\left\{4\kappa D,\Xi^1(0)\right\}&\mbox{if $\ell<8D$}\\
\max\left\{4\kappa D,\Psi^1(\ell-8D)-2\kappa D\right\}&\mbox{else.}
\end{cases}
\end{equation*}

By induction on $k\in \N$, we thus have that

\begin{equation*}
\Psi^1(\ell)\le \max\{4\kappa D, \Xi^1(0)-2k\kappa D\}
\end{equation*}

for all $\ell \in [8kD,8(k+1)D)$.
The claim of the lemma follows by noting that $\ell\ge 4\Xi^1(0)/\kappa$ results in $k\ge \Xi^1(0)/(2\kappa D)$.

Note that this lemma shows that $\Psi^1$ self-stabilizes <cit.> within $O(\Xi^1(0)/\kappa)$ layers.

We remark that a more careful analysis reveals a bound on $\Psi^1(\ell)$ that converges to $2\kappa D$.
We confine ourselves to stating this result for the small input skew that we guarantee.

If $\localskew_0\le 4\kappa$, then $\Psi^1(\ell)\le 2\kappa D$ for all $\ell\in \N$.

Note that

\begin{equation*}
\Xi^1(0)=\max_{v,w\in V}\{t_{v,0}-t_{w,0}-2\kappa d(v,w)\}\le \max_{v,w\in V}\{(\localskew_0-2\kappa)d(v,w)\}\le (\localskew_0-2\kappa)D\le 2\kappa D.
\end{equation*}

By replacing $8D$ with $4D$ in the induction from the proof of <Ref>, we get that

\begin{equation*}
\Psi^1(\ell)\le \begin{cases}
\max\left\{2\kappa D,\Xi^1(0)\right\}&\mbox{if $\ell<4D$}\\
\max\left\{2\kappa D,\Psi^1(\ell-4D)\right\}&\mbox{else,}
\end{cases}
\end{equation*}

implying a uniform bound of $\Psi^1(\ell)\le 2\kappa D$ for all $\ell\in \N$.

For the sake of completeness, we also infer that $\sup_{\ell\in \N}\{\Psi^0(\ell)\}$, also referred to as the global skew in the literature, is in $O(u+(1-1/\vartheta)(\Lambda-d))$.
Provided that $\Lambda\in O(d+u/(\vartheta-1))$, this bound is asymptotically optimal <cit.>.

If $\localskew_0\le 4\kappa$, then $\Psi^0(\ell)\le 6\kappa D\in O(u+(1-1/\vartheta)(\Lambda-d))$ for all $\ell\in \N$.

Follows from <Ref>, the fact that $\Psi^0(\ell)\le \Psi^1(\ell)+4\kappa D$, and the choice of $\kappa$.

In order to bound the local skew, we now turn to attention to $\Psi^s(\ell)$ for $s>1$.

For some $s\in \N$, $s>0$, suppose that $\Psi^{s-1}(\ell)\le \Psi^{s-1}$ for all $\ell \in \N$.

\begin{equation*}
\Psi^s(\ell)\le \begin{cases}
\Xi^s(0)+\frac{\Psi^{s-1}}{2} &\mbox{if $\ell<\Psi^{s-1}/\kappa$}\\
\frac{\Psi^{s-1}}{2} &\mbox{else.}
\end{cases}
\end{equation*}

Recall that $\kappa=2(u+(1-1/\vartheta)(\Lambda-d))$.
For $\ell<\Psi^{s-1}/\kappa$, by <Ref> with $\bar{\ell}=\ell$ and $\underline{\ell}=0$ we have that

\begin{equation*}
\Psi^s(\ell)\le \Xi^s(0)+\frac{\kappa\ell}{2}\le \Xi^s(0)+\frac{\Psi^{s-1}}{2}.
\end{equation*}

Note that $\Xi^s(\ell)\le \Psi^{s-1}(\ell)\le \Psi^{s-1}$ for all $\ell\in \N$.
Thus, for $\ell\ge \Psi^{s-1}/\kappa$ by <Ref> with $\bar{\ell}=\ell$ and $\underline{\ell}=\ell - \lfloor \Psi^{s-1}/\kappa\rfloor$ we have that

\begin{equation*}
\Psi^s(\ell)\le \max\left\{0,\Xi^s\left(\ell-\left\lfloor \frac{\Psi^{s-1}}{\kappa}\right\rfloor\right)-\left(\left\lfloor \frac{\Psi^{s-1}}{\kappa}\right\rfloor+1\right)\kappa\right\}+\left\lfloor \frac{\Psi^{s-1}}{\kappa}\right\rfloor\frac{\kappa}{2}
\le \frac{\Psi^{s-1}}{2}.\qedhere
\end{equation*}

Using this lemma, we can bound the local skew by $O(\kappa (1+\log D))=O((u+(1-1/\vartheta)(\Lambda-d))(1+\log D))$.

By <Ref>, $\localskew_0\le 4\kappa$.
By <Ref>, $\Psi^1(\ell)\le 2\kappa D$ for all $\ell\in \N$.
By the assumption that $\localskew_0\le 4\kappa$, for all $s>1$ we have that

\begin{equation*}
\Xi^s(0)=\max_{v,w\in V}\{t_{v,0}-t_{w,0}-(4s-2)\kappa d(v,w)\}\le\max_{v,w\in V}\{(\localskew_0-6\kappa)d(v,w)\}=0.
\end{equation*}

Hence, inductive use of <Ref> yields that $\Psi^s(\ell)\le 2^{2-s}\kappa D$.
In particular, $\Psi^{\lfloor \log D\rfloor}\le 8\kappa$.
The claim now follows by <Ref>.

Moreover, in addition we obtain the following self-stabilization property.

If for $s,s'\in \N$, $s\le s'$, we have that $\Psi^s(\ell)\le \Psi^s$ for all $\ell\ge \underline{\ell} \in \N$, then for $\ell\ge \underline{\ell}$

\begin{equation*}
\localskew_{\ell}\le \begin{cases}
4s\kappa+\Psi^s&\mbox{if $\underline{\ell}\le \ell<\underline{\ell}+2\Psi^s/\kappa$ and}\\
4s'\kappa+\frac{\Psi^s}{2^{s'-s}}&\mbox{if $\ell\ge \underline{\ell}+2\Psi^s/\kappa$.}
\end{cases}
\end{equation*}

Inductive use[As is, the lemma applies only if $\underline{\ell}=0$. However, the algorithm and hence all statements are invariant under shifting indices by $\underline{\ell}$.] of <Ref> yields for $s'\ge s$ and $\ell\ge \underline{\ell}+\sum_{\sigma=s+1}^{s'}\Psi^{s}/(2^{\sigma-s}\kappa)$ that

\begin{equation*}
\Psi^{s'}\le \frac{\Psi^{s}}{{2^{s'-s}}}.
\end{equation*}

Since the sum forms a geometric series, this in particular applies to all $\ell\ge \underline{\ell}+2\Psi^s/\kappa$.
The claim now follows by applying <Ref>.

§.§ Bounding Skews in the Presence of Faults

To analyze how skews evolve with faults, we relate the setting with faults to the bounds we have for a fault-free system.
The key property the algorithm guarantees is that, up to an additive $2\kappa$, the pulse time is within the interval spanned by the correct predecessors' pulse times plus $\Lambda$.
We first show this for the case that for some node $(v,\ell)$, $(v,\ell-1)$ is faulty.

Suppose that the only faulty predecessor of $(v,\ell)\in V_{\ell}$, $\ell>0$, is $(v,\ell-1)$.

\begin{align*}
t_{\min}&:=\min_{\{v,w\}\in E}\{t_{w,\ell-1}\}\mbox{ and}\\
t_{\max}&:=\max_{\{v,w\}\in E}\{t_{w,\ell-1}\}.
\end{align*}

\begin{equation*}
t_{\min}+\Lambda-2\kappa \le t_{v,\ell} \le t_{\max}+\Lambda+2\kappa.
\end{equation*}

By the assumption of the lemma, for all $\{v,w\}\in E$, $(w,\ell-1)\notin F$.
We have that

\begin{align*}
H_{\own}-H_{\max}&=\min_{s\in \N}\{H_{\own}-H_{\max}+4s\kappa\}\\
&\le \min_{s\in \N}\{\max\{H_{\own}-H_{\max}+4s\kappa,H_{\own}-H_{\min}-4 s\kappa \}\}\\
&\le \max\{H_{\own}-H_{\max},H_{\own}-H_{\min}\}\\
&= H_{\own}-H_{\min}.
\end{align*}

Hence, abbreviating

\begin{equation*}
\Delta=\min_{s\in \N}\{\max\{H_{\own}-H_{\max}+4s\kappa,H_{\own}-H_{\min}-4 s\kappa \}\}-\frac{\kappa}{2},
\end{equation*}

it holds that

\begin{equation*}
H_{\own}-H_{\max}-\frac{\kappa}{2}\le \Delta\le H_{\own}-H_{\min}-\frac{\kappa}{2}.
\end{equation*}

Taking into account the adjustments in case $\Delta\notin [0,\vartheta \kappa]$ and using that $H_{\min}\le H_{\max}$ we get that

\begin{equation*}
H_{\own}-H_{\max}-\frac{3\kappa}{2} \le \Cor_{v,\ell}
\le H_{\own}-H_{\min}+\frac{3\kappa}{2}.
\end{equation*}

Therefore, the local time $H_{v,\ell}(t_{v,\ell})=H_{\own}+\Lambda-d-\Cor_{v,\ell}$ at which $(v,\ell)$ generates its pulse satisfies

\begin{equation*}
H_{\min}+\Lambda-d-\frac{3\kappa}{2}\le H_{v,\ell}(t_{v,\ell}) \le H_{\max}+\Lambda-d+\frac{3\kappa}{2}.
\end{equation*}

If $H_{\min}>H_{v,\ell}(t_{v,\ell})$, we have that

\begin{equation*}
t_{\min}-t_{v,\ell}\le H_{\min}-H_{v,\ell}(t_{v,\ell}).
\end{equation*}

Applying the lower bound of $d-u$ on message delay and <Ref>, we get that

\begin{equation*}
t_{v,\ell}\ge t_{\min}+d-u+\Lambda-d-\frac{3\kappa}{2}>t_{\min}+\Lambda-2\kappa.
\end{equation*}

If $H_{\min}\le H_{v,\ell}(t_{v,\ell})$, the bounds on message delays and hardware clock drift together with <Ref> yield that

\begin{align*}
t_{v,\ell}&\ge t_{\min}+d-u+\frac{\Lambda-d-3\kappa/2}{\vartheta}\\
\end{align*}

Concerning the upper bound on $t_{v,\ell}$, note that because $t_{v,\ell}$ is increasing in $H_{v,\ell}(t_{v,\ell})$, to bound $t_{v,\ell}$ from above we may assume that

\begin{equation*}
H_{v,\ell}(t_{v,\ell}) = H_{\max}+\Lambda-d+\frac{3\kappa}{2}>H_{\max},
\end{equation*}

where the last step uses <Ref>.
In this case,

\begin{equation*}
t_{v,\ell}-t_{\max}\le H_{v,\ell}(t_{v,\ell}) - H_{\max}+d\le \Lambda+\frac{3\kappa}{2} < \Lambda+2\kappa.\qedhere
\end{equation*}

Similar reasoning covers the case that for some $(v,\ell)\in V_{\ell}$ and $\{v,w\}\in E$, $(w,\ell-1)$ is faulty.

Suppose that for $(v,\ell)\in V_{\ell}$, $\ell>0$, $(v,\ell-1)$ is not faulty, and at most one predecessor is faulty.

\begin{align*}
t_{\min}&:=\min_{\substack{((w,\ell-1),(v,\ell))\in E_{\ell-1}\\ (w,\ell-1)\notin F}}\{t_{w,\ell-1}\}\mbox{ and}\\
t_{\max}&:=\max_{\substack{((w,\ell-1),(v,\ell))\in E_{\ell-1}\\ (w,\ell-1)\notin F}}\{t_{w,\ell-1}\},
\end{align*}

\begin{equation*}
t_{\min}+\Lambda-2\kappa \le t_{v,\ell} \le t_{\max}+\Lambda.
\end{equation*}

By <Ref>, $\Cor_{v,\ell}\ge 0$ implies that

\begin{equation*}
t_{v,\ell}-t_{\min}\le t_{v,\ell}-t_{v,\ell-1}\le \Lambda,
\end{equation*}

while $\Cor_{v,\ell}\le \vartheta \kappa$ yields that

\begin{equation*}
t_{v,\ell}-t_{\max}\ge t_{v,\ell}-t_{v,\ell-1}\ge d-u+\frac{\Lambda-d}{\vartheta}-\kappa \ge \Lambda - 2\kappa.
\end{equation*}

It remains to show the upper bound on $t_{v,\ell}$ if $\Cor_{v,\ell}<0$ and the lower bound if $\Cor_{v,\ell}>\vartheta \kappa$.

Consider first the case that $\Cor_{v,\ell}<0$.

\begin{equation*}
\Cor_{v,\ell}=H_{\own}-H_{\min}-\frac{\kappa}{2}+2\kappa>H_{\own}-H_{\min}.
\end{equation*}

It follows that

\begin{align*}
H_{v,\ell}(t_{v,\ell})=H_{\own}+\Lambda-d-\Cor_{v,\ell}\le H_{\min}+\Lambda-d.
\end{align*}

Noting that the reception time of the first message from a predecessor is bounded from above by the reception time of the message from a correct predecessor, we conclude that

\begin{equation*}
t_{v,\ell}\le t_{\min}+\Lambda.
\end{equation*}

Now consider the case that $\Cor_{v,\ell}>\vartheta \kappa$.

\begin{equation*}
\Cor_{v,\ell}=H_{\own}-H_{\max}-\frac{\kappa}{2}-\kappa>H_{\own}-H_{\max}-\vartheta u.
\end{equation*}

It follows that the local time $H$ at which $(v,\ell)$ generates its pulse satisfies that

\begin{align*}
H=H_{\own}+\Lambda-d-\Cor_{v,\ell}\ge H_{\max}+\Lambda-d+\vartheta u.
\end{align*}

Noting that the reception time of the latest message from a predecessor is bounded from below by the reception time of the latest message from a correct predecessor, by <Ref> we conclude that

\begin{equation*}
t_{v,\ell}\ge t_{\max}+d+\frac{\Lambda-d}{\vartheta}>t_{v,\ell-1}+\Lambda - \kappa.\qedhere
\end{equation*}

\begin{align*}
t_{\min}&:=\min_{\substack{((w,\ell-1),(v,\ell))\in E_{\ell-1}\\ (w,\ell-1)\notin F}}\{t_{w,\ell-1}\}\mbox{ and}\\
t_{\max}&:=\max_{\substack{((w,\ell-1),(v,\ell))\in E_{\ell-1}\\ (w,\ell-1)\notin F}}\{t_{w,\ell-1}\}.
\end{align*}

\begin{equation*}
t_{\min}+\Lambda-2\kappa \le t_{v,\ell} \le t_{\max}+\Lambda+2\kappa.
\end{equation*}

Immediate from <Ref> and the assumption that no node has more than one faulty predecessor.

Using this result, we can bound the impact of a fault in layer $\ell-1$ on successors via the skew bounds of close-by nodes on layer $\ell-1$;
we exploit that all bounds we show would in fact also apply to the faulty node if it was correct.

Suppose for a node $(v,\ell)\in V_{\ell}$, $\ell>0$, that one of its predecessors is faulty.
Moreover, assume that in an execution that differs only in that the faulty predecessor of $(v,\ell)$ is correct, it holds that $\max_{\{v,w\}\in E}\{|t_{v,\ell-1}-t_{w,\ell-1}|\}\le B$.
Then in the execution with the predecessor being faulty, the pulse time of $(v,\ell)$ differs by at most $2B+4\kappa$.

Denote by standard variables values in the execution without the predecessor being faulty and by primed variables values in the one where it is.
In particular, for node $(v,\ell)\in V_{\ell}\setminus F$

\begin{align*}
t_{\min}&:=\min_{((w,\ell-1),(v,\ell))\in E_{\ell-1}}\{t_{w,\ell-1}\},\\
t_{\max}&:=\max_{((w,\ell-1),(v,\ell))\in E_{\ell-1}}\{t_{w,\ell-1}\},\\
t_{\min}'&:=\min_{\substack{((w,\ell-1),(v,\ell))\in E_{\ell-1}\\ (w,\ell-1)\notin F}}\{t_{w,\ell-1}\}\mbox{, and}\\
t_{\max}'&:=\max_{\substack{((w,\ell-1),(v,\ell))\in E_{\ell-1}\\ (w,\ell-1)\notin F}}\{t_{w,\ell-1}\}.
\end{align*}

denote the earliest and latest pulsing times of (correct) predecessors without and with faults on layer $\ell-1$, respectively.

Observe that

\begin{equation*}
t_{v,\ell-1}-B\le t_{\min}\le t_{\min'}\le t_{\max'}\le t_{\max}\le t_{v,\ell-1}+B.
\end{equation*}

Hence, <Ref> (applied to both executions) shows that

\begin{align*}
t_{v,\ell-1}-B-2\kappa &\le t_{v,\ell}\le t_{v,\ell-1}+B+2\kappa\mbox{ and}\\
t_{v,\ell-1}-B-2\kappa &\le t_{v,\ell}'\le t_{v,\ell-1}+B+2\kappa.\qedhere
\end{align*}

Finally, we observe that such a “time shift” propagates without further increase, so long as there are no faults.
However, a subtlety here is that this is only true for our bounds on timing:
a change in timing might leave more time for drift of the local clock to accumulate;
since our worst-case bounds include the maximum time error that can possibly be accumulated from drift (so long as local skews do not become exceedingly large), this is already accounted for in the bound provided by <Ref>.
Hence, we obtain the following generalized variant of <Ref>.

Suppose that for $v\in V$ and $\ell\in \N_{>0}$ the predecessors of $(v,\ell)$ are correct.
If we shift the pulse times of these predecessors by at most $\delta \in \R$, where <Ref> still holds for the shifted times, then

\begin{equation*}
d-u+\frac{\Lambda-d-\Cor_{v,\ell}}{\vartheta}-\delta \le t_{v,\ell}'-t_{v,\ell-1} \le \Lambda-\Cor_{v,\ell}+\delta,
\end{equation*}

where $t_{v,\ell}'$ denotes the pulse time of $(v,\ell)$ in the execution with the shifts applied.

Pulse times are increasing as functions of pulse times of predecessors.
Therefore, in order to maximize or minimize $t_{v,\ell}'$, we need to maximize or minimize the predecessors' pulse times, respectively.
Shifting all predecessors' pulse times uniformly by $\delta$ also shifts $t_{v,\ell}'$ by $\delta$ relative to $t_{v,\ell}$.
The statement now follows analogously to the proof of <Ref>, carrying the uniform shift through all inequalities.

With these tools in place, we can conclude that skews do not grow arbitrarily in the face of faults.

If there are at most $f$ faulty nodes in the system and none in layer $0$, then $\localskew_{\ell}\in O(5^f\kappa\log D)$.

We prove by induction on the number $i\le f$ of layers $\ell>0$ with faults that the skew is bounded by $B_i:=4\kappa(2+\log D)5^i\sum_{j=0}^i 5^{-j}\in O(5^f\kappa\log D)$.
By <Ref>, $\localskew_0\le \kappa/2<4\kappa$.
Thus, if there are no faults in layers $\ell>0$, by <Ref> we have that $\localskew_{\ell}\le B_0:= 4\kappa(2+\log D)$ for all $\ell\in \N$.

Assume that we completed step $i\in \N$ and that $\ell_{i+1}$ is the next layer where faults need to be added.
Then we have that for all $\ell\le \ell_{i+1}$ that $\localskew_{\ell'}\le B_i=4\kappa(2+\log D)5^f\sum_{j=0}^i 5^{-j}$ both before and after adding the faults on layer $i+1$.
By <Ref>, it follows that pulsing times on layer $\ell_{i+1}+1$ do not change by more than $2B_i+4\kappa$ due to the addition of faults.
By <Ref>, this extends to all bounds[Due to drifting hardware clocks, this does not apply to the pulse times themselves. However, we rely on <Ref> to prove our bounds in the absence of faults, and this is covered by <Ref>.] we compute on pulse times in layers $\ell>\ell_{i+1}$.
Since $D\ge 1$ and thus $\log D\ge 0$, we get that the local skew in step $i+1$ is bounded by

\begin{equation*}
5B_i+4\kappa = 4\kappa(2+\log D)5^{i+1}\sum_{j=0}^i 5^{-j}+4\kappa \le 4\kappa(2+\log D)5^{i+1}\sum_{j=0}^{i+1} 5^{-j}=B_{i+1}.\qedhere
\end{equation*}

§.§ Bounding Skews with Uniform Fault Distribution

The bound in <Ref>, which is exponential in $f$, seems to suggest that the system can only support a very small number of faults or the local skew explodes.
However, we have not yet taken into account that the starting point of our entire approach is the assumption that faults are sufficiently sparse, meaning that it is highly unlikely that many of them cluster together in a way that causes an exponential pile-up of local skew.
This enables the self-stabilization properties of the algorithm to prevent such a build-up altogether.

In the following, assume that each node fails uniformly and independently with probability $o(n^{-1/2})$.
This is the largest probability of error we can support while guaranteeing that no node has more than one faulty predecessor with probability $1-o(1)$.
A key observation is that this entails that within a fairly large distance of $n^{1/12}$, no node has more than a constant number of faulty nodes that can influence it.
We now formalize and show this claim.

For node $(v,\ell)\in V_{\ell}$ and $\delta\in \N$, its distance-$\delta$ ancestors are all nodes $(w,\ell')\in V_G\setminus \{(v,\ell)\}$ such that there is a (directed) path of length at most $\delta$ from $(w,\ell')$ to $(v,\ell)$ in $G$.

Node $(v,\ell)\in V_{\ell}$, $\ell\in \N_{>0}$ is distance-$\delta$ $k$-faulty if $k\in \N$ is minimal such that there are at most $k$ faulty nodes among the distance-$((k+1)\delta)$ ancestors of $(v,\ell)$.

Suppose that $\delta\le n^{1/12}$.
If nodes fail independently with probability $p\in o(1/\sqrt{n})$, then with probability $1-o(1)$ all nodes are distance-$\delta$ $k$-faulty for $k\le 2$.

In order to be distance-$\delta$ $k$-faulty for $k> 2$, a node must have at least $3$ faults among its distance-$(3\delta)$ ancestors.
The number of these ancestors is bounded by $(3\delta)^2\in O(n^{1/6})$.
Since $p\in o(1/\sqrt{n})$, the probability for this to happen is bounded by $O(p^3 \binom{n^{1/6}}{3})=O(p^3\sqrt{n}) \subset o(1/n)$.
The claim follows by applying a union bound over all $n$ nodes.

We can exploit this to control how much skews grow as the result of faults much better.

Suppose that $\Psi^s(\ell)\le B_{s,\ell}$ and $\localskew_{\ell}\le B$ for all layers $\ell\ge \underline{\ell}$ and $s\in \N$, where $\ell,\underline{\ell}\in \N$, if there are no faults in these layers.
If no node in a layer $\ell\ge \underline{\ell}$ has more than $2$ faulty nodes among its distance-$(\ell-\underline{\ell}\,)$ ancestors, then $\Psi^s(\ell)\le B_{s,\ell}+12B+24\kappa$ for all $\ell \ge \underline{\ell}$.

We examine by how much adding faults on layers $\ell \ge \bar{\ell}$ might affect pulsing times.
For $\ell\ge \bar{\ell}$ and $(v,\ell)\in V_{\ell}$, denote by $f_{v,\ell}\in \{0,1,2\}$ the number of faulty distance-$(\ell-\bar{\ell})$ ancestors of $(v,\ell)$.
For $f_{v,\ell}=0$, there is no change in $t_{v,\ell}$.
For $f_{v,\ell}>0$, consider two cases.
If $(v,\ell)$ has no faulty predecessor, then by <Ref>, $t_{v,\ell}$ is changed at most by the maximum shift that any of its predecessors undergoes.
On the other hand, if $(v,\ell)$ does have a faulty predecessor, then $f_{v,\ell}>f_{w,\ell-1}$ for all correct predecessors of $(v,\ell)$.
Thus, by <Ref> we can bound shifts by $B_{f_{v,\ell}}$, where $B_0:=0$ and $B_{f+1}:=2(B+B_f)+4\kappa$.

By assumption, $f_{v,\ell}\le 2$ and hence the maximum shift is bounded by $B_2=6B+12\kappa$.
We conclude that $\Psi^s(\ell)\le B_{s,\ell}+2B_2=B_{s,\ell}+12B+24\kappa$, as claimed.

Together with <Ref>, <Ref> shows that skews do not increase by more than a constant factor within $n^{1/12}$ layers.
However, we need to handle a total of $\Theta(\sqrt{n})$ layers.
To this end, we slice up the task into chunks of $n^{1/12}$ layers and leverage the self-stabilization properties of the algorithm.
For simplicity, in the following we assume that $n^{1/12}$ is integer.
As we prove asymptotic bounds, this does not affect the results.

Slice $i\in \N_{>0}$ consists of layers $\ell \in [(i-1)n^{1/12},i n^{1/12}-1]$.

Note that there are no more than $n^{5/12}$ slices, because the nodes are arranged in square grid.
Due to the duplication of nodes on layer $0$ and the boundary nodes on layers $\ell>0$, the number of slices is actually $n^{5/12}-\Theta(1)$.

As our next step towards a probabilistic skew bound, we prove that if the local skew remains bounded, then for levels $s$ that are not too large, $\Psi^s$ remains almost as small as without faults.
First, we show a loose bound that naively accumulates shifts slice by slice.

Suppose that

* $\localskew_0\le 4\kappa$,

* each node is distance-$n^{1/12}$ $k$-faulty for $k\le 2$, and

* $\localskew_{\ell}\le B$ for all $\ell\in \N$.

Then for each $s\in \N$ and layer $\ell$ in slice $i\in \N_{>0}$, we have that

\begin{equation*}
\Psi^s(\ell)\le 2^{2-s}\kappa D+i(12B+24\kappa).
\end{equation*}

for all $\ell\in \N$.

Assume first that there are no faults.
In this case, analogously to the proof of <Ref>, we get that $\Psi^s(\ell)\le 2^{2-s}\kappa D$ for all $\ell \in \N$.
Now we “add” faults inductively slice by slice, by <Ref> each time increasing the bound on $\Psi^s(\ell)$ by $12B+24\kappa$ for all slices $j\ge i$.

For larger values of $s$, $2^{2-s}\kappa D\ll n^{1/12}$, meaning that this naive bound is insufficient to show that $\Psi^s(\ell)$ does not increase much compared to the fault-free setting.
However, we can take things much further by leveraging <Ref>.

Suppose that

* $\localskew_0\le 4\kappa$,

* each node is distance-$n^{1/12}$ $k$-faulty for $k\le 2$, and

* $\localskew_{\ell}\le B\in o(n^{1/12}\kappa/\log D)$ for all $\ell\in \N$.

Then for[If $D=1$, we assume the upper bound on $s$ to be negative and the claim is vacuously true. Note that we are making an asymptotic statement in $n$ and that $D$ grows with $n$, so this case is actually of no concern here.] $s\in \N_{>0}$, $s\le \log D-\log(B/\kappa)-2\log\log D$, it holds that

\begin{equation*}
\Psi^s(\ell)\le \Psi^s\in (1+o(1))2^{2-s}\kappa D.
\end{equation*}

Note that $D\in \Theta(n^{1/2})$ and hence $\log \log D\in \omega(1)$.
Accordingly, the prerequisites of the lemma ensure that $n^{5/12}(B+\kappa)\in o(\kappa D/\log D)$ and $B+\kappa \in o(\Psi^{s-1}/\log D)$.
Hence, we may fix a suitable $\varepsilon \in o(1)$ such that

\begin{align*}
n^{5/12}(12B+24\kappa)&\le \frac{\varepsilon}{\log D}\cdot 2\kappa D\mbox{ and}\\
\left(\left\lceil\frac{\Psi^{s-1}}{n^{5/12}\kappa}\right\rceil+1\right)(12B+24\kappa)&\le \frac{\varepsilon}{4\log D}\cdot \Psi^{s-1}.
\end{align*}

We claim that if $n$ is sufficiently large such that $\varepsilon\le 1$, we have that

\begin{equation*}
\Psi^s(\ell)\le \Psi^s:=2^{2-s}\kappa D \cdot \left(1+\frac{\varepsilon s}{\log D}\right),
\end{equation*}

which we show by induction on $s\in \N_{>0}$.

For the base case of $s=1$, note that there are no more than $n^{5/12}$ slices, yielding by <Ref> that

\begin{equation*}
\Psi^1(\ell)\le 2\kappa D+n^{5/12}(12B+24\kappa)\le \left(1+\frac{\varepsilon}{\log D}\right)2\kappa D,
\end{equation*}

i.e., indeed $\Psi^1(\ell)\le \Psi^1$.

Now assume that the claim holds for $s-1\in \N_{>0}$.
Then, by <Ref> and the induction hypothesis, for layers $\ell$ in slices $i\le \lceil(\Psi^{s-1}/(n^{1/12}\kappa)\rceil$, we have that

\begin{equation*}
\Psi^s(\ell)\le 2^{2-s}\kappa D+\left\lceil\frac{\Psi^{s-1}}{n^{1/12}\kappa}\right\rceil(12B+24\kappa)<\frac{\Psi^{s-1}}{2}+\left(\left\lceil\frac{\Psi^{s-1}}{n^{1/12}\kappa}\right\rceil+1\right)(12B+24\kappa).
\end{equation*}

For a layer $\ell$ in a slice $i>\lceil(\Psi^{s-1}/(n^{1/12}\kappa)\rceil$, assume first that we add only faults in slices $j<i-\lceil(\Psi^{s-1}/(n^{1/12}\kappa)\rceil$.
Hence, we can apply <Ref>, shifting layer indices such that “layer $0$” is the first layer of slice $i-\lceil(\Psi^{s-1}/(n^{1/12}\kappa)\rceil$.
In this setting, we thus have that $\Psi^s(\ell)\le \frac{\Psi^{s-1}}{2}$.
We now apply <Ref> inductively to slices $j\in [i-\lceil(\Psi^{s-1}/(n^{1/12}\kappa)\rceil,i]$, adding in total $(\lceil\Psi^{s-1}/(n^{1/12}\kappa)\rceil+1)(12B+24\kappa)$ to the bound, i.e.,

\begin{align*}
\Psi^s(\ell)&\le \frac{\Psi^{s-1}}{2}+\left(\left\lceil\frac{\Psi^{s-1}}{n^{1/12}\kappa}\right\rceil+1\right)(12B+24\kappa)\\
&\le \left(\frac{1}{2}+\left(\frac{\varepsilon}{4\log D}\right)\right)\Psi^{s-1}\\
&=\left(\frac{1}{2}+\left(\frac{\varepsilon}{4\log D}\right)\right)2^{2-(s-1)}\kappa D \cdot \left(1+\frac{\varepsilon (s-1)}{\log D}\right)\\
&=2^{2-s}\kappa D \cdot \left(1+\frac{\varepsilon (s-1/2)}{\log D}+\frac{\varepsilon^2}{2\log^2 D}\right)\\
&\le 2^{2-s}\kappa D \cdot \left(1+\frac{\varepsilon s}{\log D}\right),
\end{align*}

where the last step assumes that $n$ is large enough so that $\varepsilon \le 1$.

Our goal is to bound $\Psi^{\lfloor \log D\rfloor}$ by $O(\kappa \log D)$, since by <Ref> this implies a bound of $O(\kappa \log D)$ on the local skew.
Thus, we will use the above lemma with $B\in O(\kappa \log D)$, which gets us within $O(\log \log D)$ levels of our “target” level $\lfloor \log D\rfloor$.
To bridge this remaining gap, we exploit that the time required for stabilizing the remaining $O(\log \log D)$ levels after a fault-induced increase of skews takes only $\log^{O(1)}D = \log^{O(1)}n \subset o(n^{1/12})$ layers, since the involved potentials are bounded by $o(\kappa n^{1/12})$.

Suppose that

* $\localskew_0\le 4\kappa$ and

* each node is distance-$n^{1/12}$ $k$-faulty for $k\le 2$.

Then $\localskew_{\ell}\in O(\kappa \log D)$.

Assume towards a contradiction that the claim is false, and let $\bar{\ell}\in \N_{>0}$ be minimal such that $\localskew_{\ell}$ is too large.
Hence, for layers $\ell<\bar{\ell}$, we may assume that $\localskew_{\ell}\le C\kappa \log D$ for a sufficiently large constant $C$.

Consider $s= \lfloor\log D-\log(B/\kappa)-2\log\log D-\log C\rfloor-5$.
By <Ref>, for all $\ell\in \N$, $\ell<\bar{\ell}$ it holds that

\begin{equation*}
\Psi^s(\ell)\in \Psi^s := (1+o(1))2^{2-s}\kappa D \subseteq \left(\frac{1}{4}+o(1)\right)\log^3 D,
\end{equation*}

which for sufficiently large $n$ is smaller than $\lfloor\log^3 D\rfloor/2$.
In fact, this bound also applies to layer $\bar{\ell}$, since the pulsing times of nodes on layer $\bar{\ell}$ depend only on the behavior of nodes on layer $\bar{\ell}-1$ and the delays of messages sent to nodes on layer $\bar{\ell}$.

Now assume that $n$ is sufficiently large.
This ensures that $\log^3 D \le n^{1/12}$, implying by the prerequisites of the lemma that each node is distance-$(\log^3 D)$ $k$-faulty for $k\le 2$.
Consider adjacent correct nodes $(v,\ell),(w,\ell)\in V_{\ell}\setminus F$ for any $\ell\in \N$, $\ell\le \bar{\ell}$, and $\{v,w\}\in E$.
We first show that distance-$(\log^3 D)$ $0$-faulty nodes satisfy that

\begin{equation}
t_{v,\ell}-t_{w,\ell}\in (4+o(1))\kappa(2+\log D)\subset O(\kappa \log D).\label{eq:skew_faulty}
\end{equation}

Since faults that are not among the ancestry of a node cannot affect its pulse time, this follows by applying <Ref> with $\underline{\ell}=\ell-\lfloor(\log^3 D)\rfloor\le \ell - 2\Psi^s$ and $s':=\lfloor\log D\rfloor$.

To extend this to distance-$(\log^3 D)$ $k$-faulty nodes for $k\in \{1,2\}$, we show by induction on $k\in \{0,1,2\}$ that such nodes have their pulse time shifted by no more than $O(\kappa \log D)$ relative to an execution in which they are distance-$(\log^3 D)$ $0$-faulty.
The base case of $k=0$ is trivial.

To perform the step from $k-1\in \{0,1\}$ to $k$, assume towards a contradiction that there is a node $(v,\ell)$ with a larger shift, on some minimal layer.
Now consider a distance-$(\log^3 D)$ $k$-faulty node $(v,\ell)\in V_{\ell}\setminus F$, $\ell\le \bar{\ell}$, whose predecessors are all correct.
There must be a distance-$(\log^3 D)$ ancestor of $(v,\ell)$ that is faulty, since otherwise $(v,\ell)$ would be distance-$(\log^3 D)$ $0$-faulty.
Let $d$ be the minimal distance in which there is a faulty ancestor of $(v,\ell)$.
Then all ancestors of $(v,\ell)$ in distance $d$ are distance-$(\log^3 D)$ $k'$-faulty for $k'<k$, as otherwise $(v,\ell)$ would be $k'$-faulty for some $k'>k$.

Consider an ancestor of $(v,\ell)$ in distance $d-1$.
If its predecessors are all correct, by the induction hypothesis and <Ref> their pulse time is shifted by $O(\kappa \log D)$ relative to an execution in which they are distance distance-$(\log^3 D)$ $0$-faulty.
If there is a faulty predecessor, we infer this from the induction hypothesis, <Ref>, and <Ref>.[Here the constants in the $O$-notation change, while <Ref> maintains the bound used in its prerequisites. Since we perform only two inductive steps, we do not need to keep track of how much the constants increase.]
If $d>1$, we now inductively apply <Ref> until having extended this bound to all ancestors of $(v,\ell)$ within distance $d-1$ and finally $(v,\ell)$ itself.
This is a contradiction to $(v,\ell)$ violating the claimed bound on the shift.

We conclude that indeed shifts are bounded by $O(\kappa \log D)$.
From this and <Ref>, it immediately follows that $\localskew_{\bar{\ell}}\in O(\kappa \log D)$.
As $C$ is sufficiently large, for sufficiently large $n$ this is a contradiction.
We conclude that $\localskew_{\ell}\in O(\kappa \log D)$ for all $\ell\in \N$, as claimed.

Putting these results together, we arrive the desired bound on the local skew.

By <Ref>, with probability $1-o(1)$ it holds that $\localskew_0\le \kappa/2$.
By <Ref>, with probability $1-o(1)$ each node is distance-$n^{1/12}$ $k$-faulty for $k\le 2$.
By a union bound, both events occur concurrently with probability $1-o(1)$.
Hence, the claim follows by applying <Ref>.

§ GENERATING SYNCHRONIZED INPUTS

In this appendix we describe a method for generating well synchronised pulses at layer $0$, at a rate of roughly one pulse per $\Lambda$ time units.
There are several ways of approaching this task, but even when aiming for a fault-tolerant solution, this is an easy problem.
The reason is that we merely need to maintain a small local skew on a line topology, with no alternative propagation paths to neighboring nodes.

Since our goal is to handle an independent probability of $p\in o(n^{-1/2})$ of node failures, in fact we can simply exploit that at most $\sqrt{n}$ nodes are required on layer $0$.
We provide a trivial scheme that is suitable for our specific setting of the base graph $G$ being a line (with replicated endpoints).
Pulse forwarding algorithm for nodes $(i,0)$, $i\in \{1,\ldots,D\}$; node $(0,0)$ is the clock source. The parameter $\Lambda$ is as described in <Ref>.

received pulse from $(i-1,0)$
$H := H_{i,0}(t)$
broadcast pulse to $(i+1,0)$ and successors on layer $1$.

For $k\in \N$, assume that the clock source at node $(0,0)$ generates its $k$-th pulse at time $(k-1)\Lambda$.
If all nodes on layer $0$ are correct, the scheme given in the above algorithm generates pulses with local skew $\localskew_0\le \kappa/2$ and $t_{i,0}^k\in [(k+i-1)\Lambda-i\kappa/2,(k+i-1)\Lambda]$. Moreover, it stabilizes after transient faults within time $D\Lambda$.

Consider first the case that there are no transient faults.
We prove the statement by induction on $i\in \N$, where the base case is covered by the assumptions on node $0$.

For the step from $i-1\in \N$ to $i$, we perform an induction over the pulse number $k\in \N_{>0}$.
The induction hypothesis is that pulses $1,\ldots,k-1$ have been generated in accordance with the claim of the lemma and the first $k-1$ loop iterations at node $i$ have been completed by the time the $k$-th pulse message from node $i-1$ arrives.
Note that we can use $k=0$ as base case for this induction, for which the claim is vacuously true.
For the step from $k-1\in \N$ to $k$, denote by $t'_{i-1,k}\in [t_{i-1,k}+d-u,t_{i-1,k}+d]$ the reception time of the pulse message from node $(0,i-1)$ at node $(0,i)$.
By the bounds on hardware clock rates, <Ref>, and the induction hypothesis of the induction on $i$, node $(0,i)$ generates its $k$-th pulse at time

\begin{align*}
t_{i,k}&\in \left[t_{i-1,k}+d-u+\frac{\Lambda-d}{\vartheta},t_{i-1,k}+\Lambda\right]\\
&\subseteq \left[t_{i-1,k}+\Lambda-\frac{\kappa}{2},t_{i-1,k}+\Lambda\right]\\
&\subseteq \left[(k+i-1)\Lambda-\frac{i\kappa}{2},(k+i-1)\Lambda\right],
\end{align*}

unless it receives another pulse message from $(i-1,0)$ before doing so.
This, however, is not the case, since we assume that message delays and hardware clock rates do not vary over time, entailing that these reception times lie $\Lambda$ time apart.[Note that a separation of $\Lambda-d$ time would suffice. The slack of $d$ means that small changes in timing between pulses are unproblematic, which we exploit in <Ref>.]

It remains to show the claimed bound on stabilization time.
To this end, observe that the only state information that nodes maintain is $H$.
On reception of a pulse message, this state is overwritten.
This will remove spurious state from the system.