* Self-stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus

Christoph Lenzen $\cdot$<EMAIL_ADDRESS>
Department of Algorithms and Complexity,
Max Planck Institute for Informatics,
Saarland Informatics Campus

Joel Rybicki $\cdot$<EMAIL_ADDRESS>
Institute of Science and Technology Austria (IST Austria)

#### Abstract.

We give fault-tolerant algorithms for establishing synchrony in distributed
systems in which each of the $n$ nodes has its own clock. Our algorithms
operate in a very strong fault model: we require self-stabilisation, i.e., the
initial state of the system may be arbitrary, and there can be up to $f<n/3$
ongoing Byzantine faults, i.e., nodes that deviate from the protocol in an
arbitrary manner. Furthermore, we assume that the local clocks of the nodes
may progress at different speeds (clock drift) and communication has bounded
delay. In this model, we study the pulse synchronisation problem, where the
task is to guarantee that eventually all correct nodes generate well-separated
local pulse events (i.e., unlabelled logical clock ticks) in a synchronised
manner.

Compared to prior work, we achieve _exponential_ improvements in stabilisation
time and the number of communicated bits, and give the first sublinear-time
algorithm for the problem:

  * •

In the deterministic setting, the state-of-the-art solutions stabilise in time
$\Theta(f)$ and have each node broadcast $\Theta(f\log f)$ bits per time unit.
We exponentially reduce the number of bits broadcasted per time unit to
$\Theta(\log f)$ while retaining the same stabilisation time.

  * •

In the randomised setting, the state-of-the-art solutions stabilise in time
$\Theta(f)$ and have each node broadcast $O(1)$ bits per time unit. We
exponentially reduce the stabilisation time to $\operatorname{polylog}f$ while
each node broadcasts $\operatorname{polylog}f$ bits per time unit.

These results are obtained by means of a recursive approach reducing the above
task of _self-stabilising_ pulse synchronisation in the _bounded-delay_ model
to _non-self-stabilising_ binary consensus in the _synchronous_ model. In
general, our approach introduces at most logarithmic overheads in terms of
stabilisation time and broadcasted bits over the underlying consensus routine.

###### Contents

  1. 1 Introduction
    1. 1.1 Pulse synchronisation
    2. 1.2 Background and related work
    3. 1.3 Contributions
    4. 1.4 Hardness of pulse synchronisation
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Reference time and clocks
    3. 2.3 The bounded-delay model
    4. 2.4 Algorithms, configurations, and executions
    5. 2.5 Pulse synchronisation algorithms
    6. 2.6 Resynchronisation algorithms
    7. 2.7 Synchronous consensus routines
  3. 3 The transformation framework
    1. 3.1 The main result
    2. 3.2 Proof of Theorem 1
    3. 3.3 The auxiliary results
    4. 3.4 Proof of Lemma 1
    5. 3.5 Organisation of the remainder of the paper
  4. 4 Byzantine-tolerant pulse synchronisation
    1. 4.1 Pulse synchronisation without self-stabilisation
    2. 4.2 Description of the algorithm
    3. 4.3 Algorithm analysis
  5. 5 Self-stabilising pulse synchronisation
    1. 5.1 Overview of the ingredients
    2. 5.2 High-level idea of the construction
    3. 5.3 Outline of the proof
    4. 5.4 Analysing the state machines
    5. 5.5 Ensuring stabilisation
    6. 5.6 Proof of Theorem 2
  6. 6 Resynchronisation algorithms
    1. 6.1 The high-level idea
    2. 6.2 Filtering spurious pulses
    3. 6.3 Proof of Theorem 3
    4. 6.4 Proof of Lemma 20
    5. 6.5 Proof of Lemma 21
    6. 6.6 Proof of Lemma 22
    7. 6.7 Proof of Lemma 18
  7. 7 Randomised algorithms
  8. Acknowledgements

##  1 Introduction

Many of the most fundamental problems in distributed computing relate to
timing and fault tolerance. Even though most distributed systems are
inherently asynchronous, it is often convenient to design such systems by
assuming some degree of synchrony provided by reliable global or distributed
clocks. For example, the vast majority of existing Very Large Scale Integrated
(VLSI) circuits operate according to the synchronous paradigm: an internal
clock signal is distributed throughout the chip neatly controlling alternation
between computation and communication steps. Of course, establishing the
synchronous abstraction is of high interest in numerous other large-scale
distributed systems, as it makes the design of algorithms considerably easier.

However, as the accuracy and availability of the clock signal is typically one
of the most basic assumptions, clocking errors affect system behavior in
unpredictable ways that are often hard – if not impossible – to tackle at
higher system layers. Therefore, _reliably_ generating and distributing a
joint clock is an essential task in distributed systems. Unfortunately, the
cost of providing fault-tolerant synchronisation and clocking is still poorly
understood.

###  1.1 Pulse synchronisation

In this work, we study the _self-stabilising Byzantine pulse synchronisation_
problem [16, 14], which requires the system to achieve synchronisation despite
severe faults. We assume a fully connected message-passing system of $n$
nodes, where

  1. 1.

an unbounded number of transient faults may occur anywhere in the network, and

  2. 2.

up to $f<n/3$ of the nodes can be faulty and exhibit _arbitrary_ ongoing
misbehaviour.

In particular, the transient faults may arbitrarily corrupt the state of the
nodes and result in loss of synchrony. Moreover, the nodes that remain faulty
may deviate from any given protocol, behave adversarially, and collude to
disrupt the other nodes by sending them _different_ misinformation even after
transient faults have ceased. Note that this also covers faults of the
communication network, as we may map faults of communication links to one of
their respective endpoints. The goal is now to (re-)establish synchronisation
once transient faults cease, despite up to $f<n/3$ Byzantine nodes. That is,
we need to consider algorithms that are simultaneously (1) self-stabilising
[7, 15] and (2) Byzantine fault-tolerant [23].

More specifically, the problem is as follows: after transient faults cease, no
matter what is the initial state of the system, the choice of up to $f<n/3$
faulty nodes, and the behaviour of the faulty nodes, we require that after a
bounded _stabilisation time_ all the _non-faulty_ nodes must generate pulses
that

  * •

occur almost simultaneously at each correctly operating node (i.e., have small
_skew_), and

  * •

satisfy specified minimum and maximum frequency bounds (_accuracy_).

While the system may have arbitrary behaviour during the initial stabilisation
phase due to the effects of transient faults, eventually the above conditions
provide synchronised unlabelled clock ticks for all non-faulty nodes:

In order to meet these requirements, it is necessary that nodes can estimate
the progress of time. To this end, we assume that nodes are equipped with
(continuous, real-valued) hardware clocks that run at speeds that may vary
arbitrarily within 1 and $\vartheta$, where $\vartheta\in O(1)$. That is, we
normalize minimum clock speed to $1$ and assume that the clocks have drift
bounded by a constant. Observe that in an asynchronous system, i.e., one in
which communication and/or computation may take unknown and unbounded time,
even perfect clocks are insufficient to ensure any relative timing guarantees
between the actions of different nodes. Therefore, we additionally assume that
the nodes can send messages to each other that are received and processed
within at most $d\in\Theta(1)$ time. The clock speeds and message delays can
behave adversarially within the respective bounds given by $\vartheta$ and
$d$.

In summary, this yields a highly adversarial model of computing, where further
restrictions would render the task infeasible:

  1. 1.

transient faults are arbitrary and may involve the entire network,

  2. 2.

ongoing faults are arbitrary, cover erroneous behavior of both the nodes and
the communication links, and the problem is not solvable if $f\geq n/3$ [9],
and

  3. 3.

the assumptions on the accuracy of local clocks and communication delay are
minimal to guarantee solvability.

###  1.2 Background and related work

If one takes any one of the elements described above out of the picture, then
this greatly simplifies the problem. Without permanent/ongoing faults, the
problem becomes trivial: it suffices to have all nodes follow a designated
leader. Without transient faults [22], straightforward solutions are given by
elegant classics [31, 32], where [32] also guarantees asymptotically optimal
skew [27]. Taking the uncertainty of unknown message delays and drifting
clocks out of the equation leads to the so-called digital clock
synchronisation problem [3, 11, 26, 24], where communication proceeds in
synchronous rounds and the task is to agree on a consistent (bounded) round
counter. While this abstraction is unrealistic as a basic system model, it
yields conceptual insights into the pulse synchronisation problem in the
bounded-delay model. Moreover, it is useful to assign numbers to pulses after
pulse synchronisation is solved, in order to get a fully-fledged shared
system-wide clock [25].

In contrast to these relaxed problem formulations, the pulse synchronisation
problem was initially considered to be very challenging – if not impossible –
to solve. In a seminal article, Dolev and Welch [16] proved otherwise, albeit
with an algorithm having an impractical exponential stabilisation time. In a
subsequent line of work, the stabilisation time was reduced to polynomial [6]
and then linear in $f$ [8]. However, the linear-time algorithm relies on
simulating multiple instances of synchronous _consensus_ algorithms [28]
concurrently, which results in a high communication complexity.

The consensus problem [28, 23] is one of the fundamental primitives in fault-
tolerant computing. Most relevant to this work is synchronous binary consensus
with (up to $f$) Byzantine faults. Here, 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: 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=x$.

  3. 3.

Termination: All correct nodes eventually decide on $y(v)$ and terminate.

In this setting, two of the above main obstacles are not present: the system
is properly initialised (no self-stabilisation required) and computation
proceeds in synchronous rounds, i.e., well-ordered compute-send-receive
cycles. This confines the task to understanding how to deal with the
interference from Byzantine nodes. Synchronous consensus is extremely well-
studied; see e.g. [30] for a survey. It is known that precisely
$\lfloor(n-1)/3\rfloor$ faults can be tolerated in a system of $n$ nodes [28],
$\Omega(nf)$ messages need to be sent in total [13], the connectivity of the
communication network must be at least $2f+1$ [12], deterministic algorithms
require $f+1$ rounds [19, 1], and randomised algorithms can solve the problem
in constant expected time [18]. In constrast, no non-trivial lower bounds on
the time or communication complexity of pulse synchronisation are known.

The linear-time pulse synchronisation algorithm in [8] relies on simulating
(up to) one synchronous consensus instance for each node simultaneously.
Accordingly, this protocol requires each node to broadcast $\Theta(f\log f)$
bits per time unit. Moreover, the use of _deterministic_ consensus is crucial,
as failure of any consensus instance to generate correct output within a
prespecified time bound may result in loss of synchrony, i.e., the algorithm
would fail _after_ apparent stabilisation. In [14], these obstacles were
overcome by avoiding the use of consensus by reducing the pulse
synchronisation problem to the easier task of generating at least one well-
separated “resynchronisation point”, which is roughly uniformly distributed
within any period of $\Theta(f)$ time. This can be achieved by trying to
initiate such a resynchronisation point at random times, in combination with
threshold voting and locally checked timing constraints to rein in the
influence of Byzantine nodes. In a way, this seems much simpler than solving
consensus, but the randomisation used to obtain a suitable resynchronisation
point strongly reminds of the power provided by shared coins [29, 2, 18, 3] –
and this is exactly what the core routine of the expected constant-round
consensus algorithm from [18] provides.

###  1.3 Contributions

Table 1: Summary of pulse synchronisation algorithms for $f\in\Theta(n)$. For each respective algorithm, the first two columns give the stabilisation time and the number of bits broadcasted by a node per time unit. The third column denotes whether algorithm is deterministic or randomised. The fourth column indicates additional details or model assumptions. All algorithms tolerate $f<n/3$ faulty nodes except for (*), where we have $f<n/(3+\varepsilon)$ for any constant $\varepsilon>0$. time | bits | type | notes | reference
---|---|---|---|---
$\operatorname{poly}f$ |  $O(\log f)$ | det. |  | [6]
$O(f)$ |  $O(f\log f)$ | det. |  | [8]
$O(f)$ |  $O(\log f)$ | det. |  | this work and [4]
$2^{O(f)}$ |  $O(1)$ | rand. | adversary cannot predict coin flips | [16]
$O(f)$ |  $O(1)$ | rand. | adversary cannot predict coin flips | [14]
$\operatorname{polylog}f$ |  $\operatorname{polylog}f$ | rand. | private channels, (*) | this work and [21]
$O(\log f)$ |  $\operatorname{poly}f$ | rand. | private channels | this work and [18]

Our main result is a framework that reduces pulse synchronisation to an
arbitrary synchronous binary consensus routine at very small overheads. In
other words, given _any_ efficient algorithm that solves consensus in the
standard synchronous model of computing _without_ self-stabilisation, we show
how to obtain an efficient algorithm that solves the _self-stabilising_ pulse
synchronisation problem in the bounded-delay model with clock drift.

While we build upon existing techniques, our approach has many key
differences. First of all, while Dolev et al. [14] also utilise the concept of
resynchronisation pulses, these are generated probabilistically. Moreover,
their approach has an inherent time bound of $\Omega(f)$ for generating such
pulses. In contrast, we devise a new recursive scheme that allows us to (1)
_deterministically_ generate resynchronisation pulses in $\Theta(f)$ time and
(2) _probabilistically_ generate resynchronisation pulses in $o(f)$ time. To
construct algorithms that generate resynchronisation pulses, we employ
resilience boosting and filtering techniques inspired by our recent line of
work on digital clock synchronisation in the _synchronous_ model [26, 24]. One
of its main motivations was to gain a better understanding of the linear
time/communication complexity barrier that research on pulse synchronisation
ran into, without being distracted by the additional timing uncertainties due
to communication delay and clock drift. The challenge here is to port these
newly developed tools from the synchronous model to the bounded-delay bounded-
drift model in a way that keeps them in working condition.

The key to efficiency is a recursive approach, where each node participates in
only $\lceil\log f\rceil$ consensus instances, one for each level of
recursion. On each level, the overhead of the reduction over a call to the
consensus routine is a constant multiplicative factor both in time and bit
complexity; concretely, this means that both complexities increase by overall
factors of $O(\log f)$. Applying suitable consensus routines yields
_exponential improvements_ in bit complexity of deterministic and time
complexity of randomised solutions, respectively:

  1. 1.

In the deterministic setting, we exponentially reduce the number of bits each
node broadcasts per time unit to $\Theta(\log f)$, while retaining $\Theta(f)$
stabilisation time. This is achieved by employing the phase king algorithm [4]
in our construction.

  2. 2.

In the randomised setting, we exponentially reduce the stabilisation time to
$\operatorname{polylog}f$, where each node broadcasts
$\operatorname{polylog}f$ bits per time unit. This is achieved using the
algorithm by King and Saia [21]. We note that this slightly reduces resilience
to $f<n/(3+\varepsilon)$ for any fixed constant $\varepsilon>0$ and requires
private communication channels.

  3. 3.

In the randomised setting, we can also obtain a stabilisation time of $O(\log
f)$, polynomial communication complexity, and optimal resilience of $f<n/3$ by
assuming private communication channels. This is achieved using the consensus
routine of Feldman and Micali [18]. This almost settles the open question by
Ben-Or et al. [3] whether pulse synchronisation can be solved in expected
constant time.

The running time bounds of the randomised algorithms (2) and (3) hold with
high probability and the additional assumptions on resilience and private
communication channels are inherited from the employed consensus routines.
Here, private communication channels mean that Byzantine nodes must make their
decision on which messages to sent in round $r$ based on knowledge of the
algorithm, inputs, and all messages faulty nodes receive up to and including
round $r$. The probability distribution is then over the independent internal
randomness of the correct nodes (which the adversary can only observe
indirectly) and any possible randomness of the adversary. Our framework does
not impose these additional assumptions: stabilisation is guaranteed for
$f<n/3$ on each recursive level of our framework as soon as the underlying
consensus routine succeeds (within prespecified time bounds) constantly many
times in a row. Our results and prior work are summarised in Table 1.

Regardless of the employed consensus routine, we achieve a skew of $2d$, where
$d$ is the maximum message delay. This is optimal in our model, but overly
pessimistic if the sum of communication and computation delay is not between
$0$ and $d$, but from $(d^{-},d^{+})$, where $d^{+}-d^{-}\ll d^{+}$. In terms
of $d^{+}$ and $d^{-}$, a skew of $\Theta(d^{+}-d^{-})$ is asymptotically
optimal [27, 32]. We remark that in [20], it is shown how to combine the
algorithms from [14] and [32] to achieve this bound without affecting the
other properties shown in [14]; we are confident that the same technique can
be applied to the algorithm proposed in this work. Finally, all our algorithms
work with any clock drift parameter $1<\vartheta\leq 1.004$, that is, the
nodes’ clocks can have up to $0.4\%$ drift. In comparison, cheap quartz
oscillators achieve $\vartheta\approx 1+10^{-5}$.

###  1.4 Hardness of pulse synchronisation

