method on $\mathit{view\\_timer}_{i}$ (line 8); we denote this invocation by
$\mathit{Inv}^{\prime}_{v}$. When $\mathit{Inv}_{v}^{\prime}$ was invoked,
$\mathit{epoch}_{i}=e_{\mathit{final}}$ and $\mathit{view}_{i}=f+1$. By Lemma
A.28, we know that the earliest time $\mathit{Inv}_{v}^{\prime}$ can be
canceled (line 16 or line 22) is
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$.

Let us investigate the first time $P_{i}$ enters another view after entering
the $j$-th view of $e_{\mathit{final}}$. This could happen at the following
places of Algorithm 2:

    * –

line 9: This means that, when processing the expiration event of
$\mathit{view\\_timer}_{i}$ (denoted by $\mathit{Exp}_{v}^{*}$) at line 4
(before executing the check at line 5), $\mathit{view}_{i}<f+1$. Hence,
$\mathit{Exp}_{v}^{*}$ is not produced by $\mathit{Inv}_{v}^{\prime}$ (by
Lemma A.13).

By contradiction, suppose that $\mathit{Exp}_{v}^{*}$ is processed before time
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$. In this case,
$\mathit{Exp}_{v}^{*}$ is processed before the expiration event produced by
$\mathit{Inv}_{v}^{\prime}$ would (potentially) be processed (which is
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$ at the earliest). Thus,
$\mathit{Inv}_{v}^{\prime}$ must be immediately followed by an invocation of
the $\mathsf{cancel()}$ method on $\mathit{view\\_timer}_{i}$ in
$h_{i}|_{\mathit{view}}$ (by lemmas A.7 and A.9). As previously shown, the
earliest time $\mathit{Inv}^{\prime}_{v}$ can be canceled is
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$, which implies that
$\mathit{Exp}_{v}^{*}$ cannot be processed before time
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$. Therefore,
$\mathit{Exp}_{v}^{*}$ is processed at
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$ (at the earliest), which
concludes the induction step for this case.

    * –

line 30: Suppose that, by contradiction, this happens before time
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$. Hence, the
$\mathsf{measure}(\cdot)$ method was invoked on
$\mathit{dissemination\\_timer}_{i}$ (line 18 or line 24) before time
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$ (by Lemma A.3) and after
$P_{i}$ has entered the $j$-th view of $e_{\mathit{final}}$, which implies
that $\mathit{Inv}_{v}^{\prime}$ is canceled before time
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$ (line 16 or line 22).
However, this is impossible as the earliest time for
$\mathit{Inv}^{\prime}_{v}$ to be canceled is
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$. Hence, $P_{i}$ enters
another view at time $t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$ (at
the earliest), which concludes the induction step in this case.

The conclusion of the induction step concludes the proof of the lemma.

Finally, we prove that RareSync ensures the eventual synchronization property.

######  Theorem A.32 (Eventual synchronization).

RareSync ensures eventual synchronization. Moreover, the first synchronization
time at or after $\mathit{GST}$ occurs by time
$t_{e_{\mathit{final}}}+f\cdot\mathit{view\\_duration}+2\delta$.

######  Proof A.33.

Lemma A.30 proves that all correct processes overlap in each view of
$e_{\mathit{final}}$ for (at least) $\Delta$ time. As the leader of one view
of $e_{\mathit{final}}$ must be correct (since $\mathsf{leader}(\cdot)$ is a
round-robin function), the eventual synchronization is satisfied by RareSync:
correct processes synchronize in (at least) one of the views of
$e_{\mathit{final}}$. Finally, as the last view of $e_{\mathit{final}}$ is
entered by every correct process by time
$t^{*}=t_{e_{\mathit{final}}}+f\cdot\mathit{view\\_duration}+2\delta$ (by
Lemma A.30), the first synchronization time at or after $\mathit{GST}$ must
occur by time $t^{*}$.

Proof of complexity. We start by showing that, if a correct process sends an
epoch-completed message for an epoch $e$, then the “most recent” epoch entered
by the process is $e$.

######  Lemma A.34.

Let $P_{i}$ be a correct process and let $P_{i}$ send an epoch-completed
message for an epoch $e$ (line 12). Then, $e$ is the last epoch entered by
$P_{i}$ in $\beta_{i}$ before sending the epoch-completed message.

######  Proof A.35.

By Lemma A.17, $P_{i}$ enters $e$ before sending the epoch-completed message
for $e$. By contradiction, suppose that $P_{i}$ enters some other epoch
$e^{*}$ after entering $e$ and before sending the epoch-completed message for
$e$. By Lemma A.5, $e^{*}>e$.

When $P_{i}$ enters $e^{*}$ (line 30), $\mathit{epoch}_{i}=e^{*}$. As the
value of the $\mathit{epoch}_{i}$ variable only increases throughout the
execution, $P_{i}$ does not send the epoch-completed message for $e$ after
entering $e^{*}>e$. Thus, we reach a contradiction, and the lemma holds.

Next, we show that, if a correct process sends an enter-epoch message for an
epoch $e$ at time $t$, the process enters $e$ at time $t$.

######  Lemma A.36.

Let a correct process $P_{i}$ send an enter-epoch message (line 26) for an
epoch $e$ at time $t$. Then, $P_{i}$ enters $e$ at time $t$.

######  Proof A.37.

When $P_{i}$ sends the enter-epoch message, we have that
$\mathit{epoch}_{i}=e$. Hence, $P_{i}$ enters $e$ at time $t$ (line 30).

Next, we show that a correct process sends (at most) $O(n)$ epoch-completed
messages for a specific epoch $e$.

######  Lemma A.38.

For any epoch $e$ and any correct process $P_{i}$, $P_{i}$ sends at most
$O(n)$ epoch-completed messages for $e$ (line 12).

######  Proof A.39.

Let $\mathit{Exp}_{v}$ denote the first expiration event of
$\mathit{view\\_timer}_{i}$ which $P_{i}$ processes (line 4) in order to
broadcast the epoch-completed message for $e$ (line 12); if $\mathit{Exp}_{v}$
does not exist, the lemma trivially holds. Hence, let $\mathit{Exp}_{v}$
exist.

When $\mathit{Exp}_{v}$ was processed, $\mathit{epoch}_{i}=e$. Let
$\mathit{Inv}^{\prime}_{v}$ denote the first invocation of the
$\mathsf{measure}(\cdot)$ method on $\mathit{view\\_timer}_{i}$ after the
processing of $\mathit{Exp}_{v}$. If $\mathit{Inv}^{\prime}_{v}$ does not
exist, there does not exist an expiration event of $\mathit{view\\_timer}_{i}$
processed after $\mathit{Exp}_{v}$ (by Lemma A.11), which implies that the
lemma trivially holds.

Let us investigate where $\mathit{Inv}^{\prime}_{v}$ could have been invoked:

  * •

