$\rho\in O(d)$ and separation window $\Psi$ for $n$ nodes that tolerates
$f<n/3$ faulty nodes. That is, we want an algorithm that guarantees that there
exists a time $t$ such that all correct nodes locally generate a single
resynchronisation pulse during the interval $[t,t+\rho)$ and no new pulse
during the interval $[t+\rho,t+\rho+\Psi)$. Note that a correct
resynchronisation algorithm is also allowed to generate various kinds of
spurious resynchronisation pulses, such as pulses that are followed by a new
resynchronisation pulse too soon (i.e., before $\Psi$ time units have passed)
or pulses that are only generated by a subset of the correct nodes.

#### The algorithm idea.

In order to illustrate the idea behind our resynchronisation algorithm, let us
ignore clock drift and suppose we have two sources of pulses that generate
pulses with fixed frequencies. Whenever either source generates a pulse, then
a resynchronisation pulse is triggered as well. If the sources generate pulses
with frequencies that are coprime multiples of (a sufficiently large)
$C\in\Theta(\Psi)$, then we are guaranteed that eventually one of the sources
produces a pulse followed by at least $\Psi$ time units before a new pulse is
generated by either of the two sources. See Figure 7a for an illustration.

Figure 7:  Idea of the resynchronisation algorithm. We take two pulse sources
(top two rows) with coprime frequencies and output the logical OR of the two
sources (bottom row). Here, the dim gray lines delimit time intervals of
length $C\in\Theta(\Psi)$. The blue regions indicate intervals when a
correctly operating source should generate a pulse. In this example, the
pulses of the first source should occur approximately every $2C$ time units,
whereas the pulses of the second source should occur approximately every $3C$
time units. (a) Two correct sources that pulse with set frequencies. All
correct nodes observe the same input pulses, and hence, produce the same
output pulses. A good resynchronisation pulse is a pulse that is followed by a
green block indicating a silence of at least $\Psi$ time units. (b) One faulty
source that produces spurious pulses. As one of the sources is faulty, two
nodes may have different observations on the output of a faulty source given
in View 1 (upper figure) and View 2 (lower figure). In this example, a
spurious input pulse occurs, that is, an input pulse that is inconsistently
detected by different nodes. We devise our construction so that only pulses
that follow the frequency bounds of the source are accepted and if the source
fails to adhere to the frequency bounds, it will be ignored for some time.
Here, the nodes observing View 1 do not receive the input pulse, and thus,
they ignore any pulses from the first source for a while (gray region).
However, nodes observing View 2 receive a spurious pulse that adheres to the
frequency bounds (and do not detect any suspicious behaviour). Thus, nodes
with View 2 output a pulse, although nodes observing View 1 do not (red
region). Once the faulty source is silenced, the correctly working source has
time to produce a good resynchronisation pulse no matter what the faulty
source does. This ensures that nodes observing either view generate an output
signal within a small enough time window that is followed by at least $\Psi$
time of silence.

Put otherwise, suppose $p_{h}(v,t)\in\\{0,1\\}$ indicates whether node $v$
observe the pulse source $h\in\\{0,1\\}$ generating a pulse at time $t$. Using
the above scheme, the output variable for the resynchronisation algorithm
would be $r(v,t)=\max\\{p_{h}(v,t)\\}$. If, eventually, each source $h$
generates a pulse roughly every $C_{h}$ time units, setting $C_{0}<C_{1}$ to
be coprime integer multiples of $C\in\Theta(\Psi)$ (we allow for a constant-
factor slack to deal with clock drift, etc.), we eventually have a time when a
pulse is generated by one source, but no source will generate another pulse
for at least $\Psi$ time units.

Obviously, if we had such reliable self-stabilising pulse sources for $n$
nodes and $f<n/3$ faulty nodes, then we would have effectively solved the
pulse synchronisation problem already. However, our construction given in
Section 5 relies on having a resynchronisation algorithm. Thus, in order to
avoid this chicken-and-egg problem, we partition the set of $n$ nodes into two
and have each part run an instance of a pulse synchronisation algorithm with
resilience almost $f/2$. That is, we take two _pulse synchronisation
algorithms_ with low resilience, and use these to obtain a _resynchronisation
algorithm_ with high resilience. This allows us to recursively construct
resynchronisation algorithms starting from trivial pulse synchronisation
algorithms that do not tolerate any faulty nodes.

The final obstacle to this construction is that we cannot guarantee that
_both_ instances with smaller resilience operate correctly, as the total
number of faults exceeds the number that can be tolerated by each individual
instance. We overcome this by enlisting the help of _all_ nodes to check, for
each instance, whether its output appears to satisfy the desired frequency
bounds. If not, its output is conservatively filtered out (for a sufficiently
large period of time) by a voting mechanism. This happens only for an
incorrect output, implying that the fault threshold for the respective
instance must have been exceeded. Accordingly, the other instance is operating
correctly and, thanks to the absence of further interference from the faulty
instance, succeeds in generating a resynchronisation pulse. Figure 7b
illustrates this idea.

#### Using two pulse synchronisers.

We now overview how to use two pulse synchronisation algorithms to implement
our simple resynchronisation algorithm described above. Let

$\displaystyle n_{0}=\lfloor n/2\rfloor$ $\displaystyle\text{ and
}n_{1}=\lceil n/2\rceil$ $\displaystyle f_{0}=\lfloor(f-1)/2\rfloor$
$\displaystyle\text{ and }f_{1}=\lceil(f-1)/2\rceil.$

Observe that we have $n=n_{0}+n_{1}$ and $f=f_{0}+f_{1}+1$. We partition the
set $V$ of $n$ nodes into two sets $V_{h}$ for $h\in\\{0,1\\}$ such that
$V=V_{0}\cup V_{1}$, where $V_{0}\cap V_{1}=\emptyset$ and $|V_{h}|=n_{h}$. We
now pick two pulse synchronisation algorithms $\mathbf{A}_{0}$ and
$\mathbf{A}_{1}$ with the following properties:

  * •

$\mathbf{A}_{h}$ runs on $n_{h}$ nodes and tolerates $f_{h}$ faulty nodes,

  * •

$\mathbf{A}_{h}$ stabilises in time $T(\mathbf{A}_{h})$ and sends
$M(\mathbf{A}_{h})$ bits per time unit and channel, and

  * •

$\mathbf{A}_{h}$ has skew $\sigma\in O(d)$ and accuracy bounds
$\Phi_{h}=(\Phi^{-}_{h},\Phi^{+}_{h})$, where $\Phi^{-}_{h},\Phi^{+}_{h}\in
O(\Psi)$.

We let the nodes in set $V_{h}$ execute the pulse synchronisation algorithm
$\mathbf{A}_{h}$.

An optimistic approach would be to use each $\mathbf{A}_{h}$ as a source of
pulses by checking whether at least $n_{h}-f_{h}$ nodes in the set $V_{h}$
generated a pulse within a time window of (roughly) length $\sigma=2d$.
Unfortunately, we cannot directly use the pulse synchronisation algorithms
$\mathbf{A}_{0}$ and $\mathbf{A}_{1}$ as reliable sources of pulses. There can
be a total of $f=f_{0}+f_{1}+1<n/3$ faulty nodes, and thus, it may be that for
one $h\in\\{0,1\\}$ the set $V_{h}$ contains more than $f_{h}$ faulty nodes.
Hence, the algorithm $\mathbf{A}_{h}$ may never stabilise and can generate
spurious pulses at uncontrolled frequencies. In particular, the algorithm may
always generate pulses with frequency less than $\Psi$, preventing our simple
solution from working. However, we are guaranteed that at least one of the
algorithms stabilises.

######  Lemma 17.

If there are at most $f$ faulty nodes, then there exists $h\in\\{0,1\\}$ such
that $\mathbf{A}_{h}$ stabilises by time $T(\mathbf{A}_{h})$.

###### Proof.

Observe that $f_{0}+f_{1}+1=f$. In order to prevent both algorithms from
stabilising, we need to have at least $f_{0}+1$ faults in the set $V_{0}$ and
$f_{1}+1$ faults in the set $V_{1}$, totalling $f_{0}+f_{1}+2>f$ faults in the
system. ∎

Once the algorithm $\mathbf{A}_{h}$ for some $h\in\\{0,1\\}$ stabilises, we
have at least $n_{h}-f_{h}$ correct nodes in set $V_{h}$ locally generate
pulses with skew $\sigma$ and accuracy bounds
$\Phi_{h}=(\Phi^{-}_{h},\Phi^{+}_{h})$. However, it may be that the other
algorithm $\mathbf{A}_{1-h}$ never stabilises. Moreover, the algorithm
$\mathbf{A}_{1-h}$ may forever generate spurious pulses at arbitrary
frequencies. Here, a spurious pulse refers to any pulse that does not satisfy
the skew $\sigma$ and accuracy bounds of $\mathbf{A}_{1-h}$. For example, a
spurious pulse may be a pulse that only a subset of nodes generate, one with
too large skew, or a pulse that occurs too soon or too late.

In order to tackle this problem, we employ a series of threshold votes and
timeouts to filter out any spurious pulses generated by an unstabilised
algorithm _that violate timing constraints._ This way, we can impose some
control on the frequency at which an unstabilised algorithm may trigger
resynchronisation pulses. As long as these frequency bounds are satisfied, it
is inconsequential if a non-stabilised algorithm triggers resynchronisation
pulses at a subset of the nodes only. We want our filtering scheme to
eventually satisfy the following properties:

  * •

If $\mathbf{A}_{h}$ has stabilised, then all pulses generated by
$\mathbf{A}_{h}$ are accepted.

  * •

If $\mathbf{A}_{h}$ has not stabilised, then only pulses that respect given
frequency bounds are accepted.

More precisely, in the first case the filtered pulses respect (slightly
relaxed) accuracy bounds $\Phi_{h}$ of $\mathbf{A}_{h}$. In the second case,
we enforce that the filtered pulses must either satisfy roughly at the same
accuracy bounds $\Phi_{h}$ or they must be sufficiently far apart. That is,
the nodes will reject any pulses generated by $\mathbf{A}_{h}$ if they occur
either too soon or too late.

