# Optimal Clock Synchronization with Signatures

Christoph Lenzen<EMAIL_ADDRESS>and  Julian Loss<EMAIL_ADDRESS>CISPA
Helmholtz Center for Information SecurityGermany

(2018)

###### Abstract.

Cryptographic signatures can be used to increase the resilience of distributed
systems against adversarial attacks, by increasing the number of faulty
parties that can be tolerated. While this is well-studied for consensus, it
has been underexplored in the context of fault-tolerant clock synchronization,
even in fully connected systems. Here, the honest parties of an $n$-node
system are required to compute output clocks of small skew (i.e., maximum
phase offset) despite local clock rates varying between $1$ and $\vartheta>1$,
end-to-end communication delays varying between $d-u$ and $d$, and the
interference from malicious parties. So far, it is only known that clock
pulses of skew $d$ can be generated with (trivially optimal) resilience of
$\lceil n/2\rceil-1$ (ADDNR19, ), improving over the tight bound of $\lceil
n/3\rceil-1$ holding without signatures for _any_ skew bound (DHS84, ; ST85,
). Since typically $d\gg u$ and $\vartheta-1\ll 1$, this is far from the lower
bound of $u+(\vartheta-1)d$ that applies even in the fault-free case (BW01, ).

We prove matching upper and lower bounds of $\Theta(u+(\vartheta-1)d)$ on the
skew for the resilience range from $\lceil n/3\rceil$ to $\lceil n/2\rceil-1$.
The algorithm showing the upper bound is, under the assumption that the
adversary cannot forge signatures, deterministic. The lower bound holds even
if clocks are initially perfectly synchronized, message delays between honest
nodes are known, $\vartheta$ is arbitrarily close to one, and the
synchronization algorithm is randomized. This has crucial implications for
network designers that seek to leverage signatures for providing more robust
time. In contrast to the setting without signatures, they must ensure that an
attacker cannot easily bypass the lower bound on the delay on links with a
faulty endpoint.

††copyright: acmcopyright††journalyear: 2018††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation email; June 03–05, 2018; Woodstock, NY

##  1\. Introduction

Synchronizing clocks is a key task in distributed systems, which received
extensive attention over the years. Given that distributed systems are prone
to faults and attacks, a sizeable fraction of this literature is dedicated to
studying _fault-tolerant_ clock synchronization. Under faults, the question
whether clocks can be synchronized has a fundamental impact: A message passing
system prone to crash faults can simulate synchronous execution if and only if
communication delay satisfies a known bound and time can be locally
approximately measured. If either assumption fails to hold, the FLP proof of
impossibility of deterministic consensus applies (FLP85, ). Conversely, if
both assumptions hold, a network synchronizer (A85, ) can be implemented by
detecting crash faults via timeout. At the same time, these conditions are
necessary and sufficient to compute logical clocks of bounded _skew,_ i.e.,
bounded maximum difference of concurrent clock readings, on each connected
component of the network.

Naturally, assuming crash faults is too optimistic in practice. However, for
any less benign fault model, the situation is similar. On the one hand, from
the above we know that it is necessary to have bounded delay and a local sense
of the progress of time to be able to simulate synchronous execution. On the
other hand, these assumptions imply that if we are given a synchronizer, (i)
it is guaranteed to complete simulation of a round within bounded time and
(ii) we can enforce an arbitrarily large minimum duration of each simulated
round (by letting nodes sleep for some time). Intuitively, this allows us to
solve the clock synchronization task by using the current round number as
“target” logical clock value and from this compute logical clocks of bounded
skew and rates by interpolation (this intuition is formalized in (Lec21, , Ch.
9, Sec. 3.3.4)).

In light of the above, the task of clock synchronization can be seen as a more
general and precise version of running a synchronizer (A85, ):

  * •

Logical clocks with bounded skew and rates of progress can be readily used to
implement a synchronizer. The maximum duration of a simulated round then is
$r(d+\mathcal{S})$, where $r$ is the ratio between maximum and minimum clock
rate, $d$ is the (maximum) communication delay, and $\mathcal{S}$ is (the
bound on) the skew.

  * •

In contrast to a synchronizer, clocks can also be used to coordinate actions
in terms of real time.

Note that both of these application scenarios share the property that
controlling the rates of the computed logical clocks as well as their skew as
precisely as possible matters.

To understand how well clocks can be synchronized under realistic faults or
even malicious interference, the research community studied the clock
synchronization task in the presence of Byzantine (i.e., worst-case) faults.
In striking similarity to consensus (LSP82, ), it is possible to synchronize
clocks in a fully connected message passing system with authenticated channels
if and only if the number of Byzantine faults is strictly less than one third
(ST85, ; DHS84, ). This is good news: one can run synchronous consensus on top
of clock synchronization, without any negative impact on resilience! Even
better, this is also true with respect to performance: the same asymptotic
bounds on skew can be achieved as in the fault-free case, without any loss in
resilience (BW01, ; LL84, ).

Concretely, denote by $d-u$ the _minimum_ communication delay, i.e., the time
between a message being sent and the receiving node completing to process it
is between $d-u$ and $d$, and let $\vartheta>1$ be the maximum rate of the
local reference clocks, whose minimum rate we normalize to $1$. The main
result of (LL84, ) can then be read as saying that $\mathcal{S}\in
O(u+(\vartheta-1)d)$ and $r\in 1+O(\vartheta-1)$ can be achieved, so long as
$\vartheta<\vartheta_{0}$ for a constant $\vartheta_{0}$ and strictly less
than one third of the nodes are faulty, cf. (KL18, ). This means that using
the computed clocks to simulate synchronous execution, each simulated round
takes $r(d+\mathcal{S})\in d+O(u+(\vartheta-1)d)$ time. Given that in practice
$u\ll d$ and $\vartheta-1\ll 1$, we have that $d+O(u+(\vartheta-1)d)\approx
d$. In other words, synchrony can be simulated with negligible overhead in
time!

For these theoretical results to be of practical value, it is paramount to
minimize the overheads incurred by achieving fault-tolerance. While the
resilience bound is tight under the assumption of authenticated channels, it
is a well-known result that when _messages_ are authenticated, consensus can
be achieved in a fully connected system when up to $\lceil n/2\rceil-1$ nodes
are faulty (DS83, ). Indeed, also when synchronizing clocks the resilience can
be boosted to $\lceil n/2\rceil-1$ by authenticating broadcasts (ST85, ;
HSSD84, ). However, these algorithms have skew $\Theta(d)\gg u$. This begs the
question

> _“Which skew can be obtained with signatures at optimal resilience $\lceil
> n/2\rceil-1$?”_

### Our Contribution

In this work, we show that the answer to this question is nuanced. To obtain
an asymptotically optimal upper bound on the achievable skew, we set out on
the track that readers familiar with the literature might expect. The
algorithm from (LL84, ) is based on simulating iterations of synchronous
_approximate agreement._

###### Definition 1 (Approximate Agreement).

Let $\Pi$ be protocol executed among $n$ nodes where each node $v$ holds an
input $r_{v}\in\mathbb{R}$ and nodes terminate upon generating an output
$o_{v}\in\mathbb{R}$. Denoting by $\mathcal{H}$ the set of honest nodes, we
say that $\Pi$ is a _$(\ell,\epsilon,f)$ -secure protocol for approximate
agreement_ if the following properties hold whenever at most $f$ nodes are
corrupted and $\max_{v,w\in\mathcal{H}}\\{r_{v}-r_{w}\\}\leq\ell$:

  * •

$\epsilon$-Consistency:
$\max_{v,w\in\mathcal{H}}\\{o_{v}-o_{w}\\}\leq\epsilon$.

  * •

Validity: For all all $v\in\mathcal{H}$,
$\min_{w\in\mathcal{H}}\\{r_{w}\\}\leq
o_{v}\leq\max_{w\in\mathcal{H}}\\{r_{w}\\}$.

Without signatures, this task can be solved if and only if fewer than one
third of the nodes are faulty (DLPSW86, ; FLM85, ). The reason is that faulty
nodes might claim different inputs to different nodes. Signatures can overcome
this by being able to prove to others which input a sender claimed. While
achieving consensus on inputs might take a non-constant number of rounds even
with randomization, for approximate agreement it is sufficient that at most
one value from each sender is accepted by correct nodes. This is easily
achieved by outputting “$\bot$” – no value – if another node proved to receive
a conflicting value. The resulting relaxed variant of reliable broadcast is
referred to as _crusader broadcast_ in the literature (D82, ).

We show that when communication is by crusader broadcast, approximate
agreement can be solved in a logarithmic number of rounds with resilience
$\lceil n/2\rceil-1$.

###### Corollary 2.

There is an $(\ell,\epsilon,\lceil n/2\rceil-1)$-secure protocol for
approximate agreement running in $2\lceil\log(\ell/\epsilon)\rceil$ rounds.

In contrast to standard approximate agreement, for synchronization purposes
the crucial “content” of the messages is their _timing._ With message delays
between $d-u$ and $d$, we can simulate crusader broadcast in a timed fashion,
which allows each node to estimate the offset between its own and other
correct nodes in the system with an error of $O(u+(\vartheta-1)d)$. The
property that faulty nodes communicate no different values then is relaxed,
too, in that if two correct nodes accept a broadcast from the same sender,
then their respective reception times agree up to $O(u+(\vartheta-1)d)$.

With this subroutine in place, we can adapt the algorithm from (LL84, ) by
replacing plain broadcasts by (simulated) crusader broadcasts and adjusting
clocks in accordance with the more resilient approximate agreement algorithm
with signatures. The algorithm solves so-called _pulse synchronization_ ,
which (up to minor order terms) is equivalent to computing logical clocks of
small skew and bounded rates at all times, cf. (Lec21, , Ch. 9, Sec. 3.3.3 and
3.3.4).

###### Definition 3 (Pulse Synchronization).

Let $\Pi$ be a protocol executed among $n$ nodes, where the set of honest
nodes is $\mathcal{H}$. We say that $\Pi$ is an _$f$ -secure protocol for
pulse synchronization with skew $\mathcal{S}$, minimum period
$P_{\mathsf{min}}>0$, and maximum period $P_{\mathsf{max}}$_ if the following
properties hold whenever at most $f$ nodes are corrupted:

  * •

Liveness: for all $i\in\mathbb{N}_{>0}$ and each node $v\in\mathcal{H}$, $v$
outputs pulse $i$ exactly once. We denote $p_{v,i}$ as the time where $v$
outputs its $i$th pulse.

  * •

$\mathcal{S}$-bounded skew:
$\sup_{i\in\mathbb{N}_{>0},v,w\in\mathcal{H}}\\{|p_{v,i}-p_{w,i}|\\}\leq\mathcal{S}$

  * •

$P_{\mathsf{min}}$-minimum period:
$\inf_{i\in\mathbb{N}}\\{\min_{v\in\mathcal{H}}\\{p_{v,i+1}\\}-\max_{v\in\mathcal{H}}\\{p_{v,i}\\}\\}\geq
P_{\mathsf{min}}$.

  * •

$P_{\mathsf{max}}$-maximum period:
$\sup_{i\in\mathbb{N}_{>0}}\\{\max_{v\in\mathcal{H}}\\{p_{v,i+1}\\}-\min_{v\in\mathcal{H}}\\{p_{v,i}\\}\\}\leq
P_{\mathsf{max}}$.

In case of a randomized algorithm, the skew bound is allowed to depend on the
randomness of the algorithm; $\mathcal{S}$ is then defined as the expected
worst-case value, where the expectation is taken over the randomness of the
algorithm.

corollarysync If $\vartheta\leq 1.11$, there are choices $T\in\Theta(d)$ and
$S\in\Theta(u+(\vartheta-1)d)$ such that Algorithm 3 is a $(\lceil
n/2\rceil-1)$-secure pulse synchronization protocol with skew $S$, minimum
period $P_{\min}\in\Theta(d)$ and maximum period $P_{\max}\in
P_{\min}+\Theta(S)$.

Since this skew bound is asymptotically optimal even without faults (BW01, ),
at first glance it might appear that this settles our above question. However,
there is a crucial difference to the signature-free setting. For the above
result, it is necessary that also _faulty_ nodes must obey the minimum message
delay of $d-u$, both when receiving and sending messages. Otherwise, they
could obtain and send a signature used by a correct sender in a crusader
broadcast so early that correct nodes reject the sender’s broadcast. This is
in stark contrast to the algorithm from (LL84, ), for which faulty nodes can
have full information of the system state at all times, including the future!