line 8: By Lemma A.11, we conclude that the processing of $\mathit{Exp}_{v}$
leads to $\mathit{Inv}^{\prime}_{v}$. However, this is impossible as the
processing of $\mathit{Exp}_{v}$ leads to the broadcasting of the epoch-
completed messages (see the check at line 5).

  * •

line 29: In this case, $P_{i}$ processes an expiration event
$\mathit{Exp}_{d}$ of $\mathit{dissemination\\_timer}_{i}$ (line 25). By Lemma
A.3, the invocation $\mathit{Inv}_{d}$ of the $\mathsf{measure}(\cdot)$ method
on $\mathit{dissemination\\_timer}_{i}$ immediately precedes
$\mathit{Exp}_{d}$ in $h_{i}$. Hence, $\mathit{Inv}_{d}$ follows
$\mathit{Exp}_{v}$ in $h_{i}$ and $\mathit{Inv}_{d}$ could have been invoked
either at line 18 or at line 24. Just before invoking $\mathit{Inv}_{d}$,
$P_{i}$ changes its $\mathit{epoch}_{i}$ variable to a value greater than $e$
(line 15 or line 21; the value of $\mathit{epoch}_{i}$ only increases
throughout the execution).

Therefore, when $\mathit{Inv}^{\prime}_{v}$ is invoked,
$\mathit{epoch}_{i}>e$. As the value of the $\mathit{epoch}_{i}$ variable only
increases throughout the execution, $P_{i}$ broadcasts the epoch-completed
messages for $e$ at most once (by Lemma A.11), which concludes the proof.

The following lemma shows that a correct process sends (at most) $O(n)$ enter-
epoch messages for a specific epoch $e$.

######  Lemma A.40.

For any epoch $e$ and any correct process $P_{i}$, $P_{i}$ sends at most
$O(n)$ enter-epoch messages for $e$ (line 26).

######  Proof A.41.

Let $\mathit{Exp}_{d}$ denote the first expiration event of
$\mathit{dissemination\\_timer}_{i}$ which $P_{i}$ processes (line 25) in
order to broadcast the enter-epoch message for $e$ (line 26); if
$\mathit{Exp}_{d}$ does not exist, the lemma trivially holds. When
$\mathit{Exp}_{d}$ was processed, $\mathit{epoch}_{i}=e$. Let
$\mathit{Inv}^{\prime}_{d}$ denote the first invocation of the
$\mathsf{measure}(\cdot)$ method on $\mathit{dissemination\\_timer}_{i}$ after
the processing of $\mathit{Exp}_{d}$. If $\mathit{Inv}^{\prime}_{d}$ does not
exist, there does not exist an expiration event of
$\mathit{dissemination\\_timer}_{i}$ processed after $\mathit{Exp}_{d}$ (by
Lemma A.3), which implies that the lemma trivially holds.

$\mathit{Inv}^{\prime}_{d}$ could have been invoked either at line 18 or at
line 24. However, before that (still after the processing of
$\mathit{Exp}_{d}$), $P_{i}$ changes its $\mathit{epoch}_{i}$ variable to a
value greater than $e$ (line 15 or line 21). Therefore, when
$\mathit{Inv}^{\prime}_{d}$ is invoked, $\mathit{epoch}_{i}>e$. As the value
of the $\mathit{epoch}_{i}$ variable only increases throughout the execution,
$P_{i}$ broadcasts the enter-epoch messages for $e$ at most once (by Lemma
A.3), which concludes the proof.

Next, we show that, after $\mathit{GST}$, two “epoch-entering” events are
separated by at least $\delta$ time.

######  Lemma A.42.

Let $P_{i}$ be a correct process. Let $P_{i}$ trigger $\mathsf{advance}(v)$ at
time $t\geq\mathit{GST}$ and let $P_{i}$ trigger
$\mathsf{advance}(v^{\prime})$ at time $t^{\prime}$ such that (1)
$\mathsf{advance}(v)\stackrel{{\scriptstyle\beta_{i}}}{{\prec}}\mathsf{advance}(v^{\prime})$,
and (2) $v$ (resp., $v^{\prime}$) is the first view of an epoch $e$ (resp.,
$e^{\prime}$). Then, $t^{\prime}\geq t+\delta$.

######  Proof A.43.

Let $\mathsf{advance}(v^{*})$, where $v^{*}$ is the first view of an epoch
$e^{*}$, be the first “epoch-entering” event following $\mathsf{advance}(v)$
in $\beta_{i}$ (i.e.,
$\mathsf{advance}(v)\stackrel{{\scriptstyle\beta_{i}}}{{\prec}}\mathsf{advance}(v^{*})$);
let $\mathsf{advance}(v^{*})$ be triggered at time $t^{*}$. In order to prove
the lemma, it suffices to show that $t^{*}\geq t+\delta$.

The $\mathsf{advance}(v^{*})$ upcall is triggered at line 30. Let
$\mathit{Exp}_{d}$ denote the processed expiration event of
$\mathit{dissemination\\_timer}_{i}$ (line 25) which leads $P_{i}$ to trigger
$\mathsf{advance}(v^{*})$. Let $\mathit{Inv}_{d}$ denote the invocation of the
$\mathsf{measure}(\delta)$ on $\mathit{dissemination\\_timer}_{i}$ that has
produces $\mathit{Exp}_{d}$. By Lemma A.3, $\mathit{Inv}_{d}$ immediately
precedes $\mathit{Exp}_{d}$ in the timer history $h_{i}$ of $P_{i}$. Note that
$\mathit{Inv}_{d}$ was invoked after $P_{i}$ has entered $e$ (this follows
from Lemma A.3 and the fact that $P_{i}$ enters $e$ after invoking
$\mathsf{measure}(\cdot)$ on $\mathit{view\\_timer}_{i}$), which means that
$\mathit{Inv}_{d}$ was invoked at some time $\geq t\geq\mathit{GST}$. As local
clocks do not drift after $\mathit{GST}$, $\mathit{Exp}_{d}$ is processed at
some time $\geq t+\delta$, which concludes the proof.

Next, we define $t_{s}$ as the first synchronization time at or after
$\mathit{GST}$.

######  Definition A.44.

We denote by $t_{s}$ the first synchronization time at or after $\mathit{GST}$
(i.e., $t_{s}\geq\mathit{GST}$).

The next lemma shows that no correct process enters any epoch greater than
$e_{\mathit{final}}$ by $t_{s}+\Delta$. This lemma is the consequence of Lemma
A.28 and Theorem A.32.

######  Lemma A.45.

No correct process enters an epoch greater than $e_{\mathit{final}}$ by time
$t_{s}+\Delta$.

######  Proof A.46.

By Lemma A.28, no correct process enters an epoch $>e_{\mathit{final}}$ before
time $t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$. By Theorem A.32, we
have that $t_{s}<t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}-\Delta$,
which implies that
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}>t_{s}+\Delta$. Hence, the
lemma.