Once we have the filtering mechanism in place, it becomes relatively easy to
implement our conceptual idea for the resynchronisation algorithm. We apply
the filtering mechanism for both algorithms $\mathbf{A}_{0}$ and
$\mathbf{A}_{1}$ and use the filtered outputs as a source of pulses in our
algorithm, as illustrated in Figure 8. We are guaranteed that at least one of
the sources eventually produces pulses with well-defined accuracy bounds.
Furthermore, we know that also the other source must either respect the given
accuracy bounds or refrain from generating pulses for a long time. In the case
that both sources respect the accuracy bounds, we use the coprimality of
frequencies to guarantee a sufficiently large separation window for the
resynchronisation pulses. Otherwise, we exploit the fact that the unreliable
source stays silent for sufficiently long for the reliable source to generate
a pulse with a sufficiently large separation window.

Figure 8: Example of the resynchronisation construction for $8$ nodes
tolerating $2$ faults. We partition the network into two parts, each running a
pulse synchronisation algorithm $\mathbf{A}_{i}$. The output of
$\mathbf{A}_{i}$ is fed into the respective filter and any pulse that passes
the filtering is used as a resynchronisation pulse. The filtering consists of
(1) having _all_ nodes in the network participate in a threshold vote to see
if anyone thinks a pulse from $\mathbf{A}_{i}$ occurred (i.e. enough nodes
running $\mathbf{A}_{i}$ generated a pulse) and (2) keeping track of when was
the last time a pulse from $\mathbf{A}_{i}$ occurred to check that the
accuracy bounds of $\mathbf{A}_{i}$ are respected: pulses that appear too
early or too late are ignored. Moreover, if $\mathbf{A}_{i}$ generates pulses
at incorrect frequencies, the filtering mechanism blocks all pulses generated
by $\mathbf{A}_{i}$ for $\Theta(\Psi)$ time.

###  6.2 Filtering spurious pulses

Our pulse filtering scheme follows a similar idea as our recent construction
of synchronous counting algorithms [24]. However, considerable care is needed
to translate the approach from the (much simpler) synchronous round-based
model to the bounded-delay model with clock drift. We start by describing the
high-level idea of the approach before showing how to implement the filtering
scheme in the bounded-delay model considered in this work. Figure 9
illustrates how the underlying pulse synchronisation algorithms are combined
with the filtering mechanism.

Figure 9: Construction of an $f$-resilient resynchronisation algorithm on $n$
nodes from $f_{i}$-resilient pulse synchronisation algorithms on $n_{i}$
nodes, where $f=f_{0}+f_{1}+1$ and $n=n_{0}+n_{1}$. The $n$ nodes are divided
into two groups of $n_{0}$ and $n_{1}$ nodes. These groups run pulse
synchronisation algorithms $\mathbf{A}_{0}$ and $\mathbf{A}_{1}$,
respectively. At least one of these algorithms is guaranteed to stabilise
eventually. Here, $\mathbf{A}_{1}$ (gray block) has too many faulty nodes and
does not stabilise. All of the $n$ nodes together run two filtering mechanisms
$\mathbf{F}_{0}$ and $\mathbf{F}_{1}$ for the outputs of $\mathbf{A}_{0}$ and
$\mathbf{A}_{1}$, respectively. These ensure that no correct node locally
generates a resynchronisation pulse without all correct nodes registering this
event, and then apply timeout constraints to enforce the desired frequency
bounds.

For convenience, we refer to the nodes in set $V_{h}$ as _block $h$._ First,
for each block $h\in\\{0,1\\}$ every node $v\in G$ performs the following
threshold vote:

  1. 1.

If $v$ observes at least $n_{h}-f_{h}$ nodes in $V_{h}$ generating a pulse,
vote for generating a resynchronisation pulse.

  2. 2.

If at least $n-f$ nodes in $V$ voted for a pulse by block $h$ (within the time
period this should take), then $v$ accepts it.

The idea here is that if some correct node _accepts_ a pulse in Step 2, then
every correct node must have seen at least $n-2f\geq f+1$ _votes_ due to Step
1. Moreover, once a node observes at least $f+1$ votes, it can deduce that
some correct node saw at least $n_{h}-f_{h}$ nodes in block $h$ generate a
pulse. Thus, if any correct node accepts a pulse generated by block $h$, then
all correct nodes are aware that a pulse _may_ have happened.

Second, we have the nodes perform temporal filtering by keeping track of when
block $h$ last (may have) generated a pulse. To this end, each node has a
local “cooldown timer” that is reset if the node suspects that block $h$ has
not yet stabilised. If a pulse is accepted by the above voting mechanism, then
a resynchronisation pulse is triggered if the following conditions are met:

  1. 1.

the cooldown timer has expired, and

  2. 2.

not too much time has passed since the most recent pulse from $h$.

A correct node $v\in G$ resets its cooldown timer if it

  1. 1.

observes at least $f+1$ votes for a pulse from block $h$, but not enough time
has passed since $v$ last saw at least $f+1$ votes,

  2. 2.

observes at least $f+1$ votes, but not $n-f$ votes in a timely fashion, or

  3. 3.

has not observed a pulse from block $h$ for too long, that is, block $h$
should have generated a new pulse by now.

Thus, whenever a block $h\in\\{0,1\\}$ triggers a resynchronisation pulse at
node $v\in G$, then each node $u\in G$ either resets its cooldown timer or
also triggers a resynchronisation pulse. Furthermore, if $v\in G$ does not
observe a pulse from block $h$ within the right time window, it will also
reset its cooldown counter. Finally, each node refuses to trigger a
resynchronisation pulse when its cooldown timer is active. Note that if
$\mathbf{A}_{h}$ stabilises, then eventually the cooldown timer for block $h$
expires and is not reset again. This ensures that eventually at least one of
the blocks triggers resynchronisation pulses.

Figure 10: The voter state machine is the first of the two state machines used
to trigger resynchronisation pulses by block $h\in\\{0,1\\}$. Every node runs
a separate copy of the voter machine for both blocks. The voter state machine
performs a threshold vote to ensure that if at _some_ node a resynchronisation
pulse is (or might be) triggered by block $h$, then _all_ correct nodes see
this by observing at least $f+1$ vote messages within $T_{\text{att}}$ local
time. Note that nodes immediately transition from fail and go to state idle,
as there are no guards blocking these transitions. The two states are used to
signal the validator state machine given in Figure 11 to generate
resynchronisation pulses or to refrain from doing so until the cooldown timer
expires.  Figure 11: The validator state machine is the second of the two
state machines used to trigger resynchronisation pulses by block
$h\in\\{0,1\\}$. Every node runs a separate copy of the validator state
machine for both blocks. The validator checks that the go and fail transition
signals in the voter state machine given in Figure 10 satisfy the minimum time
bound and that the go transitions occur in a timely manner. Note that the
transition from state ignore to itself resets the timer $T_{\text{cool}}$.

#### Implementation in the bounded-delay model.

We implement the threshold voting and temporal filtering with two state
machines depicted in Figure 10 and Figure 11. For each block $h\in\\{0,1\\}$,
every node runs a single copy of the voter and validator state machines in
parallel. In the voter state machine given in Figure 10, there are two key
states, fail and go, which are used to indicate a local signal for the
validator state machine in Figure 11.

The key feature of the voter state machine is the voting scheme: if some node
$v\in G$ transitions from vote to go, then all nodes must transition to either
fail or go. This is guaranteed by the fact that a node only transitions to go
if it has observed at least $n-f$ nodes in the state vote within a short time
window. This in turn implies that all nodes must observe at least $n-2f>f$
nodes in vote (in a slightly larger time window). Thus, any node in state idle
must either transition directly to fail or move on to listen. If a node
transitions to state listen, then it is bound to either transition to go or
fail.

The validator state machine in turn ensures that any subsequent go transitions
of $v$ are at least $T_{\text{min},h}/\vartheta$ or
$T_{\text{cool}}/\vartheta$ time units apart. Moreover, if any fail transition
occurs at time $t$, then any subsequent go transition can occur at time
$t+T_{\text{cool}}/\vartheta$ at the earliest. The voter state machine also
handles generating a fail transition if the underlying pulse synchronisation
algorithm does not produce a pulse within time $T_{\text{max},h}$. This
essentially forces the act transitions in the validator state machine to occur
between accuracy bounds $\Lambda^{-}_{h}\approx T_{\text{min},h}/\vartheta$
and $\Lambda^{+}_{h}\approx T_{\text{max},h}$ or at least
$T_{\text{cool}}/\vartheta$ time apart. Furthermore, if the underlying pulse
synchronisation algorithm $\mathbf{A}_{h}$ stabilises, then the act
transitions roughly follow the accuracy bounds of $\mathbf{A}_{h}$.

We give a detailed analysis of the behaviour of the two state machines later
in Sections 6.5–6.6. The conditions we impose on the timeouts and other
parameters are listed in Table 4. As before, the system of inequalities listed
in Table 4 can be satisfied by choosing the timeouts carefully. This is done
in Section 6.7.

######  Lemma 18.

Let $\sigma$ and $1<\vartheta<\varphi$ be constants such that
$\vartheta^{2}\varphi<31/30$. There exists a constant
$\Psi_{0}(\vartheta,\varphi,d)$ such that for any given
$\Psi>\Psi_{0}(\vartheta,\varphi,d)$ we can satisfy the constraints in Table 4
by choosing

  1. 1.

$X\in\Theta(\Psi)$,

  2. 2.

$\Phi^{-}_{0}=X$ and $\Phi^{+}_{0}=\varphi X$,

  3. 3.

$\Phi^{-}_{1}=rX$ and $\Phi^{+}_{1}=\varphi rX$ for a constant $r>1$, and

  4. 4.

all remaining timeouts in $O(X)$.