Given that it might be very challenging or even impossible for system
designers to guarantee that an attacker must obey a minimum communication
delay of $d-u$ for $u\ll d$, we need to determine whether this limitation is
inherent. Perhaps surprisingly, we prove that this is indeed the case, by
providing a matching lower bound. If either messages to or from faulty nodes
have delays from $[d-\tilde{u},d]$ for some $\tilde{u}\in[u,d]$, then we can
prove a lower bound of $\Omega(\tilde{u})$ on the skew, regardless of $u$.
theoremlb Let $n\geq 3$ and $\Pi$ be an $\lceil n/3\rceil$-secure protocol for
pulse synchronization with skew $S$. Then $\mathbb{E}[S]\geq 2\tilde{u}/3$.
Since a lower bound of $(\vartheta-1)d$ follows from a simple
indistinguishability argument even in absence of faults, we hence establish an
asymptotically tight bound of $\Theta(\tilde{u}+(\vartheta-1)d)$ on the skew
that can be achieved when the number of faults is at least $n/3$. We stress
that Definition 3 imposes no restrictions on $\Pi$, which might be randomized,
holds under perfect initial synchronization, for arbitrarily small
$\vartheta-1$ and $u=0$, and our adversary is static, i.e., chooses which
nodes to corrupt upfront. In other words, all the typical loopholes one might
try to exploit to improve on our upper bound result are unavailable, implying
asymptotic optimality of its skew in a strong sense.

#### Organization of this article.

In Section 2, we specify our model and cover some preliminaries, including
synchronous approximate agreement with resilience $\lceil n/2\rceil-1$. In
Section 3, we provide and analyze our Crusader Pulse Synchronization
algorithm. Section 4 proves the lower bound. Due to space constraints,
discussion of further related work, a synchronous Crusader Broadcast
algorithm, and some proofs are deferred to Appendices A, B, and C,
respectively.

##  2\. Preliminaries and Model

We consider a network of $n$ nodes connected by pairwise, authenticated
channels. An unknown subset of the nodes is faulty or even malicious; we
denote by $\mathcal{H}$ the set of the remaining honest nodes. We also assume
that nodes have established a _public key infrastructure (PKI)_. This means
that every node $v$ has a _public key $\mathsf{pk}_{v}$_ that all other nodes
agree on. Any honest node is also assumed to hold a matching _secret key
$\mathsf{sk}_{v}$_ with which it can create a _signature $\left<m\right>_{v}$_
on a message $m$ via
$\left<m\right>_{v}\leftarrow\mathsf{Sign}(\mathsf{sk}_{v},m)$. A signature
can be verified via $\mathsf{Verify}(\mathsf{pk}_{v},\left<m\right>_{v},m)$,
which returns a bit 0 _(invalid)_ or 1 _(valid)_. Therefore, we assume that a
signature with respect to $\mathsf{pk}_{v}$ on any message $m$ is impossible
to create without knowledge of $\mathsf{sk}_{v}$. We also assume _perfect
correctness_ : for any message $m\in\\{0,1\\}$,
$\mathsf{Verify}(\mathsf{pk}_{v},\mathsf{Sign}(\mathsf{sk}_{v},m),m)=1$.

Assumptions on the Network. We use a continuous notion of time; thus time
takes values in $\mathbb{R}_{\geq 0}$. We assume a fully connected network
with known minimum and maximum delays of $d-u$ and $d$, respectively. This
means that any message sent to or from an honest node is delivered after at
most $d$ time and no faster than $d-u$ time, where $d$ and $u$ are known
parameters. We refer to $u$ as the _uncertainty_. When proving our lower
bound, we will allow for the possibility that messages to and from faulty
nodes might violate the minimum delay bound of $d-u$ and instead satisfy only
a weaker bound of $d-\tilde{u}$ for some $\tilde{u}\in[u,d]$. Note that we
assume that the network is fault-free, since we are free to map link failures
to node failures. Finally, we assume that only finitely many messages are sent
in finite time; this must clearly be satisfied in any real-world network and
it simplifies our lower bound construction by enabling us to perform induction
over the messages sent by the honest parties executing an arbitrary, but fixed
algorithm.

Hardware Clocks and Clock Rate. Nodes have no access to the “true” time
$t\in\mathbb{R}_{\geq 0}$. Instead, each node $v$ can measure the progress of
time approximately via its _hardware clock._ The hardware clock of node $v$ is
modelled by a function $H_{v}\colon\mathbb{R}_{\geq
0}\longrightarrow\mathbb{R}_{\geq 0}$ which the node can evaluate at any point
in time. That is, $H_{v}$ maps time $t\in\mathbb{R}_{\geq 0}$ to a _local
time_ $H_{v}(t)\in\mathbb{R}_{\geq 0}$. We assume that hardware clocks run at
rates between $1$ and $\vartheta$ for a known constant $\vartheta>1$, i.e.,
for all $t^{\prime}\geq t\in\mathbb{R}_{\geq 0}$, it holds that

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

Furthermore, we assume some degree of initial synchrony, represented by
bounding $\max_{v,w\in\mathcal{H}}\\{|H_{v}(0)-H_{w}(0)|\\}$. For simplicity,
we assume this bound to equal $S$ when showing our upper bound; our lower
bound result holds under the assumption of perfect initial synchrony, i.e.,
$H_{v}(0)=H_{w}(0)$ for all $v,w\in\mathcal{H}$.

Adversary and Executions. The adversary is in full control of message delays
and hardware clocks within the bounds specified by the model. That is, the
adversary specifies arbitrary hardware clock functions and message delays
subject to the above constraints. Our algorithm is resilient to any adversary
that cannot forge signatures, i.e., it is deterministically correct under this
assumption. On the other hand, our lower bound holds for a static adversary
that decides which nodes to corrupt upfront. The adversary may use corrupted
nodes’ secrets to generate signatures for them, but needs to obtain signatures
of honest nodes affecting a message it intends to send before it can generate
the message. Apart from this restriction, the adversary fully controls the
behavior of faulty nodes.

Formally, an _execution_ is fully specified by determining $\mathcal{H}$,
$H_{v}$ for each $v\in\mathcal{H}$, which messages faulty nodes send and when,
and the delays of all messages. An execution is _well-defined_ , i.e.,
conforms with our model, if these parameters specify the above specification
and for each message $m$ sent by a faulty node at time $t$, it receives all
messages $m^{\prime}$ containing signatures from honest nodes that $m$ depends
on, some faulty node received a message $m^{\prime\prime}$ with the same
signature by time $t$.111In our lower bound construction, we simply guarantee
that the faulty sender of $m$ receives $m^{\prime}$ by time $t$.

Synchronous Execution and Rushing Adversary. For the sake of clarity of
presentation, we use a classic synchronous model in our description and
analysis of our solution to the approximate agreement problem. That is,
computation proceeds in compute-send-receive rounds, and the goal is to
complete the task in as few communication rounds as possible. While working in
the synchronous model, we also assume a rushing adversary that can immediately
observe honest nodes’ messages in any given round and choose its own messages
based on them. However, since our goal is to synchronize clocks in the above
model, we will later show how to overcome this assumption in our main
synchronization protocol.

Crusader Broadcast. In the synchronous setting, we assume a subroutine
implementing Crusader Broadcast to be available.

###### Definition 1 (Crusader Broadcast).

Let $\Pi$ be protocol executed among $n$ nodes where a designated dealer $v$
holds an input $b_{v}\in\\{0,1\\}$ and nodes terminate upon generating an
output $o_{v}\in\\{0,1,\bot\\}$. We say that $\Pi$ is an _$f$ -secure protocol
for crusader agreement_ if the following holds whenever at most $f$ nodes are
corrupted:

  * •

Validity: If $v\in\mathcal{H}$, then $o_{w}=b_{v}$ for all $w\in\mathcal{H}$.

  * •

Crusader Consistency: If $o_{u}\in\\{0,1\\}$ for some $u\in\mathcal{H}$, then
for all $w\in\mathcal{H}$, $o_{w}\in\\{\bot,o_{u}\\}$.

For completeness, Appendix B lists Algorithm $\mathsf{CB}$ implementing
crusader broadcast with signatures in, whose correctness is shown in (Dolev82,
).

###  2.1. Approximate Agreement with Signatures

In this section, we describe a simple synchronous $2$-round
$(\ell,\ell/2,\lceil n/2\rceil-1)$-secure approximate agreement algorithm,
where we describe the protocol from the view of node $v$ with input $r_{v}$
and $\ell$ denotes the initial range of honest nodes’ values. Note that a
$(\ell,\epsilon,\lceil n/2\rceil-1)$-secure approximate agreement algorithm
follows immediately by repeating the algorithm $\lceil\log\ell/\epsilon\rceil$
times, feeding the output of the previous iteration as input into the new
instance.

The algorithm is given in Figure 1. Intuitively, its correctness follows from
the facts that (i) nodes always discard enough values to ensure that the
remaining ones lie within input range, where any received $\bot$ guarantees
that the respective sender is faulty and does not contribute to the list of
received non-$\bot$ values and (ii) the intervals spanned by the remaining
values must intersect, implying that their midpoints can only be $\ell/2$
apart.

Algorithm $\mathsf{APA}$ • $v$ sends $r_{v}$ to all nodes using (an instance
of) Algorithm $\mathsf{CB}$ • Denote $r_{w}$ the value received from $w$
(which might be $\bot$). Determine $o_{v}$ as follows: – Denote $b$ as the
number of $\mathsf{CB}$ instances that output $\bot$ in the previous step. –
Sort all the non-$\bot$ values received via the instances of $\mathsf{CB}$ in
the previous step, then discard the lowest $f-b$ and the highest $f-b$ of
those values. Denote $I$ the interval spanned by the remaining values. –
Output the midpoint $o_{v}$ of $I$.

Figure 1.  A synchronous $2$-round $(\ell,\ell/2,f)$-secure algorithm for
approximate agreement, where $f=\lceil n/2\rceil-1$.

The first point is immediate from the properties of crusader broadcast. To
show the second point, we argue as follows. First, observe that if there are
no $\bot$-values received by honest parties, all of them have the same lists
and, trivially, retain the same interval. Second, a node receiving a
$\bot$-value can only increase the interval it retains, allowing us to extend
this statement by induction on the number of $\bot$ values received by honest
parties to all executions.

We now formalize this intuition. To this end, we denote as
$I_{v}:=[a_{v},b_{v}]$ the interval spanned by the remaining values received
by node $v\in\mathcal{H}$ in the first step (i.e., the ones that remain after
discarding the highest and lowest values for that iteration). For any
execution of the protocol in which some $v\in\mathcal{H}$ receives at least
one $\bot$ value and any $x\in\mathbb{R}$, we denote by
$\tilde{I}^{x}_{v}=[\tilde{a}_{v},\tilde{b}_{v}]$ the interval $I_{v}$ that
results from an alternative execution of the protocol in which $v$ receives
identical messages except that one of the $\bot$ values is replaced by $x$.

###### Lemma 2.

For all $x\in\mathbb{R}$ and all $v\in\mathcal{H}$,
$\tilde{I}^{x}_{v}\subseteq I_{v}$.

###### Proof.

Fix an arbitrary node $v\in\mathcal{H}$ receiving at least one $\bot$ value.
For $0<b\leq f$, denote by $r^{1}_{v},...,r^{n-k}_{v}$ the $n-b$ non-$\bot$
values that $v$ receives in this iteration and assume they are ordered in
ascending fashion. Similarly, denote by
$\tilde{r}^{1}_{v},...,\tilde{r}^{n-k+1}_{v}$ the corresponding values in the
alternative execution in which in addition $x$ is received by $v$. Because the
second list is identical to the old one except for exactly one additional
value, we have for all $1\leq j\leq n-b$ that $\tilde{r}^{j}_{v}\leq
r^{j}_{v}\leq\tilde{r}^{j+1}_{v}$. In particular,

$\tilde{a}_{v}=\tilde{r}_{v}^{f-(b-1)+1}\geq r_{v}^{f-b+1}=a_{v}$

and

$\tilde{b}_{v}=\tilde{r}_{v}^{n-(f-(b-1))}\leq r_{v}^{n-(f-(b-1))}\leq
r_{v}^{n-(f-b)}=b_{v},$

i.e.,
$\tilde{I}^{x}_{v}=[\tilde{a}_{v},\tilde{b}_{v}]\subseteq[a_{v},b_{v}]=I_{v}$.
∎

###### Lemma 3.

There exists $x\in\mathbb{R}$ such that $x\in I_{v}$ for all
$v\in\mathcal{H}$.

###### Proof.

We prove the claim by induction over the total number $k$ of $\bot$ values
received by honest nodes.

  * •