Next, we define $e_{\mathit{max}}$ as the greatest epoch entered by a correct
process before time $\mathit{GST}$. Note that $e_{\mathit{max}}$ is properly
defined in any execution as only finite executions are possible until
$\mathit{GST}$.

######  Definition A.47.

We denote by $e_{\mathit{max}}$ the greatest epoch entered by a correct
process before $\mathit{GST}$. If no such epoch exists, $e_{\mathit{max}}=0$.

The next lemma shows that $e_{\mathit{final}}$ (Definition A.25) is
$e_{\mathit{max}}+1$.

######  Lemma A.48.

$e_{\mathit{final}}=e_{\mathit{max}}+1$.

######  Proof A.49.

If $e_{\mathit{max}}=0$, then $e_{\mathit{final}}=1$. Hence, let
$e_{\mathit{max}}>0$ in the rest of the proof.

By the definitions of $e_{\mathit{final}}$ (Definition A.25) and
$e_{\mathit{max}}$ (Definition A.47) and by Lemma A.21,
$e_{\mathit{final}}\geq e_{\mathit{max}}+1$. Therefore, we need to prove that
$e_{\mathit{final}}\leq e_{\mathit{max}}+1$.

By contradiction, suppose that $e_{\mathit{final}}>e_{\mathit{max}}+1$. By
Lemma A.21, epoch $e_{\mathit{final}}-1$ was entered by the first correct
process at some time $t_{\mathit{prev}}\leq t_{e_{\mathit{final}}}$. Note that
$e_{\mathit{final}}-1\geq e_{\mathit{max}}+1$. Moreover,
$t_{\mathit{prev}}\geq\mathit{GST}$; otherwise, we would contradict the
definition of $e_{\mathit{max}}$. Thus, the first new epoch to be entered by a
correct process at or after $\mathit{GST}$ is not $e_{\mathit{final}}$, i.e.,
we contradict Definition A.25. Hence, the lemma holds.

Next, we show that every correct process enters epoch $e_{\mathit{max}}$ by
time $\mathit{GST}+2\delta$ or epoch $e_{\mathit{final}}=e_{\mathit{max}}+1$
by time $\mathit{GST}+3\delta$.

######  Lemma A.50.

Every correct process (1) enters epoch $e_{\mathit{max}}$ by
$\mathit{GST}+2\delta$, or (2) enters epoch $e_{\mathit{max}}+1$ by
$\mathit{GST}+3\delta$.

######  Proof A.51.

Lemma A.48 shows that $e_{\mathit{final}}$ is $e_{\mathit{max}}+1$. Recall
that $t_{e_{\mathit{final}}}\geq\mathit{GST}$. Consider a correct process
$P_{i}$. If $e_{\mathit{max}}=1$ (resp., $e_{\mathit{final}}=1$), then $P_{i}$
enters $e_{\mathit{max}}$ (resp., $e_{\mathit{final}}$) by time
$\mathit{GST}$, which concludes the lemma. Hence, let $e_{\mathit{max}}>1$;
thus, $e_{\mathit{final}}>1$ by Lemma A.48.

Lemma A.28 proves that no correct process broadcasts an epoch-completed
message for an epoch $\geq e_{\mathit{max}}+1$ before time
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}\geq\mathit{GST}+\mathit{epoch\\_duration}$.

By time $\mathit{GST}+\delta$, every correct process $P_{i}$ receives an
enter-epoch message for epoch $e_{\mathit{max}}>1$ (line 19) sent by the
correct process which has entered $e_{\mathit{max}}$ before $\mathit{GST}$
(the message is sent at line 26). Therefore, by time $\mathit{GST}+\delta$,
$\mathit{epoch}_{i}$ is either $e_{\mathit{max}}$ or $e_{\mathit{max}}+1$;
note that $\mathit{epoch}_{i}$ cannot take a value greater than
$e_{\mathit{max}}+1$ before time
$\mathit{GST}+\mathit{epoch\\_duration}>\mathit{GST}+\delta$ since no correct
process broadcasts an epoch-completed message for an epoch $\geq
e_{\mathit{max}}+1$ before this time.

Let us consider both scenarios:

  * •

Let $\mathit{epoch}_{i}=e_{\mathit{max}}+1$ by time $\mathit{GST}+\delta$. In
this case, $\mathit{dissemination\\_timer}_{i}$ expires in $\delta$ time (line
25), and $P_{i}$ enters $e_{\mathit{max}}+1$ by time $\mathit{GST}+2\delta$
(line 30) as $\mathit{GST}+\mathit{epoch\\_duration}>\mathit{GST}+2\delta$.
Hence, the statement of the lemma is satisfied in this case.

  * •

Let $\mathit{epoch}_{i}=e_{\mathit{max}}$ by time $\mathit{GST}+\delta$. If,
within $\delta$ time from updating $\mathit{epoch}_{i}$ to $e_{\mathit{max}}$,
$P_{i}$ does not cancel its $\mathit{dissemination\\_timer}_{i}$,
$\mathit{dissemination\\_timer}_{i}$ expires (line 4), and $P_{i}$ enters
$e_{\mathit{max}}$ by time $\mathit{GST}+2\delta$.

Otherwise, $\mathit{epoch}_{i}=e_{\mathit{max}}+1$ by time
$\mathit{GST}+2\delta$ as $\mathit{dissemination\\_timer}_{i}$ was canceled;
$\mathit{epoch}_{i}$ cannot take any other value as epoch-completed messages
are not broadcast before time
$\mathit{GST}+\mathit{epoch\\_duration}>\mathit{GST}+2\delta$. As in the
previous case, $\mathit{dissemination\\_timer}_{i}$ expires in $\delta$ time
(line 25), and $P_{i}$ enters $e_{\mathit{max}}+1$ by time
$\mathit{GST}+3\delta$ (line 30) as
$\mathit{GST}+\mathit{epoch\\_duration}>\mathit{GST}+3\delta$. Hence, the
statement of the lemma holds in this case, as well.

Since the lemma is satisfied in both possible scenarios, the proof is
concluded.

The direct consequence of Lemma A.48 is that
$t_{e_{\mathit{final}}}\leq\mathit{GST}+\mathit{epoch\\_duration}+4\delta$.

######  Lemma A.52.

$t_{e_{\mathit{final}}}\leq\mathit{GST}+\mathit{epoch\\_duration}+4\delta$.

######  Proof A.53.

By contradiction, let
$t_{e_{\mathit{final}}}>\mathit{GST}+\mathit{epoch\\_duration}+4\delta$. Lemma
A.50 proves that every correct process enters epoch $e_{\mathit{max}}$ by time
$\mathit{GST}+2\delta$ or epoch $e_{\mathit{final}}=e_{\mathit{max}}+1$ by
time $\mathit{GST}+3\delta$. Additionally, Lemma A.28 proves that no correct
process broadcasts an epoch-completed message for an epoch $\geq
e_{\mathit{final}}$ (line 12) before time
$t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}>\mathit{GST}+2\cdot\mathit{epoch\\_duration}+4\delta$.