We consider our results of interest beyond the immediate improvements in
complexity of the best known algorithms for pulse synchronisation. Since our
framework may employ any consensus algorithm, it proves that pulse
synchronisation is, essentially, _as easy_ as synchronous consensus – a
problem without the requirement for self-stabilisation or any timing
uncertainty. Apart from the possibility for future improvements in consensus
algorithms carrying over, this accentuates the following fundamental open
question:

> Is pulse synchronisation _at least as hard_ as synchronous consensus?

Due to the various lower bounds and impossibility results on consensus [28,
19, 12, 13] mentioned earlier, a positive answer would immediately imply that
the presented techniques are near-optimal. However, one may speculate that
pulse synchronisation may rather have the character of (synchronous)
approximate agreement [10, 17], as _precise_ synchronisation of the pulse
events at different nodes is not required. Considering that approximate
agreement can be deterministically solved in $O(\log n)$ rounds, a negative
answer is a clear possibility as well. Given that all currently known
solutions either explicitly solve consensus, leverage techniques that are
likely to be strong enough to solve consensus, or are very slow, this would
suggest that new algorithmic techniques and insights into the problem are
necessary.

##  2 Preliminaries

In this section, we describe the model of computation, introduce notation used
in the subsequent sections, and formally define the pulse synchronisation and
resynchronisation problems.

###  2.1 Notation

We use $\operatorname{\mathbb{N}}=\\{1,2,\ldots\\}$ to denote positive
integers and
$\operatorname{\mathbb{N}}_{0}=\operatorname{\mathbb{N}}\cup\\{0\\}$. For any
$k \in\operatorname{\mathbb{N}}$, we define the short-hand
$[k]=\\{0,1,\ldots,k-1\\}$. Finally, we write $\mathbb{R}^{+}=[0,\infty)$ for
the set of non-negative real numbers. For $a,b\in\mathbb{R}^{+}$ we use the
notation $[a,b)$ and $(a,b]$ for half-open intervals and $[a,b]$ for closed
intervals. Finally, we write $\mathbb{R}^{+}\cup\\{\infty\\}=[0,\infty]$.

###  2.2 Reference time and clocks

Throughout this work, we assume a global _reference time_ that is _not_
available to the nodes in the distributed system. The reference time is only
used to reason about the behaviour of the system. A _clock_ is a strictly
increasing function $C\colon\mathbb{R}^{+}\to\mathbb{R}^{+}$ that maps the
reference time to local (perceived) time. That is, at reference time $t$ clock
$C$ indicates that the local time is $C(t)$. We say that a clock $C$ has
_drift_ at most $\vartheta-1>0$ if for any $t,t^{\prime}\in\mathbb{R}^{+}$,
where $t<t^{\prime}$, the clock satisfies

$t^{\prime}-t\leq C(t^{\prime})-C(t)\leq\vartheta(t^{\prime}-t).$

That is, if we have two such clocks, then their measurements of elapsed time
are at most factor $\vartheta$ apart.

###  2.3 The bounded-delay model

We consider a _bounded-delay message-passing model_ of distributed
computation. The system is modelled as a fully connected network of $n$ nodes,
where $V$ denotes the set of all nodes. We assume that each node has a unique
identifier from the set $[n]$. Each node $v\in V$ has local clock $C(v)$ with
maximum drift $\vartheta-1$ for a known global constant $\vartheta>1$. We
assume that the nodes cannot directly read their local clock values, but
instead they can set up local timeouts of predetermined length. That is, a
node $v$ can request to be signalled after $T$ time units have passed on the
node’s own local clock $C(v)$ since the timeout was started.

For communication, we assume sender authentication, that is, each node can
distinguish the senders of the messages it receives. In other words, every
incoming communication link is labelled with the identifier of the sender.
Unlike in fully synchronous models, where communication and computation
proceeds in lock-step at all nodes, we consider a model in which each message
has an associated delay in $(0,d)$. For simplicity, we assume that the
_maximum delay_ $d\in\Theta(1)$ is a known constant and we consider $d$ as the
basic time unit in the system. We note that even though we assume continous,
real-valued clocks, any constant offset in clock readings, e.g. due to
discrete clocks, can be modelled by increasing $d$ if needed.

We assume that the system can experience transient faults that arbitrarily
corrupt the state of the entire system; we formally define below what this
entails in our model. Once the transient faults cease, we assume that up to
$f$ of the $n$ nodes in the system may remain Byzantine faulty, that is, they
have arbitrary (mis)behaviour and do not necessarily follow the given
protocol. We use $F\subseteq V$, where $|F|\leq f$, to denote an arbitrary set
of _faulty nodes_ and $G=V\setminus F$ is the set of _correct_ nodes.

###  2.4 Algorithms, configurations, and executions

#### Algorithms.

We assume that each node executes a finite state machine whose state
transitions can depend on the current state of the node, the set of recently
received messages, and local timeouts. Formally, an algorithm is a tuple
$\mathbf{A}=(\mathcal{S},\mathcal{P},\mathcal{M},\mathcal{T},\delta,\mu)$,
where

  * •

$\mathcal{S}$ is a finite set of _states_ ,

  * •

$\mathcal{P}\subseteq\mathcal{S}$ is subset of states that trigger a _pulse
event_ ,

  * •

$\mathcal{M}$ is a finite set of messages,

  * •

$\mathcal{T}\subseteq\mathbb{R}^{+}\times 2^{\mathcal{S}}$ is a finite set of
_timers_ ,

  * •

$\delta\colon
V\times\mathcal{S}\times\mathcal{M}^{n}\times\\{0,1\\}^{h}\to\mathcal{S}$,
where $h=|\mathcal{T}|$, is the state transition function, and

  * •

$\mu\colon V\times V\times\mathcal{S}\to\mathcal{M}$ is a message function.

We now explain in detail how the system state evolves and algorithms operate.

#### Local configurations, timers, and timeouts.

The local configuration $x(v,t)$ of a node $v\in G$ at time
$t\in\mathbb{R}^{+}$ consists of

  1. 1.

its current state $s(v,t)\in\mathcal{S}$,

  2. 2.

the state of its _input channels_ $m(v,t)\in\mathcal{M}^{n}$,

  3. 3.

its local clock value $C(v,t)\in\mathbb{R}^{+}$,

  4. 4.

its _memory flags_ $M(v,m,t)\subseteq V$, and

  5. 5.

timer states $T_{k}(v,t)\in[0,T_{k}]$ for each $(T_{k},S_{k})\in\mathcal{T}$
and $k\in[h]$.

Recall that we assume that the transient faults have left the system in an
arbitrary state at time $t=0$. This entails that for each node $v\in V$ the
initial values at $t=0$ for (1)–(5) are arbitrary.

In the following, we use the shorthand $T_{k}$ for timer
$(T_{k},S_{k})\in\mathcal{T}$. We say that timer $T_{k}$ of node $v$ expires
at time $t$ if $T_{k}(v,t)$ changes to $0$ at time $t$. It is expired at time
$t$ if $T_{k}(v,t)=0$. Timers may cause state transitions of nodes when
expiring. Let $e(v,t)\in\\{0,1\\}^{h}$ indicate which timers are expired, that
is, $e_{k}(v,t)=1$ if $T_{k}$ is expired and $e(v,t)=0$ otherwise. If at time
$t$ the value of either $m(v,t)$ changes (that is, the input channels of node
$v\in G$ are updated due to a received message) or some local timer expires,
the node updates its current state to $s=\delta(v,s^{\prime},m(v,t),e(v,t))$,
where $s^{\prime}$ is the node’s state prior to this computation. If $s\neq
s^{\prime}$, we say that node $v$ transitions to state $s$ at time $t$ (and
write $s(v,t)=s$).

For convenicence, let us define the predicate $\Delta(v,s,t)=1$ if $v\in G$
transitions to $s$ at time $t$ and $\Delta(v,s,t)=0$ otherwise. When node $v$
transitions to state $s\in\mathcal{S}$, it resets all timers $(T_{k},S_{k})$
for which $s\in S_{k}$. Accordingly, at each time $t>0$, the timer state is
defined as