Table 4: The conditions employed in the construction of Section 6. Here $h\in\\{0,1\\}$.  (15) | $T_{\text{min},h}=\Phi^{-}_{h}-\rho$
---|---
(16) | $T_{\text{max},h}=\vartheta(\Phi^{+}_{h}+T_{\text{vote}})$
(17) | $T_{\text{vote}}=\vartheta(\sigma+2d)$
(18) | $T_{\text{idle}}=\vartheta(\sigma+d)$
(19) | $T_{\text{att}}=\vartheta(T_{\text{vote}}+2d)$
(20) | $\rho=T_{\text{vote}}$
(21) | $T_{\text{cool}}\in\Theta(\max\\{\Phi^{+}_{h},\Psi\\})$
(22) | $T^{*}=\max_{h\in\\{0,1\\}}\\{T(\mathbf{A}_{h})+2\Phi^{+}_{h}\\}+T_{\text{cool}}+\sigma+2d+\rho$
(23) | $\Phi^{-}_{h}>\Psi+2\rho$
(24) | $\Phi^{-}_{h}\geq T_{\text{vote}}+T_{\text{idle}}+T_{\text{att}}+\sigma+2d$
(25) | $T_{\text{min},h}<T_{\text{cool}}$
(26) | $T_{\text{min},h}/\vartheta>\Psi+\rho$
(27) | $T_{\text{cool}}/\vartheta>15\beta$
(28) | $C_{0}=4,C_{1}=5$
(29) | $\Lambda^{+}_{h}=T_{\text{max},h}+T_{\text{vote}}$
(30) | $\Lambda^{-}_{h}=T_{\text{min},h}/\vartheta$
(31) | $\beta>2\Psi+4(T_{\text{vote}}+d)+\rho$
(32) |  $\beta\cdot(C_{h}\cdot j)\leq j\cdot\Lambda^{-}_{h}<j\cdot\Lambda^{+}_{h}+\rho\leq\beta\cdot(C_{h}\cdot j+1)$ for $0\leq j\leq 3$

#### The resynchronisation algorithm.

We now have described all ingredients of our resynchronisation algorithm. It
remains to define what is the output of our resynchronisation algorithm.
First, for each $h\in\\{0,1\\}$, $v\in G$ and $t\geq 0$, let us define an
indicator variable for act transitions:

$r_{h}(u,t)=\begin{cases}1&\text{if node }u\text{ transitions to
}\textsc{act}\ \text{at time }t\\\ 0&\text{otherwise.}\end{cases}$

Furthermore, for each $v\in V_{0}\cup V_{1}$, we define the output of our
resynchronisation algorithm as follows:

$r(v,t)=\max\\{r_{0}(v,t),r_{1}(v,t)\\}.$

We say that block $h$ _triggers a resynchronisation pulse_ at node $v$ if
$r_{h}(v,t)=1$. That is, node $v$ generates a resynchronisation pulse if
either block $0$ or block $1$ triggers a resynchronisation pulse at node $v$.
Our goal is to show that there exists a time $t\in O(\Phi^{+}+\Psi)$ such that
every node $v\in G$ generates a resynchronisation pulse at some time
$t^{\prime}\in[t,t+\rho)$ and neither block triggers a new resynchronisation
pulse before time $t+\Psi$ at any node $v\in G$. First, however, we observe
that the communication overhead incurred by running the voter and validator
state machines is small.

######  Lemma 19.

In order to compute the values $r(v,t)$ for each $v\in G$ and $t\geq 0$, the
nodes send at most $\max\\{M(\mathbf{A}_{h})\\}+O(1)$ bits per time unit.

###### Proof.

For both $h\in\\{0,1\\}$, we have every $v\in V_{h}$ broadcast a single bit
when $\mathbf{A}_{h}$ generates a pulse locally at node $v$. Observe that we
can assume w.l.o.g. that $\mathbf{A}_{h}$ generates a pulse only once per time
unit even during stabilisation: we can design a wrapper for $\mathbf{A}_{h}$
that filters out any pulses that occur within e.g. time $d$ of each other. As
we have $\Phi^{-}_{h}>d$ by Constraint (4), this does not interfere with the
pulsing behaviour once the algorithm has stabilised.

In addition to the pulse messages, it is straightforward to verify that the
nodes only need to communicate whether they transition to states idle, vote or
pass in the voter state machine. Due to the $T_{\text{vote}}$ and
$T_{\text{max},h}$ timeouts, a node $v\in G$ cannot transition to the same
state more than once within $d$ time, as these timeouts are larger than
$\vartheta d$ by Constraint (4) and Constraint (4). ∎

###  6.3 Proof of Theorem 3

We take a top-down approach for proving Theorem 3. We delay the detailed
analysis of the voter and state machines themselves to later sections and now
state the properties we need in order to prove Theorem 3.

First of all, as we are considering self-stabilising algorithms, it takes some
time for $\mathbf{A}_{h}$ to stabilise, and hence, also for the voter and
validator state machines to start operating correctly. We will show that this
is bound to happen by time

$T^{*}\in\max\\{T(\mathbf{A}_{h})\\}+O(\max\\{\Phi^{+}_{h}\\}+T_{\text{cool}})\subseteq\max\\{T(\mathbf{A}_{h})\\}+O(\Psi).$

The exact value of $T^{*}$ is given by Constraint (4) and will emerge later in
our proofs. We show in Section 6.4 that the resynchronisation pulses triggered
by a single correct block have skew
$\rho=T_{\text{vote}}=\vartheta(\sigma+2d)\in O(d)$ and the desired separation
window of length $\Psi$; we later argue that a faulty block cannot incessantly
interfere with the resynchronisation pulses triggered by the correct block.

######  Lemma 20 (Stabilisation of correct blocks).

Suppose $h\in\\{0,1\\}$ is a correct block. Then there exist times
$r_{h,0}\in[T^{*},T^{*}+\Phi^{+}_{h}+\rho)$ and for $i\geq 0$ the times
$r_{h,i+1}\in[r_{h,i}+\Phi^{-}-\rho,r_{h,i}+\Phi^{+}+\rho]$ satisfying the
following properties for all $v\in G$ and $i\geq 0$:

  * •

$r_{h}(v,t)=1$ for some $t\in[r_{h,i},r_{h,i}+\rho)$,

  * •

$r_{h}(v,t^{\prime})=0$ for any $t^{\prime}\in(t,r_{h,i}+\rho+\Psi)$.

We also show that if either block $h\in\\{0,1\\}$ triggers a resynchronisation
pulse at some correct node $v\in G$, then for every $u\in G$ (1) a
resynchronisation pulse is also triggered by $h$ at roughly the same time or
(2) node $u$ refrains from generating a resynchronisation pulse for a
sufficiently long time. The latter holds true because node $u$ observes that a
resynchronisation pulse _might_ have been triggered somewhere (due to the
threshold voting mechanism); $u$ thus resets its cooldown counter, that is,
transitions to state ignore in Figure 10. Formally, this is captured by the
following lemma, shown in Section 6.5.

######  Lemma 21 (Grouping lemma for validator machine).

Let $h\in\\{0,1\\}$ be any block, $t\geq T^{*}$, and $v\in G$ be such that
$r_{h}(v,t)=1$. Then there exists $t^{*}\in[t-2T_{\text{vote}}-d,t]$ such that
for all $u\in G$ we have

$r_{\text{next}}(u,t^{*})\in[t^{*},t^{*}+2(T_{\text{vote}}+d)]\cup[t^{*}+T_{\text{cool}}/\vartheta,\infty],$

where $r_{\text{next}}(u,t^{*})=\inf\\{t^{\prime}\geq
t^{*}:r_{h}(u,t^{\prime})=1\\}$.

Now with the above two lemmas in mind, we take the following proof strategy.
Fix a correct block $k\in\\{0,1\\}$ and let $r_{k,0}$ be the time given by
Lemma 20. Observe that if no node $v\in G$ has $r_{1-k}(u,t)=1$ for any
$t\in[r_{k,0},r_{k,0}+\rho+\Psi)$, then all correct nodes succeed in creating
a resynchronisation pulse with separation window $\Psi$. However, it may be
the case that the other (possibly faulty) block $1-k$ spoils the
resynchronisation pulse by also triggering a resynchronisation pulse too soon
at some correct node. That is, we may have some $v\in G$ that satisfies
$r_{1-k}(u,t)=1$, where $t\in[r_{k,0},r_{k,0}+\rho+\Psi)$. But then all nodes
observe this and the filtering mechanism now guarantees that the faulty block
either obeys the imposed frequency constraints for the following pulses or
nodes will ignore them. Either way, we can argue that a correct
resynchronisation pulse is generated by the correct block $k$ soon enough.

Accordingly, assume that the faulty block interferes, i.e., generates a
spurious resynchronisation pulse at some node $u\in G$ at time
$r_{1-k,0}\in(r_{k,0},r_{k,0}+\rho+\Psi)$. If there is no such time, the
resynchronisation pulse of the correct block would have the required
separation window of $\Psi$. Moreover, for all $v\in G$ and $i\geq 0$ we
define

$\displaystyle r_{h,0}(v)$ $\displaystyle=\inf\\{t\geq
r_{h,0}:r_{h}(t,v)=1\\}$ $\displaystyle r_{h,i+1}(v)$
$\displaystyle=\inf\\{t>r_{h,i}(v):r_{h}(t,v)=1\\}.$

Furthermore, for convenience we define the notation

$D_{h}(u)=\begin{cases}\emptyset&\text{if block }h\text{ is correct}\\\
[r_{h,0}(u)+T_{\text{cool}}/\vartheta,\infty]&\text{otherwise.}\end{cases}$

For the purpose of our analysis, we “discretise” our time into chunks of
length $\beta\in\Theta(\Psi)$. For any integers $Y>X\geq 0$, we define

$\displaystyle I_{0}(X)$
$\displaystyle=r_{k,0}-2(T_{\text{vote}}+d)+X\cdot\beta,$ $\displaystyle
I_{1}(X)$ $\displaystyle=r_{k,0}+2(T_{\text{vote}}+d)+\Psi+X\cdot\beta,$
$\displaystyle I(X,Y)$ $\displaystyle=\left[I_{0}(X),I_{1}(Y)\right).$

We abbreviate $\Lambda^{-}_{h}=T_{\text{min},h}/\vartheta$ and
$\Lambda^{+}_{h}=T_{\text{max},h}+T_{\text{vote}}$ (Constraint (4) and
Constraint (4)). The following lemma is useful for proving Theorem 3. We defer
its proof to Section 6.6.

######  Lemma 22 (Resynchronisation frequency).

For any $i\geq 0$ and $v\in G$ it holds that