If any correct process enters $e_{\mathit{max}}+1$ by time
$\mathit{GST}+3\delta$, we reach a contradiction with the fact that
$t_{e_{\mathit{final}}}>\mathit{GST}+\mathit{epoch\\_duration}+4\delta$ since
$e_{\mathit{final}}=e_{\mathit{max}}+1$ (by Lemma A.48). Therefore, all
correct processes enter $e_{\mathit{max}}$ by time $\mathit{GST}+2\delta$.

Since $t_{e_{\mathit{final}}}>\mathit{GST}+\mathit{epoch\\_duration}+4\delta$,
no correct process $P_{i}$ updates its $\mathit{epoch}_{i}$ variable to
$e_{\mathit{max}}+1$ (at line 15 or line 21) by time
$\mathit{GST}+\mathit{epoch\\_duration}+3\delta$ (otherwise, $P_{i}$ would
have entered $e_{\mathit{max}}+1$ by time
$\mathit{GST}+\mathit{epoch\\_duration}+4\delta$, which contradicts
$t_{e_{\mathit{final}}}>\mathit{GST}+\mathit{epoch\\_duration}+4\delta$). By
time $\mathit{GST}+\mathit{epoch\\_duration}+2\delta$, all correct processes
broadcast an epoch-completed message for $e_{\mathit{max}}$ (line 12). By time
$\mathit{GST}+\mathit{epoch\\_duration}+3\delta$, every correct process
$P_{i}$ receives $2f+1$ epoch-completed messages for $e_{\mathit{max}}$ (line
13), and updates its $\mathit{epoch}_{i}$ variable to $e_{\mathit{max}}+1$
(line 15). This represents a contradiction with the fact that $P_{i}$ does not
update its $\mathit{epoch}_{i}$ variable to $e_{\mathit{max}}+1$ by time
$\mathit{GST}+\mathit{epoch\\_duration}+3\delta$, which concludes the proof.

The final lemma shows that no correct process enters more than $O(1)$ epochs
during the time period $[\mathit{GST},t_{s}+\Delta]$.

######  Lemma A.54.

No correct process enters more than $O(1)$ epochs in the time period
$[\mathit{GST},t_{s}+\Delta]$.

######  Proof A.55.

Consider a correct process $P_{i}$. Process $P_{i}$ enters epoch
$e_{\mathit{max}}$ by time $\mathit{GST}+2\delta$ or $P_{i}$ enters epoch
$e_{\mathit{max}}+1$ by time $\mathit{GST}+3\delta$ (by Lemma A.50). Lemma
A.48 shows that $e_{\mathit{final}}=e_{\mathit{max}}+1$. Finally, no correct
process enters an epoch greater than $e_{\mathit{final}}=e_{\mathit{max}}+1$
by time $t_{s}+\Delta$ (by Lemma A.45).

Let us consider two scenarios according to Lemma A.50:

  1. 1.

By time $\mathit{GST}+2\delta$, $P_{i}$ enters $e_{\mathit{max}}$; let $P_{i}$
enter $e_{\mathit{max}}$ at time $t^{*}\leq\mathit{GST}+2\delta$. By Lemma
A.5, during the time period $[t^{*},t_{s}+\Delta]$, $P_{i}$ enters (at most)
$2=O(1)$ epochs (epochs $e_{\mathit{max}}$ and $e_{\mathit{max}}+1$). Finally,
during the time period $[\mathit{GST},t^{*})$, Lemma A.42 shows that $P_{i}$
enters (at most) $2=O(1)$ epochs (as $t^{*}\leq\mathit{GST}+2\delta$). Hence,
in this case, $P_{i}$ enters (at most) $4=O(1)$ epochs during the time period
$[\mathit{GST},t_{s}+\Delta]$.

  2. 2.

By time $\mathit{GST}+3\delta$, $P_{i}$ enters $e_{\mathit{max}}+1$; let
$P_{i}$ enter $e_{\mathit{max}}+1$ at time $t^{*}\leq\mathit{GST}+3\delta$. By
Lemma A.5, during the time period $[t^{*},t_{s}+\Delta]$, $P_{i}$ enters (at
most) $1=O(1)$ epoch (epoch $e_{\mathit{max}}+1$). Finally, during the time
period $[\mathit{GST},t^{*})$, Lemma A.42 shows that $P_{i}$ enters (at most)
$3=O(1)$ epochs (as $t^{*}\leq\mathit{GST}+3\delta$). Hence, in this case,
$P_{i}$ enters (at most) $4=O(1)$ epochs during the time period
$[\mathit{GST},t_{s}+\Delta]$.

Hence, during the time period $[\mathit{GST},t_{s}+\Delta]$, $P_{i}$ enters
(at most) $4=O(1)$ epochs.

Finally, we prove that RareSync achieves $O(n^{2})$ communication and $O(f)$
latency.

######  Theorem A.56 (Complexity).

RareSync achieves $O(n^{2})$ communication complexity and $O(f)$ latency
complexity.

######  Proof A.57.

Fix a correct process $P_{i}$. For every epoch $e$, $P_{i}$ sends (at most)
$O(n)$ epoch-completed and enter-epoch messages for $e$ (by lemmas A.38 and
A.40). Moreover, if $P_{i}$ sends an epoch-completed message for an epoch $e$
at time $t$, then $e$ is the last epoch entered by $P_{i}$ prior to sending
the message (by Lemma A.34). Similarly, if $P_{i}$ sends an enter-epoch
message for an epoch $e$ at time $t$, then $P_{i}$ enters $e$ at $t$ (by Lemma
A.36). Hence, during the time period $[\mathit{GST},t_{s}+\Delta]$, $P_{i}$
sends epoch-completed or enter-epoch messages for (at most) $O(1)$ epochs (by
Lemma A.54). Thus, $P_{i}$ sends (at most) $O(1)\cdot O(n)=O(n)$ messages
during the time period $[\mathit{GST},t_{s}+\Delta]$, which implies that
$P_{i}$ sends $O(n)$ words in this time period (as each epoch-completed and
enter-epoch message contains a single word). Therefore, the communication
complexity of RareSync is indeed $n\cdot O(n)=O(n^{2})$.

By Theorem A.32,
$t_{s}+\Delta<t_{e_{\mathit{final}}}+\mathit{epoch\\_duration}$. Moreover,
Lemma A.52 shows that
$t_{e_{\mathit{final}}}\leq\mathit{GST}+\mathit{epoch\\_duration}+4\delta$.
Therefore,
$t_{s}+\Delta<\mathit{GST}+2\cdot\mathit{epoch\\_duration}+4\delta$.
Furthermore,
$t_{s}+\Delta-\mathit{GST}<2\cdot\mathit{epoch\\_duration}+4\delta$. Since
$\mathit{epoch\\_duration}=(f+1)\cdot\mathit{view\\_duration}=O(f)$ (recall
that $\mathit{view\\_duration}$ is constant),
$t_{s}+\Delta-\mathit{GST}=O(f)$, which proves the linear latency complexity
of RareSync.