base case: Suppose that $k=0$. Thus, for all $v,w\in\mathcal{H}$,
$I_{v}=I_{w}$ by crusader consistency of $\mathsf{CB}$. Since $f=\lceil
n/2\rceil-1$, each node retains at least one value, i.e., this interval is
non-empty.

  * •

step from $k$ to $k+1$: Suppose the claim holds for $k\in\mathbb{N}$. By the
induction hypothesis, there is $x\in\mathbb{R}$ such that $x\in I_{v}$ for all
$v\in\mathcal{H}$. Consider an alternative execution in which all nodes
receive the same messages except that for some honest node $w$, one of its
values is replaced by $\bot$. Denote by $\tilde{I}_{v}$, $v\in\mathcal{H}$,
the intervals in this new execution. For each honest node $v\neq w$, we have
that $x\in I_{v}=\tilde{I}_{v}$. For $w$, we have that $x\in
I_{w}\supseteq\tilde{I}_{w}$ by Lemma 2.

Since this construction applies for any inputs $r_{v}$, $v\in\mathcal{H}$, and
we imposed no restrictions on the values received from faulty nodes, the claim
of the lemma follows for all executions of the algorithm. ∎

###### Theorem 4.

Algorithm 1 is an $(\ell,\ell/2,\lceil n/2\rceil-1)$-secure $2$-round protocol
for approximate agreement.

###### Proof.

Without loss of generality, we order the inputs of the honest nodes in
ascending order. As there are at most $f=\lceil n/2\rceil-1$ corrupted nodes
and $\mathsf{CB}$ has validity, we have that $r_{1}\leq a_{v}$ and
$r_{n-f}\geq b_{v}$ for all $v\in\mathcal{H}$. Hence, $o_{v}=(a_{v}+b_{v})/2$
satisfies the validity condition of approximate agreement.

By Lemma 3, there is $x\in\mathbb{R}$ such that $x\in I_{v}=[a_{v},b_{v}]$ for
all $v\in\mathcal{H}$. For all $v,w\in\mathcal{H}$, we can hence infer that

$o_{v}-o_{w}=\frac{a_{v}+b_{v}-a_{w}-b_{w}}{2}\leq\frac{x+r_{n-f}-r_{1}-x}{2}=\frac{r_{n-f}-r_{1}}{2}\leq\frac{\ell}{2}.\qed$

Corollary 2 readily follos by inductive application of Theorem 4, where the
output of the $i$-th run is used as input for the $(i+1)$-th run.

##  3\. Crusader Pulse Synchronization

In this section, we provide and prove correct our pulse synchronization
algorithm. In analogy to the classic algorithm by Lynch and Welch (LL84, )
that achieves asymptotically optimal skew in the signature-free setting, the
algorithm can be viewed as simulating iterations of synchronous approximate
agreement. The goal is to agree on the pulse times, i.e., pull them closer
together despite interference from faulty nodes.

There are two notable differences from running “plain” approximate agreement.
One is that the goal is to agree on (real) times, which cannot directly be
accessed by the nodes. This results in the algorithm using communication and
the hardware clocks to estimate the _differences_ between pulse times. Because
these measurements are inexact and clocks drift, the second difference
emerges: while approximate agreement works towards decreasing the error in
each iteration, (in the worst case) these inaccuracies in the nodes’
perception work towards increasing them.

In the following, assume parties are running an algorithm for pulse
synchronization, where $\vec{p}_{r}$ denotes the pulse times of honest parties
for the $r$th pulse.222Since a priori there is no formal guarantee that
$v\in\mathcal{H}$ will indeed generate all pulses, one can define
$p_{v}^{r}:=\infty$ if $v$ generates fewer than $r$ pulses. However, our
inductive proof does not need to reason about $p_{v,r+1}$ before it is
established that it is finite. We define
$\|\vec{p}_{r}\|:=\max_{v\in\mathcal{H}}\\{p_{v}^{r}\\}-\min_{v\in\mathcal{H}}\\{p_{v}^{r}\\}$.
Denote by $S$ the upper bound on $\|\vec{p}_{r}\|$ for all $r\in\mathbb{N}$
that we are going to show. Note that the algorithm is allowed to make use of
$S$, even though we will be able to determine $S$ only once our analysis is
complete.

###  3.1. Timed Crusader Broadcast

Before presenting the full algorithm, let us discuss how estimates of clock
offsets can be obtained that comply with the requirements of (our simulation
of) Algorithm $\mathsf{APA}$. Intuitively, instead of communicating the
(unknown) pulse times, each node $v\in\mathcal{H}$ will broadcast (up to a
small, fixed local time offset) when locally generating its pulse. Knowing
that these messages are underway for about $d$ time, each recipient
$w\in\mathcal{H}$ can then determine an approximation of $\Delta_{v,w}^{r}$ of
$p_{w}^{r}-p_{v}^{r}$ of error $O(u+(\vartheta-1)d)$.

In order for these estimates to be used in the simulation of Algorithm
$\mathsf{APA}$, we need them to satisfy a timed analogon of Crusader
Consistency. In the absence of any error, this would mean that for any two
honest parties $v,w\in\mathcal{H}$ and (possibly faulty) node
$x\in\mathcal{H}$ such that $\Delta_{v,x}^{r},\Delta_{w,x}^{r}\neq\bot$, it
holds that $\Delta_{v,x}^{r}-\Delta_{w,x}^{r}=p_{w}^{r}-p_{v}^{r}$. Under this
condition, the estimates $p_{v}^{r}+\Delta_{v,x}^{r}$ and
$p_{w}^{r}+\Delta_{w,x}^{r}$ are equal, i.e., it is as if faulty node $x$ had
broadcast to a subset of the honest nodes at some specific time $p_{x}^{r}$
that each $v\in\mathcal{H}$ with $\Delta_{v,x}^{r}\neq\bot$ agrees on.
Naturally, we cannnot ensure such an exact match, but signatures give us the
possibility to prove reception time up to an error of $O(u+(\vartheta-1)d)$.
By rejecting the broadcast message from node $x$ if another node proves to
have received the same “broadcast” more than $u$ (real) time earlier, we can
hence ensure the above consistency condition up to an error of
$O(u+(\vartheta-1)d)$. The protocol ensuring these guarantees is given in
Figure 2.

Algorithm $\mathsf{TCB}^{r}$ We describe the protocol from the view of node
$v$, where $w$ is the dealer. • If $v$ is the dealer, i.e., $v=w$, $v$ sends
$\left<r\right>_{v}$ to all nodes at local time
$H_{v}(p^{r}_{v})+\vartheta\cdot S$ and terminates. • If $v$ is not the
dealer, i.e., $v\neq w$: – If no correctly formed signature
$\left<r\right>_{w}$ is received from $w$ at a local time
$h\in(H_{v}(p^{r}_{v}),H_{v}(p^{r}_{v})+\vartheta(d+(\vartheta+1)S))$,
terminate with output $\bot$. – Otherwise, denote by $h$ the first such local
time. Forward $\left<r\right>_{w}$ to all nodes at time $h$. – If $v$ receives
a correctly formed signature $\left<r\right>_{w}^{\prime}$ at a local time
$h^{\prime}\in(H_{v}(p^{r}_{v}),h+d-2u)$ from a node $x\neq w$, it terminates
with output $\bot$. – Otherwise, $v$ terminates with output $h$ at local time
$h+d-2u$.

Figure 2.  Timed Crusader Broadcast. The routine assumes that
$\|\vec{p}_{r}\|\leq S$, where $p^{r}_{v}$ is the time at which $v$ generates
the $r$th pulse. Encoding $r\in\mathbb{N}$ allows to distinguish instances,
which ensures that faulty nodes cannot reuse “old” signatures to disrupt an
instance.

We now formalize the above claims. We first establish that honest dealers’
messages are always accepted, i.e., recipients will output their local
reception time, which corresponds to validity of Crusader Broadcast.

###### Lemma 1.

Let $r\in\mathbb{N}$ and suppose that $\|\vec{p}^{r}\|\leq S$. Then for all
$v,w\in\mathcal{H}$, $v$ outputs $h\neq\bot$ in $\mathsf{TCB}^{r}$ with $w$ as
the sender.

###### Proof.

We begin by proving that $w$’s signature is received by $v$ at a local time
$h\in(H_{v}(p^{r}_{v}),H_{v}(p^{r}_{v})+\vartheta(d+(\vartheta+1)S))$. Denote
by $t_{w}$ the (unique) time at which $w$ sends $\left<r\right>_{w}$ and let
$t_{v}\in[t_{w}+d-u,t_{w}+d]$ be the time at which $v$ receives it. We observe
that

$\displaystyle S=\frac{H_{w}(t_{w})-H_{w}(p_{w}^{r})}{\vartheta}\leq
t_{w}-p_{w}^{r}\leq H_{w}(t_{w})-H_{w}(p_{w}^{r})=\vartheta S.$

Hence,

$\displaystyle H_{v}(t_{v})\geq
H_{v}(t_{w})=H_{v}(t_{w})-H_{v}(p_{v}^{r})+H_{v}(p_{v}^{r})\geq
t_{w}-p_{v}^{r}+H_{v}(p_{v}^{r})\geq
p_{w}^{r}-p_{v}^{r}+S+H_{v}(p_{v}^{r})\geq H_{v}(p_{v}^{r}),$

where the last step uses that $\|\vec{p}^{r}\|\leq S$ by assumption. For the
upper bound on $h$, we get that

$\displaystyle H_{v}(t_{v})$ $\displaystyle\leq H_{v}(t_{w}+d)$
$\displaystyle\leq H_{v}(p_{w}^{r}+\vartheta
S+d)-H_{v}(p_{v}^{r})+H_{v}(p_{v}^{r})$
$\displaystyle\leq\vartheta(p_{w}^{r}-p_{v}^{r}+\vartheta\cdot
S+d)+H_{v}(p_{v}^{r})$
$\displaystyle\leq\vartheta((\vartheta+1)S+d)+H_{v}(p_{v}^{r}).$

It remains to prove that $v$ receives no correct signature of the form
$\left<r\right>_{w}^{\prime}$ at a local time
$h^{\prime}\in(H_{v}(p_{v}^{r}),h+d-2u)$ from $x\neq w$. Since $w$ sends no
other signature than $\left<r\right>_{w}$ and signatures cannot be forged, any
such message must be sent after $x$ learned $\left<r\right>_{w}$, at time
$t_{x}\geq t_{w}+d-u$. Hence, $v$ receives any such message at a time
$t_{v}^{\prime}\geq t_{x}+d-u\geq t_{w}+2(d-u)$. On the other hand $t_{v}\leq
t_{w}+d$, implying that $t_{v}^{\prime}-t_{v}\geq d-2u$. We conclude that
$h^{\prime}-h=H_{v}(t_{v}^{\prime})-H_{v}(t_{v})\geq t_{v}^{\prime}-t_{v}\geq
d-2u$. ∎

Having established that honest nodes broadcasts are accepted, let us establish
the counterpart of Crusader Consistency, namely that if honest nodes accept a
broadcast, they do so within a short time of each other.

###### Lemma 2.

Let $r\in\mathbb{N}$ and $u,v\in\mathcal{H}$. Suppose that $u,v$ participate
in an instance of $\mathsf{TCB}^{r}$ with dealer $w$ and output
$h_{u},h_{v}\not\in\\{\bot\\}$, respectively. Let $t_{u},t_{v}$ denote the
times at which $u$ and $v$ receive the messages from $w$, respectively. Then
$|t_{u}-t_{v}|\leq(1-1/\vartheta)\cdot d+2u/\vartheta$.

###### Proof.

Denote as $t_{u},t_{v}$ the times that $u$ and $v$ receive a message from $w$
in $\mathsf{TCB}^{r}$ s.t.
$H_{u}(t_{u})\in(H_{u}(p^{r}_{u}),H_{u}(p^{r}_{u})+\vartheta(d+\vartheta\cdot
S))$ (and similarly for $v$). If for either $u$ or $v$ no such time exists,
then that party outputs $\bot$ and the claim is vacuously true.

Without loss of generality, assume that $t_{u}\geq t_{v}$. $u$ receives the
echo from $v$ at time $t\leq t_{v}+d$. Since $u$ does not output $\bot$, we
have that $\vartheta\cdot(t-t_{u})\geq H_{u}(t)-H_{u}(t_{u})\geq d-2u.$ This
implies that $t-t_{u}\geq(d-2u)/\vartheta$. It follows
$t_{u}-t_{v}=t-t_{v}-(t-t_{u})\leq d-(d-2u)/\vartheta=(1-1/\vartheta)\cdot
d+2u/\vartheta$. ∎

###  3.2. Pulse Synchronization Algorithm