$r_{h,i}(v)\in\left[r_{h,0}-2(T_{\text{vote}}+d)+i\cdot\Lambda^{-}_{h},r_{h,0}+2(T_{\text{vote}}+d)+i\cdot\Lambda^{+}_{h}\right)\cup
D_{h}(v).$

######  Corollary 8.

Let $h\in\\{0,1\\}$ and $0\leq i\leq 3$. For any $v\in G$ we have

$r_{h,i}(v)\in I(i\cdot C_{h},i\cdot C_{h}+1)\cup D_{h}(v).$

###### Proof.

Recall that $r_{1-k,0}\in(r_{k,0}-2(T_{\text{vote}}+d),r_{k,0}+\rho+\Psi)$. By
Constraint (4), for all $i\leq 3$ and $h\in\\{0,1\\}$ it holds that

$\beta\cdot C_{h}\cdot i\leq
i\cdot\Lambda^{-}_{h}<i\cdot\Lambda^{+}_{h}+\rho\leq\beta\cdot(C_{h}\cdot
i+1).$

Using Lemma 22, this inequality, and the above definitions, a straightforward
manipulation shows that $r_{h,j}(v)$ lies in the interval

$\displaystyle\quad\,\,[r_{h,0}-2(T_{\text{vote}}+d)+i\cdot\Lambda^{-}_{h},r_{h,0}+2(T_{\text{vote}}+d)+i\cdot\Lambda^{+}_{h})\cup
D_{h}(v)$
$\displaystyle\subseteq[r_{k,0}-2(T_{\text{vote}}+d)+i\cdot\Lambda^{-}_{h},r_{k,0}+2(T_{\text{vote}}+d)+\Psi+\rho+i\cdot\Lambda^{+}_{h})\cup
D_{h}(v)$
$\displaystyle\subseteq[r_{k,0}-2(T_{\text{vote}}+d)+\beta\cdot(C_{h}\cdot
i),r_{k,0}+2(T_{\text{vote}}+d)+\Psi+\beta\cdot(C_{h}\cdot i+1))\cup D_{h}(v)$
$\displaystyle=[I_{0}(i\cdot C_{h}),I_{1}(i\cdot C_{h}+1))\cup D_{h}(v)$
$\displaystyle=I(i\cdot C_{h},i\cdot C_{h}+1)\cup D_{h}(v).\qed$

With the above results, we can now show that eventually the algorithm outputs
a good resynchronisation pulse.

######  Lemma 23.

There exists a time $t\in\max\\{\mathbf{A}_{h}\\}+O(\Psi)$ such that for all
$v\in G$ there exists a time $t_{v}\in[t,t+\rho]$ satisfying

  * •

$r(v,t_{v})=1$, and

  * •

$r(v,t^{\prime})=0$ for $h\in\\{0,1\\}$ and any
$t^{\prime}\in(t_{v},t_{v}+\Psi)$.

###### Proof.

Suppose block $k\in\\{0,1\\}$ is correct. The lemma follows by proving that we
have the following properties for some $t\leq I_{1}(11)$ and each $v\in G$:

  * •

$r_{k}(v,t_{v})=1$ for some $t_{v}\in[t,t+\rho]$, and

  * •

$r_{h}(v,t^{\prime})=0$ for $h\in\\{0,1\\}$ and any
$t^{\prime}\in(t_{v},t_{v}+\Psi)$.

Recall that $r_{1-k,0}\in(r_{k,0}-2(T_{\text{vote}}+d),r_{k,0}+\rho+\Psi)$, as
otherwise the claim trivially follows for $t=r_{k,0}$. Consider any $v\in G$.
Corollary 8 and the fact that $C_{0}=4$ by Constraint (4) imply

$\displaystyle r_{0,0}(v)$ $\displaystyle\in I(0,1)\cup D_{0}(v)$
$\displaystyle r_{0,1}(v)$ $\displaystyle\in I(4,5)\cup D_{0}(v)$
$\displaystyle r_{0,2}(v)$ $\displaystyle\in I(8,9)\cup D_{0}(v)$
$\displaystyle r_{0,3}(v)$ $\displaystyle\in I(12,13)\cup D_{0}(v).$

As $T_{\text{cool}}/\vartheta\geq 15\beta$ by Constraint (4), it follows for
all $t\geq r_{0,0}$ that if $r_{0}(v,t)=1$, then

$t\in I(0,1)\cup I(4,5)\cup I(8,9)\cup[I_{0}(12),\infty].$

Similarly, as $C_{1}=5$, for all $t\geq r_{1,0}$ we get that if
$r_{1}(v,t)=1$, then

$t\in I(0,1)\cup I(5,6)\cup I(10,11)\cup[I_{0}(15),\infty].$

Let $k$ be the correct block we have fixed. Recall that $D_{k}(v)=\emptyset$.
The claim now follows from a simple case analysis:

  1. 1.

If $k=0$, then $r_{k,2}(v)\in I(8,9)$ and $r_{1-k}(v,t^{\prime})=0$ for all
$t^{\prime}\in[I_{1}(6),I_{0}(10))\supset[I_{0}(8),I_{1}(9)+\Psi+\rho)$ (by
Constraint (4)).

  2. 2.

If $k=1$, then $r_{k,2}(v)\in I(10,11)$ and $r_{1-k}(v,t^{\prime})=0$ for all
$t^{\prime}\in[I_{1}(9),I_{0}(12))\supset[I_{0}(10),I_{1}(11)+\Psi+\rho)$ (by
Constraint (4)).

Thus, in both cases $t=\min_{v\in G}\\{r_{k,2}(v)\\}$ satisfies the claim of
the lemma, provided that $t\leq I_{1}(11)\in\max\\{\mathbf{A}_{h}\\}+O(\Psi)$.
This is readily verified from the constraints given in Table 4. ∎

See 3

###### Proof.

Computation shows that for $\vartheta\leq 1.004$, we have that
$\vartheta^{2}\phi_{0}(\vartheta)<31/30$ (where
$\phi_{0}(\vartheta)=1+5(\vartheta-1)/(2+2\vartheta-3\vartheta^{2})$ is given
in Corollary 7). Thus, Lemma 18 shows that for a sufficiently small choice of
$\varphi>\varphi_{0}(\vartheta)>\vartheta$ we can pick
$\Phi^{-}_{h}\in\Theta(\Psi)$, where
$1<\max\\{\Phi^{+}_{h}/\Phi^{-}_{h}\\}\leq\varphi$, such that the conditions
given in Table 4 are satisfied. Thus, using our assumption, we can choose the
algorithms $\mathbf{A}_{h}$ with these accuracy bounds $\Phi_{h}$; note that
here we use sufficiently small $\vartheta$ and $\varphi$ that satisfy both our
initial assumption and the preconditions of Lemma 18.

In order to compute the output value $r(v,t)\in\\{0,1\\}$ for each $v\in G$
and $t\geq 0$, Lemma 19 shows that our resynchronisation algorithm only needs
to communicate $O(1)$ bits per time unit in addition to the message sent by
underlying pulse synchronisation algorithms $\mathbf{A}_{0}$ and
$\mathbf{A}_{1}$. By Lemma 23, we have that a good resynchronisation pulse
with skew $\rho\in O(d)$ happens at a time
$t\in\max\\{\mathbf{A}_{h}\\}+O(\Psi)$. ∎

###  6.4 Proof of Lemma 20

We now show that eventually a correct block $h\in\\{0,1\\}$ will start
triggering resynchronisation pulses with accuracy bounds
$\Lambda_{h}=(\Lambda^{-}_{h},\Lambda^{+}_{h})$. Our first goal is to show
that after the algorithm $\mathbf{A}_{h}$ has stabilised in a correct block
$h$, all correct nodes will start transitioning to go in a synchronised
fashion. Then we argue that eventually the transitions to the state go will be
coupled with the transitions to act.

Recall that the pulse synchronisation algorithm $\mathbf{A}_{h}$ has skew
$\sigma$ and accuracy bounds $\Phi_{h}=(\Phi^{-}_{h},\Phi^{+}_{h})$. Let
$p_{h}(v,t)\in\\{0,1\\}$ indicate whether node $v\in V_{h}\setminus F$
generates a pulse according to algorithm $\mathbf{A}_{h}$ at time $t$. If
block $h\in\\{0,1\\}$ is corrrect, then by time $T(\mathbf{A}_{h})$ the
algorithm $\mathbf{A}_{h}$ has stabilised. Moreover, then there exists a time
$T(\mathbf{A}_{h})\leq p_{h,0}\leq T(\mathbf{A}_{h})+\Phi^{+}_{h}$ such that
each $v\in V_{h}\setminus F$ satisfies $p_{h}(v,t)=1$ for some
$t\in[p_{h,0},p_{h,0}+\sigma)$. Since block $h$ and algorithm $\mathbf{A}_{h}$
are correct, there exist for each $v\in V_{h}\setminus F$ and $i\geq 0$ the
following values:

$\displaystyle p_{h,i}(v)$ $\displaystyle=\inf\\{t\geq
p_{h,i}:p_{h}(v,t)=1\\}\neq\infty,$ $\displaystyle p_{h,i+1}$
$\displaystyle\in[p_{h,i}+\Phi^{-}_{h},p_{h,i}+\Phi^{+}_{h}),$ $\displaystyle
p_{h,i+1}(v)$ $\displaystyle\in[p_{h,i+1},p_{h,i+1}+\sigma).$

That is, $\mathbf{A}_{h}$ generates a pulse at node $v\in V_{h}$ for the $i$th
time after stabilisation at time $p_{h,i}(v)$.

First, let us observe that the initial “clean” pulse makes every correct node
transition to go or fail, thereby resetting the $T_{\text{max},h}$ timeouts,
where the nodes will wait until the next pulse.

######  Lemma 24.

Suppose block $h\in\\{0,1\\}$ is correct. Each correct node $v\in G$ is in
state idle at time $p_{h,1}$ and its local $T_{\text{max},h}$ timer does not
expire during the interval $[p_{h,1},p_{h,1}+\sigma+d)$.

###### Proof.

