######  Proof E.10.

Since all processes in $\mathcal{S}$ invoke $\mathsf{advance}$ upon starting,
by Startup some process in $\mathcal{S}$ enters view $1$. We now show that
infinitely many views are entered by some process in $\mathcal{S}$. Assume the
contrary, so that there exists a maximal view $v$ entered by any process in
$\mathcal{S}$. Let $P\subseteq\mathcal{S}$ be any set of more than
$\frac{n}{2}$ processes and consider an arbitrary process $p_{i}\in P$ that
enters $v$.

Suppose $p_{i}$ decides in $v$. Then there exists a time $t$, a view
$v^{\prime}\geq v$ and a value $x$ such that $p_{i}.\mathsf{M2B}(t)$ contains
more than $\frac{n}{2}$ entries equal to $(v^{\prime},x)$. Let $Q$ be the set
of processes these entries correspond to. Then one of them must be from
$\mathcal{S}$. Because no process from $\mathcal{S}$ enters a view $>v$, the
precondition at line 5 ensures that $v^{\prime}=v$. For similar reasons, the
value of $p_{i}.\mathsf{M2B}$ remains unchanged from $t$ onwards. Then there
exists a time $t^{\prime}\geq{\sf GST}$ such that
$p_{i}.\mathsf{M2B}(t^{\prime})$ contains more than $\frac{n}{2}$ entries
equal to $(v,x)$.

By Proposition E.5,
$p_{j}.\mathsf{M2B}(t^{\prime}+\Delta)[k]=p_{i}.\mathsf{M2B}(t^{\prime})[k]$
for each $p_{k}\in Q$. Because no process from $\mathcal{S}$ enters a view
$>v$, the value of $p_{j}.\mathsf{M2B}$ remains unchanged from
$t^{\prime}+\Delta$ onwards. Then the precondition at line 5 is satisfied at
$p_{j}$ at a time $t_{dj}$. Therefore, by $t_{dj}$ the process $p_{j}$ sets
$\mathsf{val}=x$ and $\mathsf{phase}={\tt DECIDED}$. But then the
$\mathsf{propose}$ operation invoked by $p_{j}$ returns by
$\max\\{t_{pj},t_{dj}\\}$, contradicting the assumption that it never does so.

Therefore, $p_{i}$ never decides in $v$. Then by Lemma E.1, $p_{i}$ eventually
invokes $\mathsf{advance}$ in $v$. Since $p_{i}$ was picked arbitrarily, we
have $\forall p_{i}\in P.\ E_{i}(v)\mathpunct{\downarrow}\implies
A_{i}(v)\mathpunct{\downarrow}$. By Progress, $E_{\rm
first}^{\mathcal{S}}(v+1)\mathpunct{\downarrow}$, which contradicts the fact
that $v$ is the maximal view entered by any process in $\mathcal{S}$. Thus,
processes in $\mathcal{S}$ keep entering views forever. The claim then follows
from Lemma D.7 ensuring that, if a view is entered by a process in
$\mathcal{S}$, then so are all preceding views.

Let view $v_{1}$ be the first view such that $v_{1}\geq\mathcal{V}$ and
$E_{\rm first}^{\mathcal{S}}(v_{1})$ $\geq\max\\{{\sf GST},t_{pj}\\}$; such a
view exists by Claim 1. We next show that processes in $\mathcal{S}$ increase
their timeouts high enough to satisfy the bounds in Lemma E.3.

######  Claim 2.

Every process in $\mathcal{S}$ executes the timer expiration handler (line 5)
infinitely often.

######  Proof E.11.