With Timed Crusader Broadcast in place, we are ready to proceed to the main
algorithm, i.e., iterative simulation of synchronous approximate agreement
steps on pulse times. The algorithm is given in Figure 3.

Algorithm $\mathsf{CPS}$ We describe the protocol from the view of node $v$.
Wait until local time $S$. Then do for all $r\in\mathbb{N}$: • Generate $r$th
pulse. • Simultaneously participate in an execution of $\mathsf{TCB}^{r}$ with
sender $w$, for each node $w\in[n]$. Let $h_{v,w}$ denote the output of the
instance corresponding to sender $w$. • For each node $w\in[n]$ s.t.
$h_{v,w}\neq\bot$, compute $\Delta_{v,w}^{r}:=h_{v,w}-H_{v}(p_{v}^{r})-d+u-S$.
For all remaining $w\in[n]$, set $\Delta_{v,w}^{r}:=\bot$. Denote $b$ the
number of $\bot$ values. • Sort all the non-$\bot$ values computed in the
previous step, then discard the lowest $f-b$ and the highest $f-b$ of those
values. Denote $I$ the interval spanned by the remaining values. • Set
$\Delta_{v}^{r}$ to the midpoint of $I$. • Wait until local time
$H_{v}(p_{v}^{r})+\Delta_{v}^{r}+T$.

Figure 3.  Crusader Pulse Synchronization, where $f=\lceil n/2\rceil-1$ is the
number of faulty nodes that can be sustained. The algorithm assumes that
$H_{v}(0)\in[0,S]$ for all $v\in\mathcal{H}$.

Intuitively, in each iteration $r\in\mathbb{N}$ the algorithm lets each node
$w$ communicate its pulse time using crusader broadcast. The output of this
subroutine at $v$ is then used to compute an estimate $\Delta_{v,w}^{r}$ of
$p_{w}^{r}-p_{v}^{r}$, which in case of a faulty sender might fail and result
in $\bot$. These estimates are then used exactly as in Algorithm
$\mathsf{APA}$ to determine a value of $\Delta$, which is then used as a
correction to the next pulse time relative to the nominal duration of an
iteration of $T$. The fact that Algorithm $\mathsf{APA}$ is used on the
_differences_ of pulse times is compensated for by adding its output to the
previous local pulse time of $H_{v}(p_{v}^{r})$; since substracting
$p_{v}^{r}$ does not change the order of the received values and the output is
a convex combination of two inputs of a specific rank, up to the errors
introduced by clock drift and delay uncertainty, this is equivalent to
executing Algorithm $\mathsf{APA}$ on inputs $p_{v}^{r}$.

We begin our analysis of the algorithm by translating the validity and
consistency guarantees of Algorithm $\mathsf{TCB}^{r}$ into corresponding
guarantees on the computed estimates $\Delta_{v,w}^{r}$. In the following, we
will bound the error in the estimates by
$\delta:=2u+(\vartheta^{2}-1)d+2(\vartheta^{3}-\vartheta^{2})S$. First, we
show validity, i.e., that honest nodes compute estimates of their difference
in pulse times with error smaller than $\delta$. The result is shown
analogously to (Lec21, , Ch. 10, Lem. 10.8); we defer the full proof to
Appendix C.

###### Lemma 3.

Let $r\in\mathbb{N}$ and suppose that $\|\vec{p}^{r}\|\leq S$. Let
$v,w\in\mathcal{H}$ and suppose that $v$ participates in an instance of
$\mathsf{TCB}^{r}$ with dealer $w$. Consider $\Delta^{r}_{v,w}$ as defined in
algorithm $\mathsf{CPS}$. Then
$\Delta_{v,w}^{r}\in[p^{r}_{w}-p^{r}_{v},p^{r}_{w}-p^{r}_{v}+\delta).$

###### Proof Sketch..

The computation of $\Delta^{r}_{v,w}$ accounts for the minimum time (and hence
local time) that passes before $v$ receives the message from $w$, which is
accepts by Lemma 1. The upper bound follows by checking the maximum local time
that passes, which is proportional to $\vartheta$ times the real difference
between the pulse times plus a delay uncertainty. ∎

Next, we show the counterpart of Crusader Consistency, i.e., that non-$\bot$
estimates are consistent up to error $\delta$.

###### Lemma 4.

Let $r\in\mathbb{N}$ and suppose that $\|\vec{p}^{r}\|\leq S$. Moreover, let
$v,w\in\mathcal{H}$, $x\in[n]/\mathcal{H}$, and $h_{v},h_{w}\not\in\\{\bot\\}$
denote the outputs of $v$ and $w$ in $\mathsf{TCB}^{r}$ with sender $x$. Then
$|\Delta_{v,x}^{r}-\Delta_{w,x}^{r}-(p^{r}_{w}-p^{r}_{v})|<\delta$.

###### Proof.

Let again $t_{v}$ and $t_{w}$ denote the times at which $v$ and $w$ receive
the messages from the dealer $x$. By Lemma 2, it holds that
$t_{v}-t_{w}\leq(1-1/\vartheta)d+2u/\vartheta$. We get that

$\displaystyle\Delta_{v,x}^{r}-\Delta_{w,x}^{r}-(p_{v}^{r}-p^{r}_{u})$
$\displaystyle=H_{v}(t_{v})-H_{v}(p_{v}^{r})-(H_{w}(t_{w})-H_{w}(p^{r}_{w}))-(p_{w}^{r}-p^{r}_{v})$
$\displaystyle\leq\vartheta(t_{v}-p_{v}^{r})-(t_{w}-p^{r}_{w})-(p_{v}^{r}-p^{r}_{w})$
$\displaystyle=(\vartheta-1)(t_{v}-p_{v}^{r})+t_{v}-t_{w}$
$\displaystyle\leq(\vartheta-1)(t_{v}-p_{v}^{r})+\left(1-\frac{1}{\vartheta}\right)d+\frac{2u}{\vartheta}$
$\displaystyle\leq(\vartheta-1)(H_{v}(t_{v})-H_{v}(p_{v}^{r}))+\left(1-\frac{1}{\vartheta}\right)d+\frac{2u}{\vartheta}$
$\displaystyle\leq(\vartheta-1)(\vartheta
d+(\vartheta^{2}+\vartheta)S)+\left(1-\frac{1}{\vartheta}\right)d+\frac{2u}{\vartheta}<\delta.\qed$

Based on the above bounds, we will prove by induction that for all
$r\in\mathbb{N}$, $\|\vec{p}^{r}\|\leq S$. The base of the induction is given
by the assumption that hardware clocks are initialized with skew $S$. The
following lemma is the key argument required for the step, establishing that,
essentially, an approximate agreement step on the pulse times with error at
most $\delta$ is performed, assuming that the estimates satisfy the above
validity and consistency conditions.

###### Lemma 5.

Fix $r\in\mathbb{N}$. Suppose that each $v\in\mathcal{H}$ computes for each
$w\in[n]$ a value $\Delta^{r}_{v,w}\in\mathbb{R}\cup\\{\bot\\}$, such that the
following properties hold:

  * •

For $v,w\in\mathcal{H}$,
$\Delta_{v,w}^{r}\in[p_{w}^{r}-p_{v}^{r},p_{w}^{r}-p_{v}^{r}+\delta]$.

  * •

For $v,w\in\mathcal{H}$ and $x\in[n]$ such that
$\Delta_{v,x}^{r},\Delta_{w,x}^{r}\not\in\\{\bot\\}$,
$|\Delta^{r}_{v,x}-\Delta_{w,x}^{r}-(p_{w}^{r}-p_{v}^{r})|\leq\delta$.

Then the following statements are true:

  1. (1)

For all $v\in\mathcal{H}$:
$-\|\vec{p}^{r}\|\leq\Delta_{v}^{r}\leq\|\vec{p}^{r}\|+\delta.$

  2. (2)

$\|\vec{\Delta}^{r}+\vec{p}^{r}\|\leq\|\vec{p}^{r}\|/2+\delta.$

###### Proof.

We first show the claim for the special case $\delta=0$. Consider an honest
node $v\in\mathcal{H}$ and a faulty node $x\in[n]\setminus\mathcal{H}$ such
that $\Delta_{v,x}^{r}\neq\bot$. We define
$p^{r}_{x}:=\Delta^{r}_{v,x}+p^{r}_{v}$. We observe that
$p_{v}^{r}+\Delta^{r}_{v,x}=p_{w}^{r}+\Delta^{r}_{w,x}$ for any correct node
$w\in\mathcal{H}$ from the second condition of the statement and the
assumption that $\delta=0$. Hence $p^{r}_{x}=p_{w}^{r}+\Delta^{r}_{w,x}$ for
all $w\in\mathcal{H}$ satisfying $\Delta_{w,x}^{r}\neq\bot$.

We next show that $p_{v}^{r}+\Delta^{r}_{v}$ for $v\in\mathcal{H}$ equals the
output of $v$ in an iteration of an execution of algorithm $\mathsf{APA}$
specified as follows:

  * •

Nodes $v\in\mathcal{H}$ have input $p_{v}^{r}$.

  * •

For nodes $x\in[n]\setminus\mathcal{H}$ such that $\mathsf{CB}$ with dealer
$x$ outputs $\Delta_{v,x}^{r}\neq\bot$ at $v\in\mathcal{H}$, $v$ receives
$p^{r}_{x}$ from $x$.

We consider the vector $L$ of values used to compute the value
$\Delta_{v}^{r}$ in iteration $r$ of $\mathsf{CPS}$. For $w\in[n]$,
$\Delta^{r}_{v,w}=p_{w}^{r}-p^{r}_{v}$. Hence, $L$ can be obtained by shifting
the non-$\bot$ input values used in the above execution of $\mathsf{APA}$ by
$-p_{v}^{r}$. This implies that in both computations, $v$ assigns the input
corresponding to node $w$ to the same position $i_{w}$ in the sorted vector of
non-$\bot$ inputs. Hence, the indices of discarded inputs in the list $L$
remains the same in both of these executions as well. Let $\ell=|L|$ denote
the length of $L$ and $b:=n-\ell$ the number of $\bot$ values. Without loss of
generality, we assume $L$ to be sorted in ascending order, and that parties
are sorted in ascending order by size of their pulse times $\vec{p}$. Then in
the $r$th iteration of $\mathsf{CPS}$, $v$ computes the midpoint
$\Delta_{v}^{r}$ of interval $I_{L}$ spanned by the remaining points in $L$ as

$\displaystyle\Delta_{v}^{r}=\frac{L_{\ell-f+b}+L_{f-b+1}}{2}=\frac{(p^{r}_{\ell-f+b}-p_{v}^{r})+(p^{r}_{f-b+1}-p_{v}^{r})}{2}=\frac{p^{r}_{\ell-f+b}+p^{r}_{f-b+1}}{2}-p_{v}^{r}.$

By comparison, the above execution of $\mathsf{APA}$ computes the midpoint as
$(p^{r}_{\ell-f+b}+p^{r}_{f-b+1})/2=M_{v}$ for every node $v\in\mathcal{H}$.
Thus, both executions compute the same midpoint, up to a shift of $p_{v}^{r}$,
i.e., $\mathsf{CPS}$ computes the vector of midpoints
$\Delta_{v}^{r}=M_{v}-p_{v}^{r}$ for every node $v\in\mathcal{H}$. As
$\mathsf{APA}$ satisfies the $1/2$-consistency condition of approximate
agreement, we know that the above execution of $\mathsf{APA}$ computes
midpoints $\vec{M}$ satisfying $\|\vec{M}\|\leq\|p^{r}\|/2$. It follows that
$\|\vec{\Delta}^{r}+\vec{p}^{r}\|=\|\vec{M}\|\leq\|\vec{p}^{r}\|/2.$ This
proves the second statement of the lemma.

To prove the first statement, we use the validity condition of approximate
agreement. We obtain that for all $v\in\mathcal{H}$,
$\min_{w\in\mathcal{H}}\\{p^{r}_{w}\\}\leq
M_{v}\leq\max_{w\in\mathcal{H}}\\{p^{r}_{w}\\}$. Since
$\vec{\Delta}^{r}=\vec{M}-\vec{p}^{r}$, we obtain for all $v\in\mathcal{H}$
that

$\displaystyle-\|p^{r}\|$
$\displaystyle=\min_{w\in\mathcal{H}}\\{p^{r}_{w}\\}-\max_{w\in\mathcal{H}}\\{p^{r}_{w}\\}\leq
M_{v}-p^{r}_{v}=\Delta_{v}^{r}\leq\max_{w\in\mathcal{H}}\\{p_{w}^{r}\\}-\min_{w\in\mathcal{H}}\\{p^{r}_{w}\\}=\|p^{r}\|.$