##  Appendix B Quad: Pseudocode & Proof of Correctness and Complexity

In this section, we give the complete pseudocode of Quad’s view core module
(Algorithms 6 and 7), and we formally prove that Quad solves consensus (with
weak validity) with $O(n^{2})$ communication complexity and $O(f)$ latency
complexity.

Algorithm 6 Quad: View core’s utilities (for process $P_{i}$)

1:function $\mathsf{msg(String}\text{ }\mathit{type},\mathsf{Value}\text{
}\mathit{value},\mathsf{Quorum\\_Certificate}\text{
}\mathit{qc},\mathsf{View}\text{ }\mathit{view}\mathsf{)}$:

2: $m.\mathit{type}\leftarrow\mathit{type}$;
$m.\mathit{value}\leftarrow\mathit{value}$;
$m.\mathit{qc}\leftarrow\mathit{qc}$; $m.\mathit{view}\leftarrow\mathit{view}$

3: return $m$

4:function $\mathsf{vote\\_msg(String}\text{
}\mathit{type},\mathsf{Value}\text{
}\mathit{value},\mathsf{Quorum\\_Certificate}\text{
}\mathit{qc},\mathsf{View}\text{ }\mathit{view}\mathsf{)}$:

5:
$m\leftarrow\mathsf{msg(}\mathit{type},\mathit{value},\mathit{qc},\mathit{view}\mathsf{)}$

6:
$m.\mathit{partial\\_sig}\leftarrow\mathit{ShareSign}_{i}([m.\mathit{type},m.\mathit{value},m.\mathit{view}])$

7: return $m$

8:$\triangleright$ All the messages in $M$ have the same type, value and view

9:function $\mathsf{qc(Set(Vote\\_Message)}\text{ }M\mathsf{)}$:

10: $\mathit{qc}.\mathit{type}\leftarrow m.\mathit{type}$, where $m\in M$

11: $\mathit{qc}.\mathit{value}\leftarrow m.\mathit{value}$, where $m\in M$

12: $\mathit{qc}.\mathit{view}\leftarrow m.\mathit{view}$, where $m\in M$

13:
$\mathit{qc}.\mathit{sig}\leftarrow\mathit{Combine}\big{(}\\{\mathit{partial\\_sig}\,|\,\mathit{partial\\_sig}\text{
is in a message that belongs to }M\\}\big{)}$

14: return $\mathit{qc}$

15:function $\mathsf{matching\\_msg(Message}\text{ }m,\mathsf{String}\text{
}\mathit{type},\mathsf{View}\text{ }\mathit{view}\mathsf{)}$:

16: return $m.\mathit{type}=\mathit{type}$ and $m.\mathit{view}=\mathit{view}$

17:function $\mathsf{matching\\_qc(Quorum\\_Certificate}\text{
}\mathit{qc},\mathsf{String}\text{ }\mathit{type},\mathsf{View}\text{
}\mathit{view}\mathsf{)}$:

18: return $\mathit{qc}.\mathit{type}=\mathit{type}$ and
$\mathit{qc}.\mathit{view}=\mathit{view}$

Algorithm 7 Quad: View core (for process $P_{i}$)

1:upon $\mathsf{init(Value}\text{ }\mathit{proposal})$:

2: $\mathit{proposal}_{i}\leftarrow\mathit{proposal}$ $\triangleright$
$P_{i}$’s proposal

3:upon $\mathsf{start\\_executing(View}\text{ }\mathit{view}\mathsf{)}$:

4: $\triangleright$ Prepare phase

5: send $\mathsf{msg(}\textsc{view-
change},\bot,\mathit{prepareQC},\mathit{view}\mathsf{)}$ to
$\mathsf{leader}(\mathit{view})$

6: as $\mathsf{leader}(\mathit{view})$:

7: wait for $2f+1$ view-change messages:

8: $M\leftarrow\\{m\,|\,\mathsf{matching\\_msg(}m,\textsc{view-
change},\mathit{view}\mathsf{)}\\}$

9: $\mathsf{Quorum\\_Certificate}\text{ }\mathit{highQC}\leftarrow\mathit{qc}$
with the highest $\mathit{qc}.\mathit{view}$ in $M$

10: $\mathsf{Value}\text{
}\mathit{proposal}\leftarrow\mathit{highQC}.\mathit{value}$

11: if $\mathit{proposal}=\bot$:

12: $\mathit{proposal}\leftarrow\mathit{proposal}_{i}$ $\triangleright$
$\mathit{proposal}_{i}$ denotes the proposal of $P_{i}$

13: broadcast
$\mathsf{msg(}\textsc{prepare},\mathit{proposal},\mathit{highQC},\mathit{view}\mathsf{)}$

14: as a process: $\triangleright$ every process executes this part of the
pseudocode

15: wait for message $m$:
$\mathsf{matching\\_msg(}m,\textsc{prepare},\mathit{view}\mathsf{)}$ from
$\mathsf{leader}(\mathit{view})$

16: if $m.\mathit{qc}.\mathit{value}=m.\mathit{value}$ and
($\mathit{lockedQC}.\mathit{value}=m.\mathit{value}$ or
$\mathit{qc}.\mathit{view}>\mathit{lockedQC}.\mathit{view}$):

17: send
$\mathsf{vote\\_msg(}\textsc{prepare},m.\mathit{value},\bot,\mathit{view}\mathsf{)}$
to $\mathsf{leader}(\mathit{view})$

18: $\triangleright$ Precommit phase

19: as $\mathsf{leader}(\mathit{view})$:

20: wait for $2f+1$ votes:
$V\leftarrow\\{\mathit{vote}\,|\,\mathsf{matching\\_msg(}\mathit{vote},\textsc{prepare},\mathit{view}\mathsf{)}\\}$

21: $\mathsf{Quorum\\_Certificate}\text{
}\mathit{qc}\leftarrow\mathsf{qc(}V\mathsf{)}$

22: broadcast
$\mathsf{msg(}\textsc{precommit},\bot,\mathit{qc},\mathit{view}\mathsf{)}$

23: as a process: $\triangleright$ every process executes this part of the
pseudocode

24: wait for message $m$:
$\mathsf{matching\\_qc(}m.\mathit{qc},\textsc{prepare},\mathit{view}\mathsf{)}$
from $\mathsf{leader}(\mathit{view})$

25: $\mathit{prepareQC}\leftarrow m.\mathit{qc}$