First observe that if the timer $T_{\text{max},h}$ is reset at time $p_{h,0}$
or later, then it will not expire before time
$p_{h,0}+T_{\text{max},h}/\vartheta>p_{h,0}+\Phi^{+}_{h}+\sigma+d\geq
p_{h,1}+\sigma+d$ by Constraint (4) and Constraint (4). Because every node
receives $n_{h}-f_{h}$ pulse messages from different nodes in $V_{h}$ during
$(p_{h,0},p_{h,0}+\sigma+d)$ and $T_{\text{idle}}=\vartheta(\sigma+d)$ by
Constraint (4), every node that is in state idle at time $p_{h_{0}}$ leaves
this state during $(p_{h_{0}},p_{h_{0}}+\sigma+d)$. Recall that nodes cannot
stay in states go or fail. Because nodes leave states listen, vote, and pass
when the timeout $\langle T_{\text{vote}},\textsc{listen}\rangle$ expires, any
node not in state idle must transition to this state within $T_{\text{vote}}$
time. Accordingly, each correct node resets its $T_{\text{max},h}$ timer
during $(p_{h,0},p_{h,0}+T_{\text{vote}}+\sigma+d)$.

Next, note that during $(p_{h_{0}}+T_{\text{idle}}+\sigma+d,p_{h_{1}})$, no
correct node has any pulse messages from correct nodes in $V_{h}$ in its
respective buffer. Therefore, no correct node can transition to vote during
this time interval. This, in turn, implies that no correct node has any vote
messages from correct nodes in its respective buffer with timeout
$T_{\text{att}}$ during
$(p_{h_{0}}+T_{\text{idle}}+T_{\text{att}}+\sigma+2d,p_{h_{1}})$. Therefore,
no correct node can leave state idle during this period. Finally, any correct
nodes not in state idle at time
$p_{h_{0}}+T_{\text{idle}}+T_{\text{att}}+\sigma+2d$ must transition back to
idle by time
$p_{h_{0}}+T_{\text{vote}}+T_{\text{idle}}+T_{\text{att}}+\sigma+2d$. As
$T_{\text{vote}}+T_{\text{idle}}+T_{\text{att}}+\sigma+2d\leq\Phi^{-}$ by
Constraint (4), the claim follows. ∎

Let us define an indicator variable for go transitions:

$g_{h}(v,t)=\begin{cases}1&\text{if node }u\text{ transitions to }\textsc{go}\
\text{at time }t\\\ 0&\text{otherwise.}\end{cases}$

Similarly to above, we now also define for $v\in G$ and $i\geq 1$ the values

$\displaystyle g_{h,1}$ $\displaystyle=\inf\\{t\geq p_{1}:g_{h}(u,t)=1,u\in
G\\},$ $\displaystyle g_{h,1}(v)$ $\displaystyle=\inf\\{t\geq
g_{h,1}:g_{h}(v,t)=1\\},$ $\displaystyle g_{h,i+1}(v)$
$\displaystyle=\inf\\{t>g_{h,i}(v)\\}.$

In words, the time $g_{h,1}$ is the minimal time that some correct node
transitions to state go in the voter state machine of block $h$ at or after
the second pulse of $\mathbf{A}_{h}$ after stabilisation. The two other values
indicate the $i$th time a correct node $v\in G$ transitions to go starting
from time $g_{h,1}$.

We now show that starting from the second pulse $p_{h,1}$ of a correct block
$h$, the go signals essentially just “echo” the pulse.

######  Lemma 25.

If block $h$ is correct, then for all $v\in G$ and $i>0$ it holds that

$g_{h,i}(v)\in(p_{h,i}+\sigma+2d,p_{h,i}+\sigma+2d+\rho),$

where $\rho=\vartheta(\sigma+2d)=T_{\text{vote}}$. Moreover, node $v$ does not
transition to state fail at any time $t\geq p_{h,1}$.

###### Proof.

By Lemma 24 we have that each $v\in G$ is in state idle at time $p_{h,1}$ and
Guard G3 is not active during $[p_{h,1},p_{h,1}+\sigma+d)$. During
$(p_{h,1},p_{h,1}+\sigma+d)$, i.e., within $T_{\text{idle}}$ local time by
Constraint (4), each node receives $n_{h}-f_{h}$ pulse messages from different
nodes in $V_{h}$ and thus transitions to vote. Thus, all nodes receive $n-f$
vote messages from different nodes during $(p_{h,1},p_{h,1}+\sigma+2d)$. As
$T_{\text{vote}}/\vartheta=\sigma+2d$ by Constraint (4), each correct node
transitions to pass before $\langle T_{\text{vote}},\textsc{listen}\rangle$
expires and transitions to go at a time from
$(p_{h,1}+\sigma+2d,p_{h,1}+\sigma+2d+T_{\text{vote}})=(p_{h,1}+\sigma+2d,p_{h,1}+\sigma+2d+\rho)$.
In particular, it resets its buffers after all pulse and vote messages from
correct nodes are received. Consequently, correct nodes stay in state idle
until either the next pulse or $T_{\text{max},h}$ expires. The former occurs
at all correct nodes in $V_{h}$ no earlier than time
$p_{h,2}>p_{h,1}+T_{\text{att}}+\sigma+2d>p_{h,1}+T_{\text{vote}}+\sigma+2d$
by Constraint (4) and Constraint (4), and each pulse is received before time
$p_{h,2}+\sigma+d<p_{h,1}+\Phi_{h}^{+}+T_{\text{vote}}$ by Constraint (4) and
Constraint (4). Thus, each correct node stay in state idle until time
$p_{h,2}$ with $T_{\text{max},h}$ expiring no earlier than time
$p_{h,2}+\sigma+d$. Consequently, we can repeat the above reasoning
inductively to complete the proof. ∎

We define the following time bound for each $h\in\\{0,1\\}$:

$T^{*}_{h}=T(\mathbf{A}_{h})+T_{\text{cool}}+2\Phi^{+}_{h}+\sigma+2d+\rho.$

We now show that by time $T^{*}_{h}$ we are guaranteed that transitions to go
and act have become coupled if block $h$ is correct.

######  Lemma 26.

Suppose block $h\in\\{0,1\\}$ is correct. Then for any $v\in G$ and $t\geq
T^{*}_{h}$ it holds that

$r_{h}(v,t)=1\text{ if and only if }g_{h}(v,t)=1.$

###### Proof.

Note that node $u\in G$ can transition to state act from wait in the validator
state machine only if the voter state machine transitions to go. Consider the
time $g_{h,i}(v)$ for $i>0$. Observe that there are three states in which $v$
may be at this time: wait, hold, or ignore. We argue that in each case node
$v$ eventually is in state wait in the validator state machine when the voter
state machine transitions to state go, and thus, node $v$ transitions to act.

First of all, note that by Lemma 25 node $v$ does not transition to the state
fail at any time $t\geq p_{h,1}$. We utilise this fact in each of the three
cases below:

  1. 1.

In the first case, node $v$ transitions from wait to act at time $g_{h,i}(v)$
and hence we have $r_{h}(v,g_{h,i}(v))=1$. By applying both Lemma 25 and
Constraint (4), we get that $g_{h,i+1}(v)\geq g_{h,i}(v)+\Phi^{-}_{h}\geq
g_{h,i}(v)+T_{\text{min},h}$. Moreover, $v$ does not transition to the fail
state in the voter state machine at any time $t\geq g_{h,j}$. Hence, by
induction, node $v$ transitions from state wait to act at time $g_{h,j}(v)$
for each $j\geq i$.

  2. 2.

In the second case, $v$ transitions from hold to ignore at time $g_{h,i}(v)$.
By time $r\leq g_{h,i}(v)+T_{\text{cool}}$ node $v$ transitions to wait.
Hence, for any $j$ with $g_{h,j}(v)\geq r$, the first case applies.

  3. 3.

In the third case, $v$ resets its $T_{\text{cool}}$ timeout and remains in
state ignore until at a time $r\leq g_{h,i}(v)+T_{\text{cool}}$ its
$T_{\text{cool}}$ timer expires and $v$ transitions to wait. Again, for any
$j$ with $g_{h,j}(v)\geq r$, the first case applies.

Now consider the time
$g_{h,1}(v)\in[p_{h,1}+\sigma+2d,p_{h,1}+\sigma+2d+\rho)$ given by Lemma 25.
From the above case analysis we get that node $v$ is in state wait by time

$g_{h,1}(v)+T_{\text{cool}}<p_{h,1}+\sigma+2d+\rho+T_{\text{cool}}\leq
T^{*}_{h},$

and from then on each transition to go entails a transition to act, as
claimed. ∎

See 20

###### Proof.

First, observe that by Constraint (4) we have $T^{*}=\max\\{T^{*}_{h}\\}$. Let
$p_{h,j}\in[T^{*}-\sigma-2d,T^{*}-\sigma-2d+\Phi^{+}_{h}]$ for some $j>0$. By
Lemma 25, we have that for all $i\geq j$ and $v\in G$ it holds that

$g_{h,i}(v)\in(p_{h,i}+\sigma+2d,p_{h,i}+\sigma+2d+\rho),$

and by Lemma 26, we have $r_{h}(v,t)=1$ for all $g_{h,i}(v)=t\geq T^{*}$ and
$r_{h}(v,t)=0$ for all other $t\geq T^{*}$. We set $r_{h,i}=\min_{v\in
G}\\{g_{h,j+i}(v)\\}$. As
$p_{h,i^{\prime}+1}-p_{h,i^{\prime}}\in[\Phi^{-},\Phi^{+}]$ for all
$i^{\prime}\geq 0$, this shows all required time bounds but
$r_{h}(v,t^{\prime})=0$ for each $v\in G$, $i$, and
$t^{\prime}\in(g_{h,j+i}(v),r_{h,i}+\rho+\Psi)$. The latter follows because
$\Phi^{-}>\Psi+2\rho$ by Constraint (4). ∎

###  6.5 Proof of Lemma 21

See 21

In order to show Lemma 21, we analyse how the voting and validator state
machines given in Figure 10 and Figure 11 behave. We show that the voter
machines for a single block $h\in\\{0,1\\}$ are roughly synchronised in the
following sense: if some correct node transitions to go, then every correct
node will transition to either go or fail within a short time window.

######  Lemma 27.