For the general case of $\delta>0$, we note that the list of values received
by $v\in\mathcal{H}$ can be obtained from the one of an execution with
$\delta=0$ by adding to each received value a shift between $0$ and $\delta$.
Thus, our analysis for the case of $\delta=0$ implies that

$\frac{p^{r}_{\ell-f+b}+p^{r}_{f-b+1}}{2}-p_{v}^{r}\leq\Delta_{v}^{r}\leq\frac{p^{r}_{\ell-f+b}+\delta+p^{r}_{f-b+1}+\delta}{2}-p_{v}^{r}=\frac{p^{r}_{\ell-f+b}+p^{r}_{f-b+1}}{2}-p_{v}^{r}+\delta.$

We conclude that
$-\|\vec{p}^{r}\|\leq\Delta_{v}^{r}\leq\|\vec{p}^{r}\|+\delta$, showing the
first claim of the lemma. Moreover,
$\Delta_{v}^{r}+p^{r}_{v}\in[M_{v},M_{v}+\delta]$ and hence,
$\|\Delta^{r}+p^{r}\|\leq\|\vec{M}\|+\delta\leq\|p^{r}\|/2+\delta$. ∎

An immediate consequence of Lemma 5 is that if the hypothesis of our induction
holds, i.e., $\|\vec{p}^{r}\|\leq S$, then the computed shifts
$\vec{\Delta}^{r}$ are feasible, in the sense that $v\in\mathcal{H}$ the
waiting statement at the end of the main loop of Algorithm $\mathsf{CPS}$
refers to a local time that is larger then the local time when all instances
of crusader broadcast for round $r$ have terminated at $v$, so that $v$ can
compute $\Delta_{v}^{r}$; a proof is given in Appendix C.

###### Corollary 6.

Fix $r\in\mathbb{N}$. Suppose that
$T\geq(\vartheta^{2}+\vartheta+1)S+(\vartheta+1)d-2u$ and $\|\vec{p}^{r}\|\leq
S$. Moreover, denote as $\tau^{r}_{v}$ the time at which $v\in\mathcal{H}$
finalizes the computation of $\Delta^{r}_{v}$. Then for all $v\in\mathcal{H}$,
$H_{v}(p_{v}^{r})+\Delta^{r}_{v}+T\geq H_{v}(\tau^{r}_{v})$.

Similarly to (Lec21, , Ch. 10, Lem. 10.7), we can now prove that the induction
steps succeeds, i.e., that if $\|\vec{p}^{r}\|\leq S$, then also
$\|\vec{p}^{r+1}\|\leq S$; the details are given in Appendix C.

###### Lemma 7.

Suppose that $T\geq(\vartheta^{2}+\vartheta+1)S+(\vartheta+1)d-2u$,
$S\geq(2(2\vartheta-1)\delta+2(\vartheta-1)T)/(2-\vartheta)$, and
$\|\vec{p}^{r}\|\leq S$. Then

  * •

$(T-S)/\vartheta\leq\min_{w\in\mathcal{H}}\\{p_{w}^{r+1}\\}-\min_{w\in\mathcal{H}}\\{p_{w}^{r}\\}\leq
T+S+\delta$ and

  * •

$\|\vec{p}^{r+1}\|\leq S$.

###### Proof Sketch..

Lemma 5 allows us to interpret the new pulse times as the result of performing
an approximate agreement step with error $\delta$ on the previous pulse times
(up to adding $T$ and clock drift). The first statement follows from the
resulting bound of
$-S\leq\|\vec{p}^{r}\|\leq\Delta_{v}^{r}\leq\|\vec{p}^{r}\|+\delta\leq
S+\delta$. The second statement is shown by using that approximate agreement
reduces the “old” error carried over from the previous iteration by
$\|\vec{p}^{r}\|/2$, which compensates for the “new” error due to the
measurement error of $\delta$ and clock drift. ∎

The proof of the main theorem is analogous to (Lec21, , Ch. 10, Thm. 10.9); we
defer it to Appendix C.

###### Theorem 8.

Suppose that $4-\vartheta+\vartheta^{2}-3\vartheta^{3}>0$ and

$\displaystyle
T\geq\frac{(\vartheta^{2}+\vartheta+1)2(2\vartheta-1)(2u+(\vartheta^{2}-1)d)}{4-\vartheta+\vartheta^{2}-3\vartheta^{3}}+(\vartheta+1)d-2u\in
O(d).$

Define $S$ as

$\displaystyle
S:=\frac{2(2\vartheta-1)(u+(\vartheta-1)d)+2(\vartheta-1)T}{4-2\vartheta-\vartheta^{2}}\in
O(u+(1-1/\vartheta)T),$

and suppose that $\max_{v\in\mathcal{H}}\\{H_{v}(0)\\}\leq S$. Then Algorithm
$\mathsf{CPS}$ is an $(\lceil n/2\rceil-1)$-secure clock synchronizaton
protocol with skew $S$, minimum period
$P_{\mathsf{min}}\geq(T-(\vartheta+1)S)/\vartheta$, and maximum period
$P_{\mathsf{max}}\leq T+3S$.

###### Proof Sketch..