26: send
$\mathsf{vote\\_msg(}\textsc{precommit},m.\mathit{qc}.\mathit{value},\bot,\mathit{view}\mathsf{)}$
to $\mathsf{leader}(\mathit{view})$

27: $\triangleright$ Commit phase

28: as $\mathsf{leader}(\mathit{view})$:

29: wait for $2f+1$ votes:
$V\leftarrow\\{\mathit{vote}\,|\,\mathsf{matching\\_msg(}\mathit{vote},\textsc{precommit},\mathit{view}\mathsf{)}\\}$

30: $\mathsf{Quorum\\_Certificate}$
$\mathit{qc}\leftarrow\mathsf{qc(}V\mathsf{)}$

31: broadcast
$\mathsf{msg(}\textsc{commit},\bot,\mathit{qc},\mathit{view}\mathsf{)}$

32: as a process: $\triangleright$ every process executes this part of the
pseudocode

33: wait for message $m$:
$\mathsf{matching\\_qc(}m.\mathit{qc},\textsc{precommit},\mathit{view}\mathsf{)}$
from $\mathsf{leader}(\mathit{view})$

34: $\mathit{lockedQC}\leftarrow m.\mathit{qc}$

35: send
$\mathsf{vote\\_msg(}\textsc{commit},m.\mathit{qc}.\mathit{value},\bot,\mathit{view}\mathsf{)}$
to $\mathsf{leader}(\mathit{view})$

36: $\triangleright$ Decide phase

37: as $\mathsf{leader}(\mathit{view})$:

38: wait for $2f+1$ votes:
$V\leftarrow\\{\mathit{vote}\,|\,\mathsf{matching\\_msg(}\mathit{vote},\textsc{commit},\mathit{view}\mathsf{)}\\}$

39: $\mathsf{Quorum\\_Certificate}$
$\mathit{qc}\leftarrow\mathsf{qc(}V\mathsf{)}$

40: broadcast
$\mathsf{msg(}\textsc{decide},\bot,\mathit{qc},\mathit{view}\mathsf{)}$

41: as a process: $\triangleright$ every process executes this part of the
pseudocode

42: wait for message $m$:
$\mathsf{matching\\_qc(}m.\mathit{qc},\textsc{commit},\mathit{view}\mathsf{)}$
from $\mathsf{leader}(\mathit{view})$

43: trigger $\mathsf{decide}(m.\mathit{qc}.\mathit{value})$

Proof of correctness. In this paragraph, we show that Quad ensures weak
validity, termination and agreement. Recall that the main body of Quad is
given in Algorithm 3, whereas its view synchronizer RareSync is presented in
Algorithm 2 and its view core in Algorithm 7. We underline that the proofs
concerned with the view core of Quad can be found in [56], as Quad uses the
same view core as HotStuff.

We start by proving that Quad ensures weak validity.

######  Theorem B.1 (Weak validity).

Quad ensures weak validity.

######  Proof B.2.

Suppose that all processes are correct. Whenever a correct process updates its
$\mathit{prepareQC}$ variable (line 25 of Algorithm 7), it updates it to a
quorum certificate vouching for a proposed value. Therefore, leaders always
propose a proposed value since the proposed value is “formed” out of
$\mathit{prepareQC}$s of processes (line 9 of Algorithm 7). Given that a
correct process executes line 43 of Algorithm 7 for a value proposed by the
leader of the current view, which is proposed by a process (recall that all
processes are correct), the weak validity property is ensured.

Next, we prove agreement.

######  Theorem B.3 (Agreement).

Quad ensures agreement.

######  Proof B.4.

Two conflicting quorum certificates associated with the same view cannot be
obtained in the view core of Quad (Algorithm 7); otherwise, a correct process
would vote for both certificates, which is not possible according to Algorithm
7. Therefore, two correct processes cannot decide different values from the
view core of Quad in the same view. Hence, we need to show that, if a correct
process decides $v$ in some view $\mathit{view}$ in the view core (line 43 of
Algorithm 7), then no conflicting quorum certificate can be obtained in the
future views.

Since a correct process decides $v$ in view $\mathit{view}$ in the view core,
the following holds at $f+1$ correct processes:
$\mathit{lockedQC}.\mathit{value}=v$ and
$\mathit{lockedQC}.\mathit{view}=\mathit{view}$ (line 34 of Algorithm 7). In
order for another correct process to decide a different value in some future
view, a prepare quorum certificate for a value different than $v$ must be
obtained in a view greater than $\mathit{view}$. However, this is impossible
as $f+1$ correct processes whose $\mathit{lockedQC}.\mathit{value}=v$ and
$\mathit{lockedQC}.\mathit{view}=\mathit{view}$ will not support such a
prepare quorum certificate (i.e., the check at line 16 of Algorithm 7 will
return false). Thus, it is impossible for correct processes to disagree in the
view core even across multiple views. The agreement property is ensured by
Quad.

Finally, we prove termination.

######  Theorem B.5 (Termination).

Quad ensures termination.

######  Proof B.6.

RareSync ensures that, eventually, all correct processes remain in the same
view $\mathit{view}$ with a correct leader for (at least) $\Delta=8\delta$
time after $\mathit{GST}$. When this happens, all correct processes decide in
the view core.

Indeed, the leader of $\mathit{view}$ learns the highest obtained locked
quorum certificate through the view-change messages (line 9 of Algorithm 7).
Therefore, every correct process supports the proposal of the leader (line 17
of Algorithm 7) as the check at line 16 of Algorithm 7 returns true. After the
leader obtains a prepare quorum certificate in $\mathit{view}$, all correct
processes vote in the following phases of the same view. Thus, all correct
processes decide from the view core (line 43 of Algorithm 7), which concludes
the proof.

Thus, Quad indeed solves the Byzantine consensus problem with weak validity.

######  Corollary B.7.

Quad is a partially synchronous Byzantine consensus protocol ensuring weak
validity.

Proof of complexity. Next, we show that Quad achieves $O(n^{2})$ communication
complexity and $O(f)$ latency complexity. Before we start the proof, we
clarify one point about Algorithm 3: as soon as $\mathsf{advance}(v)$ is
triggered (line 7), for some view $v$, the process immediately stops accepting
and sending messages for the previous view. In other words, it is as if the
“stop accepting and sending messages for the previous view” action immediately
follows the $\mathsf{advance}(\cdot)$ upcall in Algorithm 2.888Note that this
additional action does not disrupt RareSync (nor its proof of correctness and
complexity).

We begin by proving that, if a correct process sends a message of the view
core associated with a view $v$ which belongs to an epoch $e$, then the last
entered epoch prior to sending the message (in the behavior of the process) is
$e$ (this result is similar to the one of Lemma A.34). A message is a _view-
core_ message if it is of view-change, prepare, precommit, commit or decide
type.

######  Lemma B.8.