Assume the contrary and let $C_{\rm fin}$ and $C_{\rm inf}$ be the sets of
processes in $\mathcal{S}$ that execute the timer expiration handler finitely
and infinitely often, respectively. Then $C_{\rm fin}\neq\varnothing$, and by
Claim 1 and Validity, $C_{\rm inf}\neq\varnothing$. The $\mathsf{timeout}$
value increases unboundedly at processes from $C_{\rm inf}$, and does not
change after some view $v_{2}$ at processes from $C_{\rm fin}$. By Claim 1 and
since leaders rotate round-robin, there exists a view
$v_{3}\geq\max\\{v_{1},v_{2}\\}$ led by $p_{j}$ such that any process
$p_{i}\in C_{\rm inf}$ that enters $v_{3}$ has
$\mathsf{timeout}_{i}(v_{3})>d+3\Delta$. By Claim 1 and Validity, at least one
process in $\mathcal{S}$ calls $\mathsf{advance}$ in $v_{3}$; let $p_{k}$ be
the first process to do so. Because $v_{3}\geq v_{2}$, this process cannot be
in $C_{\rm fin}$, since none of these processes can increase their timers in
$v_{3}$. Then $p_{k}\in C_{\rm inf}$, contradicting Lemma E.4.

By Claims 1 and 2, there exists a view $v_{4}\geq v_{1}$ led by $p_{j}$ such
that some process in $\mathcal{S}$ enters $v_{4}$, and for any process
$p_{i}\in\mathcal{S}$ that enters $v_{4}$ we have
$\mathsf{timeout}_{i}(v_{4})>d+3\Delta$. By Lemma E.3, no process in
$\mathcal{S}$ calls $\mathsf{advance}$ in $v_{4}$. On the other hand, by Claim
1, some process in $\mathcal{S}$ enters $v_{4}+1$. Then by Validity, some
process in $\mathcal{S}$ calls $\mathsf{advance}$ in $v_{4}$, which is a
contradiction.

##  Appendix F Proofs of the Theorems from §6

###  F.1 Impossibility of Consensus in System $S$

Aguilera et al. [3] show that $\Omega$ can be implemented in system $S$
wherein in every execution, all links can be flaky apart from those emanating
from an a priori unknown correct process (_timely source_), which are required
to be eventually reliable and timely. Below we show that in $S$ no algorithm
can implement a a _$t$ -resilient obstruction-free_ consensus, which in
addition to the standard agreement and validity properties satisfies the
following weak termination guarantee:

$t$-Obstruction Freedom: In any execution in which at most $t$ processes
crash, every solo-executing propose operation invoked by a correct process
eventually returns.

######  Corollary 6.1 (restated).

For all $n>0$ and $0<t<n$, there is no algorithm implementing a $t$-resilient
obstruction-free consensus in $S$.

######  Proof F.1.

Assume by contradiction that there exists $t<n$ and an algorithm $\mathcal{A}$
implementing $t$-resilient obstruction-free consensus in $S$. Since $S$ is
strictly weaker than a partial synchrony model in which all links are reliable
and timely after ${\sf GST}$, the lower bound of [24] implies that no
algorithm can solve $t$-resilient consensus in $S$ if $n\leq 2\vee
t>\lfloor\frac{n-1}{2}\rfloor$.

Suppose

$n>2\wedge 0<t\leq\lfloor\frac{n-1}{2}\rfloor,$ (3)

and let $\mathcal{F}_{S}$ be the fail-prone system induced by $S$. Thus,
$\mathcal{F}_{S}$ consists of all failure patterns $(P,C)$ such that $|P|<n$
and $C$ satisfies

$\exists p\in\mathcal{P}\setminus P.\,\forall
q\in\mathcal{P}.\,q\in\mathcal{P}\setminus P\wedge q\neq p\implies(p,q)\not\in
C.$ (4)

Intersecting $\mathcal{F}_{S}$ with (3), we obtain a fail-prone system
$\mathcal{F}_{S,t}$ consisting of all failure patterns $(P,C)$ such that

$|P|=\lfloor\frac{n-1}{2}\rfloor,$ (5)

and $C$ satisfies (4). Then, by the obstruction freedom property of consensus,
$\mathcal{A}$ must be an $(\mathcal{F}_{S,t},\tau)$-obstruction-free
implementation of consensus such that $\forall
f\in\mathcal{F}_{S,t}.\,\tau(f)\neq\emptyset\wedge\tau(f)\subseteq\mathcal{P}\setminus
P$. Since $\mathcal{F}_{S,t}$ is a $\lfloor\frac{n-1}{2}\rfloor$-fail-prone
system, and $S$ is weaker than our model $\mathcal{M}_{{\rm PRD}}$ in terms of
its timeliness and link reliability assumptions, we can apply Theorem 4.11 to
derive that for all $f\in\mathcal{F}_{S,t}$, there exists a strongly connected
component of ${\mathcal{G}}\setminus{f}$ that contains $\tau(f)$ and has a
cardinality greater than $\lfloor\frac{n-1}{2}\rfloor$. By (5) and (4),
$\mathcal{F}_{S,t}$ includes a failure pattern $f=(P,C)$ such that