Let $t\geq 2T_{\text{vote}}+d$ and $v\in G$ such that $g_{h}(v,t)=1$. Then
there exists $t^{*}\in(t-2T_{\text{vote}}-d,t]$ such that all correct nodes
transition to go or fail during the interval
$[t^{*},t^{*}+2(T_{\text{vote}}+d))$.

###### Proof.

Note that at any time $t^{\prime}\geq T_{\text{vote}}+d$, any vote message
stored at a correct node (supposedly) sent by another correct node must
actually have been sent at a time greater than $0$. Since $v\in G$ satisfies
$g_{h}(v,t)=1$, this means that it transitioned to listen at a time
$t^{\prime}\in[t-T_{\text{vote}},t]$, implying that $v$ received at least
$n-2f$ vote messages from different correct nodes during the interval
$[t^{\prime}-T_{\text{vote}},t^{\prime}]$. Hence, every correct $u\in G$ must
receive at least $n-2f>f$ vote messages from different nodes during the
interval $I=(t^{\prime}-T_{\text{vote}}-d,t^{\prime}+d)$.

Let $t^{*}<t^{\prime}$ be the minimal time a correct node transitions to vote
during the interval $I$. Consider any node $u\in G$. If $u$ does not clear its
vote memory flags (by transitioning to idle) during the interval $I$, by the
above observations $u$ has memorised at least $f+1$ vote messages in the
buffer using timeout $T_{\text{att}}$ at some time
$t^{\prime\prime}\in[t^{*},t^{\prime}+d]$ (where we use Constraint (4)) and
must transition to listen in case it is in state idle. However, any node
transitioning to listen will transition to go or fail within $T_{\text{vote}}$
time. Overall, each correct node must transition to fail or go during the
interval
$[t^{*},t^{\prime}+T_{\text{vote}}+d]\subseteq[t^{*},t^{*}+2(T_{\text{vote}}+d)]$.
∎

We now show a similar synchronisation lemma for the validator state machines
as well: if some correct node transitions to act and triggers a
resynchronisation pulse, then every correct node triggers a resynchronisation
pulse or transitions to ignore within a short time window.

######  Lemma 28.

Let $t\geq 2T_{\text{vote}}+d$ and suppose $r_{h}(u,t)=1$ for some $v\in G$.
Then there exists a time $t^{*}\in(t-2T_{\text{vote}}-d,t]$ such that all
correct nodes transition to act or ignore during the time interval
$[t^{*},t^{*}+2(T_{\text{vote}}+d))$.

###### Proof.

Suppose some node $v$ transitions to state act at time $t$. Then it must have
transitioned to state go in the voter state machine at time $t$ as well. By
Lemma 27 we get that there exists $t^{*}\in(t-2T_{\text{vote}}-d,t]$ such that
all correct nodes transition to go or fail during the interval
$[t^{*},t^{*}+2(T_{\text{vote}}+d))$. Once $u\in G$ transitions to either of
these states in the voter state machine, this causes a transition in the
validator state machine to either act or ignore, as can be seen from Figure
11. Hence, during the same interval, all correct nodes will either transition
to act or ignore. ∎

Observe that once $v\in G$ transitions to ignore at time $t$, then it cannot
transition back to act before $T_{\text{cool}}$ time has passed on its local
clock, that is, before time $t+T_{\text{cool}}/\vartheta$. Thus, Lemma 28 now
implies Lemma 21, as $T^{*}\geq 2T_{\text{vote}}+d$.

###  6.6 Proof of Lemma 22

We now aim to prove Lemma 22. Hence, let $r_{h,0}$ be as defined in Section
6.3. We have shown above that if block $h$ is correct, then the
resynchronisation pulses generated by block $h$ are coupled with the pulses
generated by the underlying pulse synchronisation algorithm $\mathbf{A}_{h}$.
We will argue that any block $h\in\\{0,1\\}$, including a faulty one, must
either respect the accuracy bounds
$\Lambda_{h}=(\Lambda^{-}_{h},\Lambda^{+}_{h})$ when triggering
resynchronisation pulses or refrain from triggering a resynchronisation pulse
for at least time $T_{\text{cool}}/\vartheta$.

######  Lemma 29.

Let $u\in G$, $h\in\\{0,1\\}$, and $i\geq 0$. Then

$r_{h,i+1}(u)\in[r_{h,i}(u)+\Lambda^{-}_{h},r_{h,i}(u)+\Lambda^{+}_{h}]\cup
D_{h}(u).$

###### Proof.

First observe that in case $r_{h,i}(u)=\infty$ for any $i\geq 0$, by
definition $r_{h,i+1}(u)=\infty\in D_{h}(u)$ and the claim holds.

Hence, let $t=r_{h,i}(u)\neq\infty$. Since $u$ transitions to act at time $t$,
it follows that $u$ also transitions to state go at time $t$, that is,
$g_{h}(u,t)=1$. Therefore, $u$ will transition to state idle in the voter
state machine and state hold in the validator state machine. Observe that $u$
cannot transition to act again before time
$t+\min\\{T_{\text{min},h},T_{\text{cool}}\\}/\vartheta$, that is, before
either local timer $T_{\text{min},h}$ or $T_{\text{cool}}$ expires. Since
$T_{\text{min},h}<T_{\text{cool}}$ by Constraint (4), we get that
$r_{h,i+1}(u)\geq t+T_{\text{min},h}/\vartheta=t+\Lambda^{-}_{h}$.

Next note that $u$ transitions to fail when (1) the local timer
$T_{\text{max},h}$ expires when in state idle or (2) $T_{\text{vote}}$, which
is reset only upon leaving idle, expires when not in state idle. Thus, by time
$t+T_{\text{max},h}+T_{\text{listen}}$, node $u$ transitioned to fail or go
again. This implies that by time $t+T_{\text{max},h}+T_{\text{vote}}$ node $u$
has transitioned to either act or ignore in the validator state machine.
Hence, we get that $r_{h,i+1}(u)\leq
t+T_{\text{max},h}+T_{\text{vote}}=r_{h,i}(u)+\Lambda^{+}_{h}$ or
$r_{h,i+1}(u)\geq r_{h,i}(u)+T_{\text{cool}}/\vartheta\geq
r_{h,0}(u)+T_{\text{cool}}/\vartheta$. Therefore, the claim follows. ∎

Lemma 22 readily follows. See 22

###### Proof.

Again, observe that if $r_{h,i}(v)=\infty$, then the claim vacuously holds for
all $j\geq i$. We prove the claim by induction on increasing $i$, so w.l.o.g.
we may assume that $r_{h,i}\neq\infty$ for all $i\geq 0$. The base case $i=0$
follows directly from the definition of $r_{h,0}$ and Lemma 21. By applying
Lemma 29 to index $i$, $v$, and $h$, and using the induction hypothesis we get
that $r_{h,i+1}(v)$ lies in the interval

$\displaystyle\quad\,\,[r_{h,i}(v)+\Lambda^{-}_{h},r_{h,i}(v)+\Lambda^{+}_{h}]\cup[r_{h,i}(v)+T_{\text{cool}}/\vartheta,\infty]$
$\displaystyle\subseteq[r_{h,0}-2(T_{\text{vote}}+d)+(i+1)\cdot\Lambda^{-}_{h},r_{h,0}+2(T_{\text{vote}}+d)+(i+1)\cdot\Lambda^{+}_{h})\cup
D_{h}(v).\qed$

###  6.7 Proof of Lemma 18

See 18

###### Proof.

We show that we can satisfy the constraints by setting

$\displaystyle\Phi^{-}_{0}$ $\displaystyle=X$ $\displaystyle\Phi^{+}_{0}$
$\displaystyle=\varphi X$ $\displaystyle\Phi^{-}_{1}$ $\displaystyle=rX$
$\displaystyle\Phi^{+}_{1}$ $\displaystyle=r\varphi X$ $\displaystyle\Psi$
$\displaystyle=aX$ $\displaystyle\beta$ $\displaystyle=bX$ $\displaystyle
T_{\text{cool}}$ $\displaystyle=cX,$

where $a=b/3$, $b=6/25\cdot\vartheta\varphi$, $c=16\vartheta b$, and
$r=31/25$, and by picking a sufficiently large $X>X_{0}(\vartheta,\varphi,d)$.
Here $X_{0}(\vartheta,\varphi,d)$ depends only on the given constants. Note
that the choice of $T_{\text{cool}}$ satisfies Constraint (4).

First, let us pick the values for the remaining timeouts and variables as
given by Constraints (4)–(4), (4), and (4)–(4); it is easy to check that these
equalities can be satisfied simultaneously. Regarding Constraint (4), observe
that $2/25\cdot\vartheta\varphi<1$ and

$\Phi^{-}_{h}\geq X>2/25\cdot\vartheta\varphi X+2\rho=aX+2\rho=\Psi+2\rho$

when
$X>2\rho/(1-2/25\cdot\vartheta\varphi)=2\vartheta(\sigma+2d)/(1-2/25\cdot\vartheta\varphi)$,
that is, $X$ is larger than a constant. Furthermore, Constraint (4) is also
satisfied by picking the constant bounding $X$ from below to be large enough.

To see that Constraint (4) holds, observe that
$T_{\text{cool}}=cX=16\vartheta^{2}\varphi X\cdot 6/25>96/25\cdot X>31/25\cdot
X=rX\geq\Phi^{-}_{h}$ for both $h\in\\{0,1\\}$. Assuming $X>2\rho\cdot
375/344=2\rho/(1-2/25\cdot 31/30)$, Constraint (4) is satisfied since

$\Phi^{-}_{h}-\rho\geq X-\rho>2/25\cdot 31/30\cdot
X+\rho>2/25\cdot\vartheta^{2}\varphi X+\rho>b/3\cdot
X+\rho=aX+\rho=\Psi+\rho.$

Constraint (4) is satisfied as
$T_{\text{cool}}/\vartheta=cX/\vartheta=16bX=16\beta>15\beta$. Having
$X>3/b\cdot(5\rho+4d)$ yields that Constraint (4) is satisfied, since then

$2\Psi+4(T_{\text{vote}}+d)+\rho=2\Psi+5\rho+4d=2b/3\cdot
X+5\rho+4d<bX=\beta.$