$S$ and $T$ are chosen in accordance with the prerequisites of Lemma 7, from
which the claims readily follow. As $T\in\Omega(S)$ and
$S\in\Omega((\vartheta-1)T$, this is only feasible if $\vartheta-1$ is small
enough. ∎

By checking for which values of $\vartheta>1$ the polynomial in $\vartheta$ in
the preconditions of the theorem is positive, we arrive at Definition 3. *

##  4\. Lower Bound on the Skew

Algorithm $\mathsf{CPS}$ exploits signatures in order to prevent faulty nodes
from equivocating about their own perception of time, i.e., when they
broadcast. However, echoing signatures comes not only at the expense of
another message delay (and thus timing uncertainty $u$), but also at the
expense of adding indirection to communication relevant for the algorithm. As
a result, the timing delay uncertainty determining its skew bound is actually
$\tilde{u}$, the uncertainty on communication links involving a faulty party,
which might be larger than $u$.

In this section, we prove that this restriction is inherent. Concretely, we
show that no algorithm can achieve a skew smaller than $2\tilde{u}/3$, even if
$u=0$. Our lower bound is established by the standard technique of
manipulating hardware clocks in a way that is hidden by adjusting message
delays, enabling us to construct three executions that are indistinguishable
to honest nodes. Two executions are indistinguishable to an honest node if the
sequence of received messages as well as the local reception times are
identical; in this case, the algorithm must send the same messages at the same
local times and generate pulses at the same time.333For a randomized
algorithm, this holds only after fixing the randomness. However, the strategy
of the adversary is independent of the algorithm, which allows us to prove the
result for deterministic algorithms and infer the general statement by Yao’s
principle. The hardware clock skew of $2\tilde{u}/3$ we build up then
translates to a skew of at least $2\tilde{u}/3$ between pulses in at least one
of the three executions.

In our setting, this approach faces the technical challenge that it is not
sufficient to define the executions such that hardware clocks and message
delays conform to the model, followed by proving their indistinguishability.
In addition, we must prove that the adversary can obtain the required
knowledge to determine its strategy upfront and have faulty nodes send the
required messages to maintain indistinguishability in time.

We now set up to formally prove the lower bound. Fix an arbitrary
deterministic pulse synchronization algorithm $\mathcal{A}$. For convenience
of notation, w.l.o.g. we assume that no two messages are received at the exact
same local time; the general case can be covered by breaking ties
lexicographically. Also w.l.o.g., we can assume $n=3$; the general case
follows from a simple simulation argument we provide later. In order to
distinguish the three executions we construct, we use superscripts $i\in[3]$.
For notational convenience, both execution and node indices are always taken
modulo $3$, which also exposes the symmetry of the construction.

Throughout this section, all considered execution triples
$(\mathsf{Ex}^{i})_{i\in[3]}$, share the following properties $P$:

  * •

$\mathcal{H}^{i}=[3]\setminus\\{i\\}$.

  * •

Messages sent between honest parties have delay $d$.

  * •

All other messages have delay $d-\tilde{u}$.

  * •

$H^{i}_{i+1}(t)=t$.

  * •

$H^{i}_{i+2}(t)=\vartheta t$ for $t\leq 2\tilde{u}/(3(\vartheta-1))$ and
$H^{i}_{i+2}(t)=t+2\tilde{u}/3$ for $t\geq 2\tilde{u}/(3(\vartheta-1))$.

In particular, hardware clocks of honest nodes never deviate by more than
$2\tilde{u}/3$ from real time.

We construct our triple of executions by induction over the number of messages
$k$ sent by faulty nodes, where indistinguishability holds before the maximum
local reception time of such a message. The base case is trivial; the
following lemma performs the step.

###### Lemma 1.

Let $n=3$, $k\in\mathbb{N}$, and $\Pi$ be a $1$-secure protocol for pulse
synchronization with skew $S$. Suppose there exist executions
$\mathsf{Ex}^{1},\mathsf{Ex}^{2},\mathsf{Ex}^{3}$ of $\Pi$ satisfying $P$ and
the following properties.

  * •

Faulty nodes send a total of $k$ messages in $\mathsf{Ex}^{1}$,
$\mathsf{Ex}^{2}$, and $\mathsf{Ex}^{3}$.

  * •

Let $h^{*}$ be the maximum local time at which a message from a faulty node is
received (or $0$ if faulty nodes send no messages). Honest node $i$ cannot
distinguish $\mathsf{Ex}^{i+1}$ and $\mathsf{Ex}^{i+2}$ until local time
$h^{*}$.

If there exists a node $i$ that can distinguish $\mathsf{Ex}^{i+1}$ and
$\mathsf{Ex}^{i+2}$, then there exist executions
$\widetilde{\mathsf{Ex}}^{1}$, $\widetilde{\mathsf{Ex}}^{2}$, and
$\widetilde{\mathsf{Ex}}^{3}$ with the same properties, except that faulty
nodes send an additional message which is received at a local time $h>h^{*}$.
Moreover, for $i\in[3]$, nodes $i+1$ and $i+2$ cannot distinguish
$\widetilde{\mathsf{Ex}}^{i}$ from $\mathsf{Ex}^{i}$ before time $h$.

###### Proof.

Let $h$ denote the minimum local time (over all executions) at which a node
$i$ can distinguish $\mathsf{Ex}^{i+1}$ and $\mathsf{Ex}^{i+2}$. By the
prerequisites and the assumption that no two messages are received at the same
time, there exists an honest message $m$ that $i$ receives in exactly one of
these executions at local time $h>h^{*}$. Observe that the requirements on
$\widetilde{\mathsf{Ex}}^{1},\widetilde{\mathsf{Ex}}^{2},\widetilde{\mathsf{Ex}}^{3}$
fully specify these executions save for the additional message that is sent by
some faulty party. We rule that the additional message is $m$, which is sent
by the same (there faulty) node with the same local reception time at $i$. We
will need to establish that
$\widetilde{\mathsf{Ex}}^{1},\widetilde{\mathsf{Ex}}^{2},\widetilde{\mathsf{Ex}}^{3}$
are well-defined, in that faulty nodes always learn all signatures required
for the messages they send. However, let us first establish the
indistinguishability statements, as these are needed to show well-definedness.

We begin by showing that for each $j\in[3]$, executions
$\widetilde{\mathsf{Ex}}^{j+1}$ and $\mathsf{Ex}^{j+1}$ are indistinguishable
before time $h$. An analogous statement holds for
$\widetilde{\mathsf{Ex}}^{j+2}$ and $\mathsf{Ex}^{j+2}$. Toward a
contradiction, suppose that there exists a local time $\tilde{h}<h$ at which
some node $j$ can distinguish
$\widetilde{\mathsf{Ex}}^{j+1},\mathsf{Ex}^{j+1}$. Without loss of generality,
we let $\tilde{h}$ denote the minimal such time. This implies that $j$
receives a message $\tilde{m}$ at local time $\tilde{h}$ in execution
$\widetilde{\mathsf{Ex}}^{j+1}$, which it does not receive in
$\mathsf{Ex}^{j+1}$ (or vice versa).

We analyze two cases:

  * •

$\tilde{m}$ is sent by an honest node $j^{\prime}\neq j$: As $d>2\tilde{u}/3$,
honest parties’ local clocks are less than $d$ apart at all times. As messages
sent between honest parties have delay $d$, thus $j^{\prime}$ must have sent
$\tilde{m}$ at some local time less than $\tilde{h}$. Because
$\widetilde{\mathsf{Ex}}^{j+1}$ and $\mathsf{Ex}^{j+1}$ are indistinguishable
before time $\tilde{h}$, $j^{\prime}$ sends $\tilde{m}$ in both
$\mathsf{Ex}^{j+1}$ and $\widetilde{\mathsf{Ex}}^{j+1}$. Hence, $\tilde{m}$ is
received at the same local time by $j$ in both $\mathsf{Ex}^{j+1}$ and
$\widetilde{\mathsf{Ex}}^{j+1}$. This is a contradiction.

  * •

$\tilde{m}$ is sent by an faulty node $j^{\prime}\neq j$: As $\tilde{m}$ is
received by $j$ before local time $h$, $\tilde{m}\neq m$. It follows that
$j^{\prime}$ sends $\tilde{m}$ in both executions. Hence it is received at the
same local time by $j$ in both $\mathsf{Ex}^{j+1}$ and
$\widetilde{\mathsf{Ex}}^{j+1}$. This is a contradiction.

Since $\mathsf{Ex}^{j+1}$ and $\mathsf{Ex}^{j+2}$ are indistinguishable to $j$
before local time $h$, it follows that $\widetilde{\mathsf{Ex}}^{j+1}$ and
$\mathsf{Ex}^{j+2}$ are also indistinguishable before local time $h$ to $j$.
As, analogously, $\mathsf{Ex}^{j+2}$ and $\widetilde{\mathsf{Ex}}^{j+2}$ are
indistinguishable to $j$ before local time $h$,
$\widetilde{\mathsf{Ex}}^{j+1}$ and $\widetilde{\mathsf{Ex}}^{j+2}$ are also
indistinguishable to $j$ before local time $h$. Finally, by construction and
the assumption that only one message is received at any given time,
$\widetilde{\mathsf{Ex}}^{j+1}$ and $\widetilde{\mathsf{Ex}}^{j+2}$ are also
indistinguishable to $j$ at local time $h$.

It remains to show that the behaviour of faulty nodes in executions
$\widetilde{\mathsf{Ex}}^{1},\widetilde{\mathsf{Ex}}^{2},\widetilde{\mathsf{Ex}}^{3}$
is also well-defined. Suppose that faulty node $i\in[3]$ sends $\tilde{m}$ in
$\widetilde{\mathsf{Ex}}^{i}$. Let $\bar{h}\leq h$ be the local time when
$\tilde{m}$ is received (by an honest node) in $\widetilde{\mathsf{Ex}}^{i}$.
Denote as $t^{i}\geq\bar{h}-2\tilde{u}/3$ the time at which $\tilde{m}$ is
received in $\widetilde{\mathsf{Ex}}^{i}$. By definition, $i$ sends
$\tilde{m}$ at time $t^{i}-d+\tilde{u}\geq\bar{h}-d+\tilde{u}/3$ in
$\widetilde{\mathsf{Ex}}^{i}$. It is sufficient to show that $i$ receives
every message $m^{\prime}$ on which $\tilde{m}$ depends by this time.

Consider such a message $m^{\prime}$ and suppose that $i+1\neq i$ is its
sender; the case that $i+2$ is the sender is treated analogously. We
distinguish two cases based on which node receives $\tilde{m}$.

  * •

$i+2$ receives $\tilde{m}$: Since $H^{i+1}_{i+2}(\bar{h})\geq\bar{h}$, and $i$
sends $\tilde{m}$ no later than time $\bar{h}-d$ in
$\widetilde{\mathsf{Ex}}^{i+1}$. Thus, $m^{\prime}$ is received by $i$ in
$\widetilde{\mathsf{Ex}}^{i+1}$ no later than at time $\bar{h}-d$, which
corresponds to local time at most
$h^{i+1}:=H^{i+1}_{i}(\bar{h}-d)\leq\bar{h}-d+2\tilde{u}/3<\bar{h}$. By
indistinguishability of executions before local time $h\geq\bar{h}$, $i$
receives $m^{\prime}$ by the same local time $h^{i+1}$ in
$\widetilde{\mathsf{Ex}}^{i+2}$, and accordingly no later than (real) time
$h^{i+1}$. Hence, $i+1$ sends $m^{\prime}$ in $\widetilde{\mathsf{Ex}}^{i+2}$
by time $h^{i+1}-d$ and local time $h^{i+2}:=H^{i+2}_{i+1}(h^{i+1}-d)\leq
h^{i+1}-d+2\tilde{u}/3<\bar{h}$. By indistinguishability of
$\widetilde{\mathsf{Ex}}^{i}$ and $\widetilde{\mathsf{Ex}}^{i+2}$ before local
time $h$, it follows that $i+1$ sends $m^{\prime}$ in
$\widetilde{\mathsf{Ex}}^{i}$ by local time (and also time) $h^{i+2}$. Hence,
in $\widetilde{\mathsf{Ex}}^{i}$, $i$ receives $m^{\prime}$ by time

$\displaystyle h^{i+2}+d-\tilde{u}$ $\displaystyle\leq
h^{i+1}-\frac{\tilde{u}}{3}\leq\bar{h}-d+\frac{\tilde{u}}{3}.$

  * •

$i+1$ receives $\tilde{m}$: Since $H^{i+2}_{i+1}(\bar{h})\geq\bar{h}$, we have
that $i$ sends $\tilde{m}$ by time $\bar{h}-d$ in
$\widetilde{\mathsf{Ex}}^{i+2}$. Thus, $m^{\prime}$ is received by $i$ in
$\widetilde{\mathsf{Ex}}^{i+2}$ by time $\bar{h}-d$, and hence sent by $i+1$
by time $\bar{h}-2d$. This corresponds to local time
$h^{i+2}:=(H^{i+2}_{i+1})(\bar{h}-2d)\leq\bar{h}-2d+2\tilde{u}/3<\bar{h}$. By
indistinguishability of executions before local time $h\geq\bar{h}$, $i+1$
sends $m^{\prime}$ by the same local time and time $h^{i+2}$ in
$\widetilde{\mathsf{Ex}}^{i}$. Hence, $i$ receives $m^{\prime}$ at time at
most

$\displaystyle h^{i+2}+d-\tilde{u}$
$\displaystyle\leq\bar{h}-d-\frac{\tilde{u}}{3}<\bar{h}-d+\frac{\tilde{u}}{3}.\qed$

Using the Lemma 1 inductively, we construct executions that are
indistinguishable to honest nodes at all times. A full proof of Lemma 2 is
provided in the appendix.

###### Lemma 2.

Let $n=3$ and let $\Pi$ be a $1$-secure protocol for pulse synchronization
with skew $S$. Then there exist executions
$\mathsf{Ex}^{1},\mathsf{Ex}^{2},\mathsf{Ex}^{3}$ of $\Pi$ that satisfy $P$
and where node $i\in[3]$ cannot distinguish $\mathsf{Ex}_{i+1}$ and
$\mathsf{Ex}_{i+2}$.

###### Proof Sketch..

Inductive application of Lemma 1 yields a series of triples of executions with
an increasing number of messages sent by faulty nodes, which cannot be
distinguished by correctness up to the largest local time when such a message
is received. There are two cases: The induction halts, because the
indistinguishability holds at all times; in this case we are done. Otherwise,
the constructed executions share indistinguishable prefixes with those that
are constructed later. As only finitely many messages are sent in finite time,
these prefixes must become arbitrarily long. Hence, they define limit
executions satisfying the required properties. ∎

Equipped with these executions, we are in the position to prove the claimed
lower bound. *

###### Proof.

We show the statement for the special case of $n=3,t=1$. For general $n$, we
can reduce the argument to the case of $n=3,t=1$ as follows. Assume the
existence of an $\lceil n/3\rceil$-secure protocol $\Pi$ for pulse
synchronization with skew $S<2\tilde{u}/3$. Now, partition the set of $n$
nodes into three non-empty subsets $S_{1},S_{2},S_{3}$ of size at most $\lceil
n/3\rceil$. Then, node $i\in[3]$ simulates the protocol behaviour of nodes in
$S_{i}$ in $\Pi$ and outputs the pulse times of the lexicographically first
node in $S_{i}$. By assumption, this yields a $1$-secure protocol for pulse
synchronization for $n=3$ with skew $S$.

Thus, let $\Pi$ be a $1$-secure protocol for pulse synchronization, and assume
for now that $\Pi$ is deterministic. By Lemma 2, there exist executions
$\mathsf{Ex}^{1},\mathsf{Ex}^{2},\mathsf{Ex}^{3}$ with the following
properties:

  * •

$\mathcal{H}^{i}=[3]\setminus\\{i\\}$.

  * •

$H^{i}_{i+1}(t)=t$.

  * •

$H^{i}_{i+2}(t)=\vartheta\cdot t$ for $t\leq 2\tilde{u}/(3(\vartheta-1))$ and
$H^{i}_{i+2}(t)=t+2\tilde{u}/3$ for $t\geq 2\tilde{u}/(3(\vartheta-1))$.

  * •

$\mathsf{Ex}_{i+1}$ and $\mathsf{Ex}_{i+2}$ are indistinguishable to node $i$.

Recall that $\Pi$ must guarantee some minimum period $P_{\mathsf{min}}>0$. We
define

$\displaystyle
r:=\left\lceil\frac{\tilde{u}}{P_{\mathsf{min}}(\vartheta-1)}\right\rceil+1$

such that for all $i\in[3]$, $\min\\{p_{i+1}^{i,r},p_{i+2}^{i,r}\\}\geq
2\tilde{u}/(3(\vartheta-1))$, where $p_{v}^{i,r}$ denotes the $r$th pulse time
of honest node $v$ in execution $\mathsf{Ex}^{i}$. Recall that for all times
$t$, $H^{i+2}_{i}(t)=t$ and for times $t\geq p_{i}^{i+1,r}$,
$H^{i+1}_{i}(t)=t+2\tilde{u}/3$. By indistinguishability of executions
$\mathsf{Ex}^{i+1}$ and $\mathsf{Ex}^{i+2}$ for node $i$,
$H_{i}^{i+1}(p_{i}^{i+1,r})=H_{i}^{i+2}(p_{i}^{i+2,r})$. Hence,

$\displaystyle
p_{i}^{i+1,r}=(H_{i}^{i+1})^{-1}(H_{i}^{i+1}(p_{i}^{i+1,r}))=(H_{i}^{i+1})^{-1}(H_{i}^{i+2}(p_{i}^{i+2,r}))=(H_{i}^{i+1})^{-1}(p_{i}^{i+2,r})=p_{i}^{i+2,r}-\frac{2\tilde{u}}{3}$

We conclude that

$\displaystyle
3S\geq(p_{i+1}^{i,r}-p_{i+2}^{i,r})+(p_{i+2}^{i+1,r}-p_{i}^{i+1,r})+(p_{i}^{i+2,r}-p_{i+1}^{i+2,r})=(p_{i}^{i+2,r}-p_{i}^{i+1,r})+(p_{i+1}^{i,r}-p_{i+1}^{i+2,r})+(p_{i+2}^{i+1,r}-p_{i+2}^{i,r})=2\tilde{u}.$

This implies that $S\geq 2\tilde{u}/3$.

It remains cover the case that $\Pi$ is randomized. To this end, we interpret
$\Pi$ as a distribution of deterministic protocols. Independently of the
randomness of $\Pi$, the adversary chooses uniformly at random a node
$i\in[3]$ to corrupt. Fixing the randomness of $\Pi$, these choices determine
executions $\mathsf{Ex}^{i}$, $i\in[3]$ as above. The adversary then lets $i$
behave such that $\mathsf{Ex}^{i}$ is realized.

We claim that, while the adversary cannot (necessarily) learn the randomness
of nodes $i+1$ and $i+2$, it is not required to do so. The messages node $i$
sends are those it would send as a correct node in $\mathsf{Ex}^{i+1}$ and
$\mathsf{Ex}^{i+2}$, respectively. It receives the same messages in
$\mathsf{Ex}^{i}$, just at different times. However, from the reception times
it can compute the corresponding local reception times at $i$ in
$\mathsf{Ex}^{i+1}$ and $\mathsf{Ex}^{i+2}$, based on the known message delays
and local times of the respective senders in the respective executions. Hence,
it can simply simulate two copies of $\Pi$ at $i$ with the randomness of $i$,
to which it feeds the received messages with the local times at which they are
received in $\mathsf{Ex}^{i+1}$ and $\mathsf{Ex}^{i+2}$, respectively. As we
have shown that all messages required in the adversary’s simulation are
received early enough to produce all appropriate messages to be sent in time,
we conclude that the adversary can indeed realize $\mathsf{Ex}^{i}$.

Finally, observe that the uniform choice of $i$ implies that, following the
above reasoning, the expected skew that occurs in $\mathsf{Ex}^{i}$ is at
least $2\tilde{u}/3$. ∎

## References

  * [1] Ittai Abraham, T.-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi.  Communication complexity of byzantine agreement, revisited.  In Principles of Distributed Computing (PODC), pages 317–326, 2019\.
  * [2] Ittai Abraham, Srinivas Devadas, Danny Dolev, Kartik Nayak, and Ling Ren.  Synchronous byzantine agreement with expected $o(1)$ rounds, expected $o(n^{2})$ communication, and optimal resilience.  In Financial Cryptography, pages 320–334, 2019.
  * [3] Baruch Awerbuch.  Complexity of network synchronization.  Journal of the ACM (JACM), 32(4):804—823, 1985.
  * [4] Saâd Biaz and Jennifer L. Welch.  Closed form bounds for clock synchronization under simple uncertainty assumptions.  Information Processing Letters (IPL), 80(3):151—157, 2001.
  * [5] Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss.  Asynchronous byzantine agreement with subquadratic communication.  In Theory of Cryptography Conference (TCC), pages 353–380, 2020\.
  * [6] Johannes Bund, Christoph Lenzen, and Will Rosenbaum.  Fault tolerant gradient clock synchronization.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 357–365, 2019.
  * [7] Christian Cachin, Klaus Kursawe, and Victor Shoup.  Random oracles in constantipole: practical asynchronous byzantine agreement using cryptography (extended abstract).  In Principles of Distributed Computing (PODC), volume 123–132, 2000\.
  * [8] Ran Canetti and Tal Rabin.  Fast asynchronous byzantine agreement with optimal resilience.  In ACM Symposium on Theory of Computing (STOC), pages 42–51, 1993\.
  * [9] T.-H. Hubert Chan, Rafael Pass, and Elaine Shi:.  Sublinear-round byzantine agreement under corrupt majority.  In Public Key Cryptography (PKC), pages 246–265, 2020.
  * [10] Shir Cohen, Idit Keidar, and Alexander Spiegelman.  Not a coincidence: Sub-quadratic asynchronous byzantine agreement whp.  In International Symposium on Distributed Computing (DISC), pages 25:1–25:17, 2020.
  * [11] Danny Dolev.  The byzantine generals strike again.  Journal of Algorithms, 3(1):14–30, 1982.
  * [12] Danny Dolev.  The byzantine generals strike again.  Journal of Algorithms, 3(1):14–30, 1982.
  * [13] Danny Dolev, Joe Halpern, and H. Raymond Strong.  On the possibility and impossibility of achieving clock synchronization.  In ACM Symposium on Theory of Computing (STOC), pages 504—511, 1984.
  * [14] Danny Dolev and Christoph Lenzen.  Clock synchronization and adversarial fault tolerance.  Online lecture notes, 2021.  https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/summer21/clock-synchronization-and-adversarial-fault-tolerance.
  * [15] Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl.  Reaching approximate agreement in the presence of faults.  Journal of the ACM (JACM), 33(3):499—516, 1986.
  * [16] Danny Dolev and Raymond Strong.  Authenticated algorithms for byzantine agreement.  SIAM Journal on Computing, 12(4):656–666, 1983.
  * [17] Danny Dolev and Andrew Chi-Chih Yao.  On the securituy of public key protocols.  IEEE Transactions on Information Theory, 29(2):198–207, 1983.
  * [18] Rui Fan and Nancy Lynch.  Gradient clock synchronization.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 320—327, 2004.
  * [19] Michael Fischer, Nanch Lynch, and Robert Patterson.  Impossibility of distributed consensus with one faulty process.  Journal of the ACM, 32(2):374–382, 1985.
  * [20] Michael J. Fischer, Nancy A. Lynch, and Michael Merritt.  Easy impossibility proofs for distributed consensus problems.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 59—70, 1985.
  * [21] Joseph Y. Halpern, Barbara Simons, Ray Strong, and Danny Dolev.  Fault-tolerant clock synchronization.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 89—102, 1984.
  * [22] Pankaj Khanchandani and Christoph Lenzen.  Self-stabilizing byzantine clock synchronization with optimal precision.  Theory of Computing Systems (TOCS), 63:261–305, 2018.
  * [23] Leslie Lamport, Robert E. Shostak, and Marshall C. Pease.  The byzantine generals problem.  ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3):382–401, 1982.
  * [24] Christoph Lenzen, Thomas Locher, and Roger Wattenhofer.  Tight bounds for clock synchronization.  Journal of the ACM (JACM), 57(2), 2010.
  * [25] Jennifer Lundelius and Nancy Lynch.  A new fault-tolerant algorithm for clock synchronization.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 75—88, 1984.
  * [26] Silvio Micali.  Very simple and efficient byzantine agreement.  In Innovations in Theoretical Computer Science Conference (ITCS), 2017.
  * [27] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song.  The honey badger of bft protocols.  In ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 31–42, 2016.
  * [28] T. K. Srikanth and Sam Toueg.  Optimal clock synchronization.  In Principles of Distributed Computing (PODC), pages 71–86, 1985\.
  * [29] Jun Wan, Hanshen Xiao, Srinivas Devadas, and Elaine Shi.  Round-efficient byzantine broadcast under strongly adaptive and majority corruptions.  In Theory of Cryptography Conference (TCC), pages 412–456, 2020\.