$|P|=\lfloor\frac{n-1}{2}\rfloor\wedge\exists p\in\mathcal{P}\setminus
P.\,\forall q\in\mathcal{P}\setminus P.\ \forall r\in\mathcal{P}\setminus
P.\,q\neq p\implies(q,r)\in C.$

Since ${\mathcal{G}}\setminus{f}$ contains all correct processes, by
obstruction freedom, any propose invoked on a process in
${\mathcal{G}}\setminus{f}$ and running solo in some $f$-compliant execution
of $\mathcal{A}$ must terminate. Therefore,
$\tau(f)\subseteq{\mathcal{G}}\setminus{f}$. However, every strongly connected
component in ${\mathcal{G}}\setminus{f}$ has a cardinality
$1\leq\lfloor\frac{n-1}{2}\rfloor$ for all $n>2$. A contradiction.

###  F.2 $\lfloor\frac{n-1}{2}\rfloor$-resilient Wait-Free Consensus in
$\mathcal{M}^{\star}_{{\rm AEF}}$

An execution has a _bidirectional star_ , if at all times, there exists a set
of eventually reliable channels connecting some correct process to every other
process in both directions. Let $\mathcal{M}^{\star}_{{\rm AEF}}$ be the model
obtained by augmenting $\mathcal{M}_{{\rm AEF}}$ with the assumption that
every execution of $\mathcal{M}^{\star}_{{\rm AEF}}$ has a bidirectional star.
A consensus algorithm $\mathcal{A}$ is _$t$ -resilient wait-free_ if it
satisfies the following termination property:

$t$-Wait Freedom: In any execution in which at most $t$ processes crash, every
propose operation invoked by a correct process eventually returns.

We now prove Corollary 6.2. We first show that
$\lfloor\frac{n-1}{2}\rfloor$-resilient wait-free atomic register can be
implemented in $\mathcal{M}^{\star}_{{\rm AEF}}$:

######  Lemma F.2.

There exists an $\lfloor\frac{n-1}{2}\rfloor$-resilient wait-free bounded-
space implementation of atomic register over $\mathcal{M}^{\star}_{{\rm AEF}}$
(asynchronous / eventually reliable / flaky / bidirectional star).

######  Proof F.3.

Let $\mathcal{F}$ be a fail-prone system such that for each
$(P,C)\in\mathcal{F}$, there exists an execution of $\mathcal{M}^{\star}_{{\rm
AEF}}$ in which all processes in $P$ and all channels in $C$ fail and
$|P|\leq\lfloor\frac{n-1}{2}\rfloor$. We first show that for all
$f\in\mathcal{F}$, ${\mathcal{G}}\setminus{f}$ is a connected core. Let
$f\in\mathcal{F}$ and $\sigma$ be an execution from which $f$ is derived. By
the bidirectional star assumption and since every eventually reliable channel
is considered correct in $\mathcal{M}^{\star}_{{\rm AEF}}$, there exists a
correct process $p$ such that no channel from/to $p$ fail in $\sigma$. Hence,
for each pair of vertices $v,v^{\prime}$ of ${\mathcal{G}}\setminus{f}$ there
exists a path $(v,p),(p,v^{\prime})$ from $v$ to $v^{\prime}$ in
${\mathcal{G}}\setminus{f}$. Thus, ${\mathcal{G}}\setminus{f}$ is strongly
connected. Furthermore, by construction of $\mathcal{F}$,
${\mathcal{G}}\setminus{f}$ also includes all correct processes in $\sigma$,
and therefore has $\geq\lceil\frac{n+1}{2}\rceil$ vertices. Hence,
${\mathcal{G}}\setminus{f}$ is a connected core.