It remains to address Constraint (4). As Constraint (4) and Constraint (4)
hold, the first inequality of Constraint (4) is equivalent to

$\vartheta\beta C_{h}=6/25\cdot\vartheta^{2}\varphi
XC_{h}\leq\Phi^{-}_{h}-\rho.$

We have set $C_{0}=4$ in accordance with Constraint (4). For
$X>\rho/(1-24/25\cdot\vartheta^{2}\varphi)$,

$24/25\cdot\vartheta^{2}\varphi X<X-\rho=\Phi^{-}_{0}-\rho$

thus shows that the inequality holds. Concerning $h=1$, we set $C_{1}=5$.
Recalling that $\vartheta^{2}\varphi<31/30$, we may assume that
$X>\rho/(31/25-6/5\cdot\vartheta^{2}\varphi)$, yielding

$6/5\cdot\vartheta^{2}\varphi X<31/25\cdot X-\rho=rX-\rho=\Phi^{-}_{1}-\rho,$

i.e., the first inequality of Constraint (4) is satisfied for $h=1$. The
middle inequality is trivially satisfied, as
$\Lambda^{-}_{h}<\Lambda^{+}_{h}$. By the already established equalities, the
final inequality in Constraint (4) is equivalent to

$j\vartheta\Phi^{+}_{h}+((\vartheta+1)j+1)\rho\leq\beta(C_{h}\cdot j+1)$

for all $h\in\\{0,1\\}$ and $0\leq j\leq 3$.

Let $A_{j}=((\vartheta+1)j+1)\rho$ and observe that $25/3\cdot A_{3}>25/4\cdot
A_{2}>5A_{1}$. For any $X>25/3\cdot A_{3}$ and $h=0$, a simple calculation
thus shows

$\displaystyle\vartheta\varphi X+A_{1}$
$\displaystyle<30/25\cdot\vartheta\varphi X=5bX$ $\displaystyle
2\vartheta\varphi X+A_{2}$ $\displaystyle<54/25\cdot\vartheta\varphi X=9bX$
$\displaystyle 3\vartheta\varphi X+A_{3}$
$\displaystyle<78/25\cdot\vartheta\varphi X=13bX.$

Since $\Phi^{+}_{0}=\varphi X$, $\beta=bX$, and $C_{0}=4$, this covers the
case of $h=0$. Similarly, as $r=31/25=1+b/(\vartheta\varphi)$, we have

$\displaystyle\vartheta\varphi rX+A_{1}$ $\displaystyle<6bX$ $\displaystyle
2\vartheta\varphi rX+A_{2}$ $\displaystyle<11bX$ $\displaystyle
3\vartheta\varphi rX+A_{3}$ $\displaystyle<16bX,$

covering the case of $h=1$ with $C_{1}=5$. Overall, we conclude that
Constraint (4) is satisfied.

Finally, observe that in all cases we assumed that $X$ is bounded from below
by a function $X_{0}(\vartheta,\varphi,d)$ that depends only on the constants
$\vartheta$, $\varphi$, and $d$. Thus, the constraints can be satisfied by
picking $X>X_{0}(\vartheta,\varphi,d)$ which yields that we can satisfy the
constraints for any
$\Psi>\Psi_{0}(\vartheta,\varphi,d)=aX_{0}(\vartheta,\varphi,d)$. ∎

##  7 Randomised algorithms

While we have so far only considered deterministic algorithms, our framework
also extends to randomised algorithms. In particular, this allows us to obtain
faster algorithms by simply replacing the synchronous consensus algorithms we
use by randomised variants. Randomised consensus algorithms can break the
linear-time lower bound [19] for deterministic algorithms [29, 21]. This in
turn allows us to construct the first pulse synchronisation algorithms that
stabilise in sublinear time.

Typically, when considering randomised consensus, one relaxes the termination
property: it suffices that the algorithm terminates with probability $1$ and
gives probabilistic bounds on the (expected, w.h.p., etc.) round complexity.
However, our framework operates based on a deterministic termination
guarantee, where the algorithm is assumed to declare its output in $R$ rounds.
Therefore, we instead relax the _agreement_ property so that it holds with a
certain probability only. Formally, node $v$ is given an input
$x(v)\in\\{0,1\\}$, and it must output $y(v)\in\\{0,1\\}$ such that the
following properties hold:

  1. 1.

Agreement: With probability at least $p$, there exists $y\in\\{0,1\\}$ such
that $y(v)=y$ for all correct nodes $v$.

  2. 2.

Validity: If for $x\in\\{0,1\\}$ it holds that $x(v)=x$ for all correct nodes
$v$, then $y(v)=x$ for all correct nodes $v$.

  3. 3.

Termination: All correct nodes decide on $y(v)$ and terminate within $R$
rounds.

This modification is straightforward, as the following lemma shows.

######  Lemma 30.

Let $\mathbf{C}$ be a randomised synchronous consensus routine that terminates
in $R$ rounds in expectation and deterministically satisfies agreement and
validity conditions. Then there exists a randomised synchronous consensus
routine $\mathbf{C}^{\prime}$ that deterministically satisfies validity and
terminates within $2R$ rounds, and satisfies agreement with probability at
least $1/2$. All other properties, such as message size and resilience, of
$\mathbf{C}$ and $\mathbf{C}^{\prime}$ are the same.

###### Proof.

The modified algorithm operates as follows. We run the original algorithm for
(up to) $2R$ rounds. If it terminates at node $v$, then node $v$ outputs the
decision of the algorithm. Otherwise, node $v$ outputs its input value so that
$y(v)=x(v)$. This deterministically guarantees validity: if all correct nodes
have the same input, the original algorithm can only output that value.
Concerning agreement, observe that by Markov’s bound, the original algorithm
has terminated at all nodes within $2R$ rounds with probability at least
$1/2$. Accordingly, agreement holds with probability at least $1/2$. ∎

We remark that the construction from [24] that generates silent consensus
routines out of regular ones also applies to randomised algorithms (as
produced by Lemma 30), that is, we can obtain suitable randomised silent
consensus routines to be used in our framework.

Our framework makes use of consensus in the construction underlying Theorem 2
only. For stabilisation, we need a constant number of consecutive consensus
instances to succeed. Thus, a constant probability of success for each
individual consensus instance is sufficient to maintain an expected
stabilisation time of $O(R)$ for each individual level in the stabilisation
hierarchy. This is summarised in the following variant of Theorem 2.

######  Corollary 9.

Let $f\geq 0$ and $n>3f$. Suppose for a network of $n$ nodes there exist

  * •

an $f$-resilient resynchronisation algorithm $\mathbf{B}$ with skew $\rho\in
O(d)$ and separation window $\Psi\geq\Psi_{0}$ for a sufficiently large
$\Psi_{0}\in O(R)$ and

  * •

an $f$-resilient randomised synchronous consensus algorithm $\mathbf{C}$,

where $\mathbf{C}$ runs in $R=R(f)$ rounds, lets nodes send at most $M=M(f)$
bits per round and channel, and agreement holds with constant probability.
Then there exists a randomised $f$-resilient pulse synchronisation algorithm
$\mathbf{A}$ for $n$ nodes with skew $\sigma=2d$ and accuracy bounds
$\Phi^{-},\Phi^{+}\in\Theta(R)$ that stabilises in expected
$T(\mathbf{B})+O(R)$ time and has nodes send $M(\mathbf{B})+O(M)$ bits per
time unit and channel.

Note that once one of the underlying pulse synchronisation algorithms used in
the construction of Theorem 3 stabilise, the resynchronisation algorithm
itself stabilises deterministically, as it does not make use of consensus or
randomisation. Applying linearity of expectation and the same recursive
pattern as before, Theorem 1 thus generalises as follows.

######  Corollary 10.

Let $\langle\mathcal{C},R,M,N\rangle$ be a family of randomised synchronous
consensus routines, where each $\mathbf{C}\in\mathcal{C}$ satisfies agreement
with constant probability. Then, for any $f\geq 0$, $n\geq N(f)$, and $T\geq
T_{0}$ for some $T_{0}\in\Theta(R(f))$, there exists a $T$-pulser $\mathbf{A}$
with skew $2d$. The number of bits $M(\mathbf{A})$ sent per time unit and
channel and the _expected_ stabilisation time $T(\mathbf{A})$ satisfy

$T(\mathbf{A})\in O\left(d+\sum_{k=0}^{\lceil\log
f\rceil}R(2^{k})\right)\quad\text{and} \quad M(\mathbf{A})\in
O\left(1+\sum_{k=0}^{\lceil\log f\rceil}M(2^{k})\right),$

where the sums are empty when $f=0$.

However, while randomised algorithms can be more efficient, typically they
require additional restrictions on the model, e.g., that the adversary must
not be able to predict future random decisions. Naturally, such restrictions
then also apply when applying Corollary 9 and, subsequently, Corollary 10. A
typical assumption is that communication is via _private channels_. That is,
the faulty nodes’ behaviour at time $t$ is a function of all communication
from correct nodes to faulty nodes during the interval $[0,t]$, the inputs,
and the consensus algorithm only.

We can now obtain pulse synchronisation algorithms that are efficient both
with respect to stabilisation time and communication. For example, we can make
use of the randomised consensus algorithm by King and Saia [21].

######  Theorem 6 ([21] and Lemma 30).

Suppose communication is via private channels. There is a family of randomised
synchronous consensus routines that satisfy the following properties:

  * •

the algorithm satisfies agreement with constant probability,

  * •

the algorithm satisfies validity,

  * •

the algorithm terminates in $R(f)\in\operatorname{polylog}f$ rounds,

  * •

the number of bits sent by each node in each round is at most
$M(f)\in\operatorname{polylog}f$,

  * •

and $n(f)>(3+\varepsilon)f$ for a constant $\varepsilon>0$ that can be freely
chosen upfront.

We point out that the algorithm by King and Saia actually satisfies stronger
bounds on the _total_ number of bits sent by each node than what is implied by
our statement. As our framework requires nodes to broadcast a constant number
of bits per time unit and level of recursion of the construction, we obtain
the following corollary.

See 2