$T_{k}(v,t)=\max\\{0,T_{k}(v,t_{\text{reset}})-(C(v,t)-C(v,t_{\text{reset}})\\},$

where $t_{\text{reset}}$ is the most recent time node $v$ reset the timer
$T_{k}$ or time $0$, that is,

$t_{\text{reset}}=\max(\\{0\\}\cup\\{t^{\prime}\leq
t:\Delta(v,s,t^{\prime})=1,s\in S\\}).$

Note that $T_{k}(v,t_{\text{reset}})=T_{k}$ unless $t_{\text{reset}}=0$, since
with the exception of the arbitrary initial states the timer state is reset to
$T_{k}$ at time $t_{\text{reset}}$.

The bottomline is that, at all times $t\in\mathbb{R}^{+}$, the timer state
$T_{k}(v,t)\in[0,T_{k}]$ indicates how much time needs to pass on the local
clock $C(v,\cdot)$ of node $v$ until the timer expires; the rather involved
definition of how timers behave in order to achieve this property is owed to
the requirement of self-stabilisation.

#### Communication.

We say that a node $u$ sends the message $\mu(u,v,s(u,t))\in\mathcal{M}$ to
node $v$ at time $t$, if the value of $\mu(u,v,s(u,t))$ changes at time $t$.
Moreover, node $u$ is said to _broadcast_ the message $a$ at time $t$ if it
sends the message $a$ to every $v$ at time $t$.

As we operate in the bounded-delay setting, sent messages do not arrive at
their destinations immediately. To model this, let the _communication delay
function_ $d_{uv}\colon\mathbb{R}^{+}\to\mathbb{R}^{+}$ be a strictly
increasing function such that $0<d_{uv}(t)-t<d$. The input channels of node
$u\in G$ satisfy

$m_{v}(u,d_{uv}(t))=\begin{cases}\mu(v,u,s(v,t))&\text{if }v\in G\\\
b(u,v,t)&\text{otherwise,}\end{cases}$

where $b(u,v,t)\in\mathcal{M}$ is the message a faulty node $v\in F$ decides
to transmit to a correct node $u\in G$ at time $t$. We assume the adversary
can freely choose the communication delay functions $d_{uv}$. Thus, the
adversary can control what correct nodes receive from faulty nodes _and_ how
long the messages sent by correct nodes traverse (up to the maximum delay
bound $d$). Intuitively, $m_{v}(u,t)\in\mathcal{M}$ denotes most recent
message node $v$ received from node $u$ at time $t$. Since transient faults
may result in arbitrarily corrupted communication channels at time $0$, we
assume that $m_{v}(u,t)\in\mathcal{M}$ is arbitrary for $t<d_{uv}(0)$.

#### The adversary and executions.

After fixing $f,n\in\operatorname{\mathbb{N}}$ and an algorithm $\mathbf{A}$,
we assume that an adversary chooses

  1. 1.

the set $F\subseteq V$ of faulty nodes such that $|F|\leq f$,

  2. 2.

the initial local configuration $x(v,0)$ for all $v\in V$,

and for all $t\in\mathbb{R}^{+}$ and any $u,v\in V$

  1. 3.

the local clock values $C(v,t)$,

  2. 4.

the message delay functions $d_{uv}(t)$, and

  3. 5.

the messages $b(u,v,t)$ sent by faulty nodes.

Note that if the algorithm $\mathbf{A}$ is deterministic, then the adversary’s
choices for (1)–(5) together with $\mathbf{A}$ determine the execution, that
is, local configurations $x(v,t)$ for all $v\in G$ and $t\geq 0$.
Randomisation may be used in black-box calls to a consensus subroutine only.
For brevity, we postpone the discussion of randomisation to Section 7, which
covers the results obtained by utilising randomised consensus routines. We
remark that minor adjustments to the above definitions may be necessary
depending on the precise model of randomness and power of the adversary;
however, this does not affect the reasoning about our framework, which is
oblivious to how the employed consensus routine operates.

#### Logical state machines, memory flags, and sliding window buffers.

For ease of presentation, we do not describe our algorithms in the above low-
level state machine formalism, but instead use high-level state machines,
where state transitions are conditioned on timer expiration, memory flags and
sliding window memory buffers. While these are not part of the above described
formalism, they are straightforward to implement using additional local timers
and states.

Formally, we use a set $\mathcal{X}$ of _logical states_ and identify each
state $s\in\mathcal{S}$ with a logical state $\ell(s)\in\mathcal{X}$. That is,
we have a surjective projection $\ell\colon\mathcal{S}\to\mathcal{X}$ that
maps each state $s$ onto its equivalence class $\ell(s)$, i.e., the logical
state. In addition, we associate all timers with some logical state, that is,
for every $(T_{k},S_{k})\in\mathcal{T}$, we have that $S_{k}\in\mathcal{X}$ is
an equivalence class of states.

_Memory flags_ keep track of which messages a node has received. For a message
$m\in\mathcal{M}$, $H(v,m,t)\subseteq V$ is the set of the nodes for which
node $v$ has enabled the flag for message $m$ at time $t$. Similarly to
resetting the local timers, a node can clear the flags when transitioning to
prespecified states. Thus, if $v$ clears the memory flags for message $m$ at
time $t$, then we have $H(v,m,t)=\emptyset$. Typically, we use threshold-based
state transitions that only depend on _how many_ messages of a certain type
have been observed. This is given by $|H(v,m,t)|$, the number of type $m$
messages memorised by node $v$ at time $t$. Finally, in our analysis, we write
$K(v,m,t)=H(v,m,t)\cap G$ to denote the subset of correct nodes for which a
message $m$ is memorised.

We also employ _sliding window buffers_ in our algorithms. A sliding window
buffer of length $T$ stores the set of nodes from which (a certain type of) a
message has been received within time $T$ on the node’s local clock. Since the
local configuration $x(v,0)$ of a node $v$ is arbitrary at time 0, we have
that by time $T+d$ the contents of the sliding window buffer are guaranteed to
be valid: if the buffer of $v\in G$ contains a message $m$ from $u\in G$ at
time $t\geq T+d$, then $u$ must have sent an $m$ message to $v$ during the
interval $(t-T-d,t)$ of reference time. Vice versa, if $u$ sends a message $m$
at time $t$ to $v$, the buffer is guaranteed to contain the message during the
interval $(t+d,t+T/\vartheta)$ of reference time.

###  2.5 Pulse synchronisation algorithms

In the pulse synchronisation problem, the task is to have all the correct
nodes locally generate pulse events in an almost synchronised fashion, despite
arbitrary initial states and the presence of Byzantine faulty nodes. In
addition, these pulses have to be well-separated. Let $p(v,t)\in\\{0,1\\}$
indicate whether a correct node $v\in G$ generates a pulse at time $t$.
Moreover, let $p_{k}(v,t)\in[t,\infty)$ denote the time when node $v$
generates the $k$th pulse event at or after time $t$ and $p_{k}(v,t)=\infty$
if no such time exists. We say that the system has stabilised from time $t$
onwards if

  1. 1.

$p_{1}(v,t)\leq t+\Phi^{+}$ for all $v\in G$,

  2. 2.

$|p_{k}(v,t)-p_{k}(u,t)|<\sigma$ for all $u,v\in G$ and $k\geq 1$,

  3. 3.

$\Phi^{-}\leq p_{k+1}(v,t)-\min\\{p_{k}(u,t):u\in G\\}\leq\Phi^{+}$ for all
$v\in G$ and $k\geq 1$,

where $\Phi^{-}$ and $\Phi^{+}$ are the accuracy bounds controlling the
separation of the generated pulses. That is, (1) all correct nodes generate a
pulse during the interval $[t,t+\Phi^{+}]$, (2) the $k$th pulse of any two
correct nodes is less than $\sigma$ time apart, and (3) for any pair of
correct nodes their subsequent pulses are at least $\Phi^{-}-\sigma$, but at
most $\Phi^{+}$ time apart.

We say that $\mathbf{A}$ is an $f$-resilient pulse synchronisation algorithm
with _skew_ $\sigma$ and _accuracy_ $\Phi=(\Phi^{-},\Phi^{+})$ with
stabilisation time $T(\mathbf{A})$, if for any choices of the adversary such
that $|F|\leq f$, there exists a time $t\leq T(\mathbf{A})$ such that the
system stabilises from time $t$ onwards. This scenario is illustrated below:

Finally, we call a pulse synchronisation algorithm $\mathbf{A}$ a _$T$
-pulser_ if the accuracy bounds satisfy $\Phi^{-},\Phi^{+}\in\Theta(T)$ and
$\mathbf{A}$ has skew $\sigma\leq 2d$. We use $M(\mathbf{A})$ to denote the
maximum number of bits a correct node sends on a channel per unit time when
executing algorithm $\mathbf{A}$.

###  2.6 Resynchronisation algorithms

In our pulse synchronisation algorithms, we use so-called resynchronisation
pulses to facilitate stabilisation. The resychronisation pulses are provided
by resynchronisation algorithms that solve a weak variant of pulse
synchronisation: the guarantee is that eventually all correct nodes generate a
single resynchronisation pulse almost synchronously, which is followed by a
long period of silence (i.e. no new resynchronisation pulse). At all other
times, the behaviour can be arbitrary.

Formally, we say that $\mathbf{B}$ is an $f$-resilient resynchronisation
algorithm with skew $\rho$ and separation window $\Psi$ that stabilises in
time $T(\mathbf{B})$, if the following holds: for any choices of the adversary
such that $|F|\leq f$, there exists a time $t\leq T(\mathbf{B})$ such that
every correct node $v\in G$ locally generates a _resynchronisation pulse_ at
time $r(v)\in[t,t+\rho)$ and no other resynchronisation pulse before time
$t+\rho+\Psi$. We call such a resynchronisation pulse _good_. In particular,
we do not impose any restrictions on what the nodes do outside the interval
$[t,t+\rho+\Psi)$, that is, there may be _spurious_ resynchronisation pulses
outside this interval:

Again, we denote by $M(\mathbf{B})$ the maximum number of bits a correct node
sends on a channel per unit time when executing $\mathbf{B}$.

###  2.7 Synchronous consensus routines

As we rely on synchronous consensus algorithms, we briefly define the
synchronous model of computation for the sake of completeness. In the
synchronous model, the computation proceeds in discrete rounds, that is, the
nodes have access to a common global clock. In each round
$r\in\operatorname{\mathbb{N}}$ the nodes (1) send messages based on their
current state, (2) receive messages, and (3) perform local computations and
update their state for the next round.

In synchronous binary consensus, we assume that each $v\in V$ is given a
private input bit $x(v)\in\\{0,1\\}$, starts from a fixed initial state (no
self-stabilisation), and is to compute output $y(v)\in\\{0,1\\}$. However,
there are $f$ Byzantine faulty nodes. An $f$-resilient synchronous consensus
routine $\mathbf{C}$ with round complexity $T(\mathbf{C})$ guarantees:

  1. 1.

Agreement: There exists $y\in\\{0,1\\}$ such that $y(v)=y$ for all $v\in G$.

  2. 2.

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

  3. 3.

Termination: Each $v\in G$ decides on $y(v)$ and terminates by round
$T(\mathbf{C})$.

We use $M(\mathbf{C})$ to denote the maximum number of bits any $v\in G$ sends
to any other node in a single round of any execution of $\mathbf{C}$.

##  3 The transformation framework

Our main contribution is a modular framework that allows us to turn any _non-
self-stabilising_ synchronous consensus algorithm into a self-stabilising
pulse synchronisation algorithm in the bounded-delay model. In particular, the
transformation yields only a small overhead in time and communication
complexity. As our construction is relatively involved, we opt to present it
in a top-down fashion. First, we give our main theorem together with its
corollaries. Then we state the auxiliary results we need to prove the main
theorem and later discuss how these auxiliary results are established.

###  3.1 The main result

Before we formally state our main result, we make the following definition.

######  Definition 1 (Family of consensus routines).

Let $R,M,N\colon\operatorname{\mathbb{N}}_{0}\to\operatorname{\mathbb{N}}_{0}$
be functions that satisfy the following conditions:

  1. (i)

for any $f_{0},f_{1}\in\operatorname{\mathbb{N}}$, we have $N(f_{0}+f_{1})\leq
N(f_{0})+N(f_{1})$, and

  2. (ii)

both $M(f)$ and $R(f)$ are increasing.

We say that $\langle\mathcal{C},R,M,N\rangle$ is a _family of synchronous
consensus routines_ if for any $f\geq 0$ and $n\geq N(f)$, there exists a
synchronous consensus routine $\mathbf{C}\in\mathcal{C}$ such that

  * •

$\mathbf{C}$ runs on $n$ nodes and is $f$-resilient,

  * •

each correct node terminates in $T(\mathbf{C})=R(f)$ rounds,

  * •

and each correct node sends at most $M(\mathbf{C})=M(f)$ bits to any other
node per round.

Our main technical result states that given such a family of consensus
routines, we can obtain pulse synchronisation algorithms with only small
additional overhead. We emphasise that the algorithms in $\mathcal{C}$ are not
assumed to be self-stabilising.

######  Theorem 1.

Let $\langle\mathcal{C},R,M,N\rangle$ be a family of synchronous consensus
routines and $f\geq 0$, $n\geq N(f)$, and $1<\vartheta\leq 1.004$. Then there
exists $T_{0}\in\Theta(R(f))$ such that for any $T\geq T_{0}$ there is a
$T$-pulser $\mathbf{A}$ whose stabilisation time $T(\mathbf{A})$ and number of
bits $M(\mathbf{A})$ sent over each channel per time unit 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$.

In the deterministic case, the _phase king algorithm_ [5] provides a family of
synchronous consensus routines that satisfy the requirements. Since in the
phase king algorithm all nodes communicate by broadcasts (i.e., send the same
information to all other nodes) and the additional communication by our
framework satisfies this property as well, the same is true for the derived
pulser. Moreover, the phase king protocol achieves optimal resilience [28]
with $N(f)=3f+1$, constant message size $M(f)\in O(1)$, and asymptotically
optimal [19] round complexity $R(f)\in\Theta(f)$. Thus, this immediately
yields the following result.

######  Corollary 1.

For any $f\geq 0$ and $n>3f$, there is a deterministic $f$-resilient
$\Theta(f)$-pulser over $n$ nodes that stabilises in $O(f)$ time and has
correct nodes broadcast $O(\log f)$ bits per time unit.

Employing randomised consensus algorithms in our framework is straightforward.
We now summarise the main results related to randomised pulse synchronisation
algorithms; the details are discussed later in Section 7. First, by applying
our construction to a fast and communication-efficient randomised consensus
algorithm, e.g. the one by King and Saia [21], we get an efficient randomised
pulse synchronisation algorithm.

######  Corollary 2.

Suppose we have private channels. For any $f\geq 0$, constant $\varepsilon>0$,
and $n>(3+\varepsilon)f$, there is a randomised $f$-resilient
$\Theta(\operatorname{polylog}f)$-pulser over $n$ nodes that stabilises in
$\operatorname{polylog}f$ time w.h.p. and has nodes broadcast
$\operatorname{polylog}f$ bits per time unit.

We can also utilise the constant expected time protocol by Feldman and Micali
[18]. With some care, we can show that for $R(f)\in O(1)$, Chernoff’s bound
readily implies that the stabilisation time is not only in $O(\log n)$ in
expectation, but also with high probability.

######  Corollary 3.

Suppose we have private channels. For any $f\geq 0$ and $n>3f$, there is a
randomised $f$-resilient $\Theta(\log f)$-pulser over $n$ nodes that
stabilises in $O(\log f)$ time w.h.p. and has nodes broadcast
$\operatorname{poly}f$ bits per time unit.

###  3.2 Proof of Theorem 1

The proof of the main result takes an inductive approach. In the inductive
step, we assume two pulse synchronisation algorithms with small resilience. We
then use these to construct (via some hoops we discuss later) a new pulse
synchronisation algorithm with higher resilience. This step is formalised in
the following technical lemma, which we prove later.

######  Lemma 1.

Let $f,n_{0},n_{1}\in\operatorname{\mathbb{N}}$ and define the values

$n=n_{0}+n_{1},\quad f_{0}=\lfloor(f-1)/2\rfloor,\quad
f_{1}=\lceil(f-1)/2\rceil.$

Suppose there exists

  * •

for both $i\in\\{0,1\\}$ an $f_{i}$-resilient $\Theta(R)$-pulser
$\mathbf{A}_{i}$ that runs on $n_{i}$ nodes with accuracy
$\Phi_{i}=(\Phi^{-}_{i},\Phi^{+}_{i})$ satisfying
$\Phi^{+}_{i}=\varphi\Phi^{-}_{i}$ for sufficiently small constant
$\varphi>\vartheta$, and

  * •

an $f$-resilient consensus routine $\mathbf{C}$ for a network of $n$ nodes
that has running time $R$ and uses messages of at most $M$ bits.

Then there exists a $R$-pulser $\mathbf{A}$ that

  * •

runs on $n$ nodes and has resilience $f$,

  * •

stabilises in time
$T(\mathbf{A})\in\max\\{T(\mathbf{A}_{0}),T(\mathbf{A}_{1})\\}+O(R)$,

  * •

sends $M(\mathbf{A})\in\max\\{M(\mathbf{A}_{0}),M(\mathbf{A}_{1})\\}+O(M)$
bits over each channel per time unit,

  * •

has skew $2d$, and

  * •

has accuracy bounds $\Phi^{-}$ and $\Phi^{+}$ satisfying that
$\Phi^{+}=\varphi\Phi^{-}$.

We observe that Theorem 1 is a relatively straightforward consequence of the
above lemma.

See 1

###### Proof.

We prove the claim for
$f\in\operatorname{\mathbb{N}}=\bigcup_{k\in\operatorname{\mathbb{N}}_{0}}[2^{k},2^{k+1})$
using induction on $k$. As base case, we use $f=0$. This is trivial for all
$n$: we pick a single node as a leader that generates a pulse when $\Phi$
units have passed on its local clock. Whenever the leader node pulses, all
other nodes observe this within $d$ time units. We have all other nodes
generate a pulse whenever they observe the leader node generating a pulse.
Thus, for $f=0$ we have algorithms that stabilise in $O(d)$ time and uses
messages of $O(1)$ bits.

For the inductive step, consider $f\in[2^{k},2^{k+1})$ and suppose that, for
all $f^{\prime}<2^{k}$ and $n^{\prime}\geq N(f^{\prime})$, there exists an
$f^{\prime}$-resilient $R(f^{\prime})$-pulser algorithm $\mathbf{B}$ on
$n^{\prime}$ nodes with

$T(\mathbf{B})\leq\alpha\left(d+\sum_{k^{\prime}=0}^{\lceil\log
f^{\prime}\rceil}R(2^{k^{\prime}})\right)\text{ and
}M(\mathbf{B})\leq\beta\left(1+\sum_{k^{\prime}=0}^{\lceil\log
f^{\prime}\rceil}M(2^{k^{\prime}})\right),$

where $\alpha$ and $\beta$ are sufficiently large constants. In particular, we
can now apply Lemma 1 with $f_{0},f_{1}\leq f/2<2^{k}$ and any $n\geq N(f)$,
as $N(f)\geq N(f_{0})+N(f_{1})$ guarantees that we may choose some $n_{0}\geq
N(f_{0})$ and $n_{1}\geq N(f_{1})$ such that $n=n_{0}+n_{1}$. This yields an
$f$-resilient $R(f)$-pulser $\mathbf{A}$ over $n$ nodes, with stabilisation
time

$\displaystyle T(\mathbf{A})$
$\displaystyle\leq\max\\{T(\mathbf{A}_{0}),T(\mathbf{A}_{1})\\}+\gamma R(f)$
$\displaystyle\leq\alpha\left(d+\sum_{k=0}^{\lceil\log
f/2\rceil}R(2^{k})\right)+\gamma R(2^{\lceil\log f\rceil}),$
$\displaystyle\leq\alpha\left(d+\sum_{k=0}^{\lceil\log
f\rceil}R(2^{k})\right),$

where $\gamma\leq\alpha$ is a constant; the second step uses that $R(f)$ is
increasing. Similarly, the bound on the number of sent bits follows from Lemma
1 and the induction assumption:

$\displaystyle M(\mathbf{A})$
$\displaystyle\leq\max\\{M(\mathbf{A}_{0}),M(\mathbf{A}_{1})\\}+\gamma^{\prime}M(f)$
$\displaystyle\leq\beta\left(1+\sum_{k=0}^{\lceil\log
f/2\rceil}M(2^{k})\right)+\gamma^{\prime}M(2^{\lceil\log f\rceil}),$
$\displaystyle\leq\beta\left(1+\sum_{k=0}^{\lceil\log
f\rceil}M(2^{k})\right),$

where $\gamma^{\prime}\leq\beta$ is a constant and we used that $M(f)$ is
increasing. ∎

###  3.3 The auxiliary results

In order to show Lemma 1, we use two main ingredients: (1) a pulse
synchronisation algorithm whose stabilisation mechanism is triggered by a
resynchronisation pulse and (2) a resynchronisation algorithm providing the
latter. These ingredients are formalised in the following two theorems which
are proven in Sections 5 and 6, respectively.

######  Theorem 2.

Let $f\geq 0$, $n>3f$, and $(2+\sqrt{32})/7>\vartheta>1$. Suppose for a
network of $n$ nodes there exist

  * •

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

  * •

an $f$-resilient resynchronisation algorithm $\mathbf{B}$ with skew $\rho\in
O(d)$ and sufficiently large separation window $\Psi\in O(R)$ that tolerates
clock drift of $\vartheta$,

where $\mathbf{C}$ runs in $R=R(f)$ rounds and lets nodes send at most
$M=M(f)$ bits per round and channel. Then there exists
$\varphi_{0}(\vartheta)\in 1+O(\vartheta-1)$ such that for any constant
$\varphi>\varphi_{0}(\vartheta)$ and sufficiently large $T\in O(R)$, there
exists an $f$-resilient pulse synchronisation algorithm $\mathbf{A}$ for $n$
nodes that

  * •

has skew $\sigma=2d$,

  * •

satisfies the accuracy bounds $\Phi^{-}=T$ and $\Phi^{+}=T\varphi$,

  * •

stabilises in $T(\mathbf{B})+O(R)$ time, and

  * •

has nodes sent $M(\mathbf{B})+O(M)$ bits per time unit and channel.

To apply the above theorem, we require suitable consensus and
resynchronisation algorithms. We rely on consensus algorithms from prior work
and construct efficient resynchronisation algorithms ourselves. The idea is to
combine pulse synchronisation algorithms that have _low resilience_ to obtain
resynchronisation algorithms with _high resilience_.

######  Theorem 3.

Let $f,n_{0},n_{1}\in\operatorname{\mathbb{N}}$ and $1<\vartheta\leq 1.004$.
Define

$n=n_{0}+n_{1},\quad f_{0}=\lfloor(f-1)/2\rfloor,\quad
f_{1}=\lceil(f-1)/2\rceil.$

Suppose that for some given $\Psi\in\Omega(1)$, sufficiently small constant
$\varphi>\varphi_{0}(\vartheta)$, and $T_{0}\in\Theta(\Psi)$, it holds that
for $i\in\\{0,1\\}$ and $T_{0}\leq T\in O(\Psi)$ there exists a pulse
synchronisation algorithm $\mathbf{A}_{i}$ that

  * •

runs on $n_{i}$ nodes and has resilience $f_{i}$,

  * •

has skew $\sigma=2d$, and

  * •

has accuracy bounds $\Phi_{i}^{-}=T$ and $\Phi_{i}^{+}=T\varphi$.

Then there exists a resynchronisation algorithm $\mathbf{B}$ that

  * •

runs on $n$ nodes and has resilience $f$,

  * •

has skew $\rho\in O(d)$ and separation window of length $\Psi$,

  * •

generates a resynchronisation pulse by time
$T(\mathbf{B})\in\max\\{T(\mathbf{A}_{0}),T(\mathbf{A}_{1})\\}+O(\Psi)$, and

  * •

has nodes send
$M(\mathbf{B})\in\max\\{M(\mathbf{A}_{0}),M(\mathbf{A}_{1})\\}+O(1)$ bits per
time unit and channel.

Given a suitable consensus algorithm, one can readily combine Theorems 2 and 3
to obtain Lemma 1. Therefore, we can reduce the problem of constructing an
$f$-resilient pulse synchronisation algorithm to finding algorithms that
tolerate up to $\lfloor f/2\rfloor$ faults and recurse; Figure 1 illustrates
how these two types of algorithms are interleaved.

Figure 1: Recursively building a $2$-resilient pulse synchronisation algorithm
$\mathbf{A}(7,2)$ over $7$ nodes. The construction utilises low resilience
pulse synchronisation algorithms to build high resilience resynchronisation
algorithms which can then be used to obtain highly resilient pulse
synchronisation algorithms. Here, the base case consists of trivial
$0$-resilient pulse synchronisation algorithms $\mathbf{A}(2,0)$ and
$\mathbf{A}(3,0)$ over 2 and 3 nodes, respectively. Two copies of
$\mathbf{A}(2,0)$ are used to build a 1-resilient resynchronisation algorithm
$\mathbf{B}(4,1)$ over 4 nodes using Theorem 3. The resynchronisation
algorithm $\mathbf{B}(4,1)$ is used to obtain a pulse synchronisation
algorithm $\mathbf{A}(4,1)$ via Theorem 2. Now, the 1-resilient pulse
synchronisation algorithm $\mathbf{A}(4,1)$ over 4 nodes is used together with
the trivial 0-resilient algorithm $\mathbf{A}(3,0)$ to obtain a 2-resilient
resynchronisation algorithm $\mathbf{B}(7,2)$ for 7 nodes and the resulting
pulse synchronisation algorithm $\mathbf{A}(7,2)$. White nodes represent
correct nodes and black nodes represent faulty nodes. The gray blocks contain
too many faulty nodes for the respective algorithms to correctly operate, and
hence, they may have arbitrary output.

###  3.4 Proof of Lemma 1

###### Proof.

From Theorem 3, we get that for any sufficiently large $\Psi\in\Theta(R)$,
there exists a resynchronisation algorithm $\mathbf{B}$ with skew $\rho\in
O(d)$ and separation window of length $\Psi$ that

  * •

runs on $n$ nodes and has resilience $f$,

  * •

stabilises in time
$\max\\{T(\mathbf{A}_{0}),T(\mathbf{A}_{1})\\}+O(\Psi)=\max\\{T(\mathbf{A}_{0}),T(\mathbf{A}_{1})\\}+O(R)$,
and

  * •

has nodes send $\max\\{M(\mathbf{A}_{0}),M(\mathbf{A}_{1})\\}+O(1)$ bits per
time unit and channel.

We feed $\mathbf{B}$ and $\mathbf{C}$ into Theorem 2, yielding a pulse
synchronisation algorithm $\mathbf{A}$ with the claimed properties, as the
application of Theorem 2 increases the stabilisation time by an additional
$O(R)$ time units and adds $O(M)$ bits per time unit and channel. ∎

###  3.5 Organisation of the remainder of the paper

We dedicate the remaining sections to fill in the details we have omitted
above. Namely,

  * •

Section 4 describes a Byzantine-tolerant pulse synchronisation algorithm that
is _not_ self-stabilising. We utilise the algorithm in Section 5, but the
section also serves to provide a gentle introduction to the notation and style
of proofs we use in the following sections.

  * •

Section 5 gives the proof of Theorem 2.

  * •

Section 6 gives the proof of Theorem 3.

  * •

Section 7 extends our framework to operate with randomised consensus
algorithms. This establishes Corollaries 2 and 3.

##  4 Byzantine-tolerant pulse synchronisation

In this section, we describe a _non-self-stabilising_ pulse synchronisation
algorithm, which we utilise later in our construction of the self-stabilising
algorithm. The algorithm given here is a variant of the Byzantine fault-
tolerant clock synchronisation algorithm by Srikanth and Toeug [31] that
avoids transmitting clock values in favor of unlabelled pulses.

###  4.1 Pulse synchronisation without self-stabilisation

As said, we do not require self-stabilisation for now. However, instead of
assuming a synchronous start, we devise an algorithm where all correct nodes
synchronously start generating pulses once all correct nodes have received an
_initialisation signal_ within a short time window. In particular, we allow
that _before_ receiving an initialisation signal, a correct node can have
arbitrary behaviour, but _after_ a correct node has received this signal, it
waits until all correct nodes have received the signal and start to
synchronously generate well-separated pulses:

In the following, suppose that all correct nodes receive an initialisation
signal during the time window $[0,\tau)$. In other words, nodes can start
executing the algorithm at different times, but they all do so by some bounded
(possibly non-constant) time $\tau$. When a node receives the initialisation
signal, it immediately transitions to a special reset state, whose purpose is
to consistently initialise local memory and wait for other nodes to receive
the initialisation signal as well; before this correct nodes can have
arbitrary behaviour.

Later, we will repeatedly make use of this algorithm as a subroutine for a
self-stabilising algorithm and we need to consider the possibility that there
are still messages from earlier (possibly corrupted) instances in transit, or
nodes may be executing a previous instance in an incorrect way. Given the
initialisation signal, this is easily overcome by waiting for sufficient time
before leaving the starting state: waiting $\vartheta(\tau+d)\in O(\tau)$
local time guarantees that (i) all correct nodes transitioned to the starting
state and (ii) all messages sent before these transitions have arrived.
Clearing memory when leaving the starting state thus ensures that no obsolete
information from previous instances is stored by correct nodes.

The goal of this section is to establish the following theorem:

######  Theorem 4.

Let $n>1$, $f<n/3$, and $\tau>0$. If every correct node receives an
initialisation signal during $[0,\tau)$, then there exists a pulse
synchronisation algorithm $\mathbf{P}$ that

  * •

runs on $n$ nodes and has resilience $f$,

  * •

has $v\in G$ generate its first pulse (after the initialisation signal) at a
time $t_{0}(v)\in O(\vartheta^{2}d\tau)$,

  * •

has skew $2d$,

  * •

has accuracy bounds $\Phi^{-}\in\Omega(\vartheta d)$ and $\Phi^{+}\in
O(\vartheta^{2}d)$, and

  * •

lets each node broadcast at most one bit per time unit.

###  4.2 Description of the algorithm

Figure 2: The state machine for the non-self-stabilising pulse synchronisation
algorithm. State transitions occur when the condition of the guard in the
respective edge is satisfied (labelled gray boxes). Here, all transition
guards involve checking whether a local timer expires or a node has received
sufficiently many messages from nodes in state propose. The only communication
that occurs is when a node transitions to state propose; when this happens a
node broadcasts this information to all others. The notation $\langle
T\rangle$ indicates the expiration of a timer of length $T$ that was reset
when transitioning to the current state, that is, $T$ time units have passed
on the local clock since the transition to the current state. The box labelled
propose indicates that a node clears its propose memory flags when
transitioning from reset to start and pulse to ready. That is, the node
forgets who it has “seen” in propose the previous iteration. The algorithm
assumes that during the interval $[0,\tau)$ all nodes transition to reset.
This starts the initialisation phase of the algorithm. Eventually, all nodes
transition to pulse within a short time window and start executing the
algorithm. Whenever a node transitions to state pulse it generates a local
pulse event. Table 2 lists the constraints imposed on the timeouts.

The algorithm is illustrated in Figure 2. In the figure, the circles denote
the basic logical states (reset, start, ready, propose, pulse) of the state
machine for each node. The two states reset and start are only used during the
initialisation phase of the algorithm, which takes place during $[0,\tau)$
when the nodes receive their initialisation signals. In Figure 2, directed
edges between the states denote possible state transitions and labels give the
conditions (transition guards) when the transition is allowed to (and must)
occur. The notation is as follows: $\langle T_{k}\rangle$ denotes the
condition that timer $(T_{k},\\{s\\})$ has expired, where $s$ is the state
that is left when the guard is satisfied.

The constraints we impose on the timeouts are given in Table 2. The expression
“$>f$ propose flags set” denotes the condition $|H(v,\textsc{propose},t)|>f$.
For simplicity, we assume in all our descriptions that every time a node
transitions to a logical state, it broadcasts the name of the state to all
other nodes. Given that we use a constant number of (logical) states per node
(and in our algorithms nodes can only undergo a constant number of state
transitions in constant time), this requires broadcasting $O(1)$ bits of
information per time unit. In fact, closer inspection reveals that 1 bit per
iteration of the cycle suffices here: the only relevant information is whether
a node is in state propose or not.

The boxes labelled with propose indicate that when a node transitions to the
designated state, it clears its memory flags for message propose. For example,
if node $v$ transitions to state ready at time $t$, then it explicitly clears
its propose flags and it holds that $K(v,\textsc{propose},t)=\emptyset$.

###  4.3 Algorithm analysis

The algorithm relies heavily on the property that there are at most $f<n/3$
faulty nodes. This allows the use of the following “vote-and-pull” technique.
If some correct node receives a propose message from at least $n-f$ different
nodes at time $t$, then we must have that at least $n-2f>f$ of these
originated from correct nodes during the interval $(t-d,t)$, as every message
has a positive delay of less than $d$. Furthermore, it follows that before
time $t+d$ _all_ correct nodes receive more than $f$ propose messages.

In particular, this “vote-and-pull” technique is used in the transition to
states propose and pulse. Suppose at some point all nodes are in ready. If
some node transitions to pulse, then it must have observed at least $n-f$
nodes in propose by Guard G3\. This in turn implies that more than $f$ correct
nodes have transitioned to propose. This in turn will (in short time) “pull”
nodes that still remain in state ready into state propose. Thus, Guard G3 will
eventually be satisfied at the all nodes. The same technique is also used in
the transition from start to propose during the initialisation phase of the
algorithm. More formally, we have the following property.

######  Remark 1.

Suppose $f<n/3$. Let $u,v\in G$, $t\geq d$ and $I=(t-d,t+d)$. If
$|H(v,t,\textsc{propose})|\geq n-f$, then
$|K(u,t^{\prime},\textsc{propose})|>f$ for some $t^{\prime}\in I$ assuming $u$
does not clear its propose flags during the interval $I$.

(1) | $T_{0}/\vartheta\geq\tau+d$
---|---
(2) | $T_{1}/\vartheta\geq(1-1/\vartheta)T_{0}+\tau$
(3) | $T_{2}/\vartheta\geq 3d$
(4) | $T_{3}/\vartheta\geq(1-1/\vartheta)T_{2}+2d$
Table 2: The list of conditions used in the non-self-stabilising pulse
synchronisation algorithm given in Figure 2. Recall that $d,\vartheta\in O(1)$
and $\tau$ is a parameter of the algorithm.

For all $v\in G$ and $t>0$, let $p(v,t)\in\\{0,1\\}$ indicate whether $v$
transitions to state pulse at time $t$. That is, we have $p(v,t)=1$ if node
$v\in G$ transitions to state pulse at time $t$ and $p(v,t)=0$ otherwise.

######  Lemma 2.

There exists $t_{0}<\tau+T_{0}+T_{1}+d$ such that for all $v\in G$ it holds
that $p(v,t)=1$ for $t\in[t_{0},t_{0}+2d)$.

###### Proof.

Let $v\in G$. Node $v$ receives the initialisation signal during some time
$t_{\text{reset}}(v)\in[0,\tau)$ and transitions to state reset. From reset
node transitions to start at some time
$t_{\text{start}}(v)\in[t_{\text{reset}}(v)+T_{0}/\vartheta,t_{\text{reset}}(v)+T_{0}]$
when the timer $T_{0}$ in Guard G1 expires. Since $T_{0}/\vartheta\geq\tau+d$
by Constraint (2), we get that $t_{\text{start}}(v)\geq\tau+d$. Thus, for all
$u,v\in G$ we have $t_{\text{reset}}(u)+d\leq t_{\text{start}}(v)$.

Moreover, $v$ transitions to propose at some time
$t_{\text{propose}}(v)\in[t_{\text{start}}(v),t_{\text{start}}(v)+T_{1}]$ when
Guard G2 is satisfied. Hence, any $v\in G$ transitions to state propose no
later than time $t_{\text{start}}(v)+T_{1}\leq
t_{\text{reset}}(v)+T_{0}+T_{1}\leq\tau+T_{0}+T_{1}$. Let
$t_{\text{propose}}\geq\tau+d$ be the minimal time some node $v\in G$
transitions to state propose after transitioning to reset during $[0,\tau)$.
From our earlier argument, we get that for any
$t\in[t_{\text{start}}(v),t_{\text{propose}})\subseteq[\tau+d,t_{\text{propose}})$
node $v$ satisfies $K(v,\textsc{propose},t)=\emptyset$, that is, node $v$ will
not observe a propose message from any correct node $u\in G$ before time
$t_{\text{propose}}$.

Note that $t_{\text{propose}}\in[(T_{0}+T_{1})/\vartheta,\tau+T_{0}+T_{1})$ by
Guard G1 and Guard G2\. By Constraint (2) and our previous bounds we have that
$t_{\text{propose}}\geq
T_{0}/\vartheta+(1-1/\vartheta)T_{0}+\tau=T_{0}+\tau\geq t_{\text{start}}(u)$
for any $u\in G$. Hence, after time $T_{0}+\tau$, no $u\in G$ clears its
propose flags before transitioning to pulse at time $t_{\text{pulse}}(u)$. In
particular, we now have that $t_{\text{propose}}(v)\leq\tau+T_{0}+T_{1}$ and
hence all nodes transition to pulse by some time
$t_{\text{pulse}}(v)<\tau+T_{0}+T_{1}+d$, as each $u\in G$ must have received
a propose message by this time from least $n-f$ correct nodes, meeting the
condition of Guard G3.

Let $t_{0}=\min\\{t_{\text{pulse}}(v):v\in G\\}<\tau+T_{0}+T_{1}+d$ be the
minimal time some correct node transitions to state pulse. It remains to argue
that $t_{\text{pulse}}(v)\in[t_{0},t_{0}+2d)$. By Constraint (2), no correct
node clears its propose flags before time $t_{0}+3d$. Since some node $v\in G$
transitioned to pulse at time $t_{0}$, we must have that its condition in
Guard G3 was satisfied. That is, we have $|H(v,t_{0},\textsc{propose})|\geq
n-f$ and thus $K(v,t_{0},\textsc{propose})>f$. As these flags must have been
set after time $t_{\text{propose}}$, by then each $u\in G$ already reached
state start, and by Constraint (2) no correct node can reset its propose flags
again before time $t_{0}+3d$, it follows that
$K(u,t_{0}+d,\textsc{propose})>f$ for each $u\in G$. In particular, each $u\in
G$ transitions to state propose by time $t_{0}+d$. It now follows that at time
$t_{0}^{\prime}<t_{0}+2d$ we have $|K(u,t_{0}^{\prime},\textsc{propose})|\geq
n-f$ for all $u\in G$, implying that Guard G2 is satisfied for each such $u$.
Thus, $t_{\text{pulse}}(u)\in[t_{0},t_{0}^{\prime}]\subseteq[t_{0},t_{0}+2d)$
for each $u\in G$, as claimed. ∎

Let us now fix $t_{0}$ as given by the previous lemma. For every correct node
$v\in G$, we define

$p_{0}(v)=\inf\\{t\geq t_{0}:p(v,t)=1\\}\quad\text{ and }\quad
p_{i+1}(v)=p_{\text{next}}(v,p_{i}(v)),$

where $p_{\text{next}}(v,t)=\inf\\{t^{\prime}>t:p(v,t^{\prime})=1\\}$ is the
next time after time $t$ node $v$ generates a pulse.

######  Lemma 3.

For all $i\geq 0$, there exist

$t_{i+1}\in[t_{i}+(T_{2}+T_{3})/\vartheta,t_{i}+T_{2}+T_{3}+3d)\quad\text{
such that }\quad p_{i}(v)\in[t_{i},t_{i}+2d)\text{ for all }v\in G.$

###### Proof.

We show the claim using induction on $i$. For the case $i=0$, the claim
$p_{0}(v)\in[t_{0},t_{0}+2d)$ follows directly from Lemma 2. For the inductive
step, suppose $p_{i}(v)\in[t_{i},t_{i}+2d)$ for all $v\in G$. Each $v\in G$
transitions to state ready at a time
$t_{\text{ready}}(v)\in[t_{i}+T_{2}/\vartheta,t_{i}+2d+T_{2})$ by Guard G4\.
Moreover, by Constraint (2) we have that
$t_{\text{ready}}(v)>t_{i}+T_{2}/\vartheta\geq t_{i}+3d$. As no correct node
transitions to propose during $[t_{i}+2d,t_{i}+(T_{2}+T_{3})/\vartheta)$, this
implies that no node receives a propose message from a correct node before the
time $t_{\text{propose}}(u)$ when some node $u$ transitions to propose from
ready (for the next time after $t_{i}+3d$). Observe that
$t_{\text{propose}}(u)>t_{i}+(T_{2}+T_{3})/\vartheta>t_{i}+2d+T_{2}$ by Guard
G5 and Constraint (2). Thus, we have
$t_{\text{ready}}(v)<t_{i}+2d+T_{2}<t_{\text{propose}}(u)$ for all $u,v\in G$.
Therefore, there exists a time $t_{\text{ready}}<t_{i}+2d+T_{2}$ such that all
correct nodes are in state ready and
$|H(v,t_{\text{ready}},\textsc{propose})|= 0$ for all $v\in G$.

Next observe that $t_{\text{propose}}(v)\leq t_{i}+2d+T_{2}+T_{3}$ for any
$v\in G$. Hence, every $u\in G$ will receive a propose message from every
$v\in G$ before time $t_{\text{propose}}(v)+d\leq t_{i}+3d+T_{2}+T_{3}$. Thus,
by Guard G3 we have that $u$ transitions to pulse yielding that
$p_{i+1}(v)\in[t_{i}+t_{\text{ready}},t_{i}+3d+T_{2}+T_{3})\subseteq[t_{i}+(T_{2}+T_{3})/\vartheta,t_{i}+T_{2}+T_{3}+3d)$.
Let $t_{i+1} =\inf\\{p_{i+1}(v):v\in G\\}$. We have already established that
$t_{i+1}\in[t_{i}+(T_{2}+T_{3})/\vartheta,t_{i}+T_{2}+T_{3}+3d)$. Now using
the same arguments as in Lemma 2, it follows that for each $u\in G$,
$t_{\text{propose}}(u)<t_{i+1}+d$, as $u$ must have received more than $f$
propose messages before time $t_{i+1}+d$ triggering the condition in Guard G5
for node $u$. Thus, Guard G3 will be satisfied before time $t_{i+1}+2d$ at
each $u\in G$, implying that $p_{i+1}(u)\in[t_{i+1},t_{i+1}+2d)$ for each
$u\in G$. ∎

See 4

###### Proof.

The constraints in Table 2 are satisfied by setting

$\displaystyle T_{0}$ $\displaystyle=\vartheta(\tau+d)$ $\displaystyle T_{1}$
$\displaystyle=\vartheta^{2}(1-1/\vartheta)(\tau+d)+\tau$ $\displaystyle
T_{2}$ $\displaystyle=\vartheta 3d$ $\displaystyle T_{3}$
$\displaystyle=\vartheta^{2}(1-1/\vartheta)3d+2d.$

By Lemma 2 we get that there exists $t_{0}\in O(\vartheta^{2}d\tau)$ such that
all nodes generate the first pulse during the interval $[t_{0},t_{0}+2d)$.
Applying Lemma 3 we get that for all $i>0$, we have that nodes generate the
$i$th pulse during the interval $[t_{i},t_{i}+2d)$, where
$t_{i}\in[t_{i-1}+(T_{2}+T_{3})/\vartheta,t_{i-1}+T_{2}+T_{3}+3d)\subseteq[\Phi^{-},\Phi^{+})$.
Note that $T_{2}+T_{3}\in\Theta(\vartheta^{2}d)$ and $\vartheta,d\in O(1)$.
These observations give the first four properties. For the final property,
observe that nodes only need to communicate when they transition to propose.
By Guard G4, correct nodes wait at least for $T_{2}/\vartheta=3d$ reference
time before transitioning to propose again after generating a pulse. Hence,
nodes need to broadcast at most one bit every $3d>d$ time. ∎

##  5 Self-stabilising pulse synchronisation

In this section, we show how to use a resynchronisation algorithm and a
synchronous consensus routine to devise _self-stabilising_ pulse
synchronisation algorithms. We obtain the following result:

See 2

###  5.1 Overview of the ingredients

The pulse synchronisation algorithm presented in this section consists of two
state machines running in parallel:

  1. 1.

the so-called _main state machine_ that is responsible for pulse generation,
and

  2. 2.

an _auxiliary state machine_ , which assists in initiating consensus instances
and stabilisation.

The main state machine indicates when pulses are generated and handles all the
communication between nodes except for messages sent by simulated consensus
instances. The latter are handled by the auxiliary state machine. The
transitions in the main state machine are governed by a series of threshold
votes, local timeouts, and signals from the auxiliary state machine.

As we aim to devise self-stabilising algorithms, the main and auxiliary state
machines may be arbitrarily initialised. To handle this, a stabilisation
mechanism is used in conjunction to ensure that, regardless of the initial
state of the system, all nodes eventually manage to synchronise their state
machines. The stabilisation mechanism relies on the following three
subroutines which are summarised in Figure 3:

  1. (a)

a resynchronisation algorithm $\mathbf{B}$,

  2. (b)

the non-self-stabilising pulse synchronisation algorithm $\mathbf{P}$ from
Section 4,

  3. (c)

a synchronous consensus algorithm $\mathbf{C}$.

#### Resynchronisation pulses.

Recall that _resynchronisation algorithm_ $\mathbf{B}$ solves a weak variant
of a pulse synchronisation: it guarantees that _eventually_ , within some
bounded time $T(\mathbf{B})$, all correct nodes generate a _good_
resynchronisation pulse such that no new resynchronisation pulse is generated
before $\Psi$ time has passed. Note that at all other times, the algorithm
$\mathbf{B}$ is allowed to generate pulses at arbitrary frequencies and not
necessarily at all correct nodes. Nevertheless, at some point all correct
nodes are bound to generate a good resynchronisation pulse in rough synchrony.
We leverage this property to cleanly re-initialise the stabilisation mechanism
from time to time. Observe that the idea is somewhat similar to the use of
initialisation signals in Section 4, but now we have less control over the
incoming “initialisation signals” (i.e. resynchronisation pulses). To
summarise, we assume throughout this section that every correct node $v\in G$

  * •

receives a single resynchronisation pulse at time $t_{v}\in[0,\rho)$, and

  * •

does not receive another resynchronisation pulse before time $t_{v}+\Psi$,

where $\Psi$ is sufficiently large value we determine later. Later in Section
6, we devise efficient algorithms that produce the needed resynchronisation
pulses.

#### Simulating synchronous consensus.

The two subroutines (b) and (c) are used in conjunction as follows. We use the
variant of the Srikanth–Toueg pulse synchronisation algorithm $\mathbf{P}$
described in Section 4 to simulate a synchronous consensus algorithm (in the
bounded-delay model). Note that while this pulse synchronisation algorithm is
not self-stabilising, it works properly even if non-faulty nodes initialise
the algorithm at different times as long as they do so within a time interval
of length $\tau$.

Assuming that the nodes initialise the non-self-stabilising pulse
synchronisation algorithm $\mathbf{P}$ within at most time $\tau$ apart, it is
straightforward to simulate round-based (i.e., synchronous) algorithms: a
pulse generated by $\mathbf{P}$ indicates that a new round of the synchronous
algorithm can be started. By setting the delay between two pulses large
enough, we can ensure that

  1. 1.

all nodes have time to execute the local computations of the synchronous
algorithm and

  2. 2.

all messages related to a single round arrive before a new pulse occurs.

#### Employing silent consensus.

For convenience, we utilise so-called silent consensus routines. Silent
consensus routines satisfy exactly the same properties as usual consensus
routines (validity, agreement, and termination) with the addition that correct
nodes send no messages in executions in which all nodes have input 0.

######  Definition 2 (Silent consensus).

A consensus routine is _silent_ , if in each execution in which all correct
nodes have input $0$, correct nodes send no messages.

Any synchronous consensus routine can be converted into a silent consensus
routine essentially for free. In our prior work [24], we showed that there
exists a simple transformation that induces only an overhead of two rounds
while keeping all other properties of the algorithm the same.

######  Theorem 5 ([24]).

Any consensus protocol $\mathbf{C}$ that runs in $R$ rounds can be transformed
into a silent consensus protocol $\mathbf{C}^{\prime}$ that runs in $R+2$
rounds. Moreover, the resilience and message size of $\mathbf{C}$ and
$\mathbf{C}^{\prime}$ are the same.

Thus, without loss of generality, we assume throughout this section that the
given consensus routine $\mathbf{C}$ is silent. Moreover, this does not
introduce any asymptotic loss in the running time or number of bits
communicated.

Figure 3: Constructing a self-stabilising (SS) and Byzantine fault-tolerant
pulse synchronisation algorithm $\mathbf{A}$ in the bounded-delay model (BD)
out of Byzantine fault-tolerant non-stabilising pulse synchronisation
algorithm $\mathbf{P}$, synchronous consensus algorithm $\mathbf{C}$, and
resynchronisation algorithm $\mathbf{B}$. All algorithms run on the same set
of nodes. (1) The resynchronisation algorithm $\mathbf{B}$ eventually outputs
a good resynchronisation pulse, which resets the stabilisation mechanism used
by the auxiliary state machine. (2) The auxiliary state machine simulates the
executions of $\mathbf{C}$ using $\mathbf{P}$. Simulations are initiated
either due to nodes transitioning to a special wait state of the main state
machine (see Figure 4) or a certain time after a resynchronisation pulse. (3)
The main state machine. It generates pulses when a consensus instance outputs
“1” and, when stabilised, guarantees re-initialisation of the consensus
algorithm by the auxiliary state machine.

###  5.2 High-level idea of the construction

The high-level strategy used in our construction is as follows. We run the
resynchronisation algorithm in parallel to the self-stabilising pulse
synchronisation algorithm we devise in this section. The resynchronisation
algorithm will send the resynchronisation signals it generates to the pulse
synchronisation algorithm as shown in Figure 3.

The pulse synchronisation algorithm consists of the main state machine given
in Figure 4 and the auxiliary state machine given in Figure 5. The auxiliary
state machine is responsible for generating the output signals that drive the
main state machine (Guard G2 and Guard G2’).

Figure 4: The main state machine. When a node transitions to state pulse
(double circle) it will generate a local pulse event and send a pulse message
to all nodes. When the node transitions to state wait it broadcasts a wait
message to all nodes. Guard G1 employs a sliding window memory buffer, which
stores any pulse messages that have arrived within time $T_{1}$ (as measured
by the local clock). When a correct node transitions to pulse it resets a
local $T_{1}$ timeout. Once this expires, either Guard G1 or Guard G1’ become
satisfied. Similarly, the timer $T_{\text{wait}}$ is reset when node
transitions to wait. Once it expires, Guard G2’ is satisfied and node
transitions from wait to recover. The node can transition to pulse state when
Guard G2 is satisfied, which requires an output 1 signal from the auxiliary
state machine given in Figure 5.

The auxiliary state machine employs a consensus routine to facilitate
agreement among the nodes on whether a new pulse should occur. If the
consensus simulation outputs 1 at some node, then the auxiliary state machine
signals the main state machine to generate a pulse. Otherwise, if the
consensus instance outputs 0, then this is used to signal that something is
wrong and the node can detect that the system has not stabilised. We carefully
set up our construction so that once the system stabilises, any consensus
instance run by the nodes is guaranteed to always output 1 at every correct
node.

Figure 5: The auxiliary state machine. The auxiliary state machine is
responsible for initialising and simulating the consensus routine. The gray
boxes denote states which represent the simulation of the consensus routine
$\mathbf{C}$. When transitioning to either run 0 or run 1, the node locally
initialises the (non-self-stabilising) pulse synchronisation algorithm from
Section 4 and a new instance of $\mathbf{C}$. If the node transitions to run
0, it uses input 0 for the consensus routine. If the node transitions to run
1, it uses input 1. When the consensus simulation declares an output, the node
transitions to either output 0 or output 1 (sending the respective output
signal to the main state machine) and immediately to state listen. The
timeouts $T_{\text{listen}}$, $T_{2}$, and $T_{\text{consensus}}$ are reset
when a node transitions to the respective states that use a guard referring to
them. The timeout $T_{\text{active}}$ in Guard G3 (dashed line) is reset by
the resynchronisation signal from the underlying resynchronisation algorithm
$\mathbf{B}$. Both input 0 and input 1 have a self-loop that is activated if
Guard G4 is satisfied. This means that if Guard G4 is satisfied while in these
states, the timer $T_{2}$ is reset.

As we operate under the assumption that the initial state is arbitrary, the
non-trivial part in our construction is to get all correct nodes synchronised
well enough to even start simulating consensus jointly in the first place.
This is where the resynchronisation algorithm comes into play. We make sure
that the algorithm either stabilises or all nodes get “stuck” in a recovery
state recover. To deal with the latter case, we use the resynchronisation
pulse to let all nodes synchronously reset a local timeout. Once this timeout
expires, nodes that are in state recover start a consensus instance with input
“1”. By the time this happens, either

  * •

the algorithm has already stabilised (and thus no correct node is in state
recover), or

  * •

all correct nodes are in state recover and jointly start a consensus instance
that will output “1” (by validity of the consensus routine).

In both cases, stabilisation is guaranteed.

#### Receiving a resynchronisation signal.

The use of the resynchronisation signal is straightforward: when a correct
node $u\in G$ receives a resynchronisation signal from the underlying
resynchronisation algorithm $\mathbf{B}$, node $u$ resets its local timeout
$T_{\text{active}}$ used by the auxiliary state machine in Figure 5. Upon
expiration of the timeout, Guard G3 in the auxiliary state machine is
activated only if the node is in state recover at the time.

#### Main state machine.

The main state machine, which is given in Figure 4, is responsible for
generating the pulse events and operates as follows. If a node is in state
pulse, it generates a local pulse event and sends a pulse message to all other
nodes. Now suppose a node $u\in G$ transitions to state pulse. Two things can
happen:

  * •

If a node $u\in G$ is in state pulse and observes at least $n-f$ nodes also
generating a pulse within a short enough time window (Guard G1), it is
possible that all correct nodes generated a pulse in a synchronised fashion.
If this happens, then Guard G1 ensures that node $u$ proceeds to the state
wait. As the name suggests, the wait state is used to wait before generating a
new pulse, ensuring that pulses obey the desired frequency bounds.

  * •

Otherwise, if a node is certain that not all correct nodes are synchronised,
it transitions to from pulse to state recover (Guard G1’).

Once a node is in either wait or recover, it will not leave the state before
the consensus algorithm outputs “1”, as Guard G2 needs to be satisfied in
order for a transition to pulse to take place. The simulation of consensus is
handled by the auxiliary state machine, which we discuss below. The nodes use
consensus to agree whether sufficiently many nodes transitioned to the wait
state within a small enough time window. If the system has stabilised, all
correct nodes transition to wait almost synchronously, and hence, after
stabilisation every correct node always uses input “1” for the consensus
instance.

Once a node transitions to state wait, the node keeps track of how long it has
been there. If the node observes that it has been there longer than it would
take for a consensus simulation to complete under correct operation
(indicating that the system has not yet stabilised), it transitions to state
recover. Also, if the consensus instance outputs “0”, the node knows something
is wrong and transitions to recover. During the stabilisation phase, nodes
that transition to recover refrain from using input “1” for any consensus
routine before the local timeout $T_{\text{active}}$ expires; we refer to the
discussion of the auxiliary state machine.

Once the system stabilises, the behaviour of the main state machine is simple,
as only Guard G1 and Guard G2 can be satisfied. This implies that correct
nodes alternate between the pulse and wait states. Under stabilised operation,
we get that all correct nodes:

  * •

transition to pulse within a time window of length $2d$,

  * •

observe that at least $n-f$ nodes transitioned to pulse within a short enough
time window ensuring that Guard G1 is satisfied at every correct node,

  * •

transition to wait within a time window of length $O(d)$,

  * •

correctly initialise a simulation of the consensus algorithm $\mathbf{C}$ with
input “1”, as correct nodes transitioned to wait in a synchronised fashion
(see auxiliary state machine),

  * •

all correct nodes remain in wait until Guard G2 or Guard G2’ become satisfied.

Finally, we ensure that (after stabilisation) all correct nodes remain in
state wait in the main state machine longer than it takes to properly
initialise and simulate a consensus instance. This is achieved by using the
$T_{\text{wait}}$ timeout in Guard G2’. Due to the validity property of the
consensus routine and the fact that all correct nodes use input $1$, this
entails that Guard G2 is always satisfied before Guard G2’, such that all
correct nodes again transition to pulse within a time window of length $2d$.

#### Auxiliary state machine.

The auxiliary state machine given in Figure 5 is slightly more involved.
However, the basic idea is simple:

  1. (a)

nodes try to check whether at least $n-f$ nodes transition to the wait state
_in a short enough time window_ (that is, a time window consistent with
correct operation) and

  2. (b)

then use a consensus routine to agree whether all nodes saw this.

Assuming that all correct nodes participate in the simulation of consensus, we
get the following:

  * •

If the consensus algorithm $\mathbf{C}$ outputs “0”, then some correct node
did not see $n-f$ nodes transitioning to wait in a short time window, and
hence, the system has not yet stabilised.

  * •

If the consensus algorithm $\mathbf{C}$ outputs “1”, then all correct nodes
agree that a transition to wait happened recently.

In particular, the idea is that when the system operates correctly, the
consensus simulation will always succeed and output “1” at every correct node.

The above idea is implemented in the auxiliary state machine as follows.
Suppose that a correct node $u\in G$ is in the listen state and the local
timeout $T_{\text{active}}$ is not about to expire (recall that
$T_{\text{active}}$ is only reset by the resynchronisation signal). Node $u$
remains in this state until it is certain that at least one correct node
transitions to wait in the main state machine. Once this happens, Guard G4 is
satisfied and node $u$ transitions to the read state. In the read state, node
$u$ waits for a while to see whether it observes (1) at least $n-f$ nodes
transitioning to wait in a short time window or (2) less than $n-f$ nodes
doing this.

In case (1), node $u$ can be certain that at least $n-2f>f$ correct nodes
transitioned to wait. Thus, node $u$ can also be certain that every correct
node observes at least $f+1$ correct nodes transitioning to wait; this will be
a key property later. In case (2), node $u$ can be certain that the system has
not stabilised. If case (1) happens, we have that Guard G5 is eventually
satisfied. Node $u$ then transitions to input 1 indicating that node $u$ is
willing to use input “1” in the next simulation of consensus _unless_ it is in
the recover state in the main state machine. In case (2), we get that Guard
G5’ becomes satisfied and $u$ transitions to input 0. This means that $u$
insists on using input “0” for the next consensus simulation.

Once node $u\in G$ transitions to either input 0 or input 1, it will remain
there until the local timeout of length $T_{2}$ expires (see Guard G6, Guard
G6’ and Guard G7). However, if Guard G4 becomes satisfied _while_ node $u$ is
in either of the input states, then the local timeout is reset again. We do
this because if Guard G4 becomes satisfied while $u$ is in one of the input
states, (i) the same may be true for other correct nodes that are in state
listen and (ii) node $u$ can be certain that the system has not stabilised.
Resetting the timeout helps in ensuring that all correct nodes jointly start
the next consensus instance (guaranteeing correct simulation), if Guard G4 is
satisfied at all correct nodes at roughly the same time. In case this does not
happen, resetting the timeout at least makes sure that there will be a time
when _no_ correct node is currently trying to simulate a consensus instance.
These properties are critical for our proof of stabilisation.

###  5.3 Outline of the proof

The key difficulty in achieving stabilisation is to ensure the proper
simulation of a consensus routine despite the arbitrary initial state. In
particular, after the transient faults cease, we might have some nodes
attempting to execute consensus, whereas some do not. Moreover, nodes that are
simulating consensus might be simulating different rounds of the consensus
routine, and so on. To show that such disarray cannot last indefinitely long,
we use the following arguments:

  * •

if some correct node attempts to use input “1” for consensus, then at least
$f+1$ correct nodes have transitioned to wait in the main state machine (Lemma
4), that is, all correct nodes see if some other correct node might be
initialising a new consensus instance with input “1” soon,

  * •

if some correct node transitions to wait at time $t$, then there is a long
interval of length $\Theta(T_{2})$ during which no correct node transitions to
wait (Lemma 5), that is, correct nodes cannot transition to wait state too
often,

  * •

if some correct node attempts to use input “1” for consensus, then all correct
nodes initialise a new consensus instance within a time window of length
$\tau\in\Theta((1-1/\vartheta)T_{2})$ (Lemma 6),

  * •

if all correct nodes initialise a new consensus instance within a time window
of length $\tau$, then all correct nodes participate in the same consensus
instance and succesfully simulate an entire execution of $\mathbf{C}$ (Lemma
7).

The idea is that the timeout $T_{2}$ will be sufficiently large to ensure that
consensus instances are well-separated: if a consensus instance is initialised
with input “1” at some correct node, then there is enough time to properly
simulate a complete execution of the consensus routine before any correct node
attempts to start a new instance of consensus.

Once we have established the above properties, it is easy to see that if
synchronisation is established, then it _persists_. More specifically, we
argue that if all correct nodes transition to pulse at most time $2d$ apart,
then all correct nodes initialise a new consensus instance within a time
window of length $\tau$ using input “1” (Lemma 8). Thus, the system stabilises
if all correct nodes eventually generate a pulse with skew at most $2d$.

Accordingly, a substantial part of the proof is arguing that all nodes
eventually transition to pulse within time window of $2d$. To see that this is
bound to occur eventually, we consider an interval $[\alpha,\beta]$ of length
$\Theta(R)$ and use the following line of reasoning:

  * •

if all correct nodes are simultaneously in state recover at some time before
timeout $T_{\text{active}}$ expires at any correct node, then Guard G3 in the
auxiliary state machine becomes satisfied at all correct nodes and a new
consensus instance with all-1 input is initialised within a time window of
length $\tau$ (Lemma 9),

  * •

if some correct node attempts to use input “1” within some time interval
$[\alpha,\beta^{\prime}]\subset[\alpha,\beta]$, then either (a) all correct
nodes end up in recover before timeout $T_{\text{active}}$ expires at any node
or (b) all correct nodes eventually transition to pulse within time $2d$
(Lemma 10),

  * •

if no correct node attempts to use input “1” during the time interval
$[\alpha,\beta]$, all correct nodes will be in state recover before the
timeout $T_{\text{active}}$ expires at any node (Lemma 14).

In either of the latter two cases, we can use the first argument to guarantee
stabilisation (Corollary 4 and Corollary 5). Finally, we need to argue that
all the timeouts employed in the construction can be set so that our arguments
work out. The constraints related to all the timeouts are summarised in Table
3 and Lemma 16 shows that these can be satisfied. We now proceed to formalise
and prove the above arguments in detail. The structure of the proof is
summarised in Figure 6.

Figure 6: The overall structure of the proof of Theorem 2. The bold rectangles
denote results that are informally discussed in Section 5.3.

###  5.4 Analysing the state machines

Table 3: The timeout conditions employed in the construction of Section 5.  (5) | $d,\vartheta\in O(1)$
---|---
(6) | $T_{1}=3\vartheta d$
(7) | $T_{\text{listen}}=(\vartheta-1)T_{1}+3\vartheta d$
(8) | $T_{2}>\vartheta(T_{\text{listen}}+3T_{1}+3d)$
(9) | $(2/\vartheta-1)T_{2}>2T_{\text{listen}}+T_{\text{consensus}}+5T_{1}+4d$
(10) | $\tau=\max\left\\{(1-1/\vartheta)T_{2}+T_{\text{listen}}+d+\max\\{T_{\text{listen}}+d,3T_{1}+2d\\},(1-1/\vartheta)T_{\text{active}}+\rho\right\\}$
(11) | $T_{\text{consensus}}=\vartheta(\tau+T(R))$
(12) | $T_{\text{wait}}=T_{2}+T_{\text{consensus}}$
(13) | $T_{\text{active}}\geq 4T_{2}+T_{\text{listen}}+\vartheta(T_{\text{listen}}+T_{\text{wait}}-5T_{1}-4d+\rho)$
(14) | $T_{\text{active}}\geq 2T_{2}+T_{\text{consensus}}+\vartheta(2T_{\text{listen}}+T_{1}+T_{\text{wait}}+3d+2T_{2}+2T_{\text{consensus}})$

First let us observe that after a short time, the arbitrary initial contents
of the sliding window message buffers have been cleared.

######  Remark 2.

By time $t=\max\\{T_{1},T_{\text{listen}}\\}+d\in O(\vartheta^{2}d)$ the
sliding window memory buffers used in Guard G2, Guard G4, and Guard G5 for
each $u\in G$ have valid contents: if the buffer of Guard G2 contains a
message $m$ from $v\in G$ at any time $t^{\prime}\geq t$, then $v\in G$ sent
the message $m$ during $(t-T_{1}-d,t)$; similarly, for Guard G4 and Guard G5
this holds for the interval $(t-T_{\text{listen}}-d,t)$.

Without loss of generality, we assume that this has happened by time $0$.
Moreover, we assume that every correct node received the resynchronisation
signal during the time interval $[0,\rho)$. Thus, the contents of message
buffers are valid from time 0 on and every node has reset its
$T_{\text{active}}$ timeout during $[0,\rho)$. Hence, the timeout
$T_{\text{active}}$ expires at any node $u\in G$ during
$[T_{\text{active}}/\vartheta,T_{\text{active}}+\rho)$.

We use $T(R)\in O(\vartheta^{2}dR)$ to denote the maximum time a simulation of
the $R$-round consensus routine $\mathbf{C}$ takes when employing the non-
stabilising pulse synchronisation algorithm given in Section 4. We assume that
the consensus routine $\mathbf{C}$ is silent, as by Theorem 5 we can convert
any consensus routine into a silent one without any asymptotic loss in the
running time.

First, we highlight some useful properties of the simulation scheme
implemented in the auxiliary state machine.

######  Remark 3.

If node $v\in G$ transitions to run 0 or run 1 at time $t$, then the following
holds:

  * •

node $v$ remains in the respective state during $[t,t+\tau)$,

  * •

node $v$ does not execute the first round of $\mathbf{C}$ before time
$t+\tau$,

  * •

node $v$ leaves the respective state and halts the simulation of $\mathbf{C}$
before time $t+T_{\text{consensus}}$.

Now let us start by showing that if some node transitions to input 1 in the
auxiliary state machine, then there is a group of at least $f+1$ correct nodes
that transition to wait in the main state machine in rough synchrony.

######  Lemma 4.

Suppose node $v\in G$ transitions to input 1 at time $t\geq
T_{\text{listen}}+d$. Then there is a time
$t^{\prime}\in(t-T_{\text{listen}}-d,t)$ and a set $A\subseteq G$ with
$|A|\geq f+1$ such that each $w\in A$ transitions to wait during
$[t^{\prime},t]$.

###### Proof.

Since $v$ transitions to input 1, it must have observed at least $n-f$
distinct wait messages within time $T_{\text{listen}}$ in order to satisfy
Guard G5\. As $f<n/3$, we have that at least $f+1$ of these messages came from
nodes $A\subseteq G$, where $|A|\geq f+1$. The claim follows by choosing
$t^{\prime}$ to be the minimal time during $(t-T_{\text{listen}}-d,t)$ at
which some $w\in A$ transitioned to wait. ∎

Next we show that if some correct node transitions to wait, then this is soon
followed by a long time interval during which no correct node transitions to
wait. Thus, transitions to wait are well-separated.

######  Lemma 5.

Suppose node $v\in G$ transitions to wait at time
$t\leq(T_{\text{active}}-T_{2})/\vartheta$. Then no $u\in G$ transitions to
wait during $[t+3T_{1}+d,t+T_{2}/\vartheta-2T_{1}-d)$.

###### Proof.

Since $v\in G$ transitioned to wait at time $t$, it must have seen at least
$n-f$ nodes transitioning to pulse during the time interval $(t-2T_{1},t)$.
Since $f<n/3$, it follows that $n-2f\geq f+1$ of these messages are from
correct nodes. Let us denote this set of nodes by $A\subseteq G$.

Consider any node $w\in A$. As node $w$ transitioned to pulse during
$(t-2T_{1}-d,t)$, it transitions to state recover or to state wait at time
$t_{w}\in(t-2T_{1}-d,t+T_{1})$. Either way, as it also transitioned to listen,
transitioning to pulse again requires to satisfy Guard G3 or one of Guard G6,
Guard G6’, and Guard G7 while being in states input 0 or input 1,
respectively. By assumption, Guard G3 is not satisfied before time
$T_{\text{active}}/\vartheta\geq t+T_{2}/\vartheta$, and the other options
require a timeout of $T_{2}$ to expire, which takes at least time
$T_{2}/\vartheta$. It follows that $w$ is not in state pulse during
$[t+T_{1},t+T_{2}/\vartheta-2T_{1}-d)$.

We conclude that no $w\in A$ is observed transitioning to pulse during
$[t+T_{1}+d,t+T_{2}/\vartheta-2T_{1}-d)$. Since $|A|>f$, we get that no $u\in
G$ can activate Guard G1 and transition to wait during
$[t+3T_{1}+d,t+T_{2}/\vartheta-2T_{1}-d)$, as $n-|A|<n-f$. ∎

Using the previous lemmas, we can show that if some correct node transitions
to state input 1 in the auxiliary state machine, then every correct node
eventually initialises and participates in the same new consensus instance.
That is, every correct node initialises the underlying Srikanth–Toueg pulse
synchronisation algorithm within a time interval of length $\tau$.

######  Lemma 6.

Suppose node $u\in G$ transitions to input 1 at time
$t\in[T_{\text{listen}}+d,(T_{\text{active}}-T_{2})/\vartheta]$. Then each
$v\in G$ transitions to state run 0 or state run 1 at time
$t_{v}\in[t_{0},t_{0}+\tau)$, where
$t_{0}=t-T_{\text{listen}}-d+T_{2}/\vartheta$. Moreover, Guard G4 cannot be
satisfied at any node $v\in G$ during $[t+3T_{1}+2d,t^{*}+T_{1}/\vartheta)$,
where $t^{*}:=\min_{v\in G}\\{p(v,t+d)\\}$.

###### Proof.

By Lemma 4 there exists a set $A\subseteq G$ such that $|A|\geq f+1$ and each
$w\in A$ transitions to wait at a time $t_{w}\in(t-T_{\text{listen}}-d,t)$.
This implies that Guard G4, and thus also Guard G9, becomes satisfied for
$v\in G$ at time $t^{\prime}_{v}\in[t-T_{\text{listen}}-d,t+d)$. Thus, every
$v\in G$ transitions to state read, input 0, or input 1 at time
$t^{\prime}_{v}$; note that if $v$ was in state input 0 or input 1 before this
happened, it transitions back to the same state due to Guard G4 being
activated and resets its local $T_{2}$ timer. Moreover, by time
$t_{v}^{\prime}\leq
r_{v}<t^{\prime}_{v}+T_{\text{listen}}<t+d+T_{\text{listen}}$ node $v$
transitions to either input 0 or input 1, as either Guard G5 or Guard G5’
becomes activated in case $v$ transitions to state read at time
$t_{v}^{\prime}$.

Now we have that node $v$ remains in either input 1 or input 0 for the
interval $[r_{v},r_{v}+T_{2}/\vartheta)$, as none of Guard G6, Guard G6’, and
Guard G7 are satisfied before the local timer $T_{2}$ expires. Moreover, by
applying Lemma 5 to any $w\in A$, we get that no $v\in G$ transitions to wait
during the interval

$[t_{w}+3T_{1}+d,t_{w}+T_{2}/\vartheta-2T_{1}-d)\supseteq(t+3T_{1}+d,t+T_{2}/\vartheta-2T_{1}-T_{\text{listen}}-2d).$

Recall that for each $v\in G$, $t_{v}^{\prime}<t+d$. After this time, $v$
cannot transition to pulse again without transitioning to run 0 or run 1
first. Since $t+T_{2}/\vartheta-2T_{1}-T_{\text{listen}}-2d>t+T_{1}+d$ by
Constraint (3), we get that every $w\in G$ has arrived in state wait or
recover by time $t+T_{2}/\vartheta-2T_{1}-T_{\text{listen}}-2d$. Thus, no such
node transitions to state wait during
$[t+T_{2}/\vartheta-2T_{1}-T_{\text{listen}}-2d,t^{*}+T_{1}/\vartheta)$:
first, it must transition to pulse, which requires to satisfy Guard G2, i.e.,
transitioning to state output 1, and then a timeout of $T_{1}$ must expire;
here, we use that we already observed that
$t+T_{2}/\vartheta-2T_{1}-T_{\text{listen}}-2d>t+d$, i.e., by definition the
first node $w\in G$ to transition to pulse after time $t+T_{2}/\vartheta-
T_{1}-T_{\text{listen}}-2d$ does so at time $t^{*}$. We conclude that Guard G4
cannot be satisfied at any $v\in G$ during the interval
$[t+3T_{1}+2d,t^{*}+T_{1}/\vartheta)$, i.e., the second claim of the lemma
holds.

We proceed to showing that each $v\in G$ transitions to state run 0 or state
run 1 at time $t_{v}\in[t_{0},t_{0}+\tau)$, i.e., the first claim of the
lemma. To this end, observe that $w$ transitions to either state run 0 or run
1 at some time $t^{\prime}\in(t_{w}^{\prime},t^{*})$. By the above
observations, $t^{\prime}\geq r_{w}+T_{2}/\vartheta\geq
t-T_{\text{listen}}-d+T_{2}/\vartheta=t_{0}$. Node $w$ initialises the
Srikanth-Toueg algorithm given in Figure 2 locally at time $t^{\prime}$. In
particular, by the properties of the simulation algorithm given in Remark 3,
we have that $w$ waits until time $t^{\prime}+\tau$ before starting the
simulation of $\mathbf{C}$, and hence, $w$ remains in run 0 or run 1 at least
until time $t^{\prime}+\tau$ before the simulation of $\mathbf{C}$ produces an
output value. Thus, we get that $t^{*}\geq t^{\prime}+\tau\geq t_{0}+\tau$.

Recall that each $v\in G$ resets timeout $T_{2}$ at time
$r_{v}\in[t_{v}^{\prime},t+d+T_{\text{listen}})\subseteq[t-T_{\text{listen}}-d,t+T_{\text{listen}}+d)$
and does not reset it during $[t+3T_{1}+2d,t^{*}+T_{1}/\vartheta)$, as it does
not satisfy Guard G4 at any time from this interval. When $T_{2}$ expires at
$v$, it transitions to run 0 or run 1. Because
$t^{*}+T_{1}/\vartheta>t_{0}+\tau\geq
t+\max\\{T_{\text{listen}}+d,3T_{1}+2d\\}+T_{2}$ by Constraint (3), this
happens at time
$t_{v}\in[t-T_{\text{listen}}-d+T_{2}/\vartheta,t_{0}+\tau]=[t_{0},t_{0}+\tau]$,
as claimed. ∎

Next, we show that if all correct nodes initialise a new instance of the
Srikanth–Toueg pulse synchronisation algorithm within a time interval of
length $\tau$, then every correct node initialises, participates in, and
successfully completes simulation of the consensus routine $\mathbf{C}$.

######  Lemma 7.

Suppose there exists a time $t_{0}$ such that each node $v\in G$ transitions
to run 0 or run 1 at some time $t_{v}\in[t_{0},t_{0}+\tau)$. Let $t^{\prime}$
be the minimal time larger than $t_{0}$ at which some $u\in G$ transitions to
either output 0 or output 1. If Guard G4 is not satisfied at any $v\in G$
during $[t_{0},t^{\prime}+2d)$, then $t^{\prime}\leq
t_{0}+T_{\text{consensus}}/\vartheta-2d$ and there are times
$t^{\prime}_{v}\in[t^{\prime},t^{\prime}+2d)$, $v\in G$, such that:

  * •

each $v\in G$ transitions to output 1 or output 0 at time $t_{v}^{\prime}$
(termination),

  * •

this state is the same for each $v\in G$ (agreement), and

  * •

if each $v\in G$ transitioned to state run 1 at time $t_{v}$, then this state
is output 1 (validity).

###### Proof.

When $v\in G$ transitions to either run 0 or run 1, it sends an initialisation
signal to the non-self-stabilising Srikanth–Toueg algorithm described in
Section 4. Using the clock given by this algorithm, nodes simulate the
consensus algorithm $\mathbf{C}$. If node $v\in G$ enters state run 0, it uses
input “0” for $\mathbf{C}$. Otherwise, if $v$ enters run 1 it uses input “1”.

Note that Theorem 4 implies that if all nodes initialise the Srikanth–Toueg
algorithm within time $\tau$ apart, then the simulation of $\mathbf{C}$ takes
at most $\tau+T(R)\in O(\vartheta^{2}d(\tau+R))$ time. Moreover, all nodes
will declare the output on the same round, and hence, declare the output
within a time window of $2d$, as the skew of the pulses is at most $2d$.

Now let us consider the simulation taking place in the auxiliary state
machine. If Guard G4 is not satisfied during $[t_{0},t^{\prime}+2d)$ and the
timer $T_{\text{consensus}}$ does not expire at any node $v\in G$ during the
simulation, then by time $t^{\prime}+2d\leq t_{0}+\tau+T(R)\in
O(\vartheta^{2}d(\tau+R))$ the nodes have simulated $R$ rounds of $\mathbf{C}$
and declared output. By assumption, Guard G4 cannot be satisfied prior to time
$t^{\prime}+2d$. At node $v\in G$, the timer $T_{\text{consensus}}$ is reset
at time $t_{v}\geq t_{0}$. Hence, it cannot expire again earlier than time
$t_{0}+T_{\text{consensus}}/\vartheta\geq t_{0}+\tau+T(R)$ by Constraint (3).
Hence, the simulation succeeds.

Since the simulation of the consensus routine $\mathbf{C}$ completes at each
$v\in G$ at some time $t^{\prime}_{v}\in[t^{\prime},t^{\prime}+2d)$, we get
that Guard G8 or Guard G9 is satisfied at time $t^{\prime}_{v}$ at node $v$.
Hence, $v$ transitions to either of the output states depending on the output
value of $\mathbf{C}$. The last two claims of the lemma follow from the
agreement and validity properties of the consens routine $\mathbf{C}$. ∎

Now we can show that if all correct nodes transition to pulse within a time
window of length $2d$, then all correct nodes remain synchronised with skew
$2d$ and controlled accuracy bounds. Thus, the system stabilises.

######  Lemma 8.

Suppose there exists an interval $[t,t+2d)$ such that for all $v\in G$ it
holds that $p(v,t_{v})=1$ for some $t_{v}\in[t,t+2d)$. Then there exists
$t^{\prime}\in[t+T_{2}/\vartheta,t+(T_{2}+T_{\text{consensus}})/\vartheta-2d)$
such that $p_{\text{next}}(v,t_{v})\in[t^{\prime},t^{\prime}+2d)$ for all
$v\in G$.

###### Proof.

First, observe that if any node $v\in G$ transitions to pulse at time $t_{v}$,
then node $v$ transitions to state listen in the auxiliary state machine at
time $t_{v}$. To see this, note that node $v$ must have transitioned to output
1 in the auxiliary state machine at time $t_{v}$ in order to satisfy Guard G2
leading to state pulse. Furthermore, once this happens, node $v$ transitions
immediately from output 1 to listen in the auxiliary state machine. Note that
no $v\in G$ transitioned to wait during $(t_{v}-T_{2}/\vartheta,t_{v})$, as
$v$ waits for at least this time before initiating another consensus instance
after transitioning to output 1. Hence, Constraint (3) ensures that no correct
nodes stores any wait messages from other correct nodes in their wait sliding
window buffers. It follows that each $v\in G$ is in state listen at time
$t_{v}$ and cannot leave before time $t+T_{1}/\vartheta$.

Next, note that $v\in G$ will not transition to recover before time
$t_{v}+T_{1}/\vartheta\geq t+3d$ by Guard G1 and Constraint (3). By
assumption, every $u\in G$ transitions to pulse by time $t+2d$, and thus, node
$v$ observes a pulse message from at least $n-f$ correct nodes $u\in G$ by
time $t+3d$. Thus, all correct nodes observe a pulse message from at least
$n-f$ nodes during $[t,t+T_{1}/\vartheta)=[t,t+3d)$ satisfying Guard G1\.
Hence, every correct node $v\in G$ transitions to wait during the interval
$[t+T_{1}/\vartheta,t+T_{1}+2d)$ and remains there until Guard G2 or Guard G2’
is activated. Denote by $t^{\prime}_{v}$ the next transition of $v\in G$ to
output 1 or output 0 after time $t_{v}$ ($t_{v}^{\prime}:=\infty$ if no such
time exists) and set $t^{\prime}:=\min_{v\in G}\\{t_{v}^{\prime}\\}$. Guard
G2’ cannot be activated before time
$\min\\{t^{\prime},t+T_{\text{wait}}/\vartheta\\}$.

Now let us consider the auxiliary state machine. From the above reasoning, we
get that every node $v\in G$ will observe at least $n-f$ nodes transitioning
from pulse to wait during the interval $[t+T_{1}/\vartheta,t+T_{1}+3d)$. As we
have $T_{\text{listen}}/\vartheta\geq(1-1/\vartheta)T_{1}+3d$ by Constraint
(3), both Guard G4 and Guard G5 become satisfied for $v$ during the same
interval. Thus, node $v$ transitions to state input 1 during the interval
$[t+T_{1}/\vartheta,t+T_{1}+3d)$. Here, we use that Guard G3 is not active at
any $v\in G$ that is not in recover, implying that
$t^{\prime}\geq\min\\{t+T_{2}/\vartheta,t+T_{\text{wait}}/\vartheta\\}=t+T_{2}/\vartheta>t+T_{1}+3d$
by Constraint (3) and Constraint (3). Thus, Guard G2’ cannot become active
before time $t+T_{1}+3d$, yielding that each $v\in G$ transitions to read
before Guard G3 can become active. We claim that $v$ transitions to run 1
during
$[t+(T_{1}+T_{2})/\vartheta,t+T_{1}+T_{2}+3d)\subseteq[t+T_{2}/\vartheta,t+T_{2}/\vartheta+\tau)$
by Constraint (3). Assuming otherwise, some $v\in G$ would have to transition
to state wait before time $T_{2}/\vartheta+\tau$. However, $t^{\prime}\geq
T_{2}/\vartheta+\tau$ by Remark 3 and
$t+T_{\text{wait}}/\vartheta=t+(T_{2}+T_{\text{consensus}})/\vartheta>t+T_{2}/\vartheta+\tau$
by Constraint (3) and Constraint (3).

Note that $t+T_{1}+4d<t+T_{2}/\vartheta$ by Constraint (3) and Constraint (3)
and that no correct node transitions to wait again after time $t+T_{1}+3d$
before transitioning to output 1 and spending, by Constraint (3), at least
$T_{1}/\vartheta>2d$ time in pulse. Therefore, we can apply Lemma 7 with
$t_{0}=t+T_{2}/\vartheta$, yielding a time
$t^{\prime}<t+T_{2}/\vartheta+T_{\text{consensus}}/\vartheta-2d$ such that
each $v\in G$ transitions to output 1 in the auxiliary state machine at time
$t^{\prime}_{v}\in[t^{\prime},t^{\prime}+2d)$. This triggers a transition to
pulse in the main state machine. ∎

###  5.5 Ensuring stabilisation

We showed above that if all correct nodes eventually generate a pulse with
skew $2d$, then the pulse synchronisation routine stabilises. In this section,
we show that this is bound to happen. The idea is that if stabilisation does
not take place within a certain interval, then all nodes end up being
simultaneously in state recover in the main state machine and state listen in
the auxiliary state machine, until eventually timeout $T_{\text{active}}$
expires. This in turn allows the “passive” stabilisation mechanism to activate
by having timer $T_{\text{active}}$ expire at every node and stabilise the
system as shown by the lemma below.

######  Lemma 9.

Let $t<T_{\text{active}}/\vartheta$ and $t^{*}=\min_{v\in
G}\\{p_{\text{next}}(v,t)\\}$. Suppose the following holds for every node
$v\in G$:

  * •

node $v$ is in state recover and listen at time $t$, and

  * •

Guard G4 is not satisfied at $v$ during $[t,t^{*}+2d)$,

Then $t^{*}<T_{\text{active}}+\rho+T_{\text{consensus}}/\vartheta$ and every
$v\in G$ transitions to pulse at time $t_{v}\in[t^{*},t^{*}+2d)$.

###### Proof.

Observe that Guard G3 is not satisfied before time
$T_{\text{active}}/\vartheta$. As Guard G4 is not satisfied during
$[t,t^{*})$, no correct node leaves state $T_{\text{listen}}$ before time
$T_{\text{active}}/\vartheta$. Since no $v\in G$ can activate Guard G2 during
$[t,t^{*})$, we have that every $v\in G$ remains in state recover during this
interval. Let $t_{0}\in[T_{\text{active}}/\vartheta,T_{\text{active}}+\rho)$
be the minimal time (after time $t$) when Guard G3 becomes satisfied at some
node $v\in G$. From the properties of the simulation algorithm given in Remark
3, we get that no $w\in G$ transitions away from run 1 before time
$t_{0}+\tau\geq T_{\text{active}}/\vartheta+\tau$.

Since $\tau\geq(1-1/\vartheta)T_{\text{active}}+\rho$ by Constraint (3), we
conclude that no $w\in G$ transitions to output 1 (and thus pulse) before time
$T_{\text{active}}+\rho$. Therefore, each $w\in G$ transitions to run 1 at
some time
$r_{w}\in[T_{\text{active}}/\vartheta,T_{\text{active}}+\rho)\subseteq[t_{0},t_{0}+\tau)$.
Recall that Guard G4 is not satisfied during $[t_{0},t^{*}+2d)$. Hence, we can
apply Lemma 7 to the interval $[t_{0},t_{0}+\tau)$, implying that every $w\in
G$ transitions to output 1 at some time $t_{w}\in[t^{*},t^{*}+2d)$. Thus, each
$w\in G$ transitions from recover to pulse at time $t_{w}$. Finally, Lemma 7
also guarantees that $t^{*}<t_{0}+T_{\text{consensus}}/\vartheta\leq
T_{\text{active}}+\rho+T_{\text{consensus}}/\vartheta$. ∎

We will now establish a series of lemmas in order to show that we can either
apply Lemma 8 directly or in conjunction with Lemma 9 to guarantee
stabilisation. In the remainder of this section, we define the following
abbreviations:

$\displaystyle\alpha$ $\displaystyle=T_{\text{listen}}+d$ $\displaystyle\beta$
$\displaystyle=\alpha+T_{\text{wait}}+\gamma+4T_{1}+3d+2\delta$
$\displaystyle\beta^{\prime}$
$\displaystyle=(T_{\text{active}}-T_{2}-T_{\text{consensus}})/\vartheta$
$\displaystyle\delta$
$\displaystyle=T_{1}+d+2T_{\text{listen}}+T_{2}+T_{\text{consensus}}$
$\displaystyle\gamma$ $\displaystyle=T_{2}/\vartheta-
T_{\text{listen}}-5T_{1}-3d.$

######  Remark 4.

We have that
$\gamma<\delta<\beta\leq\beta^{\prime}<T_{\text{active}}/\vartheta$, where the
inequality $\beta\leq\beta^{\prime}$ is equivalent to Constraint (3).

In the following, we consider the time intervals $[\alpha,\beta]$ and
$[\alpha,\beta^{\prime}]$. We distinguish between two cases and show that in
either case stabilisation is ensured. The cases are:

  * •

no correct node transitions to input 1 during $[\alpha,\beta]$, and

  * •

some correct node transitions to input 1 during $[\alpha,\beta^{\prime}]$.

We start with the latter case.

######  Lemma 10.

Suppose node $v\in G$ transitions to input 1 at time
$t\in[\alpha,\beta^{\prime})$. Then there exists a time
$t^{\prime}\in[t,T_{\text{active}}/\vartheta-2d)$ such that one of the
following holds:

  1. 1.

every $u\in G$ satisfies $p(u,t_{u})=1$ for some
$t_{u}\in[t^{\prime},t^{\prime}+2d)$, or

  2. 2.

every $u\in G$ is in state recover and listen at time $t^{\prime}+2d$ and
Guard G4 is not satisfied at $u$ during $[t^{\prime}+2d,t^{*}+2d]$, where
$t^{*}:=\min_{w\in G}\\{p(w,t^{\prime}+2d)\\}$.

###### Proof.

By Constraint (3), we have $T_{1}/\vartheta>2d$. As $\alpha\leq
t<\beta^{\prime}<(T_{\text{active}}-T_{2})/\vartheta$, we can apply Lemma 6 to
time $t$. Due to Constraint (3), we can apply Lemma 7 with time
$t_{0}=t-T_{\text{listen}}-d+T_{2}/\vartheta$, yielding a time
$t^{\prime}<\beta^{\prime}-T_{\text{listen}}-3d+T_{2}/\vartheta+T_{\text{consensus}}/\vartheta<T_{\text{active}}/\vartheta-2d$
such that each $u\in G$ transitions to the same output state output 0 or
output 1 in the auxiliary state machine at time
$t_{u}\in[t^{\prime},t^{\prime}+2d)$. If this state is output 1, each $u\in G$
transitions to output 1 at time $t_{u}\in[t^{\prime},t^{\prime}+2d)$. This
implies that Guard G2 is activated and $u$ transitions to pulse so that
$p(u,t_{u})=1$. If this state is output 0, Guard G2’ implies that each $u\in
G$ either remains in or transitions to state recover at time $t_{u}$.
Moreover, node $u$ immediately transitions to state listen in the auxiliary
state machine. Finally, note that Lemma 6 also states that Guard G4 cannot be
satisfied again before time $t^{*}+T_{1}/\vartheta>t^{*}+2d$. ∎

######  Corollary 4.

Suppose node $v\in G$ transitions to input 1 at time
$t\in[\alpha,\beta^{\prime}]$. Then there exists
$t^{\prime}<T_{\text{active}}+\rho+T_{\text{consensus}}/\vartheta$ such that
every $u\in G$ satisfies $p(v,t_{u})=1$ for some
$t_{u}\in[t^{\prime},t^{\prime}+2d)$.

###### Proof.

We apply Lemma 10. In the first case of Lemma 10, the claim immediately
follows. In the second case, it follows by applying Lemma 9. ∎

We now turn our attention to the other case, where no node $v\in G$
transitions to input 1 during the time interval $[\alpha,\beta]$.

######  Lemma 11.

If no $v\in G$ transitions to input 1 during $[\alpha,\beta]$, then no $v\in
G$ transitions to state run 1 during $[\alpha+T_{1}+T_{\text{wait}},\beta)$.

###### Proof.

Observe that any $v\in G$ that does not transition to pulse during
$[\alpha,\alpha+T_{1}+T_{\text{wait}}]$ must transition to recover at some
time from that interval once Guard G2’ is satisfied. Note that leaving state
recover requires Guard G2 to be satisfied, and hence, a transition to output 1
in the auxiliary state machine. However, as no node $v\in G$ transitions to
input 1 during $[\alpha,\beta)$, it follows that each $v\in G$ that is in
state input 1 in the auxiliary state machine at time
$t\in[\alpha+T_{1}+T_{\text{wait}},\beta)$ is also in state recover in the
main state machine. Thus, Guard G6 cannot be satisfied. We conclude that no
correct node transitions to state run 1 during the interval
$[\alpha+T_{1}+T_{\text{wait}},\beta)$. ∎

We now show that if Guard G4 cannot be satisfied for some time, then there
exists an interval during which no correct node is participating in or
attempting to simulate a consensus instance.

######  Lemma 12.

Let $t\in(d,\beta-2\delta)$ and suppose Guard G4 is not satisfied during the
interval $[t,t+\gamma]$. Then there exists a time
$t^{\prime}\in[t,\beta-\delta]$ such that no $v\in G$ is in state run 0 or run
1 during $(t^{\prime}-d,t^{\prime}]$.

###### Proof.

Observe that Guard G3 cannot be satisfied before time
$t+\gamma+T_{2}/\vartheta<T_{\text{active}}/\vartheta$ at any correct node,
and by the assumption, Guard G4 is not satisfied during the interval
$[t,t+\gamma]$. We proceed via a case analysis.

First, suppose $v\in G$ is in state listen at time $t$. As Guard G3 or Guard
G4 cannot be satisfied during $[t,t+\gamma]$ node $v$ remains in listen until
time $t+\gamma$. Moreover, if $v$ leaves listen during
$[t+\gamma,t+\gamma+T_{2}/\vartheta]$, it must do so by transitioning to read.
Hence, it cannot transition to run 0 or run 1 before Guard G6, Guard G6’ or
Guard G7 are satisfied. Either way, $v$ cannot reach states run 0 or run 1
before time $t+\gamma+T_{2}/\vartheta$. Hence, in this case, $v$ is not in the
two execution states during
$I_{1}=[t,t+\gamma+T_{2}/\vartheta)=[t,t+2T_{2}/\vartheta-
T_{\text{listen}}-5T_{1}-3d)$.

Let us consider the second case, where $v$ is not in listen at time $t$. Note
that the timer $T_{2}$ cannot be reset at $v$ during the interval
$[t+T_{\text{listen}},t+\gamma]$, as this can happen only if $v$ transitions
to input 0 or input 1 and Guard G4 cannot be satisfied during $[t,t+\gamma]$.
Hence, the only way for this to happen is if $v$ transitions from read to
either input 0 or input 1 during the interval $[t,t+T_{\text{listen}}]$.

It follows that $v$ cannot _transition_ to run 0 or run 1 during the interval
$(t+T_{\text{listen}}+T_{2},t+\gamma+T_{2}/\vartheta)$. Moreover, if $v$
transitions to these states before $t+T_{\text{listen}}+T_{2}$, then $v$ must
transition away from them by time
$t+T_{\text{listen}}+T_{2}+T_{\text{consensus}}$, as Guard G8 or Guard G9
become satisfied. Therefore, node $v$ is in listen, read, input 0 or input 1
during
$I_{2}=[t+T_{\text{listen}}+T_{2}+T_{\text{consensus}},t+\gamma+T_{2}/\vartheta)$.
Applying Constraint (3), we get that

$T_{\text{listen}}+T_{2}+T_{\text{consensus}}<2T_{2}/\vartheta-
T_{\text{listen}}-5T_{1}-4d,$

and hence, by setting
$t^{\prime}=t+T_{\text{listen}}+T_{2}+T_{\text{consensus}}+d<\beta-\delta$, we
get that $(t^{\prime}-d,t^{\prime}]\subseteq I_{1}\cap I_{2}$. That is, in
either case $v$ is not in state run 0 or run 1 during this short interval. ∎

Next, we show that the precondition of the previous lemma will be satisfied in
due time.

######  Lemma 13.

There exists
$t\in[\alpha+T_{1}+T_{\text{wait}}+d,\alpha+4T_{1}+T_{\text{wait}}+3d+\gamma)\subset(d,\beta-2\delta)$
such that Guard G4 is not satisfied during $[t,t+\gamma]$ at any $v\in G$.

###### Proof.

Let
$t^{\prime}\in[\alpha+T_{1}+T_{\text{wait}},\alpha+T_{1}+T_{\text{wait}}+d+\gamma]$
be a time when some $v\in G$ transitions to state wait. If such $t^{\prime}$
does not exist, the claim trivially holds for
$t=\alpha+T_{1}+T_{\text{wait}}+d$. Otherwise, since $t^{\prime}\leq
T_{\text{listen}}+T_{1}+T_{\text{wait}}+2d+\gamma<(T_{\text{active}}-T_{2})/\vartheta$
by Constraint (3), we can apply Lemma 5 to time $t^{\prime}$, which yields
that no $u\in G$ transitions to wait during

$[t^{\prime}+3T_{1}+d,t^{\prime}+T_{2}/\vartheta-2T_{1}-d)=[t-T_{\text{listen}}-d,t+\gamma),$

where $t=t^{\prime}+T_{\text{listen}}+3T_{1}+2d$. Thus, Guard G4 is not
satisfied at any $v\in G$ during $[t,t+\gamma]$. ∎

Using the above statements, we can now infer that if no node transitions to
input 1 for a while, this implies that no node transitions to pulse for a
certain period. Subsequently, we will use this to conclude that then the
preconditions of Lemma 9 are satisfied.

######  Lemma 14.

Suppose no $v\in G$ transitions to input 1 during $[\alpha,\beta]$. Then no
$v\in G$ transitions to pulse during $[\beta-\delta,\beta]$.

###### Proof.

First, we apply Lemma 13 to obtain an interval
$[t,t+\gamma]\subseteq[\alpha+T_{1}+T_{\text{wait}}+d,\beta-2\delta]$ during
which Guard G4 cannot be satisfied at any $v\in G$. Applying Lemma 12 to this
interval yields an interval $(t^{\prime}-d,t^{\prime}]\subset(t,\beta-\delta]$
during which no $v\in G$ is in state run 0 or run 1. This implies that no node
is running a consensus instance during this time interval, and moreover, no
messages from prior consensus instances are in transit to or arrive at any
correct node at time $t^{\prime}$. In particular, any $v\in G$ that (attempts
to) simulate a consensus instance at time $t^{\prime}$ or later must first
reinitialise the simulation by transitioning to run 0 or run 1.

Next, let us apply Lemma 11, to see that no $v$ transitions to run 1 during
the interval $[\alpha+T_{1}+T_{\text{wait}},\beta]\supset[t^{\prime},\beta]$.
Thus, if any node $v\in G$ attempts to simulate $\mathbf{C}$, it must start
the simulation by transitioning to run 0. This entails that any correct node
attempting to simulate $\mathbf{C}$ does so with input 0. Because $\mathbf{C}$
is a silent consensus routine (see Definition 2), this entails that $v$ does
not send any message related to $\mathbf{C}$ unless it receives one from a
correct node first, and in absence of such a message, it will not terminate
with output $1$. We conclude that no $v\in G$ transitions to output 1 during
$[t^{\prime},\beta]\supseteq[\beta-\delta,\beta]$. The claim follows by
observing that a transition to pulse in the main state machine requires a
transition to output 1 in the auxiliary state machine. ∎

######  Lemma 15.

Suppose no $v\in G$ transitions to pulse during $[\beta-\delta,\beta]$. Then
at time $\beta$ every $v\in G$ is in state recover in the main state machine
and state listen in the auxiliary state machine. Moreover, Guard G4 is not
satisfied during $[\beta,t^{*}+2d)$, where $t^{*}=\min_{v\in
G}\\{p_{\text{next}}(v,\beta)\\}$.

###### Proof.

As no $v\in G$ transitions pulse during $[\beta-\delta,\beta]$, either Guard
G1 or Guard G2’ lead each $v\in G$ to recover. More precisely, every $v\in G$
is in state recover of the main state machine during
$[\beta-\delta+T_{1}+T_{\text{wait}},\beta]$. Next, observe that Guard G4 is
not satisfied during $[\beta-\delta+T_{1}+T_{\text{listen}}+d,\beta]$, and
because $\beta<T_{\text{active}}/\vartheta$, Guard G3 cannot be active at any
time from this interval either. It follows that each $v\in G$ is in state
listen of the auxiliary state machine during
$[\beta-\delta+T_{1}+d+2T_{\text{listen}}+T_{2}+T_{\text{consensus}},\beta]=[\beta,\beta]$,
i.e., the first claim of the lemma holds. For the second claim, observe that
Guard G4 cannot be satisfied before the next transition to wait by a correct
node occurs. This cannot happen before $T_{1}/\vartheta$ time has passed after
a correct node transitioned to pulse by Guard G1\. Since $T_{1}/\vartheta>2d$
by Constraint (3), the claim follows. ∎

We can now show that if no input 1 transitions occur during $[\alpha,\beta]$,
then all nodes end up in the recover state in the main state machine before
$T_{\text{active}}$ timeout expires at any node. This will eventually activate
Guard G3 at every correct node, leading to a correct simulation of
$\mathbf{C}$ with all 1 inputs.

######  Corollary 5.

Suppose no $v\in G$ transitions to input 1 during $[\alpha,\beta]$. Then there
exists a time $t<T_{\text{active}}+\rho+T_{\text{consensus}}$ such that every
$v\in G$ transitions to pulse at time $t_{v}\in[t,t+2d)$.

###### Proof.

By Lemma 14 and Lemma 15, the prerequisites of Lemma 9 are satisfied at time
$t=\beta<T_{\text{active}}/\vartheta$. ∎

It remains to show that the constraints in Table 3 can be satisfied for some
$\vartheta>1$ such that all timeouts are in $O(R)$.

######  Lemma 16.

Let $1<\vartheta<(2+\sqrt{32})/7\approx 1.094$. The constraints in Table 3 can
be satisfied with all timeouts in $O(R)$.

###### Proof.

Recall that $R$ is the number of rounds the consensus routine needs to declare
output and $T(R)$ is the time required to simulate the consensus routine. We
parametrize $T_{2}$ and $T_{\text{active}}$ using $X$ and $Y$, where we
require that $X\in\Theta(R)$ is chosen so that $T(R)/X\leq\varepsilon$, for a
constant $\varepsilon>0$ to be determined later. We then can set

$\displaystyle T_{1}$ $\displaystyle:=3\vartheta d$ $\displaystyle
T_{\text{listen}}$ $\displaystyle:=3\vartheta^{2}d$ $\displaystyle T_{2}$
$\displaystyle:=X$ $\displaystyle\tau$
$\displaystyle:=\max\left\\{(1-1/\vartheta)X+(3\vartheta^{2}+9\vartheta+3)d,(1-1/\vartheta)Y+\rho\right\\}$
$\displaystyle T_{\text{consensus}}$
$\displaystyle:=\vartheta(\tau+\varepsilon X)$ $\displaystyle T_{\text{wait}}$
$\displaystyle:=X+T_{\text{consensus}}$ $\displaystyle T_{\text{active}}$
$\displaystyle:=Y,$

immediately satisfying Constraint (3), Constraint (3), Constraint (3),
Constraint (3), and Constraint (3). Moreover, Constraint (3) holds by
requiring that $X$ is at least a sufficiently large constant.

For the remaining constraints, denote by $C(\vartheta,d)$ a sufficiently large
constant subsuming all terms that depend only on $\vartheta$ and $d$ and
abbreviate
$T_{\text{consensus}}^{\prime}:=(\vartheta-1)\max\\{X,Y\\}+\varepsilon\vartheta
X$ (i.e., the non-constant terms of $T_{\text{consensus}}$). To satisfy
Constraint (3), Constraint (3), and Constraint (3), it is then sufficient to
guarantee that

$\displaystyle(2/\vartheta-1)X$
$\displaystyle>T_{\text{consensus}}^{\prime}+C(\vartheta,d)$ $\displaystyle Y$
$\displaystyle\geq
4X+\vartheta(X+T_{\text{consensus}}^{\prime})+C(\vartheta,d)$ $\displaystyle
Y$ $\displaystyle\geq
2X+T_{\text{consensus}}^{\prime}+3\vartheta(X+T_{\text{consensus}}^{\prime})+C(\vartheta,d),$

where the second inequality automatically holds if the third is satisfied. We
also note that $Y\geq X$ is a necessary condition to satisfy the third
inequality, implying that we may assume that
$T_{\text{consensus}}^{\prime}=(\vartheta-1)Y+\varepsilon X$. We rearrange the
remaining inequalities, yielding

$\displaystyle(2/\vartheta-1-\varepsilon)X$
$\displaystyle>(\vartheta-1)Y+C(\vartheta,d)$
$\displaystyle(2+2\vartheta-3\vartheta^{2})Y$
$\displaystyle\geq(2+3\vartheta(1+\varepsilon\vartheta))X+C(\vartheta,d).$ (1)

Recall that $\vartheta$ and $C(\vartheta,d)$ are constant, and $\varepsilon$
is a constant under our control. Hence, these inequalities can be satisfied if
and only if

$\displaystyle(2/\vartheta-1)(2+2\vartheta-3\vartheta^{2})>(2+3\vartheta)(\vartheta-1).$

The above inequality holds for all $\vartheta\in(1,(2+\sqrt{32})/7)$. Note
that, as $\vartheta$, $\varepsilon$, and $C(\vartheta,d)$ are constants, we
can choose $X\in\Theta(R)$ as initially stated, implying that all timeouts are
in $O(R)$, as desired. ∎

######  Corollary 6.

For $\vartheta<(2+\sqrt{32})/7$ and suitably chosen timeouts, in any execution
there exists $t\in O(R)$ such that every $v\in G$ transitions to pulse during
the time interval $[t,t+2d)$.

###### Proof.

We choose the timeouts in accordance with Lemma 16. If no $v\in G$ transitions
to input 1 during $[\alpha,\beta]$, Corollary 5 yields the claim. Otherwise,
some node $v\in G$ transitions to state input 1 during the interval
$[\alpha,\beta]\subseteq[\alpha,\beta^{\prime}]$ and the claim holds by
Corollary 4. ∎

Next, we observe that the accuracy bounds can be set to be within a constant
factor apart from each other.

######  Corollary 7.

Let $\vartheta<(2+\sqrt{32})/7$ and
$\varphi_{0}(\vartheta)=1+5(\vartheta-1)/(2+2\vartheta-3\vartheta^{2})\in
1+O(\vartheta-1)$. For any constant $\varphi>\varphi_{0}(\vartheta)$, we can
obtain accuracy bounds satisfying $\Phi^{+}/\Phi^{-}\leq\varphi$ and
$\Phi^{-},\Phi^{+}\in\Theta(R)$.

###### Proof.

By Lemma 8, the accuracy bounds we get from the constuction are
$\Phi^{-}=T_{2}/\vartheta$ and
$\Phi^{+}=(T_{2}+T_{\text{consensus}})/\vartheta$. Choosing the timeouts as in
the proof of Lemma 16, we get that
$\Phi^{+}/\Phi^{-}=1+(\vartheta-1)Y/X+\varepsilon$, where $\varepsilon$ is an
arbitrarily small constant. Checking Inequality (1), we see that we can choose
$Y/X=(2+3(1+\varepsilon))/(2+2\vartheta-3\vartheta^{2})$. Choosing
$\varepsilon$ sufficiently small, the claim follows. ∎

###  5.6 Proof of Theorem 2

Finally, we are ready to prove the main theorem of this section.

See 2

###### Proof.

By the properties of the resynchronisation algorithm $\mathbf{B}$, we get that
the a good resynchronisation pulse occurs within time $T(\mathbf{B})$. Once
this happens, Corollary 6 shows all correct nodes transition to pulse during
$[t,t+2d)$ for $t\in T(\mathbf{B})+O(R)$. By Lemma 8 we get that the algorithm
stabilises by time $t$ and has skew $\sigma=2d$. From Corollary 7 we get that
the accuracy bounds can be set to be within factor $\varphi$ apart without
affecting the stabilisation time asymptotically.

To analyse the number of bits sent per time unit, first observe that the main
state machine communicates whether a node transitions to pulse or wait. This
can be encoded using messages of size $O(1)$. Moreover, as node remains
$\Omega(d)$ time in pulse or wait, the main state machine sends only $O(1)$
bits per time unit. Second, the auxiliary state machine does not communicate
apart from messages related to the simulation of consensus. The non-self-
stabilising pulse synchronisation algortihm sends messages only when a node
generates a pulse and the time between pulses is $\Omega(d)$. Thus, while
simulating $\mathbf{C}$, each node broadcasts at most $M(\mathbf{C})+O(1)$
bits per time unit. ∎

##  6 Resynchronisation algorithms

In this section, we give the second key component in the proof of Theorem 1.
We show that given _pulse synchronisation_ algorithms for networks of small
size and with low resilience, it is possible to obtain _resynchronisation_
algorithms for large networks and with high resilience. More precisely, we
show the following theorem.

See 3

###  6.1 The high-level idea

Our goal is to devise a self-stabilising resynchronisation algorithm with skew