Let $P_{i}$ be a correct process and let $P_{i}$ send a view-core message
associated with a view $v$, where $v$ belongs to an epoch $e$. Then, $e$ is
the last epoch entered by $P_{i}$ in $\beta_{i}$ before sending the message.

######  Proof B.9.

Process $P_{i}$ enters the view $v$ before sending the view-core message
(since $\mathsf{start\\_executing}(v)$ is invoked upon $P_{i}$ entering $v$;
line 8 of Algorithm 3). By Lemma A.15, $P_{i}$ enters the first view of the
epoch $e$ (and, hence, $e$) before sending the message. By contradiction,
suppose that $P_{i}$ enters another epoch $e^{\prime}$ after entering $e$ and
before sending the view-core message.

By Lemma A.5, we have that $e^{\prime}>e$. However, this means that $P_{i}$
does not send any view-core messages associated with $v$ after entering
$e^{\prime}$ (since $(e^{\prime}-1)\cdot(f+1)+1>v$ and $P_{i}$ enters
monotonically increasing views by Lemma A.5). Thus, a contradiction, which
concludes the proof.

Next, we show that a correct process sends (at most) $O(n)$ view-core messages
associated with a single epoch.

######  Lemma B.10.

Let $P_{i}$ be a correct process. For any epoch $e$, $P_{i}$ sends (at most)
$O(n)$ view-core messages associated with views that belong to $e$.

######  Proof B.11.

Recall that $P_{i}$ enters monotonically increasing views (by Lemma A.5),
which means that $P_{i}$ never invokes $\mathsf{start\\_executing}(v)$ (line 8
of Algorithm 3) multiple times for any view $v$.

Consider a view $v$ that belongs to $e$. We consider two cases:

  * •

Let $P_{i}$ be the leader of $v$. In this case, $P_{i}$ sends (at most) $O(n)$
view-core messages associated with $v$.

  * •

Let $P_{i}$ not be the leader of $v$. In this case, $P_{i}$ sends (at most)
$O(1)$ view-core messages associated with $v$.

Given that $P_{i}$ is the leader of at most one view in every epoch $e$ (since
$\mathsf{leader(\cdot)}$ is a round-robin function), $P_{i}$ sends (at most)
$1\cdot O(n)+f\cdot O(1)=O(n)$ view-core messages associated with views that
belong to $e$.

Finally, we prove the complexity of Quad.

######  Theorem B.12 (Complexity).

Quad achieves $O(n^{2})$ communication complexity and $O(f)$ latency
complexity.

######  Proof B.13.

As soon as all correct processes remain in the same view for $8\delta$ time,
all correct processes decide from the view core. As RareSync uses
$\Delta=8\delta$ in the implementation of Quad (line 3 of Algorithm 3), all
processes decide by time $t_{s}+8\delta$, where $t_{s}$ is the first
synchronization time after $\mathit{GST}$ (Definition A.44). Given that
$t_{s}+8\delta-\mathit{GST}$ is the latency of RareSync (see § 4.1) and the
latency complexity of RareSync is $O(f)$ (by Theorem A.56), the latency
complexity of Quad is indeed $O(f)$.

Fix a correct process $P_{i}$. For every epoch $e$, $P_{i}$ sends (at most)
$O(n)$ view-core messages associated with views that belong to $e$ (by Lemma
B.10). Moreover, if $P_{i}$ sends a view-core message associated with a view
that belongs to an epoch $e$, then $e$ is the last epoch entered by $P_{i}$
prior to sending the message (by Lemma B.8). Hence, in the time period
$[\mathit{GST},t_{s}+8\delta]$, $P_{i}$ sends view-core messages associated
with views that belong to (at most) $O(1)$ epochs (by Lemma A.54). Thus,
$P_{i}$ sends (at most) $O(1)\cdot O(n)=O(n)$ view-core messages in the time
period $[\mathit{GST},t_{s}+8\delta]$, each containing a single word.
Moreover, during this time period, the communication complexity of RareSync is
$O(n^{2})$ (by Theorem A.56). Therefore, the communication complexity of Quad
is $n\cdot O(n)+O(n^{2})=O(n^{2})$.

##  Appendix C SQuad: Proof of Correctness and Complexity

First, we show that the certification phase of SQuad ensures computability and
liveness.

######  Lemma C.1 (Computability & liveness).

Certification phase (Algorithm 4) ensures computability and liveness.
Moreover, every correct process sends (at most) $O(n)$ words and obtains a
certificate by time $\mathit{GST}+2\delta$.

######  Proof C.2.

As every correct process broadcasts disclose, certificate or allow-any
messages at most once and each message contains a single word, every correct
process sends (at most) $3\cdot n\cdot 1=O(n)$ words. Next, we prove
computability and liveness.

Computability. Let all correct processes propose the same value $v$ to SQuad.
Since no correct process broadcasts a disclose message for a value
$v^{\prime}\neq v$, no process ever obtains a certificate
$\sigma_{v^{\prime}}$ for $v^{\prime}$ such that
$\mathit{CombinedVerify}(v^{\prime},\sigma_{v^{\prime}})=\mathit{true}$ (line
23).

Since all correct processes broadcast a disclose message for $v$ (line 3), the
rule at line 9 never activates at a correct process. Thus, no correct process
ever broadcasts an allow-any message (line 11), which implies that no process
obtains a certificate $\sigma_{\bot}$ such that
$\mathit{CombinedVerify}(\text{``allow any''},\sigma_{\bot})=\mathit{true}$
(line 22). The computability property is ensured.

Liveness. Every correct process receives all disclose messages sent by correct
processes by time $\mathit{GST}+\delta$ (since message delays are $\delta$
after $\mathit{GST}$; see § 3). Hence, all correct processes receive (at
least) $2f+1$ disclose messages by time $\mathit{GST}+\delta$. Therefore, by
time $\mathit{GST}+\delta$, all correct processes send either (1) a
certificate message upon receiving $f+1$ disclose messages for the same value
(line 7), or (2) an allow-any message upon receiving $2f+1$ disclose messages
without a “common value” (line 11). Let us consider two possible scenarios:

  * •

There exists a correct process that has broadcast a certificate message upon
receiving $f+1$ disclose messages for the same value (line 7) by time
$\mathit{GST}+\delta$. Every correct process receives this message by time
$\mathit{GST}+2\delta$ (line 18) and obtains a certificate. Liveness is
satisfied by time $\mathit{GST}+2\delta$ in this case.

  * •

Every correct process broadcasts an allow-any message (line 11) by time
$\mathit{GST}+\delta$. Hence, every correct process receives $f+1$ allow-any
messages by time $\mathit{GST}+2\delta$ (line 12) and obtains a certificate
(line 14). The liveness property is guaranteed by time $\mathit{GST}+2\delta$
in this case as well.

The liveness property is ensured by time $\mathit{GST}+2\delta$.

Finally, we show that SQuad is a Byzantine consensus protocol with $O(n^{2})$
communication complexity and $O(f)$ latency complexity.