Note that it is trivial to boost the probability for stabilisation by
repetition, as the algorithm must stabilise in $\operatorname{polylog}f$ time
regardless of the initial system state. This was exploited in the above
corollary. However, in case of a uniform (or slowly growing) running time as
function of $f$, it is useful to apply concentration bounds to show a larger
probability of stabilisation. Concretely, the algorithm by Feldman and Micali
offers constant expected running time, regardless of $f$; this translates to
constant probability of success for an $O(1)$-round algorithm in our setting.

######  Theorem 7 ([feldman89optimal] and Lemma 30).

Suppose that communication is via private channels. There exists a family of
randomised synchronous consensus routines that satisfy the following
properties:

  * •

the algorithm satisfies agreement with constant probability,

  * •

the algorithm satisfies validity,

  * •

the algorithm terminates in $R(f)\in O(1)$ rounds,

  * •

the total number of bits broadcasted by each node is $\operatorname{poly}f$,

  * •

and $n(f)=3f+1$.

Employing this consensus routine, every $O(1)$ time units there is a constant
probability that the next level of recursion stabilises. Applying Chernoff’s
bound over the (at most) $\log n$ recursive levels of stabilisation, this
yields stabilisation in $O(\log n)$ time w.h.p.

See 3

## Acknowledgements

We are grateful to Danny Dolev for numerous discussions on the pulse
synchronisation problem and detailed comments on early drafts of this paper.
We also wish to thank Borzoo Bonakdarpour, Janne H. Korhonen, Christian
Scheideler, Jukka Suomela, and anonymous reviewers for their helpful comments.
Part of this work was done while JR was affiliated with Helsinki Institute for
Information Technology HIIT, Department of Computer Science, Aalto University
and University of Helsinki. This project has received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (grant agreement No 716562) and funding from
the European Union’s Horizon 2020 research and innovation programme under the
Marie Sk odowska-Curie (grant agreement No 754411).

## References

  * Aguilera and Toueg [1999] Marcos K. Aguilera and Sam Toueg.  Simple bivalency proof that $t$-resilient consensus requires $t+1$ rounds.  _Information Processing Letters_ , 71(3):155–158, 1999.  doi:10.1016/S0020-0190(99)00100-3.
  * Ben-Or [1983] Michael Ben-Or.  Another advantage of free choice: Completely asynchronous agreement protocols.  In _Proc. 2nd Annual ACM Symposium on Principles of Distributed Computing (PODC 1983)_ , pages 27–30, 1983.  doi:10.1145/800221.806707.
  * Ben-Or et al. [2008] Michael Ben-Or, Dolev Dolev, and Ezra N. Hoch.  Fast self-stabilizing Byzantine tolerant digital clock synchronization.  In _Proc. 27th ACM symposium on Principles of distributed computing (PODC 2008)_ , pages 385–394, 2008.  doi:10.1145/1400751.1400802.
  * Berman et al. [1989] Piotr Berman, Juan A. Garay, and Kenneth J. Perry.  Towards optimal distributed consensus.  In _Proc. 30th Annual Symposium on Foundations of Computer Science (FOCS 1989)_ , pages 410–415, 1989.  doi:10.1109/SFCS.1989.63511.
  * Berman et al. [1992] Piotr Berman, Juan A. Garay, and Kenneth J. Perry.  Bit optimal distributed consensus.  In _Computer Science: Research and Applications_ , pages 313–321, 1992.  doi:10.1007/978-1-4615-3422-8˙27.
  * Daliot et al. [2003] Ariel Daliot, Danny Dolev, and Hanna Parnas.  Self-stabilizing pulse synchronization inspired by biological pacemaker networks.  In _Proc. 6th International Symposium on Self-Stabilizing Systems (SSS 2003)_ , pages 32–48, 2003.  doi:10.1007/3-540-45032-7˙3.
  * Dijkstra [1974] Edsger W. Dijkstra.  Self-stabilizing systems in spite of distributed control.  _Communications of the ACM_ , 17(11):643–644, 1974.  doi:10.1145/361179.361202.
  * Dolev and Hoch [2007] Danny Dolev and Ezra N. Hoch.  Byzantine self-stabilizing pulse in a bounded-delay model.  In _Proc. 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2007)_ , pages 234–252, 2007.  doi:10.1007/978-3-540-76627-8˙19.
  * Dolev et al. [1986a] Danny Dolev, Joseph Y. Halpern, and H. Raymond Strong.  On the possibility and impossibility of achieving clock synchronization.  _Journal of Computer and System Sciences_ , 32(2):230–250, 1986a.  doi:10.1016/0022-0000(86)90028-0.
  * Dolev et al. [1986b] Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl.  Reaching approximate agreement in the presence of faults.  _Journal of the ACM_ , 33(3):499–516, 1986b.  doi:10.1145/5925.5931.
  * Dolev et al. [2016] Danny Dolev, Keijo Heljanko, Matti Järvisalo, Janne H. Korhonen, Christoph Lenzen, Joel Rybicki, Jukka Suomela, and Siert Wieringa.  Synchronous counting and computational algorithm design.  _Journal of Computer and System Sciences_ , 82(2):310–332, 2016.  doi:10.1016/j.jcss.2015.09.002.
  * Dolev [1982] Dolev Dolev.  The Byzantine generals strike again.  _Journal of Algorithms_ , 3(1):14–30, 1982.  doi:10.1016/0196-6774(82)90004-9.
  * Dolev and Reischuk [1985] Dolev Dolev and Rüdiger Reischuk.  Bounds on information exchange for Byzantine agreement.  _Journal of the ACM_ , 32(1):191–204, 1985.  doi:10.1145/2455.214112.
  * Dolev et al. [2014] Dolev Dolev, Matthias Függer, Christoph Lenzen, and Ulrich Schmid.  Fault-tolerant algorithms for tick-generation in asynchronous logic.  _Journal of the ACM_ , 61(5):30:1–30:74, 2014\.  doi:10.1145/2560561.
  * Dolev [2000] Shlomi Dolev.  _Self-Stabilization_.  Cambridge, MA, 2000.
  * Dolev and Welch [2004] Shlomi Dolev and Jennifer L. Welch.  Self-stabilizing clock synchronization in the presence of Byzantine faults.  _Journal of the ACM_ , 51(5):780–799, 2004.  doi:10.1145/1017460.1017463.
  * Fekete [1990] Alan D. Fekete.  Asymptotically optimal algorithms for approximate agreement.  _Distributed Computing_ , 4(1):9–29, 1990.  doi:10.1007/BF01783662.
  * [18] Pesech Feldman and Silvio Micali.  An optimal probabilistic algorithm for synchronous Byzantine agreement.  _SIAM Journal on Computing_ , 26(4):873–933.  doi:10.1137/S0097539790187084.
  * Fischer and Lynch [1982] Michael J. Fischer and Nancy A. Lynch.  A lower bound for the time to assure interactive consistency.  _Information Processing Letters_ , 14(4):183–186, 1982.  doi:10.1016/0020-0190(82)90033-3.
  * Khanchandani and Lenzen [2016] Pankaj Khanchandani and Christoph Lenzen.  Self-stabilizing Byzantine clock synchronization with optimal precision.  In _Proc. 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2016)_ , pages 213–230, 2016\.  doi:10.1007/978-3-319-49259-9˙18.
  * King and Saia [2011] Valerie King and Jared Saia.  Breaking the $O(n^{2})$ bit barrier: Scalable byzantine agreement with an adaptive adversary.  _Journal of the ACM_ , 58(4):1–24, 2011.  doi:10.1145/1989727.1989732.
  * Lamport and Melliar-Smith [1985] Leslie Lamport and P. M. Melliar-Smith.  Synchronizing clocks in the presence of faults.  _Journal of the ACM_ , 32(1):52–78, 1985.  doi:10.1145/2455.2457.
  * Lamport et al. [1982] Leslie Lamport, Robert Shostak, and Marshall Pease.  The Byzantine generals problem.  _ACM Transactions on Programming Languages and Systems_ , 4(3):382–401, 1982.  doi:10.1145/357172.357176.
  * Lenzen and Rybicki [2016] Christoph Lenzen and Joel Rybicki.  Near-optimal self-stabilising counting and firing squads.  In _Proc. 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2016)_ , pages 263–280, 2016\.  doi:10.1007/978-3-319-49259-9˙21.
  * Lenzen et al. [2013] Christoph Lenzen, Matthias Függer, Markus Hofstätter, and Ulrich Schmid.  Efficient construction of global time in SoCs despite arbitrary faults.  In _Proc. 16th Euromicro Conference Series on Digital System Design (DSD 2013)_ , pages 142–151, 2013.  doi:10.1109/DSD.2013.97.
  * Lenzen et al. [2017] Christoph Lenzen, Joel Rybicki, and Jukka Suomela.  Efficient counting with optimal resilience.  _SIAM Journal on Computing_ , 64(4):1473–1500, 2017.  doi:10.1137/16M107877X.
  * Lundelius and Lynch [1984] Jennifer Lundelius and Nancy Lynch.  An upper and lower bound for clock synchronization.  _Information and Control_ , 62(2–3):190–204, 1984.  doi:10.1016/S0019-9958(84)80033-9.
  * Pease et al. [1980] Marshall C. Pease, Robert E. Shostak, and Leslie Lamport.  Reaching agreement in the presence of faults.  _Journal of the ACM_ , 27(2):228–234, 1980.  doi:10.1145/322186.322188.
  * Rabin [1983] Michael O. Rabin.  Randomized Byzantine generals.  In _Proc. 24th Annual Symposium on Foundations of Computer Science (FOCS 1983)_ , pages 403–409, 1983.  doi:10.1109/SFCS.1983.48.
  * Raynal [2010] Michel Raynal.  _Fault-tolerant agreement in synchronous message-passing systems_.  Morgan & Claypool, 2010.
  * Srikanth and Toueg [1987] T. K. Srikanth and Sam Toueg.  Optimal clock synchronization.  _Journal of the ACM_ , 34(3):626–645, 1987.  doi:10.1145/28869.28876.
  * Welch and Lynch [1988] Jennifer L. Welch and Nancy Lynch.  A new fault tolerant algorithm for clock synchronization.  _Information and Computation_ , 77(1):1–36, 1988\.  doi:10.1016/0890-5401(88)90043-0.