##  Appendix A Further Related Work

Cryptography in Distributed Consensus. Cryptography makes it possible to
circumvent the famous $f<n/3$ bound due to Lamport, Shostak, and Pease [23] on
the number of tolerable corruptions in a synchronous protocol solving the
consensus problem. This was first demonstrated in the seminal work of Dolev
and Strong [16] who gave an authenticated algorithm for Byzantine broadcast
tolerating any $f<n-1$ corrupted parties. Early works in the area typically
use cryptography, e.g., signatures, as structure-free objects, in line with
their symbolic treatment in the Dolev-Yao model [17]. Cryptography has also
been a staple tool to facilitate randomized consensus protocols, which are
inherently required in the asynchronous setting due to the FLP result [19].
Here, cryptography is typically used in the form of more advanced primitives
such as secret sharing [8], multi-party computation [5], or threshold
signatures [7], which can be used to agree on a random coin flip. Other
advanced forms of cryptography have been (more recently) used to optimize the
round and communication complexity of consensus protocols. Verifiable random
functions produce efficiently verifiable, yet unpredictable values that can be
used to efficiently elect a random leader (or a random subcommittee) in a
consensus protocol [26, 1, 9, 10]. Threshold encryption allows to agree on a
ciphertext of unknown content which can be forcibly decrypted by a sufficient
number of honest parties. This has served as a useful tool for guaranteeing
liveness in asynchronous consensus protocols [27]. Recent work [29] has also
shown the feasibility of round efficient consensus with a strongly adaptive
adversary capable of after-the-fact-removal of messages sent by honest parties
using time-locked puzzles. Lastly, we mention the work of Abraham et al. [2]
who give randomized consensus protocols from primitives such as the above and
also provide a signature-based variant of the Srikanth-Toueg pulse
synchronizer [28]. We point out, however, that their algorithm, while
tolerating the optimal corruption fraction of $\lceil n/2\rceil-1$ Byzantine
parties, exhibits a skew of up to $d$, whereas we achieve
$O(\tilde{u}+\vartheta-1)d)$. Likewise, [21] achieves skew larger than $d$ for
the related task of clock synchronization using essentially the same scheme.

Fault-tolerant Clock Synchronization in General Networks. Little work has
directly addressed fault-tolerant synchronization in non-complete networks.
For a known topology, without signatures (node) connectivity $(2f+1)$ is
necessary and sufficient to simulate full connectivity in the presence of up
to $f$ faults [11], lifting results for consensus under full connectivity to
general networks. Analogously, $(2f+1)$-connectivity can be leveraged to
simulate full connectivity with suitable timing information to do the same for
clock synchronization, by taking the median of clock offset estimation
obtained via $2f+1$ node-disjoint paths. This comes at the expense of such
estimates being subject to the maximum over the used paths of the uncertainty
accumulated along the path, which is justified by [4], which shows for any
pair of nodes a lower bound proportional to the length of the shortest path
between them in the fault-free setting. Although we are not aware of a formal
proof of this claim, $(2f+1)$-connectivity is also necessary for
synchronization, since a majority of faulty nodes on a node cut of the network
allows for the faulty majority to claim arbitrarily large clock offsets
between the (thus effectively disconnected) parts of the network.

In light of the lower bound of $\Omega(uD)$ on the worst-case skew444We state
all bounds here for uniform link delays and uncertainties, but all bounds can
be generalized to he heterogenous case. in fault-free networks of diameter $D$
[4], Fan and Lynch proposed to study the task of gradient clock
synchronization, in which the goal is to keep the local skew, i.e., the skew
between neighbors in the network, small [18]. Matching upper and lower bounds
of $\Theta(u\log D)$ on the local skew have been proven for the fault-free
case [24]. A fault-tolerant generalization of the algorithm achieves the same
asymptotic skew bounds in the presence of $f$ faults, provided that the
(arbitrary connected) base network is augmented by copying nodes and links
$\Theta(f)$ times [6]. The existing gradient clock synchronization algorithms
require no knowledge of the topology.

In the setting with signatures, $(f+1)$-connectivity is trivially necessary
and sufficient to simulate full connectivity of the network. This allows to
carry over the existing algorithms with skew $\Theta(d)$ to this setting [2,
21], where $d$ becomes the worst-case end-to-end delay across the network
after deleting the faulty nodes ([21] in fact states the general result). Our
algorithm can be translated to any known $(f+1)$-connected network in the same
way, where $\tilde{u}$ and $d$ are replaced by the maximum end-to-end delay
and uncertainty over all paths used to simulate full connectivity. Note that
in addition to making sure that communication has stable latency on the link
level, one needs to balance the length (in terms of overall delay) of the
utilized paths in order to keep $\tilde{u}$ much smaller than $d$.

##  Appendix B Algorithm $\mathsf{CB}$

Algorithm $\mathsf{CB}$ • The dealer $v$ sends
$(b_{v},\left<b_{v}\right>_{v})$ to all nodes. • Let $(b,\sigma)$ be the value
received from the dealer. Send $(b,\sigma)$ to all nodes. • Let
$(b_{w},\sigma_{w})$ be the message received from node $w$. Output $\bot$ if
either of the following occurs: – There are nodes $w_{1}\neq w_{2}$ such that
$\mathsf{Verify}(pk_{v},\sigma_{w_{1}},b_{w_{1}})=\mathsf{Verify}(pk_{v},\sigma_{w_{2}},b_{w_{2}})=1$,
but $b_{w_{1}}\neq b_{w_{2}}$. – $\mathsf{Verify}(pk_{v},\sigma,b)=0.$
Otherwise, output $b$.

Figure 4.  A $2$-round synchronous algorithm for Crusader Broadcast.

##  Appendix C Ommitted Proofs

###### Proof of Lemma 3.

Due to Lemma 1, $\Delta_{v,w}^{r}\neq\bot$. Denote as $t_{w}$ the time that
the dealer $w$ sends its message and let $t_{v}\in[t_{w}+d-u,t_{w}+d]$ denote
the time that $v$ receives it. We bound $\Delta_{v,w}^{r}$ from below as

$\displaystyle\Delta_{v,w}^{r}$
$\displaystyle=H_{v}(t_{v})-H_{v}(p_{v}^{r})-d+u-S$ $\displaystyle\geq
t_{v}-p_{v}^{r}-d+u-S$ $\displaystyle\geq t_{w}-p_{v}^{r}-S$
$\displaystyle=t_{w}+p_{w}^{r}-p_{w}^{r}-p_{v}^{r}-S$
$\displaystyle\geq\frac{H_{w}(t_{w})-H_{w}(p^{r}_{w})}{\vartheta}+p_{w}^{r}-p_{v}^{r}-S=p_{w}^{r}-p_{v}^{r}.$

The upper bound is derived as

$\displaystyle\Delta_{v,w}^{r}$
$\displaystyle=H_{v}(t_{v})-H_{v}(p_{v}^{r})-d+u-S$
$\displaystyle\leq\vartheta(t_{v}-p_{v}^{r})-d+u-S$
$\displaystyle\leq\vartheta(t_{w}+d-p_{v}^{r})-d+u-S$
$\displaystyle=p_{w}^{r}-p_{v}^{r}+u+\vartheta(t_{w}-p_{w}^{r})+(\vartheta-1)(d+p_{w}^{r}-p_{v}^{r})-S$
$\displaystyle\leq
p_{w}^{r}-p_{v}^{r}+u+\vartheta(t_{w}-p_{w}^{r})+(\vartheta-1)d+(\vartheta-2)S$
$\displaystyle\leq
p_{w}^{r}-p_{v}^{r}+u+\vartheta(H_{w}(t_{w})-H_{w}(p_{w}^{r}))+(\vartheta-1)d+(\vartheta-2)S$
$\displaystyle=p_{w}^{r}-p_{v}^{r}+u+(\vartheta-1)d+(\vartheta^{2}+\vartheta-2)S<p_{w}^{r}-p_{v}^{r}+\delta.\qed$