######  Theorem C.3.

SQuad is a Byzantine consensus protocol with (1) $O(n^{2})$ communication
complexity, and (2) $O(f)$ latency complexity.

######  Proof C.4.

If a correct process decides a value $v^{\prime}$ and all correct processes
have proposed the same value $v$, then $v^{\prime}=v$ since (1) correct
processes ignore values not accompanied by their certificates (line 5), and
(2) the certification phase of SQuad ensures computability (by Lemma C.1).
Therefore, SQuad ensures validity.

Fix an execution $E_{\textsc{SQuad}}$ of SQuad. We denote by
$t_{\mathit{last}}$ the time the last correct process starts executing
$\textsc{Quad}_{\mathit{cer}}$ (line 5) in $E_{\textsc{SQuad}}$; i.e., by
$t_{\mathit{last}}$ every correct process has exited the certification phase.
Moreover, we denote the global stabilization time of $E_{\textsc{SQuad}}$ by
$\mathit{GST}_{1}$. Now, we consider two possible scenarios:

  * •

Let $\mathit{GST}_{1}\geq t_{\mathit{last}}$. $\textsc{Quad}_{\mathit{cer}}$
solves the Byzantine consensus problem with $O(n^{2})$ communication and
$O(f)$ latency (by Theorem B.12). As processes send (at most) $O(n)$ words
associated with the certification phase (by Lemma C.1), consensus is solved in
$E_{\textsc{SQuad}}$ with $n\cdot O(n)+O(n^{2})=O(n^{2})$ communication
complexity and $O(f)$ latency complexity.

  * •

Let $\mathit{GST}_{1}<t_{\mathit{last}}$. Importantly,
$t_{\mathit{last}}-\mathit{GST}_{1}\leq 2\delta$ (by Lemma C.1). Now, we
create an execution $E_{\textsc{Quad}}$ of the original Quad protocol in the
following manner:

    1. 1.

$E_{\textsc{Quad}}\leftarrow E_{\textsc{SQuad}}$. If a process sends a value
with a valid accompanying certificate, then _just_ the certificate is removed
in $E_{\textsc{Quad}}$ (i.e., the corresponding message stays in
$E_{\textsc{Quad}}$). Otherwise, the entire message is removed. Note that no
message sent by a correct process in $E_{\textsc{SQuad}}$ is removed from
$E_{\textsc{Quad}}$ as correct processes only send values accompanied by their
valid certificates.

    2. 2.

We remove from $E_{\textsc{Quad}}$ all events associated with the
certification phase of SQuad.

    3. 3.

The global stabilization time of $E_{\textsc{Quad}}$ is set to
$t_{\mathit{last}}$. We denote this time by
$\mathit{GST}_{2}=t_{\mathit{last}}$. Note that we can set $\mathit{GST}_{2}$
to $t_{\mathit{last}}$ as $t_{\mathit{last}}>\mathit{GST}_{1}$.

In $E_{\textsc{Quad}}$, consensus is solved with $O(n^{2})$ communication and
$O(f)$ latency. Therefore, the consensus problem is solved in
$E_{\textsc{SQuad}}$.

Let us now analyze the complexity of $E_{\textsc{SQuad}}$:

    * –

The latency complexity of $E_{\textsc{SQuad}}$ is
$t_{\mathit{last}}-\mathit{GST}_{1}+O(f)=O(f)$ (as
$t_{\mathit{last}}-\mathit{GST}_{1}\leq 2\delta$).

    * –

The communication complexity of $E_{\textsc{SQuad}}$ is the sum of (1) the
number of words sent in the time period
$[\mathit{GST}_{1},t_{\mathit{last}})$, and (2) the number of words sent at
and after $t_{\mathit{last}}$ and before the decision, which is $O(n^{2})$
since that is the communication complexity of $E_{\textsc{Quad}}$ and each
correct process sends (at most) $O(n)$ words associated with the certification
phase (by Lemma C.1).

Fix a correct process $P_{i}$. Let us take a closer look at the time period
$[\mathit{GST}_{1},t_{\mathit{last}})$:

      * *

Let $\mathit{epochs}_{\textsc{RareSync}}$ denote the number of epochs for
which $P_{i}$ sends epoch-completed or enter-epoch messages in this time
period. By Lemma A.42, $P_{i}$ enters (at most) $2=O(1)$ epochs in this time
period. Hence, $\mathit{epochs}_{\textsc{RareSync}}=O(1)$ (by lemmas A.34 and
A.36).

      * *

Let $\mathit{epochs}_{\textsc{Quad}_{\mathit{cer}}}$ denote the number of
epochs for which $P_{i}$ sends view-core messages in this time period. By
Lemma A.42, $P_{i}$ enters (at most) $2=O(1)$ epochs in this time period.
Hence, $\mathit{epochs}_{\textsc{Quad}_{\mathit{cer}}}=O(1)$ (by Lemma B.8).

For every epoch $e$, $P_{i}$ sends (at most) $O(n)$ epoch-completed and enter-
epoch messages (by lemmas A.38 and A.40). Moreover, for every epoch $e$,
$P_{i}$ sends (at most) $O(n)$ view-core messages associated with views that
belong to $e$ (by Lemma B.10).999Note that lemmas A.34, A.36, A.38, A.40,
A.42, B.8 and B.10, which we use to prove the theorem, assume that all correct
processes have started executing RareSync and Quad by $\mathit{GST}$. In
Theorem C.3, this might not be true as some processes might start executing
RareSync after $\mathit{GST}$ (since $t_{\mathit{last}}>\mathit{GST}$).
However, it is not hard to verify that the claims of these lemmas hold even in
this case. As each epoch-completed, enter-epoch and view-core message contains
a single word and $P_{i}$ sends at most $O(n)$ words during the certification
phase (by Lemma C.1), we have that $P_{i}$ sends (at most)
$\mathit{epochs}_{\textsc{RareSync}}\cdot
O(n)+\mathit{epochs}_{\textsc{Quad}_{\mathit{cer}}}\cdot O(n)+O(n)=O(n)$ words
during the time period $[\mathit{GST}_{1},t_{\mathit{last}})$. Therefore, the
communication complexity of $E_{\textsc{SQuad}}$ is $n\cdot
O(n)+O(n^{2})+O(n^{2})=O(n^{2})$.101010The first “$n\cdot O(n)$” term
corresponds to the messages sent during the time period
$[\mathit{GST}_{1},t_{\mathit{last}})$, the second “$O(n^{2})$” term
corresponds to the messages sent during the certification phase, and the third
“$O(n^{2})$” term corresponds to the messages sent at and after
$t_{\mathit{last}}$ and before the decision has been made.

Hence, consensus is indeed solved in $E_{\textsc{SQuad}}$ with $O(n^{2})$
communication complexity and $O(f)$ latency complexity.

The theorem holds.