Let $\tau:\mathcal{F}\rightarrow 2^{\mathcal{P}}$ be such that $\forall
f\in\mathcal{F}$. $\tau(f)={\mathcal{G}}\setminus{f}$. Then, by Theorem 4.9,
there exists an $(\mathcal{F},\tau)$-wait-free bounded-space implementation
$\mathcal{A}$ of an atomic register over the model $\mathcal{M}_{{\rm AEF}}$.
Since every execution of $\mathcal{M}^{\star}_{{\rm AEF}}$ is also an
execution of $\mathcal{M}_{{\rm AEF}}$, $\mathcal{A}$ implements an atomic
register in $\mathcal{M}^{\star}_{{\rm AEF}}$. Furthermore, since
$\mathcal{A}$ is $(\mathcal{F},\tau)$-wait-free in $\mathcal{M}_{{\rm AEF}}$,
every operation invoked by a correct process in an $f$-compliant execution of
$\mathcal{M}_{{\rm AEF}}$ eventually returns. Since every execution $\sigma$
of $\mathcal{A}$ in $\mathcal{M}^{\star}_{{\rm AEF}}$ in which at most a
minority of processes crash is an $f$-compliant execution of $\mathcal{A}$ in
$\mathcal{M}_{{\rm AEF}}$, every operation invoked by a correct process in
$\sigma$ eventually returns. Thus, $\mathcal{A}$ is an
$\lfloor\frac{n-1}{2}\rfloor$-resilient wait-free bounded-space implementation
of atomic register over $\mathcal{M}^{\star}_{{\rm AEF}}$, as needed.

Since wait-free atomic registers are known to be sufficient for solving wait-
free consensus in an asynchronous system augmented with a failure detector
$\Omega$ [37], Lemma F.2 implies:

######  Corollary 6.2 (restated).

Let $\mathcal{M}$ be a model which is as strong as $\mathcal{M}^{\star}_{{\rm
AEF}}$ (asynchronous / eventually reliable / flaky / bidirectional star). If a
failure detector $\Omega$ can be implemented in $\mathcal{M}$, then there
exists an $\lfloor\frac{n-1}{2}\rfloor$-resilient wait-free bounded-space
implementation of consensus over $\mathcal{M}$.

We now use Corollary 6.2 to show that Corollary 6.3 holds:

######  Corollary 6.3 (restated).

There exists an $\lfloor\frac{n-1}{2}\rfloor$-resilient wait-free bounded-
space implementation of consensus over the systems $S^{+}$ and $S^{++}$ of
[3], and the models defined in [2, 39, 33, 25].

######  Proof F.4.

Below, we prove the result for each model separately:

  * •

System $S^{+}$ [3]. This system stipulates the existence of a _fair hub_ in
every execution. A fair hub is a correct process which is connected to all
other processes via fair-lossy channels [1] in both directions. Since
eventually reliable channels can be built on top of fair-lossy ones in an
asynchronous system, the fair hub and our bidirectional star assumptions are
computationally equivalent. Thus, $S^{+}$ is as strong as
$\mathcal{M}^{\star}_{{\rm AEF}}$ and since $\Omega$ can be implemented in
$S^{+}$ [3], by Corollary 6.2, consensus can be implemented in $S^{+}$.

  * •

System $S^{++}$ [3]. In this system, every pair of processes is assumed to be
connected by fair-lossy channels. Since eventually reliable channels can be
implemented out of fair-lossy ones, the resulting system is guaranteed to
include a bidirectional star. Thus, $S^{++}$ is as strong as
$\mathcal{M}^{\star}_{{\rm AEF}}$ and since $\Omega$ can be implemented in
$S^{++}$ [3], by Corollary 6.2, consensus can be implemented in $S^{++}$.

  * •

Model of [2]. As above, in this model every pair of processes is connected via
fair-lossy channels, which implies that the resulting system upholds the
bidirectional star assumption. Since $\Omega$ can be implemented in this model
[2], Corollary 6.2 implies the required.

  * •

Models of [39, 33, 25] assume that every pair of processes is connected via
reliable channels. This yields a connectivity constraint which is stronger
than our bidirectional star assumption. Since these papers demonstrate that
$\Omega$ can be implemented in their respective models, we can apply Corollary
6.2 to obtain the result.