###### Proof of Corollary 6..

We begin by noting that Algorithm $\mathsf{TCB}$ terminates at the latest at
local time $H_{v}(p_{v}^{r})+(\vartheta+1)d-2u+(\vartheta^{2}+\vartheta)S$.
Hence, $H_{v}(\tau_{v}^{r})\leq
H_{v}(p_{v}^{r})+(\vartheta+1)d-2u+(\vartheta^{2}+\vartheta)S$. Moreover, due
to the condition $\|\vec{p}^{r}\|\leq S$, we can apply Lemmas 4 and 3, which
prove that the preconditions of Lemma 5 hold for iteration $r$. We apply the
precondition $\|\vec{p}^{r}\|\leq S$ and the first statement of Lemma 5, which
together yiels that for all $v\in\mathcal{H}$,
$-S\leq-\|\vec{p}^{r}\|\leq\Delta_{v}^{r}$. Therefore,

$\displaystyle H_{v}(p_{v}^{r})+\Delta^{r}_{v}+T$ $\displaystyle\geq
H_{v}(p_{v}^{r})-S+T\geq
H_{v}(\tau_{v}^{r})-((\vartheta+1)d-2u+(\vartheta^{2}+\vartheta+1)S)+T\geq
H_{v}(\tau_{v}^{r}).\qed$

###### Proof of Lemma 7..

We begin by noting that due to Corollary 6 (which we can apply due to the
lemma conditions), $\vec{p}^{r+1}$ is well-defined. Next, we apply Lemmas 4
and 3 to show that the preconditions of Lemma 5 hold for pulse $r$. Thus, by
the first statement of Lemma 5, for all $v\in\mathcal{H}$ we have that

$\displaystyle-S\leq-\|\vec{p}^{r}\|\leq\Delta_{v}^{r}\leq\|\vec{p}_{r}\|+\delta\leq
S+\delta.$

Consider $v:=\arg\min_{w\in\mathcal{H}}\\{p^{r+1}_{w}\\}$. Then

$\displaystyle\min_{w\in\mathcal{H}}\\{p_{w}^{r+1}\\}-\min_{w\in\mathcal{H}}\\{p_{w}^{r}\\}\geq
p_{v}^{r+1}-p_{v}^{r}\geq\frac{H_{v}(p_{v})^{r+1}-H_{v}(p_{v}^{r})}{\vartheta}\geq\frac{T+\Delta^{r}_{v}}{\vartheta}\geq\frac{T-S}{\vartheta}.$

This establishes the lower bound in item 1. For the upper bound, consider
$v:=\arg\min_{w\in\mathcal{H}}\\{p^{r}_{w}\\}$. We get

$\displaystyle\min_{w\in\mathcal{H}}\\{p_{w}^{r+1}\\}-\min_{w\in\mathcal{H}}\\{p_{w}^{r}\\}$
$\displaystyle\leq p^{r+1}_{v}-p^{r}_{v}\leq
H_{v}(p_{v}^{r+1})-H_{v}(p_{v}^{r})=T+\Delta_{v}^{r}\leq T+S+\delta.$

For the second statement of the lemma, fix arbitrary $v,w\in\mathcal{H}$ and
assume w.l.o.g. that $p_{w}^{r+1}\geq p_{v}^{r+1}$. We have that

$\displaystyle p_{w}^{r+1}-p_{v}^{r+1}$
$\displaystyle=p_{w}^{r}+p_{w}^{r+1}-p_{w}^{r}-(p_{v}^{r}+p_{v}^{r+1}-p_{v}^{r})$
$\displaystyle\leq
p_{w}^{r}+H_{w}(p_{w}^{r+1})-H_{w}(p_{w}^{r})-\left(p_{v}^{r}-\frac{H_{v}(p_{v}^{r+1})-H_{v}(p_{v}^{r})}{\vartheta}\right)$
$\displaystyle=p_{w}^{r}+\Delta_{w}^{r}-(p_{v}^{r}+\Delta_{v}^{r})+\left(1-\frac{1}{\vartheta}\right)(T+\Delta_{v}^{r})$
$\displaystyle\leq
p_{w}^{r}+\Delta_{w}^{r}-(p_{v}^{r}+\Delta_{v}^{r})+\left(1-\frac{1}{\vartheta}\right)(T+S+\delta)$
$\displaystyle\leq\frac{\|\vec{p}^{r}\|}{2}+\delta+\left(1-\frac{1}{\vartheta}\right)(T+S+\delta)$
$\displaystyle\leq\frac{S}{2}+\delta+\left(1-\frac{1}{\vartheta}\right)(T+S+\delta)\leq
S,$

where the second inequality uses the already established bound
$\Delta_{v}^{r}\leq S+\delta$, the third inequality follows from the second
statement of Lemma 5, the second to last inequality applies the precondition
$\|\vec{p}^{r}\|\leq S$, and the final inequality holds due to the
precondition on $S$. Since $v,w\in\mathcal{H}$ were arbitrary, we conclude
that $\|\vec{p}_{r+1}\|\leq S$. ∎

###### Proof of Theorem 8..

We begin by observing that

$\displaystyle S$
$\displaystyle=\frac{2(2\vartheta-1)(2u+(\vartheta^{2}-1)d)+2(\vartheta-1)T}{2-\vartheta+\vartheta^{2}-\vartheta^{3}}=\frac{2(2\vartheta-1)\delta+2(\vartheta-1)T}{2-\vartheta}>\delta$

and

$\displaystyle T$
$\displaystyle\geq\frac{(\vartheta^{2}+\vartheta+1)2(2\vartheta-1)(2u+(\vartheta^{2}-1)d)}{4-\vartheta+\vartheta^{2}-3\vartheta^{3}}+(\vartheta+1)d-2u$
$\displaystyle=(\vartheta^{2}+\vartheta+1)S+(\vartheta+1)d-2u.$

We prove the theorem by induction on the pulse number $r$, where the induction
hypothesis is that $\|\vec{p}^{r}\|\leq S$ and if $r\neq 0$ also

$\displaystyle\min_{w\in\mathcal{H}}\\{p_{w}^{r+1}\\}-\max_{w\in\mathcal{H}}\\{p_{w}^{r}\\}$
$\displaystyle\geq\frac{T-(\vartheta+1)S}{\vartheta}\quad\mbox{and}$
$\displaystyle\max_{w\in\mathcal{H}}\\{p_{w}^{r+1}\\}-\min_{w\in\mathcal{H}}\\{p_{w}^{r}\\}$
$\displaystyle\leq T+3S.$

The base case holds due to the condition of the theorem. For the step case,
assume that for $r\in\mathbb{N}$, $\|\vec{p}^{r}\|\leq S$. We invoke Lemma 7,
yielding that $\|\vec{p}^{r+1}\|\leq S$ and that
$(T-S)/\vartheta\leq\min_{w\in\mathcal{H}}\\{p_{w}^{r+1}\\}-\min_{w\in\mathcal{H}}\\{p_{w}^{r}\\}\leq
T+S+\delta$. Thus,

$\displaystyle\min_{w\in\mathcal{H}}\\{p_{w}^{r+1}\\}-\max_{w\in\mathcal{H}}\\{p_{w}^{r}\\}$
$\displaystyle\geq\min_{w\in\mathcal{H}}\\{p_{w}^{r+1}\\}-\min_{w\in\mathcal{H}}\\{p_{w}^{r}\\}+S\geq{T-(\vartheta+1)S}{\vartheta}$

and

$\displaystyle\max_{w\in\mathcal{H}}\\{p_{w}^{r+1}\\}-\min_{w\in\mathcal{H}}\\{p_{w}^{r}\\}$
$\displaystyle\leq\min_{w\in\mathcal{H}}\\{p_{w}^{r+1}\\}-\min_{w\in\mathcal{H}}\\{p_{w}^{r}\\}+S\leq
T+2S+\delta<T+3S.\qed$

###### Proof of Lemma 2..

We show the statement by inductively constructing triples of executions
$(\mathsf{Ex}_{k}^{1},\mathsf{Ex}^{k}_{2},\mathsf{Ex}_{k}^{3})$ for
$k\in\mathbb{N}$ satisfying $P$ and the following properties:

  * •

Faulty nodes send a total of $k$ messages in $\mathsf{Ex}^{1}_{k}$,
$\mathsf{Ex}^{2}_{k}$, and $\mathsf{Ex}^{3}_{k}$.

  * •

Let $h_{k}$ be the maximum local time at which a message from a faulty node is
received (or $0$ if faulty nodes send no messages). Honest node $i$ cannot
distinguish $\mathsf{Ex}^{i+1}_{k}$, $\mathsf{Ex}^{i+2}_{k}$,
$\mathsf{Ex}^{i+1}_{k+1}$, and $\mathsf{Ex}^{i+2}_{k+1}$ until time $h_{k}$.

  * •

Honest node $i$ cannot distinguish $\mathsf{Ex}^{i+1}_{k}$ and
$\mathsf{Ex}^{i+2}_{k}$ until time $h_{k}$.

Note that these conditions imply all preconditions of Lemma 1, except for the
existence of a node $i\in[3]$ that can distinguish executions
$\mathsf{Ex}^{i+1}$ and $\mathsf{Ex}^{i+2}$ after local time $h_{k}$. We begin
by noting that we can define
$(\mathsf{Ex}_{0}^{1},\mathsf{Ex}^{0}_{2},\mathsf{Ex}_{0}^{3})$ with the
necessary properties by having faulty nodes send no messages, setting message
delays to $d$, and defining the functions $H^{i}_{j}$ for all $i,j\in[3]$ as
stated above. This covers the base case of our induction.

Our induction stops at finite index $k_{0}$ if there does not exist a node
$i\in[3]$ which can distinguish executions $\mathsf{Ex}_{k_{0}}^{i+1}$ and
$\mathsf{Ex}_{k_{0}}^{i+2}$. For all $k$ not of this form, observe that if
$\mathsf{Ex}^{1}_{k}$, $\mathsf{Ex}^{2}_{k}$, and $\mathsf{Ex}^{3}_{k}$ with
the above properties exist, then all preconditions of Lemma 1 are met. Hence,
we can apply Lemma 1 for the step case of our induction, which yields
$\mathsf{Ex}_{k+1}^{1},\mathsf{Ex}_{k+1}^{2}$ and $\mathsf{Ex}_{k+1}^{2}$
which satisfy the properties stated above. This concludes the induction.

To conclude the proof, we distinguish two cases:

  * •

The induction halts at finite index $k_{0}$: Then $\mathsf{Ex}_{k_{0}}^{1}$,
$\mathsf{Ex}_{k_{0}}^{2}$, and $\mathsf{Ex}_{k_{0}}^{3}$ satisfy the
requirements of the lemma.

  * •

The induction does not halt: We note that for any two indices $k_{1}<k_{2}$
and $i\in[3]$, executions $\mathsf{Ex}_{k_{1}}^{i}$ and
$\mathsf{Ex}_{k_{2}}^{i}$ are indistinguishable up to local time $h_{k_{1}}$
in the view of nodes $i+1$ and $i+2$. Recall that this means that nodes $i+1$
and $i+2$ send and receive all messages in these executions at the same local
times (before local time $h_{k_{1}}$). This also means that these nodes send
and receive the same messages at the same local times before time
$t_{k_{1}}:=\min_{j\in\\{i+1,i+2\\}}(H^{i}_{j})^{-1}(h_{k_{1}})\geq
h_{k_{1}}-2\tilde{u}/3$. Also, this implies that the faulty node $i$ in these
executions sends and receives the same messages before time
$t_{k_{1}}-d+\tilde{u}=h_{k_{1}}-d+\tilde{u}/3$. Thus, we see that for any
$k$, executions $\mathsf{Ex}_{k}^{i},\mathsf{Ex}_{k+1}^{i},...$ are identical
until time $t_{k}-d+\tilde{u}/3$. By our model assumptions, nodes send a
finite amount of messages over any finite period of time. This implies that
$t_{k}$ grows unbounded as $k$ increases. Hence, there is a well-defined limit
execution $\mathsf{Ex}^{i}$ which for all $k\in\mathbb{N}$ is identical to
$\mathsf{Ex}_{k}^{i}$ before time $t_{k}$. These executions satisfy the claim
of the lemma.∎