IMDEA Software Institute, Spain University of Surrey, UK IMDEA Software
Institute, Spain

# Fault-tolerant computing with unreliable channels

Alejandro Naser Pastoriza  Gregory Chockler  Alexey Gotsman

###### Abstract

We study implementations of basic fault-tolerant primitives, such as consensus
and registers, in message-passing systems subject to process crashes and a
broad range of communication failures. Our results characterize the necessary
and sufficient conditions for implementing these primitives as a function of
the connectivity constraints and synchrony assumptions. Our main contribution
is a new algorithm for partially synchronous consensus that is resilient to
process crashes and channel failures and is optimal in its connectivity
requirements. In contrast to prior work, our algorithm assumes the most
general model of message loss where faulty channels are flaky, i.e., can lose
messages without any guarantee of fairness. This failure model is particularly
challenging for consensus algorithms, as it rules out standard solutions based
on leader oracles and failure detectors. To circumvent this limitation, we
construct our solution using a new variant of the recently proposed _view
synchronizer_ abstraction, which we adapt to the crash-prone setting with
flaky channels.

##  1 Introduction

We are concerned with implementing basic fault-tolerant primitives, such as
registers and consensus, in systems where processes can crash and
communication channels may lose messages. This setting is of practical
importance, since channel failures regularly occur in real-world deployments
[10, 15, 34] and often lead to system outages. For example, Alquraan et al.
[7] conducted a comprehensive study of failures due to network partitions in
widely used replicated data stores. It found that a majority of such failures
led to catastrophic effects and that the resolution of almost half of these
failures required redesigning a system mechanism. Thus, the failures were not
simply due to coding bugs, but to design flaws.

Perhaps the most challenging aspect of real-world network failures is that the
ways the network can break down can be arbitrarily complex, resulting in a
wide variety of connectivity configurations. While in the simplest case
individual channel failures may not affect the overall network connectivity
(Figure 1a), in more complex scenarios the network may become partitioned into
multiple components, some of which may end up connected in one direction, but
not in the other (Figure 1b). In the worst case, some components may become
intermittently connected, causing an arbitrary subset of the messages
transmitted between them to get lost (Figure 1c).

Although intermittent connectivity is a common occurrence in modern networks,
often arising due to bugs in switch software and configuration errors [10], it
has so far received little attention in the theory research. Most network
models for studying consensus assume that channels are either (eventually)
reliable or (eventually) disconnected (Figures 1a-b). Reliable channels are
sometimes replaced by _fair lossy_ ones, which only guarantee to deliver a
message if it was sent infinitely many times. However, reliable and fair lossy
channels are computationally equivalent: the former can be implemented from
the latter by repeatedly resending each message until it gets acknowledged and
filtering out duplicates [1].

Although the classical abstractions of failure or leader detectors [17] can be
adapted to solve consensus in the above settings [36, 45, 4, 27, 22, 23], they
are no longer useful in the presence of unconstrained message loss.
Intuitively, the reason is that in this case they may fail to correctly
identify processes with reliable connectivity, which is necessary to ensure
the liveness of consensus. For example, suppose that the pattern of message
loss experienced by the channels $2\leftrightarrow 1$ and $2\leftrightarrow 3$
in Figure 1c is such that all leader election messages are getting through.
Thus, it is possible for process $2$ to be elected as a leader. However, since
any message sent by process $2$ after being elected can be dropped (no matter
how many times it is resent), the process may not be able to drive consensus
to completion, violating liveness. In fact, leader election was found in [7]
to be the most vulnerable mechanism to channel failures, accounting for at
least 40% of the system failures.

Figure 1: Examples of irregular connectivity configurations: (a) indirect
connectivity; (b) asymmetric connectivity; and (c) flaky connectivity. All
processes are correct.

In this paper we investigate the possibility of implementing basic fault-
tolerant abstractions resilient to a broad range of communication failures,
including those induced by intermittent connectivity. To this end, we obtain
several lower and upper bounds that characterize the solvability of registers
and consensus as a function of the channel failure model, connectivity
constraints and synchrony assumptions. Our main contribution is a new crash
fault-tolerant algorithm that solves partially synchronous consensus under the
_most general_ model of message loss and is _optimal_ in terms of its network
connectivity requirements. Our algorithm furthermore offers a new way of
constructing modular protocols for unreliable networks, which does not rely on
the leader election or failure detection abstractions. Below we review our
results in more detail.

#### Lower bounds.

We first present a general framework for specifying fault-tolerance
assumptions on process and channel failures (§2-3) by generalizing the
classical notion of a fail-prone system [40]. For example, this framework
allows us to specify whether an algorithm is meant to tolerate the failure
patterns depicted in Figure 1. We then use this framework to establish minimal
connectivity requirements necessary to implement registers or consensus (§4).
To obtain strong lower bounds, we consider strong network models where correct
channels are reliable and faulty channels are disconnected, i.e., drop all
messages. We consider asynchrony for registers (model $\mathcal{M}_{{\rm
ARD}}$ in Figure 2) and partial synchrony [24] for consensus (model
$\mathcal{M}_{{\rm PRD}}$): the execution starts with an asynchronous period
and then becomes synchronous. The most interesting aspect of our lower bounds
is that, unlike the prior work on consensus under unreliable connectivity
(e.g., [2, 48]), they are proven for a very weak termination guarantee that
only requires obstruction-free termination at a _subset_ of processes.
Informally, we show that for any $n$-process implementation of register or
consensus:

  1. 1.

All processes where obstruction-freedom holds must be strongly connected via
correct channels.

  2. 2.

If the implementation tolerates $k$ process crashes and $n=2k+1$, then any
process where obstruction-freedom holds must belong to a set of $\geq k+1$
correct processes strongly connected by correct channels.

We call the largest set satisfying the condition in (2) the connected core of
the network. For example, in Figure 1a the connected core is $\\{1,2,3\\}$,
whereas in Figures 1b-c it is $\\{1,3\\}$.

The above results generalize the celebrated CAP theorem [14, 28], which says
that it is impossible to guarantee all of Consistency, Availability and
network Partition-tolerance (§4.1). Whereas CAP only says that to ensure
availability and consistency, some channels must be correct, we establish how
many are needed; and whereas CAP requires availability at all processes, we
establish conditions required to ensure it only in a part of the system.
Result (2) furthermore establishes stronger requirements for algorithms
resilient to a minority of crashes (which is optimal [38, 24]). It shows that,
even if obstruction freedom is required only at a single process, a majority
thereof must still be strongly connected by correct channels.

|  Reliable/Disconnected | Eventually reliable/Flaky
---|---|---
|  (lower bound) | (upper bound)
Asynchronous (register) | $\mathcal{M}_{{\rm ARD}}$ | $\mathcal{M}_{{\rm AEF}}$
Partially synchronous (consensus) | $\mathcal{M}_{{\rm PRD}}$ | $\mathcal{M}_{{\rm PEF}}$
Figure 2: System models with different channel types and synchrony
assumptions.

#### Upper bounds.

The second part of our contribution is to propose algorithms for registers and
consensus that match our lower bounds. These algorithms assume the existence
of the connected core and guarantee wait-freedom at all of its members. They
are designed to work in an adversarial model where correct channels are only
eventually reliable and faulty channels are flaky, i.e., can drop any messages
sent on them without any guarantee of fairness (models $\mathcal{M}_{{\rm
AEF}}$ and $\mathcal{M}_{{\rm PEF}}$ in Figure 2). Flakiness is a very broad
failure mode that captures a number of failure patterns occurring in practice,
including both full and intermittent loss of connectivity. It also subsumes
the previously considered variants of lossy channels, such as eventually
disconnected [4, 18] and fair lossy [1, 11]. Although irregular connectivity
patterns have been studied before [27, 22, 23, 4, 3], to the best of our
knowledge we are the first to propose register and consensus implementations
in the presence of flaky channels.

The implementation for consensus is the more challenging one (§5). Since, as
we explained above, failure and leader detectors are not useful in the
presence of flaky channels, we take a different approach: we generalize the
abstraction of a view synchronizer [12, 13, 41, 42], recently proposed for
Byzantine consensus, to benign failure settings with flaky channels. Roughly,
a view synchronizer facilitates a commonly used design pattern in which the
protocol execution is divided into views (aka rounds). Each view has a
designated leader that coordinates the process interaction within that view.
The task of the synchronizer is to ensure that sufficiently many correct
processes are eventually able to spend sufficient time in the same view with a
correct leader, which would then be able to drive consensus to completion.
Supporting this functionality under partial synchrony is nontrivial, as during
asynchronous periods clocks can diverge and messages used to synchronize views
could get lost or delayed. View synchronizers encapsulate the necessary logic
to deal with these complexities, thereby enabling modular design of consensus
protocols.

In contrast to failure or leader detectors, a synchronizer does not attempt to
identify the set of misbehaving processes (which, as we argued above, is
impossible with flaky channels), but instead delegates this task to the top-
level protocol. This can monitor the current leader using timeouts and other
protocol-specific logic and ask the synchronizer to switch to another view
with a different leader if it detects a lack of progress. For example, if
processes $1$ and $3$ in Figure 1c do not observe progress on behalf of
process $2$ due to message loss, they would eventually initiate a view change
and try another leader.

We present a specification of a view synchronizer sufficient to implement
consensus in the presence of flaky channels, its implementation, and prove
that the implementation satisfies our specification. Even though handling
crashes is easier than Byzantine faults, flaky channels create another
challenge: processes outside the connected core (such as process $2$ in
Figures 1b-c) falsely suspecting the current leader should not be able to
force a view change, disrupting a working view. Using our synchronizer we then
design a consensus protocol that tolerates flaky channels and prove its
correctness.

Finally, we also demonstrate how our lower and upper bounds can be applied to
establish consensus solvability in various existing models of weak
connectivity [3, 2, 39, 33, 25]. In particular, we show that some connectivity
models strong enough to implement the $\Omega$ leader detector are
nevertheless too weak to implement consensus (§6).

##  2 System Model

We consider a set $\mathcal{P}$ of $n$ processes which can fail by crashing. A
process is correct if it never crashes, and faulty otherwise. Processes
communicate by exchanging messages through a set of unidirectional channels
$\mathcal{C}$: for every pair of processes $p,q\in\mathcal{P}$ there is a
channel $(p,q)\in\mathcal{C}$ for sending messages from $p$ to $q$.

We consider two notions of channel correctness (reliable and eventually
reliable) and two notions of channel faultiness (disconnected and flaky).
Given correct processes $p$ and $q$, a channel $(p,q)\in\mathcal{C}$ is
reliable if it delivers every message sent by $p$ to $q$. A channel $(p,q)$ is
eventually reliable if there exists a time $t$ such that the channel delivers
every message sent by $p$ to $q$ after $t$. A channel $(p,q)$ is disconnected
if it drops all messages sent by $p$ to $q$. A channel $(p,q)$ is flaky if it
drops an arbitrary subset of messages sent by $p$ to $q$. Flakiness is a very
broad failure mode: it subsumes disconnections and allows the channel to
choose which messages to drop, without any guarantee of fairness. Thus, it is
strictly more permissive than fair lossy, which are computational equivalent
to reliable, as we explained in §1.

Our lower bounds assume the stronger notion of channel correctness (reliable)
and the more restrictive notion of faultiness (disconnected), whereas our
upper bounds assume weaker correctness (eventually reliable) and broader
faultiness (flaky). We combine these channel reliability assumptions with two
types of synchrony guarantees for correct channels, which yields four models
used in our results (Figure 2). We use the asynchronous model in our results
about registers, and the partially synchronous model [24, 17] in our results
about consensus. The latter assumes that there exists a global stabilization
time ${\sf GST}$ and a duration $\delta$ such that after ${\sf GST}$ message
delays between correct processes connected by correct channels are bounded by
$\delta$. However, messages sent before ${\sf GST}$ can get arbitrarily
delayed. Partial synchrony also assumes that processes have clocks that can
drift unboundedly from the real time before ${\sf GST}$, but do not drift
thereafter. Both ${\sf GST}$ and $\delta$ are unknown to our protocols.

To state our results we need an ability to restrict which processes and
channels can fail. We do this by generalizing the classical notion of a fail-
prone system [40], which we formulate in a generic fashion irrespective of a
specific channel failure type (flaky or disconnected). We specify the failure
type when stating our lower or upper bounds. A failure pattern is a pair
$(P,C)\in 2^{\mathcal{P}}\times 2^{\mathcal{C}}$ that defines which processes
and channels are allowed to fail in a single execution. We assume that $C$
only contains channels between pairs of correct processes, since those
incident to faulty processes fail automatically: $(p,q)\in
C\implies\\{p,q\\}\cap P=\emptyset$. For a failure pattern $f=(P,C)$, an
execution $\sigma$ of the system is $f$-_compliant_ if exactly the processes
in $P$ and the channels in $C$ fail in $\sigma$. A fail-prone system
$\mathcal{F}$ is a set of failure patterns. For example, a standard fail-prone
system where any minority of processes can fail and channels between correct
processes cannot fail corresponds to $\mathcal{F}_{s}=\\{(Q,\emptyset)\mid
Q\subseteq\mathcal{P}\wedge|Q|\leq\lfloor\frac{n-1}{2}\rfloor\\}$.

##  3 Correctness Properties

We consider algorithms $\mathcal{A}$ that implement shared memory objects
$\mathcal{O}$, such as a register or consensus, in the models just introduced.
For an arbitrary domain of values $\mathit{Val}$, the _register_ interface
consists of operations $\mathit{write}(v)$, $v\in\mathit{Val}$ and
$\mathit{read}()$, which return $\mathit{ack}$ and a value in $\mathit{Val}$,
respectively. The interface of a consensus object consists of a single
operation $\mathit{propose}(v)$, $v\in\mathit{Val}$, which returns a value in
$\mathit{Val}$.

#### Safety.

The consensus object is required to satisfy the standard safety properties:
(_Agreement_) all terminating $\mathit{propose}$ invocations must return the
same value; and (_Validity_) $\mathit{propose}$ can only return a value passed
to some $\mathit{propose}$ invocation.

We now specify the safety properties for registers. An operation
$\mathit{op^{\prime}}$ follows an operation $\mathit{op}$, denoted
$\mathit{op}\rightarrow\mathit{op^{\prime}}$, if $\mathit{op^{\prime}}$ is
invoked after $\mathit{op}$ returns; $\mathit{op^{\prime}}$ is concurrent with
$\mathit{op}$ if neither $\mathit{op}\rightarrow\mathit{op^{\prime}}$ nor
$\mathit{op^{\prime}}\rightarrow\mathit{op}$. The $\mathcal{O}$’s sequential
specification specifies the behavior of $\mathcal{O}$ in the executions in
which no operations are concurrent with each other. The sequential
specification of a register requires every read to return the value written by
the latest preceding write operation. An execution $\sigma$ of $\mathcal{A}$
is _linearizable_ [31] if there exists a set of responses $X$ and a
permutation $\pi=\mathit{op}_{1},\mathit{op}_{2},\dots$ of all complete
operations in $\sigma$ and some subset of incomplete operations paired with
responses in $X$ such that $\pi$ complies with the $\mathcal{O}$’s sequential
specification and satisfies $\mathit{op}_{i}\rightarrow\mathit{op}_{j}\implies
i<j$. An execution $\sigma$ of a register satisfies _safeness_ if the
subsequence of $\sigma$ consisting of all write operations and all read
operations not concurrent with any writes is linearizable. An implementation
$\mathcal{A}$ of a register is _safe_ [35] if every execution of $\mathcal{A}$
satisfies safeness; $\mathcal{A}$ is _atomic_ if its every execution is
linearizable.

#### Liveness.

Due to faulty channels some correct processes may not be able to terminate,
e.g., if they are partitioned off from the rest of the system. Therefore, to
state liveness, we parameterize the classical notions of obstruction-freedom
and wait-freedom by the failures allowed and the subsets of correct processes
where termination is required. We use the weaker obstruction-freedom in our
lower bounds and the stronger wait-freedom in our upper bounds.

For a failure pattern $f=(P,C)$, we say that $\mathcal{A}$ is $(f,T)$-_wait-
free_ if $T\subseteq\mathcal{P}\setminus P$ and for every process $p\in T$,
operation $\mathit{op}$ and $f$-compliant fair execution $\sigma$ of
$\mathcal{A}$, if $\mathit{op}$ is invoked by $p$ in $\sigma$, then
$\mathit{op}$ eventually returns. An operation $\mathit{op}$ _eventually
executes solo_ in an execution $\sigma$ if either _(i)_ $op$ returns in
$\sigma$, or _(ii)_ there exists a suffix $\sigma^{\prime}$ of $\sigma$ such
that for all operations $op^{\prime}$, if $op^{\prime}$ is concurrent with
$op$ in $\sigma$, then the process that invoked $op^{\prime}$ is crashed in
$\sigma^{\prime}$. We say that $\mathcal{A}$ is $(f,T)$-_obstruction-free_ if
for every process $p\in T$, operation $\mathit{op}$ and $f$-compliant fair
execution $\sigma$ of $\mathcal{A}$, if $\mathit{op}$ is invoked by $p$ and
eventually executes solo in $\sigma$, then $\mathit{op}$ eventually returns.
Note that our notion of obstruction freedom is equivalent to its well-known
shared memory counterparts, such as solo termination [26] and the formalized
version of obstruction freedom [32] given in [9].

We next lift these notions to a fail-prone system $\mathcal{F}$ and a
termination mapping $\tau:\mathcal{F}\rightarrow 2^{\mathcal{P}}$ – a function
mapping each failure pattern to the set of correct processes whose operations
are required to terminate (thus, $\forall f=(P,C)\in\mathcal{F}.\
\tau(f)\subseteq\mathcal{P}\setminus P$). Namely, we say that $\mathcal{A}$ is
$(\mathcal{F},\tau)$-_obstruction-free_ (respectively, _wait-free_) if for
every $f\in\mathcal{F}$, $\mathcal{A}$ is $(f,\tau(f))$-obstruction-free
(respectively, wait-free). For example, the standard guarantee of wait-freedom
under a minority of processes failures corresponds to
$(\mathcal{F}_{s},\tau_{s})$-wait-freedom, where $\mathcal{F}_{s}$ is defined
in §2 and $\tau_{s}$ is such that $\forall
f=(P,\emptyset)\in\mathcal{F}_{s}.\,\tau_{s}(f)=\mathcal{P}\setminus P$.

##  4 Inherent Connectivity Requirements for Registers and Consensus

We now investigate which connectivity requirements are necessary to implement
first registers and then consensus in the models of Figure 2. We start with a
few simple results that serve as a stepping stone for our later lower bounds.
These results are also of independent interest because they generalize the
celebrated CAP theorem [14]: it is impossible to guarantee all of Consistency,
Availability and network Partition-tolerance.

###  4.1 CAP Revisited

The CAP formalization by Gilbert and Lynch [28] considers an asynchronous
system without process failures. It models consistency as implementing an
atomic register, availability as providing wait-freedom at all processes, and
partition-tolerance as tolerating channels that can lose any messages (in our
terminology, flaky).

######  Theorem 4.1 (CAP [28, Theorem 1]).

It is impossible to implement a wait-free atomic register in a message-passing
system where processes do not fail, but all channels are flaky.

The results below generalize CAP along two dimensions. First, the lower bound
given by CAP is not tight: the theorem only says that to implement a wait-free
atomic register, some channels must be correct, but obviously, a single
correct channel would not be sufficient in general. We provide a more precise
characterization of connectivity requirements. Second, CAP requires
availability at all processes; we establish conditions required for it to hold
only in a part of the system. To further strengthen the results, we also prove
our lower bounds for a weaker object – obstruction-free safe register, and a
stronger system model $\mathcal{M}_{{\rm ARD}}$, where channels can only fail
by disconnection. Informally, we show that, in this setting, all processes
where obstruction-freedom holds must be strongly connected via correct
channels: no such process can be partitioned off from the rest.

Formally, let $\mathcal{G}=(\mathcal{P},\mathcal{C})$ be the directed graph
constructed by taking processes as vertices and channels as edges. For a
failure pattern $f=(P,C)$, let ${\mathcal{G}}\setminus{f}$ denote the subgraph
of $\mathcal{G}$ obtained by removing all processes in $P$ along with their
incident channels, as well as all channels in $C$.

######  Theorem 4.2.

Let $f$ be a failure pattern and $T\subseteq\mathcal{P}$. If some algorithm
$\mathcal{A}$ implements an $(f,T)$-obstruction-free safe register over
$\mathcal{M}_{{\rm ARD}}$ (asynchronous / reliable / disconnected), then $T$
is strongly connected in ${\mathcal{G}}\setminus{f}$.

Due to space constraints, we defer the proof of the theorem to §A. The theorem
yields the following corollary in the special case when the failure pattern
$f$ disallows process failures and obstruction-freedom is required at all
processes.

######  Corollary 4.3.

Let $f$ be a failure pattern that disallows process failures: $\exists
C\subseteq\mathcal{C}.\,f=(\emptyset,C)$. If some algorithm $\mathcal{A}$
implements an $(f,\mathcal{P})$-obstruction-free safe register over
$\mathcal{M}_{{\rm ARD}}$ (asynchronous / reliable / disconnected), then the
graph $\mathcal{G}\setminus f$ is strongly connected.

This implies CAP (Theorem 4.1): if an algorithm $\mathcal{A}$ implements an
atomic wait-free register, then it also implements an obstruction-free safe
register, and by the above corollary, all processes must be strongly connected
by correct channels. Corollary 4.3 also yields a tight lower bound. To see
this, consider its lifting to an arbitrary fail-prone system $\mathcal{F}$ and
the termination mapping $\tau_{\mathcal{P}}$ that always returns
$\mathcal{P}$:

######  Corollary 4.4.

Let $\mathcal{F}$ be a fail-prone system that disallows process failures:
$\forall f\in\mathcal{F}.\ \exists C\subseteq\mathcal{C}.\,f=(\emptyset,C)$.
If some algorithm $\mathcal{A}$ implements an
$(\mathcal{F},\tau_{\mathcal{P}})$-obstruction-free safe register over
$\mathcal{M}_{{\rm ARD}}$ (asynchronous / reliable / disconnected), then for
all $f\in\mathcal{F}$ the graph $\mathcal{G}\setminus f$ is strongly
connected.

Then the following proposition implies a matching upper bound: it shows that a
wait-free atomic register can be implemented in the more adversarial model
$\mathcal{M}_{{\rm AEF}}$ (asynchronous / eventually reliable / flaky). The
proposition follows from a more general result we present later (Theorem 4.9).

######  Proposition 4.5.

Let $\mathcal{F}$ be a fail-prone system that disallows process failures and
such that for all $f\in\mathcal{F}$, the graph $\mathcal{G}\setminus f$ is
strongly connected. Then there exists an algorithm $\mathcal{A}$ implementing
an $(\mathcal{F},\tau_{\mathcal{P}})$-wait-free atomic register over
$\mathcal{M}_{{\rm AEF}}$ (asynchronous / eventually reliable / flaky).

###  4.2 Connectivity Requirements under Bounded Process Failures

Consider a straightforward lifting of Theorem 4.2 to fail-prone systems:

######  Corollary 4.6.

Let $\mathcal{F}$ be a fail-prone system and $\tau:\mathcal{F}\rightarrow
2^{\mathcal{P}}$ a termination mapping. If some algorithm $\mathcal{A}$
implements an $(\mathcal{F},\tau)$-obstruction-free safe register over
$\mathcal{M}_{{\rm ARD}}$ (asynchronous / reliable / disconnected), then for
all $f\in\mathcal{F}$, $\tau(f)$ is strongly connected in
${\mathcal{G}}\setminus{f}$.

This result does not make any assumptions about the fail-prone system, and its
CAP-like specialization given by Corollary 4.4 only considers fail-prone
systems without process failures. However, algorithms are commonly designed to
tolerate a bounded number of process failures, and we next show that stronger
connectivity requirements are necessary in this case. To formalize this class
of algorithms, we use the following notion. A _$k$ -fail-prone system_
$\mathcal{F}$ allows any set of $k$ processes or fewer to fail, but disallows
failures of more than $k$ processes:

$(\forall P\subseteq\mathcal{P}.\ |P|\leq k{\implies}\exists
C\subseteq\mathcal{C}.\
(P,C)\in\mathcal{F})\wedge(\forall(P,C)\in\mathcal{F}.\ |P|\leq k).$

For example, the system $\mathcal{F}_{s}$ from §2 is
$\lfloor\frac{n-1}{2}\rfloor$-fail-prone.

The following theorem establishes minimal connectivity constraints required to
implement a safe register under the model $\mathcal{M}_{{\rm ARD}}$ in the
presence of $k$ process crashes. It assumes a particularly weak termination
guarantee which only requires obstruction-freedom to hold at some _non-empty_
set of processes for each failure pattern. An interesting consequence of this
theorem is that no matter how small this set is, any member thereof must still
belong to a set of $>k$ correct processes strongly connected by correct
channels. As we further show in the complementary upper bounds (Theorems 4.9
and 4.12), this connectivity is already sufficient to guarantee wait-freedom
(for both registers and consensus) at a majority of processes under the
standard assumption that at most a minority of them can fail.

######  Theorem 4.7.

Let $\mathcal{F}$ be a $k$-fail-prone system and $\tau:\mathcal{F}\rightarrow
2^{\mathcal{P}}$ a termination mapping such that $\forall
f=(P,C)\in\mathcal{F}.\,\tau(f)\neq\emptyset$. Assume that some algorithm
$\mathcal{A}$ implements an $(\mathcal{F},\tau)$-obstruction-free safe
register over $\mathcal{M}_{{\rm ARD}}$ (asynchronous / reliable /
disconnected). Then for all $f\in\mathcal{F}$, there exists a strongly
connected component of ${\mathcal{G}}\setminus{f}$ that contains $\tau(f)$ and
has a cardinality greater than $k$.

######  Proof 4.8.

Let $f\in\mathcal{F}$ and $S$ be the strongly connected component of
${\mathcal{G}}\setminus{f}$ containing $\tau(f)$. Assume by contradiction that
$|S|\leq k$. Pick an arbitrary process $p\in\tau(f)$; then $p$ is correct
according to $f$. Let $\alpha_{1}$ be a fair execution of $\mathcal{A}$ where
processes and channels in $f$ fail at the beginning, the process $p$ invokes a
read operation, and no other operation is invoked in $\alpha_{1}$. Because
$p\in\tau(f)$ and $\mathcal{A}$ is $(\mathcal{F},\tau)$-obstruction-free, the
read operation must eventually terminate. Since there are no write
invocations, the read must return $0$ – the initial value of the register. Let
$\alpha_{2}$ be the prefix of $\alpha_{1}$ ending with this response. Let $R$
be the set of processes outside $S$ that can reach $S$ in
${\mathcal{G}}\setminus{f}$.

######  Claim 1.

$R\cup S$ is unreachable from $\mathcal{P}\setminus(R\cup S)$ in
${\mathcal{G}}\setminus{f}$.

######  Claim 2.

$R$ is unreachable from $S$ in ${\mathcal{G}}\setminus{f}$.

The above claims easily follow from the definitions of $R$ and $S$. From Claim
1, it follows that the actions by processes in $R\cup S$ do not depend on
those by processes in $\mathcal{P}\setminus(R\cup S)$. Then
$\alpha_{3}=\alpha_{2}|_{R\cup S}$ is an execution of $\mathcal{A}$. Claim 2
implies that the actions by processes in $R$ do not depend on those by
processes in $S$. Then $\alpha=\alpha_{3}|_{R}\alpha_{3}|_{S}$ is also an
execution of $\mathcal{A}$.

Since $|S|\leq k$ and $\mathcal{F}$ is a $k$-fail-prone system, there exists
$C^{\prime}\subseteq\mathcal{C}$ such that
$f^{\prime}=(S,C^{\prime})\in\mathcal{F}$. Pick an arbitrary process
$q\in\tau(f^{\prime})$; then $q\not\in S$. Let $\beta_{1}$ be a fair execution
of $\mathcal{A}$ where processes and channels in $f^{\prime}$ fail at the
beginning. The execution $\beta_{1}$ starts with all the actions from
$\alpha_{3}|_{R}$ followed by a ${\it write}(1)$ invocation by process $q$,
and no other operation is invoked in $\beta_{1}$. Because
$q\in\tau(f^{\prime})$ and $\mathcal{A}$ is $(\mathcal{F},\tau)$-obstruction-
free, the write operation must eventually terminate. Let $\beta$ be the prefix
of $\beta_{1}$ ending with this response and let $\delta$ be the suffix of
$\beta$ such that $\beta=\alpha_{3}|_{R}\delta$.

Consider the execution $\sigma=\alpha_{3}|_{R}\delta\alpha_{3}|_{S}$ without
any failures. Given that $\delta$ does not contain any actions by processes in
$S$, we get:
$\sigma|_{S}=\alpha_{3}|_{S}=(\alpha_{3}|_{R}\alpha_{3}|_{S})|_{S}=\alpha|_{S}$
and $\sigma|_{\mathcal{P}\setminus S}=\alpha_{3}|_{R}\delta=\beta$. Therefore,
$\sigma$ is indistinguishable from $\alpha$ to the processes in $S$ and from
$\beta$ to the processes in $\mathcal{P}\setminus S$.

Thus, for every process, $\sigma$ is indistinguishable to this process from
some execution of $\mathcal{A}$. Furthermore, each message received by a
process in $\sigma$ has previously been sent by another process. Therefore,
$\sigma$ is an execution of $\mathcal{A}$. However, in this execution ${\it
write}(1)$ terminates before a read that fetches $0$ is invoked. This
contradicts the assumption that $\mathcal{A}$ implements a safe register. The
contradiction derives from assuming that $|S|\leq k$, so that $|S|>k$.

Theorem 4.7 is most interesting in the common practical case of $n=2k+1$,
which is the minimal number of processes needed to tolerate $k$ crashes in
asynchronous registers [38] and partially synchronous consensus [24]. In this
case the theorem ensures that for each failure pattern $f$, the graph
${\mathcal{G}}\setminus{f}$ contains a strongly connected component of a
majority of correct processes. It is easy to see that such a component is
unique for a given $f$, and we call it the connected core. For example, in
Figure 1a the connected core is $\\{1,2,3\\}$, whereas in Figures 1b-c it is
$\\{1,3\\}$. As the following theorem shows, the resulting lower bound is
tight. In fact, assuming the existence of a connected core, we can implement
an atomic register that is wait-free at all members of the connected core
under the more adversarial model $\mathcal{M}_{{\rm AEF}}$ (asynchronous /
eventually reliable / flaky).

######  Theorem 4.9.

Let $\mathcal{F}$ be a fail-prone system such that for all $f\in\mathcal{F}$,
the graph ${\mathcal{G}}\setminus{f}$ contains a connected core
$\mathcal{S}_{f}$, and let $\tau:\mathcal{F}\rightarrow 2^{\mathcal{P}}$ be
the termination mapping such that $\forall f\in\mathcal{F}$.
$\tau(f)=\mathcal{S}_{f}$. Then there exists an $(\mathcal{F},\tau)$-wait-free
implementation of an atomic register over the model $\mathcal{M}_{{\rm AEF}}$
(asynchronous / eventually reliable / flaky).

Due to space constraints we defer the proof of the theorem to §B. The proof
constructs the desired implementation as a variant of ABD [8] that uses
gossip-style data propagation to deal with indirect connectivity. The most
interesting aspect of this implementation is that, despite the need for
gossip, it uses only bounded space. We illustrate the technique for bounding
space when presenting our consensus implementation in §5.

###  4.3 Connectivity Requirements for Consensus

The lower bounds in the previous section also apply to consensus under partial
synchrony, with analogs of Theorems 4.2 and 4.7 formulated as follows:

######  Theorem 4.10.

Let $f$ be a failure pattern and $T\subseteq\mathcal{P}$. If some algorithm
$\mathcal{A}$ is an $(f,T)$-obstruction-free implementation of consensus over
$\mathcal{M}_{{\rm PRD}}$ (partially synchronous / reliable / disconnected),
then $T$ is strongly connected in ${\mathcal{G}}\setminus{f}$.

######  Theorem 4.11.

Let $\mathcal{F}$ be a $k$-fail-prone system and $\tau:\mathcal{F}\rightarrow
2^{\mathcal{P}}$ be a termination mapping such that $\forall
f=(P,C)\in\mathcal{F}.\ \tau(f)\neq\emptyset$. Assume that some algorithm
$\mathcal{A}$ is an $(\mathcal{F},\tau)$-obstruction-free implementation of
consensus over $\mathcal{M}_{{\rm PRD}}$ (partially synchronous / reliable /
disconnected). Then for all $f\in\mathcal{F}$, there exists a strongly
connected component of ${\mathcal{G}}\setminus{f}$ that contains $\tau(f)$ and
has a cardinality greater than $k$.

To see why these theorems hold observe first that Theorems 4.2 and 4.7 also
hold if the model $\mathcal{M}_{{\rm ARD}}$ is replaced with
$\mathcal{M}_{{\rm PRD}}$: e.g., since the execution $\sigma$ constructed in
the proof of Theorem 4.7 is finite, it is also a valid execution under
$\mathcal{M}_{{\rm PRD}}$ where all actions occur before ${\sf GST}$. Then the
required follows the fact that registers can be implemented from consensus (we
formally prove this for our setting in to §C).

Finally, similarly to Theorem 4.9, for the case of $n=2k+1$ we can prove an
upper bound matching Theorem 4.11 in the model $\mathcal{M}_{{\rm PEF}}$
(partially synchronous / eventually reliable / flaky). This result is much
more difficult than the upper bound for registers, and we prove it in the next
section.

######  Theorem 4.12.

Let $\mathcal{F}$ be a fail-prone system such that for all $f\in\mathcal{F}$,
the graph ${\mathcal{G}}\setminus{f}$ contains a connected core
$\mathcal{S}_{f}$, and let $\tau:\mathcal{F}\rightarrow 2^{\mathcal{P}}$ be
the termination mapping such that $\forall f\in\mathcal{F}.\
\tau(f)=\mathcal{S}_{f}$. Then there exists an $(\mathcal{F},\tau)$-wait-free
implementation of consensus over the model $\mathcal{M}_{{\rm PEF}}$
(partially synchronous / eventually reliable / flaky).

##  5 Consensus in the Presence of Flaky Channels

We now present a consensus protocol in the model $\mathcal{M}_{{\rm PEF}}$
that validates Theorem 4.12. Consider a fail-prone system $\mathcal{F}$
satisfying the conditions of the theorem: for each $f\in\mathcal{F}$, the
graph ${\mathcal{G}}\setminus{f}$ contains a connected core. For the remainder
of the section we fix a failure pattern $f\in\mathcal{F}$ and let
$\mathcal{S}$ be the corresponding connected core. Since, as we explained in
§1, classical failure and leader detectors are not useful in the presence of
flaky channels, we take a different approach. Our protocol is implemented on
top of a _view synchronizer_ [12, 13, 41, 42], which enables the processes to
divide their execution into a series of views, each with a designated leader.
At a high level, the synchronizer’s goal is to bring sufficiently many correct
processes with enough connectivity (e.g., those from $\mathcal{S}$) into a
view led by a well connected leader and keep them in that view for
sufficiently long to reach an agreement. Supporting this in the presence of
flaky channels is nontrivial as the processes outside the connected core (such
as process $2$ in Figure 1c) may fail to observe progress on behalf of the
leader of a functional view and request a premature view change. We first
present the specification (§5.1) and the implementation (§5.2) of a
synchronizer that addresses this challenge. We then use it to construct a
consensus protocol (§5.3) satisfying the requirements of Theorem 4.12.

###  5.1 Synchronizer Specification

We consider a synchronizer interface defined in [41]. Let
$\mathsf{View}=\\{1,2,\dots\\}$ be the set of views, ranged over by $v$; we
use $0$ to denote an invalid initial view. The synchronizer produces
notifications $\mathsf{new\texttt{\textunderscore}view}(v)$ at a process,
telling it to enter a view $v$. To trigger these, the synchronizer allows a
process to call a function $\mathsf{advance}()$, which signals that the
process wishes to advance to a higher view. We assume that a process does not
call $\mathsf{advance}()$ twice without an intervening
$\mathsf{new\texttt{\textunderscore}view}$ notification.

  * •

Monotonicity: a process may only enter increasing views:
$\forall i,v,v^{\prime}.\ E_{i}(v)\mathpunct{\downarrow}\ \land\
E_{i}(v^{\prime})\mathpunct{\downarrow}\ \implies(v<v^{\prime}\iff
E_{i}(v)<E_{i}(v^{\prime}))$

  * •

Validity: a process only enters $v+1$ if some process from $\mathcal{S}$ has
attempted to advance from $v$:
$\forall i,v.\ E_{i}(v+1)\mathpunct{\downarrow}\ \implies A_{\rm
first}^{\mathcal{S}}(v)\mathpunct{\downarrow}\ \land\ A_{\rm
first}^{\mathcal{S}}(v)<E_{i}(v+1)$

  * •

Bounded Entry: for some $\mathcal{V}$ and $d$, if a process from $\mathcal{S}$
enters $v\geq\mathcal{V}$ and no process from $\mathcal{S}$ attempts to
advance to a higher view within $d$, then every process from $\mathcal{S}$
will enter $v$ within $d$:
$\exists\mathcal{V},d.\ \forall v\geq\mathcal{V}.\ E_{\rm
first}^{\mathcal{S}}(v)\mathpunct{\downarrow}\ \land\ \neg(A_{\rm
first}^{\mathcal{S}}(v)<E_{\rm first}^{\mathcal{S}}(v)+d)\implies$
$(\forall p_{i}\in\mathcal{S}.\ E_{i}(v)\mathpunct{\downarrow})\land(E_{\rm
last}^{\mathcal{S}}(v)\leq E_{\rm first}^{\mathcal{S}}(v)+d)$

  * •

Startup: if $>\frac{n}{2}$ processes from $\mathcal{S}$ invoke
$\mathsf{advance}$, then some process from $\mathcal{S}$ will enter view $1$:
$(\exists P\subseteq\mathcal{S}.\ |P|>\frac{n}{2}\land\ (\forall p_{i}\in P.\
A_{i}(0)\mathpunct{\downarrow}))\implies E_{\rm
first}^{\mathcal{S}}(1)\mathpunct{\downarrow}$

  * •

Progress: if a process from $\mathcal{S}$ enters $v$ and, for some set
$P\subseteq\mathcal{S}$ of $>\frac{n}{2}$ processes, any process in $P$ that
enters $v$ eventually invokes $\mathsf{advance}$, then some process from
$\mathcal{S}$ will enter $v+1$:
$\forall v.\ E_{\rm first}^{\mathcal{S}}(v)\mathpunct{\downarrow}\ \land\
(\exists P\subseteq\mathcal{S}.\ |P|>\frac{n}{2}\ \land\ (\forall p_{i}\in P.\
E_{i}(v)\mathpunct{\downarrow}\implies
A_{i}(v)\mathpunct{\downarrow}))\implies E_{\rm
first}^{\mathcal{S}}(v+1)\mathpunct{\downarrow}$

Notation:

  * •

$E_{i}(v)$: the time when process $p_{i}$ enters a view $v$

  * •

$E_{\rm first}^{\mathcal{S}}(v)$, $E_{\rm last}^{\mathcal{S}}(v)$: the
earliest and the latest time when a process from $\mathcal{S}$ enters $v$

  * •

${E}_{\rm first}(v)$, ${E}_{\rm last}(v)$: the earliest and the latest time
when any process enters $v$

  * •

$A_{i}(v)$, $A_{\rm first}^{\mathcal{S}}(v)$, $A_{\rm last}^{\mathcal{S}}(v)$,
${A}_{\rm first}(v)$, ${A}_{\rm last}(v)$: similarly for times of attempts to
advance from $v$

  * •

$g(x)\mathpunct{\downarrow}$, $g(x)\mathpunct{\uparrow}$: $g(x)$ is
defined/undefined

Figure 3: Synchronizer properties satisfied in executions with connected core
$\mathcal{S}$.

In Figure 3 we give a specification of a view synchronizer for the system
model $\mathcal{M}_{{\rm PEF}}$, which is an adaptation of the one for the
Byzantine setting [12, 42]. The Monotonicity property ensures that, at any
given process, its view can only increase. The Validity property ensures that
a process may only enter a view $v+1$ if some process in the connected core
$\mathcal{S}$ has called $\mathsf{advance}$ in $v$. This prevents processes
with bad connectivity from disrupting $\mathcal{S}$ by forcing view changes
(e.g., process $2$ in Figure 1c, where $\mathcal{S}=\\{1,3\\}$). The Bounded
Entry property ensures that, if some process from $\mathcal{S}$ enters a view
$v$, then all processes from $\mathcal{S}$ will do so at most $d$ units of
time of each other (for some constant $d$). This only holds if within $d$ no
process from $\mathcal{S}$ attempts to advance to a higher view, as this may
make some processes from $\mathcal{S}$ skip $v$ and enter a higher view
directly. Bounded Entry only holds starting from some view $\mathcal{V}$,
since a synchronizer may not be able to guarantee it for views entered before
${\sf GST}$. The Startup property ensures that if more than $\frac{n}{2}$
processes from $\mathcal{S}$ attempt to advance from view $0$, then some
process from $\mathcal{S}$ will enter view $1$. The Progress property
determines the conditions under which some process from $\mathcal{S}$ will
enter the next view $v+1$: this will happen if a process from $\mathcal{S}$
enters $v$ and for some set $P$ of more than $\frac{n}{2}$ processes from
$\mathcal{S}$, any process in $P$ entering $v$ eventually invokes
$\mathsf{advance}$ (e.g., $1$ and $3$ in Figure 1c).

As we show below, the above properties work in tandem to ensure the liveness
of consensus in the presence of flaky channels. Informally, Progress allows
processes to iterate over views in search for one with a well connected
leader; Bounded Entry enables all processes in the connected core to promptly
enter this view; and Validity ensures that these processes can stay in it
despite any disruption from processes with flaky connectivity.

###  5.2 Synchronizer Implementation

In Figure 4 we present an algorithm that implements the specification in
Figure 3 in the model $\mathcal{M}_{{\rm PEF}}$. This implementation requires
only bounded space, despite the fact that correct channels in
$\mathcal{M}_{{\rm PEF}}$ are only eventually reliable, and thus can lose
messages before ${\sf GST}$. The current view of a process is stored in
$\mathsf{curr\texttt{\textunderscore}view}$. A process also maintains an array
$\mathsf{views}$ tracking, for every other process, the highest view to which
it wishes to advance. When the process invokes $\mathsf{advance}$ (line 4),
the synchronizer does not immediately switch to the next view. Instead, it
updates its entry in the $\mathsf{views}$ array and propagates the whole array
in a ${\tt WISH}$ message, advertising its wish to advance (line 4). Upon the
receipt of a ${\tt WISH}$ message (line 4), a process incorporates the
received information into its $\mathsf{views}$ array, keeping entries with the
highest view (line 4). This mechanism ensures that information is propagated
between processes that do not have direct connectivity while using only
bounded space.

1

2function  _$\mathsf{advance}()$_ :

3 $\mathsf{views}[i]$ $\leftarrow$
$\mathsf{curr\texttt{\textunderscore}view}+1$

4 send ${\tt WISH}(\mathsf{views})$ to all

5

6

7

8 $\textbf{when received}\ {\tt WISH}(V)$

9 for  _$p_{j}\in\mathcal{P}$_ do

10 $\mathsf{views}[j]$ $\leftarrow$ $\max(\mathsf{views}[j],V[j])$

11

12 $v^{\prime}$ $\leftarrow$ $\max\\{v\ |\ \exists p_{j}.\
\mathsf{views}[j]=v\land\linebreak\phantom{\ }\ \ \ \ \ |\\{p_{k}\ |\
\mathsf{views}[k]\geq v\\}|>\frac{n}{2}\\}$

13 if  _$v^{\prime} >\mathsf{curr\texttt{\textunderscore}view}$_ then

14 $\mathsf{curr\texttt{\textunderscore}view}$ $\leftarrow$ $v^{\prime}$

15 $\textbf{trigger}\ \mathsf{new\texttt{\textunderscore}view}(v^{\prime})$

16 send ${\tt WISH}(\mathsf{views})$ to all

17

18

19

20 ${\bf periodically}$ $\triangleright$ every $\rho$ time units

21 send ${\tt WISH}(\mathsf{views})$ to all

22

23

Figure 4: Synchronizer at a process $p_{i}$.

Since the membership of $\mathcal{S}$ is unknown to the processes, to satisfy
Validity the synchronizer cannot initiate a view change based on an
$\mathsf{advance}()$ call by a single process: the synchronizer cannot tell
whether this process is from $\mathcal{S}$ or not. Instead, we require wishes
to advance from a majority of processes, so that at least one of them must be
from $\mathcal{S}$. In more detail, upon receiving a ${\tt WISH}$ message, we
compute $v^{\prime}$ as the $(\lfloor\frac{n}{2}\rfloor+1)$-th highest view in
$\mathsf{views}$ (line 4). Thus, at least one process from $\mathcal{S}$
wishes to advance to a view $\geq v^{\prime}$. Then the current process enters
$v^{\prime}$ if this view is greater than its
$\mathsf{curr\texttt{\textunderscore}view}$ (line 4). Note that a process may
be forced to switch views even if it did not invoke $\mathsf{advance}$; this
helps lagging processes to catch up. To satisfy Bounded Entry, the process
disseminates the information that led it to enter the new view (line 4) to
ensure that other processes also do so promptly. Finally, to deal with message
loss before ${\sf GST}$, a process periodically resends its $\mathsf{views}$
array (line 4).

We can also prove that the synchronizer satisfies Progress: this property
requires $>\frac{n}{2}$ $\mathsf{advance}$ calls by processes in
$\mathcal{S}$, which are well connected enough for the corresponding ${\tt
WISH}$es to eventually propagate within $\mathcal{S}$ and enable the guard at
line 4 (e.g., processes $1$ and $3$ in Figure 1c). Note that Progress wouldn’t
hold if it required $>\frac{n}{2}$ $\mathsf{advance}$ calls by any processes,
not necessarily in $\mathcal{S}$ (e.g., processes $1$ and $2$): in this case
we wouldn’t be able to guarantee that all the corresponding ${\tt WISH}$es
eventually propagate. Due to space constraints, we defer the proof of
correctness of the synchronizer to §D.

######  Theorem 5.1.

Let $\mathcal{F}$ be such that for each $f\in\mathcal{F}$,
${\mathcal{G}}\setminus{f}$ contains a connected core. Then for every
$f\in\mathcal{F}$ with an associated connected core $\mathcal{S}$, every
$f$-compliant fair execution of the algorithm in Figure 4 over the model
$\mathcal{M}_{{\rm PEF}}$ satisfies the properties in Figure 3.

###  5.3 Consensus Protocol

1 2${\bf on\ startup}$ 3 $\mathsf{advance}$()  4 5 6 7 function  _$\mathsf{propose}(x)$_ : 8 $\mathsf{my\texttt{\textunderscore}proposal}\leftarrow x$ 9 wait until $\mathsf{phase}={\tt DECIDED}$ 10 return $\mathsf{val}$ 11 12 13 14 ${\bf on}\ \mathsf{new\texttt{\textunderscore}view}(v)$ 15 $\mathsf{view}\leftarrow v$ 16 $\mathsf{start\texttt{\textunderscore}timer}(\mathsf{decision\texttt{\textunderscore}timer},\mathsf{timeout})$ 17 $\mathsf{M1B}[i]\leftarrow(\mathsf{view},\mathsf{cview},\mathsf{val})$ 18 $\mathsf{phase}\leftarrow{\tt ENTERED}$ 19 20 21 22 when the timer $\mathsf{decision\texttt{\textunderscore}timer}$ expires 23 $\mathsf{timeout}\leftarrow\mathsf{timeout}+\gamma$ 24 $\mathsf{advance}()$ 25 26 27 28 ${\bf periodically}$ $\triangleright$ every $\rho$ time units  29 send ${\tt STATE}(\mathsf{M1B},\mathsf{M2A},\mathsf{M2B})$ to all 30 31 32 33 when received ${\tt STATE}(V1B,V2A,V2B)$ 34 for  _$p_{j}\in\mathcal{P}$_ do 35 if  _$V1B[j].{\it view} >\mathsf{M1B}[j].{\it view}$_ then 36 $\mathsf{M1B}[j]$ $\leftarrow$ $V1B[j]$ 37 38 if  _$V2A[j].{\it view} >\mathsf{M2A}[j].{\it view}$_ then 39 $\mathsf{M2A}[j]$ $\leftarrow$ $V2A[j]$ 40 41 if  _$V2B[j].{\it view} >\mathsf{M2B}[j].{\it view}$_ then 42 $\mathsf{M2B}[j]$ $\leftarrow$ $V2B[j]$ 43 44 45 46 |  47 48when $\mathsf{phase}={\tt ENTERED}\land{\sf leader}(\mathsf{view})=p_{i}\land\linebreak|\\{p_{j}\ |\ p_{j}\in\mathcal{P}\land\mathsf{M1B}[j].{\it view}=\mathsf{view}\\}|>\frac{n}{2}$ 49 $Q$ $\leftarrow$ $\\{p_{j}\ |\ p_{j}\in\mathcal{P}\land\mathsf{M1B}[j].{\it view}=\mathsf{view}\\}$ 50 if  _$\forall p_{j}.\ p_{j}\in Q{\implies}\mathsf{M1B}[j].{\it val}=\bot$_ then 51 if  _$\mathsf{my\texttt{\textunderscore}proposal}=\bot$_ then return 52 $\mathsf{M2A}[i]\leftarrow(\mathsf{view},\mathsf{my\texttt{\textunderscore}proposal})$ 53 54 else 55 let $p_{j}\in Q$ be such that $\phantom{\ }\ \ \mathsf{M1B}[j].{\it val}\neq\bot\land\linebreak\phantom{\ }\ \ \ \forall p_{k}\,{\in}\,Q.\,\mathsf{M1B}[k].{\it cview}\leq\mathsf{M1B}[j].{\it cview}$ 56 $\mathsf{M2A}[i]\leftarrow(\mathsf{view},\mathsf{M1B}[j].{\it val})$ 57 58 $\mathsf{phase}\leftarrow{\tt PROPOSED}$ 59 60 61 62 when $\mathsf{phase}\in\\{{\tt ENTERED},{\tt PROPOSED}\\}\land\linebreak p_{l}={\sf leader}(\mathsf{view})\land\mathsf{M2A}[l].{\it view}=\mathsf{view}$ 63 $(\mathsf{cview},\mathsf{val})\leftarrow\mathsf{M2A}[l]$ 64 $\mathsf{M2B}[i]\leftarrow(\mathsf{cview},\mathsf{val})$ 65 $\mathsf{phase}\leftarrow{\tt ACCEPTED}$ 66 67 68 69 when $\exists v,x.\,v\geq\mathsf{view}\land\linebreak|\\{p_{j}\ |\ p_{j}\in\mathcal{P}\land\mathsf{M2B}[j]=(v,x)\\}|>\frac{n}{2}$ 70 $\mathsf{val}$ $\leftarrow$ $x$ 71 $\mathsf{stop\texttt{\textunderscore}timer}(\mathsf{decision\texttt{\textunderscore}timer})$ 72 $\mathsf{phase}$ $\leftarrow$ ${\tt DECIDED}$ 73 74
---|---
Figure 5: Consensus protocol at a process $p_{i}$.

In Figure 5 we present a consensus protocol in the model $\mathcal{M}_{{\rm
PEF}}$ (partially synchronous / eventually reliable / flaky) that validates
Theorem 4.12. The protocol is a variation of single-decree Paxos [36] where
liveness is ensured with the help of a view synchronizer. Thus, the protocol
works in a succession of views produced by the synchronizer. Each view $v$ has
a fixed leader ${\sf leader}(v)=p_{((v-1)\mod n)+1}$ responsible for proposing
a value to the other processes, which vote on the proposal. Processes monitor
the leader’s behavior and ask the synchronizer to advance to another view if
they suspect that the leader is faulty or has a bad connectivity.

#### State and communication.

A process stores its current view in a variable $\mathsf{view}$. A variable
$\mathsf{phase}$ tracks the progress of the process through different phases
of the protocol. The initial proposal is stored in
$\mathsf{my\texttt{\textunderscore}proposal}$ (line 5). The process also
maintains the last proposal it accepted from a leader in $\mathsf{val}$, and
the view in which this happened in $\mathsf{cview}$.

Processes exchange messages analogous to the $\mathsf{1B}$, $\mathsf{2A}$ and
$\mathsf{2B}$ messages from Paxos, each tagged with the view where the message
was issued. There is no analog of the $\mathsf{1A}$ message, because leader
election is controlled by the synchronizer. Since correct processes may not be
directly connected by correct channels, each process has to forward the
information it receives from others. Since correct channels in
$\mathcal{M}_{{\rm PEF}}$ are only eventually reliable, this furthermore has
to be repeated periodically. If implemented naively, this would require
unbounded space to store all the messages that need to be forwarded. Instead,
we observe that it is sufficient to store for each message type and sender
only the message of this type received from this sender with the highest view.
These are stored in the arrays $\mathsf{M1B}$, $\mathsf{M2A}$ and
$\mathsf{M2B}$.

For simplicity, the pseudocode in Figure 5 separates computation from
communication. Most of the handlers do not send messages, but instead just
modify the arrays $\mathsf{M1B}$, $\mathsf{M2A}$ and $\mathsf{M2B}$. Then,
instead of sending individual $\mathsf{1B}$, $\mathsf{2A}$ or $\mathsf{2B}$
messages like in Paxos, a process periodically sends whole arrays
$\mathsf{M1B}$, $\mathsf{M2A}$ and $\mathsf{M2B}$ in one big ${\tt STATE}$
message (line 5). Upon receipt of a ${\tt STATE}$ message (line 5), a process
incorporates the received information into its arrays $\mathsf{M1B}$,
$\mathsf{M2A}$ and $\mathsf{M2B}$, keeping entries with the highest view. This
mechanism ensures that information is propagated between processes that do not
have direct connectivity while using only bounded space.

#### Normal protocol operation.

When the synchronizer tells a process to enter a new view $v$ (line 5), the
process sets $\mathsf{view}=v$ and writes the information about the last value
it accepted into its entry in the $\mathsf{M1B}$ array. This information will
be propagated to the leader of the view as described above. A leader waits
until its $\mathsf{M1B}$ array contains a majority of entries corresponding to
its view (line 5). Based on these the leader computes its proposal and stores
it into its entry of the $\mathsf{M2A}$ array. The computation is done
similarly to Paxos. If some process has previously accepted a value, the
leader picks the value accepted in the maximal view (line 5). Otherwise, the
leader is free to propose its own value. If $\mathsf{propose}()$ has already
been invoked at the leader, it selects
$\mathsf{my\texttt{\textunderscore}proposal}$ (line 5). If this has not
happened yet, the leader skips its turn (line 5).

Each process waits until its $\mathsf{M2A}$ array contains a proposal by the
leader of its view (line 5). The process then accepts the proposal by updating
its $\mathsf{val}$ and $\mathsf{cview}$. It also notifies all other processes
about this by storing the information about the accepted value into its entry
of the $\mathsf{M2B}$ array. Finally, once a process has a majority of
matching entries in its $\mathsf{M2B}$ array (line 5), it knows that the
decision has been reached, and it sets $\mathsf{phase}={\tt DECIDED}$. If
there is an ongoing $\mathsf{propose}()$ invocation, the condition at line 5
is then satisfied and the process returns the decision to the client.

#### Triggering view changes.

We now describe when a process invokes $\mathsf{advance}()$, which is key to
ensuring liveness. This occurs either on startup (line 5) or when the process
suspects that the current leader is faulty or has bad connectivity. To this
end, when a process enters a view, it sets a
$\mathsf{decision\texttt{\textunderscore}timer}$ for a duration
$\mathsf{timeout}$ (line 5) and stops the timer when a decision is reached
(line 5). If the timer expires before this, the process invokes
$\mathsf{advance}$ (line 5). A process may wrongly suspect a good leader if
the $\mathsf{timeout}$ is initially set too low with respect to the message
delay $\delta$, unknown to the process. To deal with this, a process increases
$\mathsf{timeout}$ each time the timer expires (line 5).

#### Correctness.

We have proved that the algorithm in Figure 5 validates Theorem 4.12. Due to
space constraints we defer a detailed proof to §E and present an outline of
the liveness argument that highlights the use of the synchronizer
specification.

######  Proof 5.2 (Proof of Theorem 4.12 (sketch)).

By contradiction, assume there exists $f\in\mathcal{F}$, $p_{j}\in\tau(f)$ and
an $f$-compliant fair execution of the algorithm in Figure 5 such that $p_{j}$
invokes $\mathsf{propose}$ but that the operation never returns. Let
$\mathcal{S}=\tau(f)$. We first show:

######  Claim 1.

Let $v$ be a view led by $p_{j}$ after ${\sf GST}$. If at each process from
$\mathcal{S}$ that enters $v$ we have
$\mathsf{timeout}>d+3\delta\mathsf{diameter}(S)$, then no process in
$\mathcal{S}$ invokes $\mathsf{advance}$ in $v$.

Intuitively, Bounded Entry ensures that all processes from $\mathcal{S}$ will
enter $v$ promptly, and since the timeouts are high enough, processes will
have sufficient time to exchange the messages needed to reach a decision and
stop the timers. Using Progress, we can also show:

######  Claim 2.

Every view is entered by some process in $\mathcal{S}$.

By Claim 2 and Validity, it occurs infinitely often that the timer expires at
some process in $\mathcal{S}$. From this we can show that every process in
$\mathcal{S}$ executes line 5 infinitely often, and hence, the timeouts keep
increasing at every process. Thus, by Claims 1-2, in some view $v$ led by
$p_{j}$, no process from $\mathcal{S}$ invokes $\mathsf{advance}$. But by
Claim 2 some process in $\mathcal{S}$ enters $v+1$. Then by Validity, some
process in $\mathcal{S}$ calls $\mathsf{advance}$ in $v$: a contradiction.

##  6 Possibility and Impossibility of Classical Consensus via
$\mathbf{\Omega}$

We now present some interesting consequences of our results. It is well-known
that the failure detector $\Omega$ [17, 16] is sufficient for implementing
wait-free consensus resilient to $\lfloor\frac{n-1}{2}\rfloor$ failures in
non-partitionable systems in the presence of crash [17, 36], crash/recovery
[5], or general omission [47, 36] failures. We now investigate if this is
still the case under flaky channels and limited connectivity. Below we
demonstrate that the answer depends on the amount of connectivity in the
underlying network, as established by our lower and upper bounds.

We first show that on the negative side, there are some weakly synchronous
environments where $\Omega$ is known to be implementable, but an obstruction-
free consensus is impossible even if at most one process can crash. One such
environment is the system $S$ of Aguilera et al. [3] wherein only the channels
emanating from some a priori unknown correct process are required to be
eventually reliable and timely, and all the other channels can be flaky (note
that this disallows full network partitions). The impossibility of consensus
in $S$ follows from Theorem 4.11 and is proved in §F:

######  Corollary 6.1.

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

On the positive side, we now show that strengthening connectivity assumptions
does enable consensus to be solved in many previously proposed models of weak
synchrony, such as systems $S^{+}$ and $S^{++}$ of [3] and those defined in
[2, 39, 33, 25]. These papers show that $\Omega$ can be implemented in their
respective models, but (with an exception of [2]) do not give a consensus
algorithm. To show that consensus is indeed possible in these models, we
introduce an intermediary model $\mathcal{M}^{\star}_{{\rm AEF}}$, which is
the same as $\mathcal{M}_{{\rm AEF}}$, but requires a slightly stronger
connectivity (similar to the fair hub of [3]). Specifically, we require that
in every execution, the network contains a _bidirectional star_ , i.e., the
set of eventually reliable channels connecting some correct process to every
other process in both directions. Then the following result (proved in §F)
follows from Theorem 4.12 and [37]:

######  Corollary 6.2.

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

As we show in §F, the above implies

######  Corollary 6.3.

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

##  7 Related Work and Discussion

Fault-tolerant distributed computing in the presence of message loss has been
extensively studied in the past. Early work focused on the models that, in
addition to crashes, allow processes to also fail to either send messages
(_send omission_) [29] or both send and receive messages (_generalized
omission_) [46]. Both these models have been shown to be equivalent to the
crash failures in their computational power in both synchronous [43] and
asynchronous [20] systems. They are however too strong to capture
partitionable systems, as they would automatically classify any non-crashed
process with unreliable connectivity as faulty.

The classical paper by Dolev [21] as well as more recent work (see [48] for
survey) study consensus solvability in general networks as a function of the
network topology, process failure models, and synchrony constraints. These
papers however, only consider the classical (i.e., non-partitionable) version
of consensus, which requires agreement to be reached by all correct processes.
They also do not consider failure models with flaky channels.

In a seminal paper [49], Santoro and Widmayer proposed a _mobile omission_
failure model, which treats message loss independently of process failures.
They showed that in order to solve consensus in a synchronous round-based
system in the absence of process failures, it is necessary and sufficient to
ensure that the communication graph contains a strongly connected component in
every round [49, 50]. In contrast, our lower bounds demonstrate that in order
to implement consensus (or even a register) in a partially synchronous system,
some processes must remain strongly connected throughout the _entire_
execution.

Subsequent work explored fault-tolerant computation in the presence of both
faulty links and processes under weakened synchrony assumptions. Basu et al.
[11] established a separation between reliable channels and either eventually
reliable or fair-lossy channels in terms of their power to solve certain
problems (such as uniform reliable broadcast and $k$-set agreement) under
asynchrony. However, their notion of a reliable link [30] is too strong to be
implementable in practice as it requires every message transmitted via a
complete send invocation to be eventually delivered to a correct destination
even if the sender later crashes.

Several generalizations of the classical failure detector abstractions of [17]
for partitionable systems were proposed in [27, 22, 23, 4] and shown
sufficient for consensus in [27, 22, 4]. However, as we explain in §1, the
failure detectors introduced in these papers cannot be implemented in the
presence of flaky channels.

Aguilera et al. [3] and follow-up work [2, 39, 33, 25] studied the problem of
implementing a failure detector $\Omega$ (which is the weakest for consensus
[16]), under various weak models of synchrony, link reliability, and
connectivity. However, these results are inapplicable in our setting as the
models considered in these papers disallow full partitions.

As we show in §6, our connectivity bounds for consensus are also applicable in
non-partitionable systems with unreliable channels. In particular, they imply
that $\Omega$ is not the only factor determining consensus solvability, and
that the degree of connectivity being assumed also plays an important role.
This suggests an interesting tradeoff across all three modeling dimensions of
synchrony, channel reliability, and connectivity considered in this paper. In
particular, to solve consensus, we assume that every non-faulty channel is
eventually timely [24] whereas the algorithm of [2] can cope with weaker
synchrony constraints. However, unlike [2], which assumes complete
connectivity via fair-lossy channels, our implementation is able to tolerate
an adversarial message loss (flakiness). Whether this tradeoff is fundamental,
or our synchrony assumptions can be further relaxed remains the subject of
future work.

Alquraan et al. [7] present a study of system failures due to network
partitions, which we already mentioned in §1. This work highlights the
practical importance of coming up with provably correct designs that
explicitly consider channel failures. A follow-up paper [6] introduces a
communication layer that can mask channel failures. While this is applicable
to any application, it requires access to networking infrastructure. In
contrast, our work focuses on ensuring the liveness of consensus without
accessing low-level infrastructure.

Raft [45, 44] elects leaders in a randomized way: a prospective leader picks a
view number and requests Votes from a majority of processes (analogous to
$\mathsf{1A}$ messages of Paxos). This may lead to split votes when multiple
processes are competing to get elected, in which case each process waits for a
randomized timeout and retries. While this mechanism works reasonably well in
practice, it does not guarantee termination under partial synchrony even with
perfect connectivity. Raft also includes a Pre-Vote optimization, which, as
Jensen et al. point out [34], can help maintain liveness under intermittent
connectivity. The optimization requires that before sending Vote requests, a
prospective leader gathers a majority of Pre-Votes from other processes,
certifying that they are ready to vote for it. This is similar to gathering
${\tt WISH}$es from a majority of processes in our synchronizer before
entering a view (Figure 4). But unlike our synchronizer Pre-Vote is a best-
effort technique, since in between a process granting a Pre-Vote and receiving
the corresponding Vote request it may vote for someone else, thereby creating
a split vote. Nevertheless, the presence of techniques similar to ours in
existing practical algorithms makes us hopeful that our work could be used to
make Paxos-based systems provably live even under adversarial network
conditions.

## References

  * [1] Yehuda Afek, Hagit Attiya, Alan D. Fekete, Michael J. Fischer, Nancy A. Lynch, Yishay Mansour, Da-Wei Wang, and Lenore D. Zuck.  Reliable communication over unreliable channels.  J. ACM, 41(6):1267–1297, 1994.
  * [2] Marcos K. Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg.  Communication-efficient leader election and consensus with limited link synchrony.  In Symposium on Principles of Distributed Computing (PODC), 2004\.
  * [3] Marcos K. Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg.  On implementing Omega in systems with weak reliability and synchrony assumptions.  Distributed Computing, 21(4):285–314, 2008.
  * [4] Marcos Kawazoe Aguilera, Wei Chen, and Sam Toueg.  Using the heartbeat failure detector for quiescent reliable communication and consensus in partitionable networks.  Theoretical Computer Science, 220(1):3–30, 1999.
  * [5] Marcos Kawazoe Aguilera, Wei Chen, and Sam Toueg.  Failure detection and consensus in the crash-recovery model.  Distributed Comput., 13(2):99–125, 2000.
  * [6] Mohammed Alfatafta, Basil Alkhatib, Ahmed Alquraan, and Samer Al-Kiswany.  Toward a generic fault tolerance technique for partial network partitioning.  In Symposium on Operating Systems Design and Implementation (OSDI), 2020.
  * [7] Ahmed Alquraan, Hatem Takruri, Mohammed Alfatafta, and Samer Al-Kiswany.  An analysis of Network-Partitioning failures in cloud systems.  In Symposium on Operating Systems Design and Implementation (OSDI), 2018.
  * [8] Hagit Attiya, Amotz Bar-Noy, and Danny Dolev.  Sharing memory robustly in message-passing systems.  J. ACM, 42(1):124–142, 1995.
  * [9] Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler.  Lower bound on the step complexity of anonymous binary consensus.  In Symposium on Distributed Computing (DISC), 2016.
  * [10] Peter Bailis and Kyle Kingsbury.  The network is reliable.  Commun. ACM, 57(9):48–55, 2014.
  * [11] Anindya Basu, Bernadette Charron-Bost, and Sam Toueg.  Simulating reliable links with unreliable links in the presence of process crashes.  In Workshop on Distributed Algorithms (WDAG), 1996.
  * [12] Manuel Bravo, Gregory Chockler, and Alexey Gotsman.  Liveness and latency of Byzantine state-machine replication.  In Symposium on Distributed Computing (DISC), 2022.
  * [13] Manuel Bravo, Gregory Chockler, and Alexey Gotsman.  Making Byzantine consensus live.  Distributed Computing, 35(6):503–532, 2022.
  * [14] Eric A. Brewer.  Towards robust distributed systems (abstract).  In Symposium on Principles of Distributed Computing (PODC), 2000\.
  * [15] Marc Brooker, Tao Chen, and Fan Ping.  Millions of tiny databases.  In Symposium on Networked Systems Design and Implementation (NSDI), 2020.
  * [16] Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg.  The weakest failure detector for solving consensus.  J. ACM, 43(4):685–722, 1996.
  * [17] Tushar Deepak Chandra and Sam Toueg.  Unreliable failure detectors for reliable distributed systems.  J. ACM, 43(2):225–267, 1996.
  * [18] Gregory Chockler, Idit Keidar, and Roman Vitenberg.  Group communication specifications: A comprehensive study.  ACM Comput. Surv., 33(4):427–469, 2001.
  * [19] Gregory Chockler, Nancy Lynch, Sayan Mitra, and Joshua Tauber.  Proving atomicity: An assertional approach.  In Symposium on Distributed Computing (DISC), 2005.
  * [20] Brian Coan.  A compiler that increases the fault tolerance of asynchronous protocols.  IEEE Trans. Comput., 37(12):1541–1553, 1988.
  * [21] Danny Dolev.  The Byzantine generals strike again.  J. Algorithms, 3(1):14–30, 1982.
  * [22] Danny Dolev, Roy Friedman, Idit Keidar, and Dahlia Malkhi.  Failure detectors in omission failure environments.  Technical Report TR96-1608, Department of Computer Science, Cornell University, 1996.
  * [23] Danny Dolev, Roy Friedman, Idit Keidar, and Dahlia Malkhi.  Failure detectors in omission failure environments (brief announcement).  In Symposium on Principles of Distributed Computing (PODC), 1997\.
  * [24] Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer.  Consensus in the presence of partial synchrony.  J. ACM, 35(2):288–323, 1988.
  * [25] Antonio Fernández Anta and Michel Raynal.  From an intermittent rotating star to a leader.  In Conference on Principles of Distributed Systems (OPODIS), 2007\.
  * [26] Faith Fich, Maurice Herlihy, and Nir Shavit.  On the space complexity of randomized synchronization.  J. ACM, 45(5):843–862, 1998.
  * [27] Roy Friedman, Idit Keidar, Dahlia Malkhi, Ken Birman, and Danny Dolev.  Deciding in partitionable networks.  Technical Report TR95-1554, Department of Computer Science, Cornell University, 1995.
  * [28] Seth Gilbert and Nancy Lynch.  Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services.  SIGACT News, 33(2):51–59, 2002.
  * [29] Vassos Hadzilacos.  Byzantine agreement under restricted type of failures (not telling the truth is different from telling lies).  Technical Report TR-18-63, Department of Computer Science, Harvard University, 1983.
  * [30] Vassos Hadzilacos and Sam Toueg.  A modular approach to fault-tolerant broadcast and related problems.  Technical Report TR94-1425, Department of Computer Science, Cornell University, 1994.
  * [31] Maurice Herlihy.  Wait-free synchronization.  ACM Transactions on Programming Languages and Systems, 13(1):124–149, 1991.
  * [32] Maurice Herlihy, Victor Luchangco, and Mark Moir.  Obstruction-free synchronization: Double-ended queues as an example.  In International Conference on Distributed Computing Systems (ICDCS), 2003.
  * [33] Martin Hutle, Dahlia Malkhi, Ulrich Schmid, and Lidong Zhou.  Chasing the weakest system model for implementing $\omega$ and consensus.  IEEE Transactions on Dependable and Secure Computing, 6(4):269–281, 2009.
  * [34] Chris Jensen, Heidi Howard, and Richard Mortier.  Examining Raft’s behaviour during partial network failures.  In Workshop on High Availability and Observability of Cloud Systems (HAOC), 2021.
  * [35] Leslie Lamport.  On interprocess communication - part I: Basic formalism, part II: Algorithms.  Distributed Computing, 1(2):77–101, 1986.
  * [36] Leslie Lamport.  The part-time parliament.  ACM Trans. Comput. Syst., 16(2):133–169, 1998.
  * [37] Wai-Kau Lo and Vassos Hadzilacos.  Using failure detectors to solve consensus in asynchronous shared-memory systems (extended abstract).  In Workshop on Distributed Algorithms (WDAG), 1994.
  * [38] Nancy Lynch.  Distributed Algorithms, chapter 17.  Morgan Kaufmann, 1996.
  * [39] Dahlia Malkhi, Florin Oprea, and Lidong Zhou.  $\omega$ meets paxos: Leader election and stability without eventual timely links.  In Symposium on Distributed Computing (DISC), 2005.
  * [40] Dahlia Malkhi and Michael K. Reiter.  Byzantine quorum systems.  Distributed Comput., 11(4):203–213, 1998.
  * [41] Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman.  Cogsworth: Byzantine view synchronization.  In Cryptoeconomics Systems Conference (CES), 2020.
  * [42] Oded Naor and Idit Keidar.  Expected linear round synchronization: The missing link for linear Byzantine SMR.  In Symposium on Distributed Computing (DISC), 2020.
  * [43] Gil Neiger and Sam Toueg.  Automatically increasing the fault-tolerance of distributed algorithms.  J. Algorithms, 11(3):374–419, 1990.
  * [44] Diego Ongaro.  Consensus: bridging theory and practice.  PhD thesis, Stanford University, USA, 2014.
  * [45] Diego Ongaro and John K. Ousterhout.  In search of an understandable consensus algorithm.  In USENIX Annual Technical Conference, 2014.
  * [46] Kenneth J. Perry and Sam Toueg.  Distributed agreement in the presence of processor and communication faults.  IEEE Transactions on Software Engineering, 12(3):477–482, 1986\.
  * [47] Roberto De Prisco, Butler W. Lampson, and Nancy A. Lynch.  Revisiting the PAXOS algorithm.  Theor. Comput. Sci., 243(1-2):35–91, 2000.
  * [48] Dimitris Sakavalas and Lewis Tseng.  Network Topology and Fault-Tolerant Consensus.  Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2019.
  * [49] Nicola Santoro and Peter Widmayer.  Time is not a healer.  In Symposium on Theoretical Aspects of Computer Science (STACS), 1989.
  * [50] Nicola Santoro and Peter Widmayer.  Distributed function evaluation in the presence of transmission faults.  In Symposium on Algorithms (SIGAL), 1990.

##  Appendix A Proof of Theorem 4.2

Assume by contradiction that $\mathcal{A}$ is an $(f,T)$-obstruction-free
implementation of a safe register, but $T$ is not strongly connected in
${\mathcal{G}}\setminus{f}$. Then for some $u,v\in T$, either there is no path
from $u$ to $v$ or from $v$ to $u$ in ${\mathcal{G}}\setminus{f}$. Without
loss of generality we assume the former. Let $S_{u}$ be the strongly connected
component of ${\mathcal{G}}\setminus{f}$ containing $u$, and $S_{v}$ the
strongly connected component of ${\mathcal{G}}\setminus{f}$ containing $v$;
then $S_{u}\cap S_{v}=\emptyset$. Let $R_{u}$ be the set of processes outside
$S_{u}$ that can reach $u$ in ${\mathcal{G}}\setminus{f}$, and $R_{v}$ the set
of processes outside $S_{v}$ that can reach $v$. See Figure 6.

Figure 6: Illustration of the sets used in the proof.

######  Claim 1.

For any $k\in\\{u,v\\}$, $R_{k}\cup S_{k}$ is unreachable from
$\mathcal{P}\setminus(R_{k}\cup S_{k})$ in ${\mathcal{G}}\setminus{f}$.

######  Claim 2.

For any $k\in\\{u,v\\}$, $R_{k}$ is unreachable from $S_{k}$ in
${\mathcal{G}}\setminus{f}$.

The above claims easily follow from the definitions of $R_{k}$ and $S_{k}$.

######  Claim 3.

$S_{u}\cap(R_{v}\cup S_{v})=\emptyset$.

Assume by contradiction that $S_{u}\cap(R_{v}\cup S_{v})\neq\emptyset$ and let
$w\in S_{u}\cap(R_{v}\cup S_{v})$. Because $w\in S_{u}$, there exists a path
from $u$ to $w$. Because $w\in R_{v}\cup S_{v}$, there exists a path from $w$
to $v$. By concatenating these two paths we get a path from $u$ to $v$ in
${\mathcal{G}}\setminus{f}$, contradicting our assumption that there is no
such path.

Let $\alpha_{1}$ be a fair execution of $\mathcal{A}$ where processes and
channels in $f$ fail at the beginning, the process $u$ invokes a read
operation, and no other operation is invoked in $\alpha_{1}$. Because $u\in T$
and $\mathcal{A}$ is $(f,T)$-obstruction-free, the read operation must
eventually terminate. Since there are no write invocations, the read must
return $0$ – the initial value of the register. Let $\alpha_{2}$ be the prefix
of $\alpha_{1}$ ending with this response. By Claim 1, $R_{u}\cup S_{u}$ is
unreachable from $\mathcal{P}\setminus(R_{u}\cup S_{u})$. Thus, the actions by
processes in $R_{u}\cup S_{u}$ do not depend on those by processes in
$\mathcal{P}\setminus(R_{u}\cup S_{u})$. Then the projection of $\alpha_{2}$
to actions by processes in $R_{u}\cup S_{u}$ is an execution of $\mathcal{A}$:
$\alpha_{3}=\alpha_{2}|_{R_{u}\cup S_{u}}$. By Claim 2, $R_{u}$ is unreachable
from $S_{u}$. Thus, the actions by processes in $R_{u}$ do not depend on those
by processes in $S_{u}$. Then $\alpha=\alpha_{3}|_{R_{u}}\alpha_{3}|_{S_{u}}$
is also an execution of $\mathcal{A}$. Notice that $\alpha_{3}|_{R_{u}}$ does
not contain any operation invocation, but it contains steps taken by processes
upon startup.

Let $\beta_{1}$ be a fair execution of $\mathcal{A}$ where processes and
channels in $f$ fail at the beginning. The execution $\beta_{1}$ starts with
all the actions from $\alpha_{3}|_{R_{u}}$ followed by a ${\it write}(1)$
invocation by process $v$, and no other operation is invoked in $\beta_{1}$.
Because $v\in T$ and $\mathcal{A}$ is $(f,T)$-obstruction-free, the write
operation must eventually terminate. Let $\beta_{2}$ be the prefix of
$\beta_{1}$ ending with this response. By Claim 1, $R_{u}\cup S_{u}$ is
unreachable from $\mathcal{P}\setminus(R_{u}\cup S_{u})$. By Claim 2, $R_{u}$
is unreachable from $S_{u}$. Therefore, $R_{u}$ is unreachable from
$\mathcal{P}\setminus R_{u}$. By Claim 1, $R_{v}\cup S_{v}$ is unreachable
from $\mathcal{P}\setminus(R_{v}\cup S_{v})$. Therefore, $R_{u}\cup R_{v}\cup
S_{v}$ is unreachable from $\mathcal{P}\setminus(R_{u}\cup R_{v}\cup S_{v})$.
Thus, the actions by processes in $R_{u}\cup R_{v}\cup S_{v}$ do not depend on
those by processes in $\mathcal{P}\setminus(R_{u}\cup R_{v}\cup S_{v})$. Then
$\beta=\beta_{2}|_{R_{u}\cup R_{v}\cup S_{v}}$ is an execution of
$\mathcal{A}$. Recall that $\beta_{1}$ starts with $\alpha_{3}|_{R_{u}}$, and
hence, so does $\beta$. Let $\delta$ be the suffix of $\beta$ such that
$\beta=\alpha_{3}|_{R_{u}}\delta$.

Consider the execution $\sigma=\alpha_{3}|_{R_{u}}\delta\alpha_{3}|_{S_{u}}$
without any failures. By Claim 3, $S_{u}\cap(R_{v}\cup S_{v})=\emptyset$, and
by the definition of $R_{u}$, we have $S_{u}\cap R_{u}=\emptyset$. Hence,
$S_{u}\cap(R_{u}\cup R_{v}\cup S_{v})=\emptyset$. Then, given that $\delta$
only contains actions by processes in $R_{u}\cup R_{v}\cup S_{v}$, we get:
$\sigma|_{R_{u}\cup R_{v}\cup
S_{v}}=(\alpha_{3}|_{R_{u}}\delta\alpha_{3}|_{S_{u}})|_{R_{u}\cup R_{v}\cup
S_{v}}=\alpha_{3}|_{R_{u}}\delta=\beta$ and
$\sigma|_{S_{u}}=(\alpha_{3}|_{R_{u}}\delta\alpha_{3}|_{S_{u}})|_{S_{u}}=\alpha_{3}|_{S_{u}}=(\alpha_{3}|_{R_{u}}\alpha_{3}|_{S_{u}})|_{S_{u}}=\alpha|_{S_{u}}$.
Therefore, $\sigma$ is indistinguishable from $\beta$ to the processes in
$R_{u}\cup R_{v}\cup S_{v}$ and from $\alpha$ to the processes in $S_{u}$.
Finally $\sigma|_{\mathcal{P}\setminus(R_{u}\cup S_{u}\cup R_{v}\cup
S_{v})}=\varepsilon$.

Thus, for every process, $\sigma$ is indistinguishable to this process from
some execution of $\mathcal{A}$. Furthermore, each message received by a
process in $\sigma$ has previously been sent by another process. Therefore,
$\sigma$ is an execution of $\mathcal{A}$. However, in this execution ${\it
write}(1)$ terminates before a read that fetches $0$ is invoked. This
contradicts the assumption that $\mathcal{A}$ implements a safe register. The
contradiction shows that $T$ must be strongly connected in
${\mathcal{G}}\setminus{f}$. ∎

##  Appendix B An Atomic Register Implementation over the Model
$\mathcal{M}_{{\rm AEF}}$

In Figure 7 we present an atomic register protocol in the model
$\mathcal{M}_{{\rm AEF}}$ (asynchronous / eventually reliable / flaky) that
validates Theorem 4.9. The protocol is a variant of ABD [8].

1 2function  _$\mathsf{write}(v)$_ : 3 pre: $\mathsf{status}={\sf idle}$ 4 $\mathsf{wr\texttt{\textunderscore}val}\leftarrow v$ 5 $\mathsf{seq}\leftarrow\mathsf{seq}+1$ 6 $\mathsf{query}[i]\leftarrow\mathsf{seq}$ 7 $\mathsf{status}\leftarrow{\sf wr\texttt{\textunderscore}query}$ 8 wait until $\mathsf{status}={\sf wr\texttt{\textunderscore}done}$ 9 $\mathsf{status}\leftarrow{\sf idle}$ 10 return ${\tt ACK}$ 11 12 13 14 function  _$\mathsf{read}()$_ : 15 pre: $\mathsf{status}={\sf idle}$ 16 $\mathsf{seq}\leftarrow\mathsf{seq}+1$ 17 $\mathsf{query}[i]\leftarrow\mathsf{seq}$ 18 $\mathsf{status}\leftarrow{\sf rd\texttt{\textunderscore}query}$ 19 wait until $\mathsf{status}={\sf rd\texttt{\textunderscore}done}$ 20 $\mathsf{status}\leftarrow{\sf idle}$ 21 return $\mathsf{rd\texttt{\textunderscore}val}$ 22 23 24 25 ${\bf periodically}$ 26 send ${\tt STATE}(\mathsf{query},\mathsf{query\texttt{\textunderscore}ack},\mathsf{write},\mathsf{write\texttt{\textunderscore}ack})$ to all 27 28 29 30 when received ${\tt STATE}(Q,R,W,X)$ 31 for  _$p_{j}\in\mathcal{P}$_ do 32 if  _$Q[j].\mathsf{seq} >\mathsf{query}[j].\mathsf{seq}$_ then 33 $\mathsf{query}[j]\leftarrow Q[j]$ 34 35 if  _$W[j].\mathsf{seq} >\mathsf{write}[j].\mathsf{seq}$_ then 36 $\mathsf{write}[j]\leftarrow W[j]$ 37 38 for  _$p_{k}\in\mathcal{P}$_ do 39 if  _$R[j][k].\mathsf{seq} >\mathsf{query\texttt{\textunderscore}ack}[j][k].\mathsf{seq}$_ then 40 $\mathsf{query\texttt{\textunderscore}ack}[j][k]\leftarrow R[j][k]$ 41 42 if  _$X[j][k].\mathsf{seq} >\mathsf{write\texttt{\textunderscore}ack}[j][k].\mathsf{seq}$_ then 43 $\mathsf{write\texttt{\textunderscore}ack}[j][k]\leftarrow X[j][k]$ 44 45 46 47 48 |  49 50when $\exists j.\ \mathsf{query}[j].\mathsf{seq}>\mathsf{query\texttt{\textunderscore}ack}[i][j].\mathsf{seq}$ 51 $\mathsf{query\texttt{\textunderscore}ack}[i][j]\leftarrow(\mathsf{val},\mathsf{tag},\mathsf{query}[j].\mathsf{seq})$ 52 53 54 55 when $\mathsf{status}={\sf rd\texttt{\textunderscore}query}\land\linebreak\phantom{\ }\ \ |\\{j\ |\ \mathsf{query\texttt{\textunderscore}ack}[j][i].\mathsf{seq}=\mathsf{seq}\\}|>\frac{n}{2}$ 56 $Q\leftarrow\\{j\ |\ \mathsf{query\texttt{\textunderscore}ack}[j][i].\mathsf{seq}=\mathsf{seq}\\}$ 57 $j\leftarrow\mathsf{argmax}\\{\mathsf{query\texttt{\textunderscore}ack}[j][i].\mathsf{tag}\ |\ j\in Q\\}$ 58 $\mathsf{rd\texttt{\textunderscore}val}\leftarrow\mathsf{query\texttt{\textunderscore}ack}[j][i].\mathsf{val}$ 59 $\mathsf{val}\leftarrow\mathsf{query\texttt{\textunderscore}ack}[j][i].\mathsf{val}$ 60 $\mathsf{tag}\leftarrow\mathsf{query\texttt{\textunderscore}ack}[j][i].\mathsf{tag}$ 61 $\mathsf{status}\leftarrow{\sf rd\texttt{\textunderscore}propagate}$ 62 $\mathsf{write}[i]\leftarrow(\mathsf{val},\mathsf{tag},\mathsf{seq})$ 63 64 65 66 when $\mathsf{status}={\sf wr\texttt{\textunderscore}query}\land\linebreak\phantom{\ }\ \ |\\{j\ |\ \mathsf{query\texttt{\textunderscore}ack}[j][i].\mathsf{seq}=\mathsf{seq}\\}|>\frac{n}{2}$ 67 $Q\leftarrow\\{j\ |\ \mathsf{query\texttt{\textunderscore}ack}[j][i].\mathsf{seq}=\mathsf{seq}\\}$ 68 $(t,\texttt{\textunderscore})\leftarrow\max\\{\mathsf{query\texttt{\textunderscore}ack}[j][i].\mathsf{tag}\ |\ j\in Q\\}$ 69 $\mathsf{val}\leftarrow\mathsf{wr\texttt{\textunderscore}val}$ 70 $\mathsf{tag}\leftarrow(t+1,i)$ 71 $\mathsf{status}\leftarrow{\sf wr\texttt{\textunderscore}propagate}$ 72 $\mathsf{write}[i]\leftarrow(\mathsf{val},\mathsf{tag},\mathsf{seq})$ 73 74 75 76 when $\exists j.\ \mathsf{write}[j].\mathsf{seq}>\mathsf{write\texttt{\textunderscore}ack}[i][j].\mathsf{seq}$ 77 if  _$\mathsf{write}[j].\mathsf{tag} >\mathsf{tag}$_ then 78 $\mathsf{val}\leftarrow\mathsf{write}[j].\mathsf{val}$ 79 $\mathsf{tag}\leftarrow\mathsf{write}[j].\mathsf{tag}$ 80 81 $\mathsf{write\texttt{\textunderscore}ack}[i][j]\leftarrow\mathsf{write}[j].\mathsf{seq}$ 82 83 84 85 when $\mathsf{status}={\sf rd\texttt{\textunderscore}propagate}\land\linebreak\phantom{\ }\ \ |\\{j\ |\ \mathsf{write\texttt{\textunderscore}ack}[j][i].\mathsf{seq}=\mathsf{seq}\\}|>\frac{n}{2}$ 86 $\mathsf{status}\leftarrow{\sf rd\texttt{\textunderscore}done}$ 87 88 89 90 when $\mathsf{status}={\sf wr\texttt{\textunderscore}propagate}\land\linebreak\phantom{\ }\ \ |\\{j\ |\ \mathsf{write\texttt{\textunderscore}ack}[j][i].\mathsf{seq}=\mathsf{seq}\\}|>\frac{n}{2}$ 91 $\mathsf{status}\leftarrow{\sf wr\texttt{\textunderscore}done}$ 92 93
---|---
Figure 7: ABD protocol at a process $p_{i}$.

  * •

$\mathsf{requested}=\\{x\in\mathcal{O}_{r}:\mathsf{status}_{x}\geq{\sf
rd\texttt{\textunderscore}query}\\}\cup\\{x\in\mathcal{O}_{w}:\mathsf{status}_{x}\geq{\sf
wr\texttt{\textunderscore}query}\\}$

  * •

$\mathsf{pending}=\\{x\in\mathcal{O}_{r}:\mathsf{status}_{x}\geq{\sf
rd\texttt{\textunderscore}query}\\}\cup\\{x\in\mathcal{O}_{w}:\mathsf{status}_{x}\geq{\sf
wr\texttt{\textunderscore}query}\\}$

  * •

$\mathsf{ordered}=\\{x\in\mathcal{O}_{r}:\mathsf{status}_{x}\geq{\sf
rd\texttt{\textunderscore}propagate}\\}\cup\\{x\in\mathcal{O}_{w}:\mathsf{status}_{x}\geq{\sf
wr\texttt{\textunderscore}propagate}\\}$

  * •

$\mathsf{completed}=\\{x\in\mathcal{O}_{r}:\mathsf{status}_{x}\geq{\sf
rd\texttt{\textunderscore}done}\\}\cup\\{x\in\mathcal{O}_{w}:\mathsf{status}_{x}\geq{\sf
wr\texttt{\textunderscore}done}\\}$

  * •

$\mathsf{responded}=\\{x\in\mathcal{O}_{r}:\mathsf{status}_{x}\geq{\sf
rd\texttt{\textunderscore}done}\\}\cup\\{x\in\mathcal{O}_{w}:\mathsf{status}_{x}\geq{\sf
wr\texttt{\textunderscore}done}\\}$

  * •

For $r\in\mathcal{O}_{r}$ :
$\mathsf{lastwrites}(r)=\\{w\in\mathcal{O}_{w}\cap\mathsf{ordered}:\mathsf{tag}_{w}=\mathsf{tag}_{r}\\}$

  * •

For $x\in\mathcal{O}$, $q\in\mathcal{P}$:

$\mathsf{newtag}(x,q)=\begin{cases}t&\text{if
}q.\mathsf{query\texttt{\textunderscore}ack}[q][p_{x}]=(\texttt{\textunderscore},t,\mathsf{seq}_{x})\\\
q.\mathsf{tag}&otherwise\end{cases}$

  * •

For $x\in\mathcal{O}$ and $Q^{\prime}=\\{j\ |\
p_{x}.\mathsf{query\texttt{\textunderscore}ack}[j][p_{x}].\mathsf{seq}=\mathsf{seq}_{x}\\}$:

$\mathsf{mintag}(x)=\begin{cases}\max(\mathsf{tag}_{x},\min_{Q\subseteq\mathcal{P}\land|Q|>\frac{n}{2}}\max(\mathsf{newtag}(x,p):p\in
Q\setminus Q^{\prime}))&\text{if }|Q^{\prime}|\leq\frac{n}{2}\\\
\mathsf{tag}_{x}&otherwise\end{cases}$

Figure 8: Derived variables from the ABD protocol.

We now outline how to prove that the algorithm implements an atomic register.
Our strategy is to show that it implements the PO-Machine from [19] by
exhibiting a forward simulation relation from ABD to the PO-Machine.

To this end, Figure 8 introduces several derived variables from the ABD
protocol that will then be used in the definition of the simulation relation.
The definitions rely on the following notation. We denote by $\mathcal{O}_{w}$
and $\mathcal{O}_{r}$ the sets of the write and the read operations
respectively, and by $\mathcal{O}=\mathcal{O}_{w}\cup\mathcal{O}_{r}$ the set
of all operations. Also, for an operation $x\in\mathcal{O}$, we let
$\mathsf{tag}_{x}$ and $\mathsf{seq}_{x}$ be the associated tag and sequence
number, respectively. Finally, let $x\in\mathcal{O}$ and $p$ be the process
who invokes $x$. We let $p_{x}.v$ be the value of $v$ at the process $p$
during the execution of $x$.

  * •

$u.\mathsf{vertices}=s.\mathsf{pending}$

  * •

$u.\mathsf{requested}=s.\mathsf{requested}$

  * •

$u.\mathsf{ordered}=s.\mathsf{ordered}$

  * •

$u.\mathsf{completed}=s.\mathsf{completed}\cup\bigcup_{r\in\mathcal{O}_{r}\cap
s.\mathsf{completed}}s.\mathsf{lastwrites}(r)$

  * •

$u.\mathsf{responded}=s.\mathsf{responded}$

  * •

$u.\mathsf{dag}\subseteq s.\mathsf{ordered}\times s.\mathsf{ordered}$

  * •

For all $x\in\mathcal{O}_{w}\cap u.\mathsf{ordered}$ and
$y\in\mathcal{O}_{r}\cap u.\mathsf{ordered}$, $(x,y)\in u.\mathsf{edges}$ iff
$s.\mathsf{tag}_{x}=s.\mathsf{tag}_{y}$

  * •

For all $x,y\in\mathcal{O}_{w}\cap u.\mathsf{ordered}$, if $(x,y)\in
u.\mathsf{dag}$, then $s.\mathsf{tag}_{x}<s.\mathsf{tag}_{y}$

  * •

For all $x\in u.\mathsf{vertices}$, if $y\in u.\mathsf{prec}(x)$, then
$s.\mathsf{tag}_{y}\leq s.\mathsf{mintag}(x)$

Figure 9: Forward simulation
$f\subseteq{\emph{s}tates}(\text{ABD})\times{\emph{s}tates}(\text{PO-
Machine})$ from ABD to PO-Machine. For each $s\in{\emph{s}tates}(\text{ABD})$
and $u\in{\emph{s}tates}(\text{PO-Machine})$, $(s,u)\in f$ if and only if the
properties hold.

Among these variables, the most interesting ones are $\mathsf{newtag}$ and
$\mathsf{mintag}$. For a given operation $x\in\mathcal{O}$ and process
$q\in\mathcal{P}$, $\mathsf{newtag}$ keeps track of the tag returned by $q$ to
$p_{x}$ during the query phase of $x$ (line 7). If $q$ has not yet responded
to $p_{x}$ during the query phase of $x$, then $\mathsf{mintag}$ is the
current value of $q.\mathsf{tag}$. The variable $\mathsf{mintag}$ keeps track
of the lowest possible tag that can be determined by a process at the end of
the query phase. At the beginning and before any process has responded, this
tag is the smallest tag among the maximum tags carried by processes in every
quorum. As the process is progressing through the query phase it might get a
response from a process whose tag is bigger than the current value of
$\mathsf{mintag}$. In this case, the definition of $\mathsf{mintag}$ ensures
that $\mathsf{mintag}$ is assigned to that higher value. Finally, upon
completion of the query phase, the value of $\mathsf{mintag}$ is fixed to be
the maximum tag received during the phase.

The simulation relation $f$ from ABD to PO-Machine is shown in Figure 9. We
now state the main result:

######  Lemma B.1.

$f$ is a forward simulation from ABD to PO-Machine.

The proof is an easy adjustment of [19, Lemma 5.18]. Then, ABD implements PO-
Machine, and by [19, Theorem 1], an atomic register.

##  Appendix C Registers from Consensus

In this section we show that registers can be implemented from consensus.
Consider the algorithm in Figure 10. Roughly, each process maintains an
implicit log where they place incoming requests. The processes use consensus
as a black box to agree on which operation is placed on which entry. The
operations are then executed sequentially following the log. Therefore,
processes execute the same operations in the same order.

1 2${\sf idx}\leftarrow 0$ 3 $\mathsf{val}\leftarrow\bot$ 4 let $C$ be the $0$-th instance of consensus 5 6 7function  _$\mathsf{execute}(op)$_ : 8 if  _$op=\mathsf{read}$_ then 9 return $\mathsf{val}$ 10 11 else 12 let $v$ be such that $op=\mathsf{write}(v)$ 13 $\mathsf{val}$ $\leftarrow$ $v$ 14 return ${\tt ACK}$ 15 16 |  17 18upon invocation of $\mathit{\mathit{op}}$ 19 pre: ${\sf wait}={\tt FALSE}$ 20 ${\sf op}\leftarrow\mathit{op}$ 21 ${\sf wait}\leftarrow{\tt TRUE}$ 22 $C.\mathsf{propose}({\sf op})$ 23 wait until ${\sf wait}={\tt FALSE}$ 24 return ${\sf res}$ 25 26 27 28 upon $C.\mathsf{decide}(\mathit{op})$ 29 ${\sf idx}\leftarrow{\sf idx}+1$ 30 let $C$ be the ${\sf idx}$-th instance of consensus 31 ${\sf res}\leftarrow\mathsf{execute}(\mathit{op})$ 32 if  _${\sf wait}={\tt TRUE}$_ then 33 if  _$\mathit{op}={\sf op}$_ then 34 ${\sf wait}\leftarrow{\tt FALSE}$ 35 36 else 37 $C.\mathsf{propose}({\sf op})$ 38 39 40 41
---|---
Figure 10: Protocol at a process $p_{i}$. Let $\mathit{Val}$ be an arbitrary
domain of values. $\mathit{op}$ can either be $\mathit{read}()$ or
$\mathit{write}(v)$, $v\in\mathit{Val}$.

######  Lemma C.1.

Let $\mathcal{F}$ be a fail-prone system and $\tau:\mathcal{F}\rightarrow
2^{\mathcal{P}}$ be such that $\forall f=(P,C)\in\mathcal{F}.\
\tau(f)\neq\emptyset\wedge\tau(f)\subseteq\mathcal{P}\setminus P$. Then the
algorithm in Figure 10 is an $(\mathcal{F},\tau)$-obstruction-free
implementation of a safe register provided that for each $i\geq 0$, the $i$-th
instance of consensus is $(\mathcal{F},\tau)$-obstruction-free.

######  Proof C.2.

It is easy to see that the algorithm implements a safe register. Therefore, we
focus on showing obstruction-freedom. Let
$f=(P,\texttt{\textunderscore})\in\mathcal{F}$, $\sigma$ be an $f$-compliant
execution of the the algorithm in Figure 10, $p\in\mathcal{P}\setminus P$ and
$\mathit{op}$ be an operation invoked by $p$ that executes solo in $\sigma$.
We show that $\mathit{op}$ must eventually return.

Indeed, let $i$ be such that $\mathit{op}$ is proposed in the $i$-th instance
of consensus at a time $t$ and assume by contradiction that $\mathit{op}$
never returns. Since $\mathit{op}$ executes solo in $\sigma$, it is not
concurrent with any operation invoked by any other correct process. And
because $\mathit{op}$ never returns, this means that no operation invocation
by a correct process occurs at any time $\geq t$. This means that from time
$t$ onwards, the only outstanding operations are either $\mathit{op}$ or
operations invoked by faulty processes. Thus, no operation by a correct
process is proposed for consensus at any time $\geq t$.

We now show that for each $j\geq i$, $\mathit{op}$ is proposed in the $j$-th
instance of consensus $C_{j}$. Because $i$ is defined to be the first instance
of consensus where $\mathit{op}$ is proposed, the result trivially holds for
$j=i$. Suppose now that $\mathit{op}$ is proposed in the $k$-th instance of
consensus for some $k>i$. Because the $k$-th instance of consensus is
$(\mathcal{F},\tau)$-obstruction-free and
$C_{k}.\mathsf{propose}(\mathit{op})$ runs solo in $\sigma$, then
$C_{k}.\mathsf{propose}(\mathit{op})$ eventually returns with some value
$\mathit{op}^{\prime}\neq\mathit{op}$. Therefore, the handler at line 10
guarantees that $\mathit{op}$ is proposed in the $(k+1)$-th instance of
consensus, as required.

Therefore, there exists $r\geq i$ such that $C_{r}$ is instantiated by $p$
after every faulty process crashed, $p$ invokes
$\mathsf{propose}(\mathit{op})$ in $C_{r}$ and $C_{r}$ decides some value
$\mathit{op}^{\prime}\neq\mathit{op}$. Because $p$ is the only process to
propose in $C_{r}$ and since the decided value must have been proposed, this
contradicts the safety properties of consensus. The contradiction shows that
$\mathit{op}$ must eventually return in $\sigma$.

##  Appendix D Synchronizer Correctness

Consider a fail-prone system $\mathcal{F}$ satisfying the conditions of
Theorem 5.1: for each $f\in\mathcal{F}$, the graph ${\mathcal{G}}\setminus{f}$
contains a connected core. For the remainder of the section we fix a failure
pattern $f\in\mathcal{F}$ and let $\mathcal{S}$ be the corresponding connected
core. We now show that every $f$-compliant execution of the algorithm in
Figure 4 over the model $\mathcal{M}_{{\rm PEF}}$ satisfies the properties in
Figure 3. The proof relies on the following propositions, whose easy proof we
omit.

######  Proposition D.1.

If a message ${\tt WISH}(V)$ is sent at a time $t$, then $V[i]\leq
p_{i}.\mathsf{curr\texttt{\textunderscore}view}(t)+1$ for every process
$p_{i}$.

######  Proposition D.2.

If a process $p_{i}$ has $p_{i}.\mathsf{views}(t)[j]>0$, then there exists an
array $V$ and a time $t^{\prime}\leq t$ such that
$V[j]=p_{i}.\mathsf{views}(t)[j]$ and $p_{j}$ sends ${\tt WISH}(V)$ at
$t^{\prime}$.

######  Proposition D.3.

If a process $p_{i}$ enters a view $v$, then there exists a process
$p_{j}\in\mathcal{S}$, an array $V$ and a time $t<E_{i}(v)$ such that
$V[j]\geq v$ and $p_{j}$ sends ${\tt WISH}(V)$ at $t$.

######  Proposition D.4.

If a process $p_{i}$ sends ${\tt WISH}(V)$ with $V[i]=v+1$ at a time $t$, then
$A_{i}(v)\mathpunct{\downarrow}\ \land\ A_{i}(v)\leq t$.

######  Lemma D.5.

(Validity) A process only enters $v+1$ if some process from $\mathcal{S}$ has
attempted to advance from $v$:
$\forall i,v.\ E_{i}(v+1)\mathpunct{\downarrow}\ \implies A_{\rm
first}^{\mathcal{S}}(v)\mathpunct{\downarrow}\ \land\ A_{\rm
first}^{\mathcal{S}}(v)<E_{i}(v+1)$.

######  Proof D.6.

Let $i$ and $v$ be such that $E_{i}(v+1)\mathpunct{\downarrow}$. By
Proposition D.3, there exists a process $p_{j}\in\mathcal{S}$, an array $V$
and a time $t<E_{i}(v+1)$ such that $V[j]\geq v+1$ and $p_{j}$ sends ${\tt
WISH}(V)$ at $t$. Suppose $V[j]=v+1$. Then, by Proposition D.4,
$A_{j}(v)\mathpunct{\downarrow}\ \land\ A_{j}(v)\leq t$. Therefore, $A_{\rm
first}^{\mathcal{S}}(v)\mathpunct{\downarrow}$ and $A_{\rm
first}^{\mathcal{S}}(v)\leq A_{j}(v)\leq t<E_{i}(v+1)$.

Suppose now $V[j]>v+1$. By Proposition D.1,
$p_{j}.\mathsf{curr\texttt{\textunderscore}view}(t)\geq V[j]-1>v$. Let $p_{k}$
be the first process to enter a view $v_{k}>v$ at a time $t_{k}\leq t$. The
process $p_{k}$ enters $v_{k}$ upon executing line 4, and by lines 4 and 4,
$p_{k}.\mathsf{views}(t_{k})$ includes more than $\frac{n}{2}$ entries $\geq
v_{k}$. Because there are at most $\frac{n}{2}$ processes not in
$\mathcal{S}$, there exists a process $p_{l}\in\mathcal{S}$ and a view
$v_{l}\geq v_{k}$ such that $p_{k}.\mathsf{views}(t_{k})[l]=v_{l}$. By
Proposition D.2, there exists an array $V^{\prime}$ and a time $t_{l}\leq
t_{k}$ such that $V^{\prime}[l]=v_{l}$ and $p_{l}$ sends ${\tt
WISH}(V^{\prime})$ at $t_{l}$. By Proposition D.1,
$p_{l}.\mathsf{curr\texttt{\textunderscore}view}(t_{l})\geq v_{l}-1\geq
v_{k}-1\geq v$. Because $p_{k}$ is the first process to enter a view $>v$ at
$t_{k}$ and $t_{l}\leq t_{k}$ then
$p_{l}.\mathsf{curr\texttt{\textunderscore}view}(t_{l})\leq v$. Therefore,
$p_{l}.\mathsf{curr\texttt{\textunderscore}view}(t_{l})=v$ and $v_{l}=v+1$.
Then, by Proposition D.4, $A_{l}(v)\mathpunct{\downarrow}\ \land\ A_{l}(v)\leq
t_{l}$. Therefore, $A_{\rm first}^{\mathcal{S}}(v)\mathpunct{\downarrow}$ and
$A_{\rm first}^{\mathcal{S}}(v)\leq A_{l}(v)\leq t_{l}\leq t_{k}\leq
t<E_{i}(v+1)$.

######  Lemma D.7.

$\mathcal{S}$ does not skip views: $\forall v,v^{\prime}.\
0<v<v^{\prime}\land{E}_{\rm first}(v^{\prime})\mathpunct{\downarrow}\ \implies
E_{\rm first}^{\mathcal{S}}(v)\mathpunct{\downarrow}\ \land\ E_{\rm
first}^{\mathcal{S}}(v)<{E}_{\rm first}(v^{\prime})$.

######  Proof D.8.

Let $v^{\prime}\geq 2$ and assume that a process enters $v^{\prime}$, so that
${E}_{\rm first}(v^{\prime})\mathpunct{\downarrow}$. We prove by induction
that for each $k$ satisfying $1\leq k\leq v^{\prime}-1$, some process in
$\mathcal{S}$ enters $v^{\prime}-k$ earlier than ${E}_{\rm first}(v^{\prime})$
and thus $E_{\rm first}^{\mathcal{S}}(v^{\prime}-k)\mathpunct{\downarrow}\
\land\ E_{\rm first}^{\mathcal{S}}(v^{\prime}-k)<{E}_{\rm first}(v^{\prime})$.

For the base case assume that a process enters $v^{\prime}$. Then by Lemma
D.5, there exists a process $p_{i}\in\mathcal{S}$ such that
$A_{i}(v^{\prime}-1)\mathpunct{\downarrow}\ \land\
A_{i}(v^{\prime}-1)<{E}_{\rm first}(v^{\prime})$. Because
$p_{i}.\mathsf{curr\texttt{\textunderscore}view}(A_{i}(v^{\prime}-1))=v^{\prime}-1$
then $E_{i}(v^{\prime}-1)\mathpunct{\downarrow}\ \land\
E_{i}(v^{\prime}-1)\leq A_{i}(v^{\prime}-1)<{E}_{\rm first}(v^{\prime})$.

For the inductive step assume that the required holds for some $k$ so that
$E_{\rm first}^{\mathcal{S}}(v^{\prime}-k)\mathpunct{\downarrow}\ \land\
E_{\rm first}^{\mathcal{S}}(v^{\prime}-k)<{E}_{\rm first}(v^{\prime})$. Then
by Lemma D.5, there exists a process $p_{i}\in\mathcal{S}$ such that
$A_{i}(v^{\prime}-k-1)\mathpunct{\downarrow}\ \land\
A_{i}(v^{\prime}-k-1)<E_{\rm first}^{\mathcal{S}}(v^{\prime}-k)$. Because
$p_{i}.\mathsf{curr\texttt{\textunderscore}view}(A_{i}(v^{\prime}-k-1))=v^{\prime}-k-1$
then $E_{i}(v^{\prime}-k-1)\mathpunct{\downarrow}\ \land\
E_{i}(v^{\prime}-k-1)\leq A_{i}(v^{\prime}-k-1)<E_{\rm
first}^{\mathcal{S}}(v^{\prime}-k)<{E}_{\rm first}(v^{\prime})$.

######  Lemma D.9.

Let $\Delta={\tt diameter}(\mathcal{S})\delta$. Consider a view $v>0$ and
assume that $v$ is entered by some process in $\mathcal{S}$. If $E_{\rm
first}^{\mathcal{S}}(v)\geq{\sf GST}$ and no process in $\mathcal{S}$ attempts
to advance from $v$ before $E_{\rm first}^{\mathcal{S}}(v)+\Delta$, then all
processes in $\mathcal{S}$ enter $v$ and $E_{\rm last}^{\mathcal{S}}(v)\leq
E_{\rm first}^{\mathcal{S}}(v)+\Delta$.

######  Proof D.10.

Suppose there exists a process $p_{i}$ and a time $t\leq E_{\rm
first}^{\mathcal{S}}(v)+\Delta$ such that
$p_{i}.\mathsf{curr\texttt{\textunderscore}view}(t)=v^{\prime}>v$. By Lemma
D.7, ${E}_{\rm first}(v+1)\mathpunct{\downarrow}\ \land\ {E}_{\rm
first}(v+1)\leq{E}_{\rm first}(v^{\prime})\leq t$. Thus, by Lemma D.5, $A_{\rm
first}^{\mathcal{S}}(v)\mathpunct{\downarrow}\ \land\ A_{\rm
first}^{\mathcal{S}}(v)<{E}_{\rm first}(v+1)\leq t\leq E_{\rm
first}^{\mathcal{S}}(v)+\Delta$, contradicting the assumption that no process
in $\mathcal{S}$ attempts to advance from $v$ before $E_{\rm
first}^{\mathcal{S}}(v)+\Delta$. Therefore, for all times $t\leq E_{\rm
first}^{\mathcal{S}}(v)+\Delta$ and processes $p_{i}$,
$p_{i}.\mathsf{curr\texttt{\textunderscore}view}(t)\leq v$.

Let $p_{i}$ be the process in $\mathcal{S}$ to enter $v$ at the time $E_{\rm
first}^{\mathcal{S}}(v)$ and $p_{j}\in\mathcal{S}$. We prove by induction on
the distance $d$ from $p_{i}$ to $p_{j}$ (considering the reliable links that
make up $\mathcal{S}$) that $E_{j}(v)\mathpunct{\downarrow}\land E_{j}(v)\leq
E_{i}(v)+d\delta$. Since $p_{i}$ is the only process at distance $0$ from
$p_{i}$, the result trivially holds for $d=0$. Assume now the result holds for
all processes in $\mathcal{S}$ at a distance $d$ from $p_{i}$ and suppose the
distance from $p_{i}$ to $p_{j}$ is $d+1$. Therefore, there exists a process
$p_{k}\in\mathcal{S}$ such that the distance from $p_{i}$ to $p_{k}$ is $d$
and the distance from $p_{k}$ to $p_{j}$ is $1$. By induction hypothesis
$p_{k}$ enters $v$ no later than $E_{i}(v)+d\delta$. The process $p_{k}$
enters view $v$ upon executing line 4, and by lines 4 and 4,
$p_{k}.\mathsf{views}(E_{k}(v))$ includes more than $\frac{n}{2}$ entries
$\geq v$.

Line 4 guarantees that upon entering $v$, $p_{k}$ sends a ${\tt
WISH}(p_{k}.\mathsf{views}(E_{k}(v)))$ to every process. Since the link
between $p_{k}$ and $p_{j}$ is timely after ${\sf GST}$, the ${\tt WISH}$
message is received by $p_{j}$ at a time $t_{j}\leq E_{i}(v)+(d+1)\delta$.
Upon receipt of the ${\tt WISH}$ message, $p_{j}$ executes lines 4 and 4,
ensuring that $p_{j}.\mathsf{views}(t_{j})\geq
p_{k}.\mathsf{views}(E_{k}(v))$. Therefore, $p_{j}.\mathsf{views}(t_{j})$
includes more than $\frac{n}{2}$ entries $\geq v$, and thus $p_{j}$ is
guaranteed to enter a view $v^{\prime}\geq v$ no later than $t_{j}$. Because
$t_{j}\leq E_{\rm first}^{\mathcal{S}}(v)+\Delta$ and no process can have a
view $>v$ before $E_{\rm first}^{\mathcal{S}}(v)+\Delta$, it follows that
$v^{\prime}=v$. Therefore, $p_{j}$ enters $v$ no later than $t_{j}$ and thus
$E_{j}(v)\leq t_{j}\leq E_{i}(v)+(d+1)\delta$. Thus, all processes in
$\mathcal{S}$ enter $v$ and $E_{\rm last}^{\mathcal{S}}(v)\leq E_{\rm
first}^{\mathcal{S}}(v)+\Delta$.

######  Lemma D.11.

(Bounded Entry) For some $\mathcal{V}$ and $d$, if a process from
$\mathcal{S}$ enters a view $v\geq\mathcal{V}$ and no process from
$\mathcal{S}$ attempts to advance to a higher view within time $d$, then every
process from $\mathcal{S}$ will enter $v$ within $d$:
$\exists\mathcal{V},d.\ \forall v\geq\mathcal{V}.\ E_{\rm
first}^{\mathcal{S}}(v)\mathpunct{\downarrow}\ \land\ \neg(A_{\rm
first}^{\mathcal{S}}(v)<E_{\rm first}^{\mathcal{S}}(v)+d)\implies(\forall
p_{i}\in\mathcal{S}.\ E_{i}(v)\mathpunct{\downarrow})\land(E_{\rm
last}^{\mathcal{S}}(v)\leq E_{\rm first}^{\mathcal{S}}(v)+d)$.

######  Proof D.12.

Let $\mathcal{V}=\max\\{v\ |\ E_{\rm
first}^{\mathcal{S}}(v)\mathpunct{\downarrow}\ \land\ E_{\rm
first}^{\mathcal{S}}(v)<{\sf GST}\\}+1$ so that $\forall v\geq\mathcal{V}.\
E_{\rm first}^{\mathcal{S}}(v)\mathpunct{\downarrow}\ \implies E_{\rm
first}^{\mathcal{S}}(v)\geq{\sf GST}$ and $d={\tt
diameter}(\mathcal{S})\delta$. Then, by Lemma D.9, Bounded Entry holds.

Given arrays $V$ and $V^{\prime}$ we say that $V\leq V^{\prime}$ iff $\forall
i.\ V[i]\leq V^{\prime}[i]$.

######  Lemma D.13.

If a process sends ${\tt WISH}(V)$ before sending ${\tt WISH}(V^{\prime})$,
then $V\leq V^{\prime}$.

######  Proof D.14.

Let $p_{j}\in\mathcal{P}$ and $t$ and $t^{\prime}$ be the times at which a
process $p_{i}$ sends ${\tt WISH}(V)$ and ${\tt WISH}(V^{\prime})$,
respectively. Notice that $V[j]=p_{i}.\mathsf{views}(t)[j]$ and
$V^{\prime}[j]=p_{i}.\mathsf{views}(t^{\prime})[j]$. Since
$p_{i}.\mathsf{views}[j]$ is non-decreasing, as guaranteed by lines 4 and 4,
$p_{i}.\mathsf{view}(t)[j]\leq p_{i}.\mathsf{view}(t^{\prime})[j]$. Therefore,
$V[j]\leq V^{\prime}[j]$. Since $p_{j}$ was picked arbitrarily, $V\leq
V^{\prime}$.

######  Lemma D.15.

For all processes $p_{i}\in\mathcal{S}$, times $t\geq{\sf GST}+\rho$ and
arrays $V$, if $p_{i}$ sends ${\tt WISH}(V)$ at a time $\leq t$, then there
exists an array $V^{\prime}\geq V$ and a time $t^{\prime}$ such that ${\sf
GST}\leq t^{\prime}\leq t$ and $p_{i}$ sends ${\tt WISH}(V^{\prime})$ at
$t^{\prime}$.

######  Proof D.16.

Let $s\leq t$ be the time at which $p_{i}$ sends ${\tt WISH}(V)$. If
$s\geq{\sf GST}$, then choosing $t^{\prime}=s$ and $V^{\prime}=V$ validates
the lemma. Assume now that $s<{\sf GST}$. Since after ${\sf GST}$ the
$p_{i}$’s local clock advances at the same rate as real time, there exists a
time $t^{\prime}$ satisfying ${\sf GST}\leq t^{\prime}\leq t$ such that
$p_{i}$ executes the retransmission code in lines 4 and 4 at $t^{\prime}$.
Then, there exists an array $V^{\prime}$ such that $p_{i}$ sends ${\tt
WISH}(V^{\prime})$ at $t^{\prime}$. By Lemma D.13, $V^{\prime}\geq V$.

######  Lemma D.17.

(Startup) If more than $\frac{n}{2}$ processes from $\mathcal{S}$ invoke
$\mathsf{advance}$, then some process from $\mathcal{S}$ will enter view $1$:
$(\exists P\subseteq\mathcal{S}.\ |P|>\frac{n}{2}\land\ (\forall p_{i}\in P.\
A_{i}(0)\mathpunct{\downarrow}))\implies E_{\rm
first}^{\mathcal{S}}(1)\mathpunct{\downarrow}$.

######  Proof D.18.

Assume by contradiction that there exists a set $P\subseteq\mathcal{S}$ of
more than $\frac{n}{2}$ processes such that $\forall p_{i}\in P.\
A_{i}(0)\mathpunct{\downarrow}$, and no process in $\mathcal{S}$ enters view
$1$. By Lemma D.7, the latter implies

$\forall v>0.\ \forall p_{i}\in\mathcal{S}.\ E_{i}(v)\mathpunct{\uparrow}.$
(1)

We now show that for every $p_{i}\in\mathcal{S}$ and $p_{j}\in P$, there
exists an array $V_{j}$ and a time $t_{j}$ such that $V_{j}[j]\geq 1$ and
$p_{i}$ receives ${\tt WISH}(V_{j})$ at $t_{j}$. Fix $p_{j}\in P$. We prove
the result by induction on the distance $d$ from $p_{j}$ to $p_{i}$
(considering the reliable links that make up $\mathcal{S}$).

Since $A_{j}(0)\mathpunct{\downarrow}$, lines 4 and 4 guarantee that there
exists an array $V_{j}$ and a time $t_{j}$ such that $V_{j}[j]=1$ and $p_{j}$
sends ${\tt WISH}(V_{j})$ at $t_{j}$. Since messages sent to itself are always
delivered and $p_{j}$ is the only process at distance $0$ from $p_{j}$, the
result trivially holds for $d=0$.

Assume now the result holds for all processes at a distance $d$ from $p_{j}$
and suppose that $p_{i}\in\mathcal{S}$ is a process at a distance $d+1$ from
$p_{j}$. Therefore, there exists a process $p_{k}\in\mathcal{S}$ such that the
distance from $p_{j}$ to $p_{k}$ is $d$ and the distance from $p_{k}$ to
$p_{i}$ is $1$. By induction hypothesis there exists an array $V_{j}$ and a
time $t_{j}$ such that $V_{j}[j]\geq 1$ and $p_{k}$ receives ${\tt
WISH}(V_{j})$ at $t_{j}$. Upon receipt of the ${\tt WISH}$ message, $p_{k}$
executes lines 4 and 4, ensuring that $p_{k}.\mathsf{views}(t_{j})[j]\geq
V[j]\geq 1$. Because the periodic handler in line 4 fires every $\rho$ units
of time, there exists an array $V_{k^{\prime}}$ and a time $t_{k^{\prime}}\leq
t_{j}+\rho$ such that $V_{k^{\prime}}[j]\geq 1$ and $p_{k}$ sends ${\tt
WISH}(V_{k^{\prime}})$ at $t_{k^{\prime}}$. Let $T_{k}=\max({\sf
GST}+\rho,t_{k}^{\prime})$. By Lemma D.15, there exists an array $V_{k}\geq
V_{k^{\prime}}$ and a time $t_{k}$ such that ${\sf GST}\leq t_{k}\leq T_{k}$
and $p_{k}$ sends ${\tt WISH}(V_{k})$ at $t_{k}$. Since the link between
$p_{k}$ and $p_{i}$ is timely after ${\sf GST}$, the ${\tt WISH}(V_{k})$ is
received by $p_{i}$ no later than $t_{k}+\delta$. And because $V_{k}\geq
V_{k^{\prime}}$ then $V_{k}[j]\geq V_{k^{\prime}}[j]\geq 1$. This completes
the induction.

Let $p_{l}\in\mathcal{S}$ be any process and, for each $p_{i}\in P$, let
$V_{i}$ and $t_{i}$ be such that $V_{i}[i]\geq 1$ and $p_{l}$ receives ${\tt
WISH}(V_{i})$ at $t_{i}$. Let $T=\max t_{i}$. Lines 4 and 4 guarantee that
$p_{l}.\mathsf{views}(T)[i]\geq 1$ for each $p_{i}\in P$. Since
$|P|>\frac{n}{2}$, $p_{k}.\mathsf{views}(T)$ includes more than $\frac{n}{2}$
entries $\geq 1$, and thus, $p_{l}.v^{\prime}(T)\geq 1$. By (1),
$p_{l}.\mathsf{curr\texttt{\textunderscore}view}(T)=0$. Hence, line 4 ensures
that $p_{l}$ enters a view $\geq 1$ by $T$, contradicting (1).

######  Lemma D.19.

(Progress) If a process from $\mathcal{S}$ enters a view $v$ and, for some set
$P\subseteq\mathcal{S}$ of more than $\frac{n}{2}$ processes, any process in
$P$ that enters $v$ eventually invokes $\mathsf{advance}$, then some process
from $\mathcal{S}$ will enter $v+1$:
$\forall v.\ E_{\rm first}^{\mathcal{S}}(v)\mathpunct{\downarrow}\ \land\
(\exists P\subseteq\mathcal{S}.\ |P|>\frac{n}{2}\ \land\ (\forall p_{i}\in
P.E_{i}(v)\mathpunct{\downarrow}\implies
A_{i}(v)\mathpunct{\downarrow}))\implies E_{\rm
first}^{\mathcal{S}}(v+1)\mathpunct{\downarrow}$

######  Proof D.20.

Assume by contradiction that there exists a set $P\subseteq\mathcal{S}$ of
more than $\frac{n}{2}$ processes such that $\forall p_{i}\in P.\
E_{i}(v)\mathpunct{\downarrow}\ \implies A_{i}(v)\mathpunct{\downarrow}$,
$E_{\rm first}^{\mathcal{S}}(v)\mathpunct{\downarrow}$, and no process in
$\mathcal{S}$ enters view $v+1$. By Lemma D.7, the latter implies

$\forall v^{\prime}>v.\ \forall p_{i}\in\mathcal{S}.\
E_{i}(v^{\prime})\mathpunct{\uparrow}.$ (2)

Let $p_{i}\in\mathcal{S}$ be the first process to enter $v$. We show that
every process $p_{j}\in\mathcal{S}$ enters $v$ by induction on the distance
$d$ from $p_{i}$ to $p_{j}$ (considering the reliable links that make up
$\mathcal{S}$). Since $p_{i}$ is the only process at distance $0$ from
$p_{i}$, the result trivially holds for $d=0$. Assume now the result holds for
all processes in $\mathcal{S}$ at a distance $d$ from $p_{i}$ and suppose the
distance from $p_{i}$ to $p_{j}$ is $d+1$. Therefore, there exists a process
$p_{k}\in\mathcal{S}$ such that the distance from $p_{i}$ to $p_{k}$ is $d$
and the distance from $p_{k}$ to $p_{j}$ is $1$. By induction hypothesis
$p_{k}$ enters $v$. The process $p_{k}$ enters view $v$ upon executing line 4,
and by lines 4 and 4, $p_{k}.\mathsf{views}(E_{k}(v))$ includes more than
$\frac{n}{2}$ entries $\geq v$.

Line 4 guarantees that upon entering $v$, $p_{k}$ sends ${\tt
WISH}(p_{k}.\mathsf{views}(E_{k}(v)))$ to every process. Let $T_{k}=\max({\sf
GST}+\rho,E_{k}(v))$. By Lemma D.15, there exists an array $V_{k}\geq
p_{k}.\mathsf{views}(E_{k}(v))$ and a time $t_{k}$ such that ${\sf GST}\leq
t_{k}\leq T_{k}$ and $p_{k}$ sends ${\tt WISH}(V_{k})$ at $t_{k}$. Since the
link between $p_{k}$ and $p_{j}$ is timely after ${\sf GST}$, the ${\tt WISH}$
message is received by $p_{j}$ at a time $t_{j}$. Upon receipt of the ${\tt
WISH}$ message, $p_{j}$ executes lines 4 and 4, ensuring that
$p_{j}.\mathsf{views}(t_{j})\geq V_{k}\geq p_{k}.\mathsf{views}(E_{k}(v))$.
Therefore, $p_{j}.\mathsf{views}(t_{j})$ includes more than $\frac{n}{2}$
entries $\geq v$, and thus $p_{j}$ is guaranteed to enter a view
$v^{\prime}\geq v$ no later than $t_{j}$. By (2), $p_{j}$ never enters a view
$>v$ and thus $p_{j}$ enters $v$. This completes the induction. Because every
process from $\mathcal{S}$ enters $v$, we have $\forall p_{i}\in P.\
E_{i}(v)\mathpunct{\downarrow}$ and thus $\forall p_{i}\in P.\
A_{i}(v)\mathpunct{\downarrow}$.

We now show that for every $p_{i}\in\mathcal{S}$ and $p_{j}\in P$, there
exists an array $V_{j}$ and a time $t_{j}$ such that $V_{j}[j]\geq v+1$ and
$p_{i}$ receives ${\tt WISH}(V_{j})$ at $t_{j}$. Fix $p_{j}\in P$. We prove
the result by induction on the distance $d$ from $p_{j}$ to $p_{i}$
(considering the reliable links that make up $\mathcal{S}$).

Since $A_{j}(v)\mathpunct{\downarrow}$, lines 4 and 4 guarantee that there
exists an array $V_{j}$ and a time $t_{j}$ such that $V_{j}[j]=v+1$ and
$p_{j}$ sends ${\tt WISH}(V_{j})$ at $t_{j}$. Since messages sent to itself
are always delivered and $p_{j}$ is the only process at distance $0$ from
$p_{j}$, the result trivially holds for $d=0$.

Assume now the result holds for all processes at a distance $d$ from $p_{j}$
and suppose that $p_{i}\in\mathcal{S}$ is a process at a distance $d+1$ from
$p_{j}$. Therefore, there exists a process $p_{k}\in\mathcal{S}$ such that the
distance from $p_{j}$ to $p_{k}$ is $d$ and the distance from $p_{k}$ to
$p_{i}$ is $1$. By induction hypothesis there exists an array $V_{j}$ and a
time $t_{j}$ such that $V_{j}[j]\geq v+1$ and $p_{k}$ receives ${\tt
WISH}(V_{j})$ at $t_{j}$. Upon receipt of the ${\tt WISH}$ message, $p_{k}$
executes lines 4 and 4, ensuring that $p_{k}.\mathsf{views}(t_{j})[j]\geq
V[j]\geq v+1$. Because the periodic handler in line 4 fires every $\rho$ units
of time, there exists an array $V_{k^{\prime}}$ and a time $t_{k^{\prime}}\leq
t_{j}+\rho$ such that $V_{k^{\prime}}[j]\geq v+1$ and $p_{k}$ sends ${\tt
WISH}(V_{k^{\prime}})$ at $t_{k^{\prime}}$. Let $T_{k}=\max({\sf
GST}+\rho,t_{k}^{\prime})$. By Lemma D.15, there exists an array $V_{k}\geq
V_{k^{\prime}}$ and a time $t_{k}$ such that ${\sf GST}\leq t_{k}\leq T_{k}$
and $p_{k}$ sends ${\tt WISH}(V_{k})$ at $t_{k}$. Since the link between
$p_{k}$ and $p_{i}$ is timely after ${\sf GST}$, the ${\tt WISH}(V_{k})$ is
received by $p_{i}$ no later than $t_{k}+\delta$. And because $V_{k}\geq
V_{k^{\prime}}$ then $V_{k}[j]\geq V_{k^{\prime}}[j]\geq v+1$. This completes
the induction.

Let $p_{l}\in\mathcal{S}$ be any process and, for each $p_{i}\in P$, let
$V_{i}$ and $t_{i}$ be such that $V_{i}[i]\geq v+1$ and $p_{l}$ receives ${\tt
WISH}(V_{i})$ at $t_{i}$. Let $T=\max t_{i}$. Lines 4 and 4 guarantee that
$p_{l}.\mathsf{views}(T)[i]\geq v+1$ for each $p_{i}\in P$. Since
$|P|>\frac{n}{2}$, $p_{k}.\mathsf{views}(T)$ includes more than $\frac{n}{2}$
entries $\geq v+1$, and thus, $p_{l}.v^{\prime}(T)\geq v+1$. By (2),
$p_{l}.\mathsf{curr\texttt{\textunderscore}view}(T)\leq v$. Hence, line 4
ensures that $p_{l}$ enters a view $\geq v+1$ by $T$, contradicting (2).

######  Theorem D.21.

Let $\mathcal{F}$ be such that for each $f\in\mathcal{F}$,
${\mathcal{G}}\setminus{f}$ contains a connected core. Then for every
$f\in\mathcal{F}$ with an associated connected core $\mathcal{S}$, every
$f$-compliant execution of the algorithm in Figure 4 over the model
$\mathcal{M}_{{\rm PEF}}$ satisfies the properties in Figure 3.

######  Proof D.22.

The guard at line 4 ensures Monotonicity. Validity, Bounded Entry, Startup and
Progress are given by Lemmas D.5, D.11, D.17 and D.19, respectively.

##  Appendix E Proof of Consensus Liveness

We next prove that the algorithm in Figure 5 validates Theorem 4.12. The proof
of the safety properties of consensus for this algorithm is virtually
identical to that of Paxos [36]. We now prove the more challenging result,
showing that the algorithm is live under the model $\mathcal{M}_{{\rm PEF}}$
(partially synchronous / eventually reliable / flaky). Fix a failure pattern
$f$ and let $\mathcal{S}$ be the corresponding connected core guaranteed to
exist by the assumptions of Theorem 4.12.

We prove liveness by showing that the protocol establishes properties
reminiscent to those of failure detectors [17]. First, similarly to their
completeness property, we prove that every correct process eventually attempts
to advance from a view where no progress is possible (e.g., because the leader
is faulty or has insufficient connectivity). We say that a process $p_{i}$
decides in a view $v$ if it executes line 5 while having $\mathsf{view}=v$.

######  Lemma E.1.

If a correct process $p_{i}$ enters a view $v$, never decides in $v$ and never
enters a view higher than $v$, then $p_{i}$ eventually invokes
$\mathsf{advance}$ in $v$.

######  Proof E.2.

Upon entering $v$ the process $p_{i}$ starts
$\mathsf{decision\texttt{\textunderscore}timer}$ (line 5). The process $p_{i}$
cannot stop the timer at line 5, since together with Monotonicity, this would
imply that $p_{i}$ enters a view higher than $v$. The process $p_{i}$ cannot
stop the timer at line 5 either, since this would imply that $p_{i}$ decides
in $v$. Therefore the timer must expire, after which $p_{i}$ invokes
$\mathsf{advance}$ in $v$ (line 5).

Our next lemma is similar to the eventual accuracy property of failure
detectors. It shows that if the timeout values are high enough, then
eventually any process in $\mathcal{S}$ that enters a view where progress is
possible (the leader is correct and has sufficient connectivity) will never
attempt to advance from it. For a failure pattern $f$ with an associated
connected core $\mathcal{S}$, let $\mathsf{diameter}(\mathcal{S})$ be the
longest distance in the graph ${\mathcal{G}}\setminus{f}$ between two vertices
in $\mathcal{S}$. Also, let $\mathcal{V}$ and $d$ be the view and the time
duration for which Bounded Entry holds, and
$\Delta=(\delta+\rho)\mathsf{diameter}(\mathcal{S})$. Finally, let
$\mathsf{timeout}_{i}(v)$ denote the value of $\mathsf{timeout}$ at the
process $p_{i}$ while in view $v$.

######  Lemma E.3.

Let $v\geq\mathcal{V}$ be a view such that ${\sf leader}(v)\in\mathcal{S}$,
$E_{\rm first}^{\mathcal{S}}(v)\geq{\sf GST}$ and ${\sf leader}(v)$ invokes
$\mathsf{propose}$ no later than $E_{\rm first}^{\mathcal{S}}(v)$. If at each
process $p_{i}\in\mathcal{S}$ that enters $v$ we have
$\mathsf{timeout}_{i}(v)>d+3\Delta$, then no process in $\mathcal{S}$ invokes
$\mathsf{advance}$ in $v$.

Lemma E.3 together with Validity implies that all processes in $\mathcal{S}$
will stay in a view where progress is possible provided the timers are high
enough. However, to apply it we need to argue that, if processes from
$\mathcal{S}$ keep changing views due to lack of progress, all of them will
increase their timeouts high enough to satisfy the bounds in Lemma E.3. To
this end, we prove the following generalization of Lemma E.3: in a
sufficiently high view $v$ with a leader from the connected core, if the
timeout at a process from $\mathcal{S}$ that enters $v$ is high enough, then
this process cannot be the first to initiate a view change. Hence, for the
protocol to enter another view, some other process with a lower timeout must
call $\mathsf{advance}$ and thus increase its duration.

######  Lemma E.4.

Let $v\geq\mathcal{V}$ be a view such that ${\sf leader}(v)\in\mathcal{S}$,
$E_{\rm first}^{\mathcal{S}}(v)\geq{\sf GST}$ and ${\sf leader}(v)$ invokes
$\mathsf{propose}$ no later than $E_{\rm first}^{\mathcal{S}}(v)$. If
$p_{i}\in\mathcal{S}$ enters $v$ and $\mathsf{timeout}_{i}(v)>d+3\Delta$, then
$p_{i}$ is not the first process in $\mathcal{S}$ to invoke $\mathsf{advance}$
in $v$.

The proof of Lemma E.4 relies on the following technical proposition. It
states that the processes from $\mathcal{S}$ exchange their most up to date
information within time $\Delta$, as long as they do not enter a higher view.

######  Proposition E.5.

Let $t\geq{\sf GST}$ be such that no process in $\mathcal{S}$ enters a view
higher than $v$ before $t+\Delta$. Then

  1. 1.

$\forall p_{i},p_{j},p_{k}\in\mathcal{S}.\ p_{i}.\mathsf{M1B}(t)[k].{\it
view}=v{\implies}p_{j}.\mathsf{M1B}(t+\Delta)[k]=p_{i}.\mathsf{M1B}(t)[k]$.

  2. 2.

$\forall p_{i},p_{j}\in\mathcal{S}.\ \forall p_{k}.\
p_{i}.\mathsf{M2A}(t)[k].{\it
view}=v{\implies}p_{j}.\mathsf{M2A}(t+\Delta)[k]=p_{i}.\mathsf{M2A}(t)[k]$.

  3. 3.

$\forall p_{i},p_{j}\in\mathcal{S}.\ \forall p_{k}.\
p_{i}.\mathsf{M2B}(t)[k].{\it
view}=v{\implies}p_{j}.\mathsf{M2B}(t+\Delta)[k]=p_{i}.\mathsf{M2B}(t)[k]$.

Informally, each process propagates its state every $\rho$ units of time (line
5). Upon receipt of the state (line 5), processes update their vectors with
the most up to date information (lines 5, 5 and 5). Because no process from
$\mathcal{S}$ is further than $\mathsf{diameter}(\mathcal{S})$ from $p_{i}$,
its state is guaranteed to be received by every other process in $\mathcal{S}$
no later than $t+\Delta$. And because no process from $\mathcal{S}$ enters a
view higher than $v$ at least until after $t+\Delta$, these values remain
unchanged until then.

######  Proof E.6 (Proof of Proposition E.5).

Let’s consider the case of $\mathsf{M2B}$; the other cases are similar. Fix
$p_{i}\in\mathcal{S}$ and let $t\geq{\sf GST}$ be a time,
$p_{k}\in\mathcal{P}$ and $x$ be a value such that
$p_{i}.\mathsf{M2B}(t)[k]=(v,x)$. Let $p_{j}\in\mathcal{S}$ and
$\mathsf{dist}(p_{i},p_{j})$ be the distance from $p_{i}$ to $p_{j}$ in
${\mathcal{G}}\setminus{f}$. We now show that
$p_{j}.\mathsf{M2B}(t+(\rho+\delta)\mathsf{dist}(p_{i},p_{j}))[k]=(v,x)$. We
prove the result by induction on the distance $d$ from $p_{j}$ to $p_{i}$.
Since $p_{i}$ is the only process at distance $0$ from $p_{i}$, the result
trivially holds for $d=0$. Assume now the result holds for all processes in
$\mathcal{S}$ at distance $d$ from $p_{i}$ and suppose the distance from
$p_{i}$ to $p_{j}$ is $d+1$. Therefore, there exists a process
$p_{m}\in\mathcal{S}$ such that the distance from $p_{i}$ to $p_{m}$ is $d$
and the distance from $p_{m}$ to $p_{j}$ is $1$. By induction hypothesis
$p_{m}.\mathsf{M2B}(t+(\rho+\delta)d)[k]=(v,x)$. Because no process in
$\mathcal{S}$ enters a view higher than $v$ before $t+\Delta$, the value of
$p_{m}.\mathsf{M2B}(t+(\rho+\delta)d)[k]$ remains unchanged from
$t+(\rho+\delta)d$ until $t+\Delta$.

Because the handler at line 5 runs every $\rho$ units of time, there exists a
time $t_{s}$ and a vector $V2B$ such that $t+(\rho+\delta)d\leq t_{s}\leq
t+(\rho+\delta)d+\rho$, $V2B[k]=(v,x)$ and $p_{m}$ sends ${\tt
STATE}(\texttt{\textunderscore},\texttt{\textunderscore},V2B)$ at $t_{s}$
(line 5). Since the link between $p_{m}$ and $p_{j}$ is reliable after ${\sf
GST}$, the ${\tt
STATE}(\texttt{\textunderscore},\texttt{\textunderscore},V2B)$ message is
received by $p_{j}$ at a time $t_{r}$ such that $t_{r}\leq t_{s}+\delta\leq
t+(\rho+\delta)d+\rho+\delta=t+(\rho+\delta)(d+1)$. Thus the process $p_{j}$
executes the handler at line 5 by $t_{r}$.

If $p_{j}.\mathsf{M2B}(t_{r})[k].{\it view}=v$, and since at most one value
can be proposed per view, then $p_{j}.\mathsf{M2B}(t_{r})[k]=(v,x)$. If
$p_{j}.\mathsf{M2B}(t_{r})[k].{\it view}<v$, then $p_{j}$ sets
$p_{j}.\mathsf{M2B}(t_{r})[k]=(v,x)$ (line 5). Because no process in
$\mathcal{S}$ enters a view higher than $v$ before $t+\Delta$ then
$p_{j}.\mathsf{M2B}(t_{r})[k].{\it view}$ cannot be greater than $v$, and also
$p_{j}.\mathsf{M2B}$ remains unchanged from $t_{r}$ until $t+\Delta$.
Therefore, $p_{j}.\mathsf{M2B}(t+(\rho+\delta)(d+1))[k]=(v,x)$.

######  Proof E.7 (Proof of Lemma E.4).

Let $T=E_{\rm first}^{\mathcal{S}}(v)+d+3\Delta$. By contradiction, assume
that $p_{i}$ is the first process in $\mathcal{S}$ to call $\mathsf{advance}$
in $v$. This only occurs if $\mathsf{decision\texttt{\textunderscore}timer}$
expires at $p_{i}$ (line 5). Because $p_{i}$ is the first process to call
$\mathsf{advance}$ in $v$ and $\mathsf{timeout}_{i}(v)>d+3\Delta$, no process
in $\mathcal{S}$ invokes $\mathsf{advance}$ in $v$ until after $T$. Then by
Bounded Entry all processes in $\mathcal{S}$ enter $v$ by $E_{\rm
last}^{\mathcal{S}}(v)\leq E_{\rm first}^{\mathcal{S}}(v)+d$. By Validity no
process can enter $v+1$ until after $T$, and by Lemma D.7, the same holds for
any view $>v$. Thus, all processes in $\mathcal{S}$ stay in $v$ at least until
$T$. We now show that during this time processes in $\mathcal{S}$ exchange the
messages needed for $p_{i}$ to decide and stop the timer, thereby reaching a
contradiction.

Let $p_{l}={\sf leader}(v)$. We first prove that $p_{l}$ proposes a value in
view $v$. Indeed, pick an arbitrary process $p_{j}\in\mathcal{S}$. Upon
entering $v$, $p_{j}$ sets
$\mathsf{M1B}[j]=(v,\texttt{\textunderscore},\texttt{\textunderscore})$ and
$\mathsf{phase}={\tt ENTERED}$ (lines 5 and 5). By Proposition E.5,
$p_{l}.\mathsf{M1B}(E_{j}(v)+\Delta)[j]=p_{j}.\mathsf{M1B}(E_{j}(v))[j]$.
Because no process enters a view $>v$ until after $T$, the value of
$p_{l}.\mathsf{M1B}[j]$ remains unchanged from $E_{j}(v)+\Delta$ until $T$.
Then, since $p_{j}$ was picked arbitrarily, by $E_{\rm
last}^{\mathcal{S}}(v)+\Delta$ the array $p_{l}.\mathsf{M1B}$ contains
$|\mathcal{S}|>\frac{n}{2}$ entries with view $v$. Thus, the precondition at
line 5 is satisfied at $p_{l}$ at a time $t_{pl}$ such that $E_{\rm
first}^{\mathcal{S}}(v)\leq t_{pl}\leq E_{\rm
last}^{\mathcal{S}}(v)+\Delta\leq E_{\rm first}^{\mathcal{S}}(v)+d+\Delta$.
Since $p_{l}$ invokes $\mathsf{propose}$ no later than $E_{\rm
first}^{\mathcal{S}}(v)$,
$p_{l}.\mathsf{my\texttt{\textunderscore}proposal}(t_{pl})\neq\bot$.
Therefore, by $t_{pl}$ the process $p_{l}$ sets $\mathsf{M2A}[l]=(v,x)$ for
some $x$, and $\mathsf{phase}={\tt PROPOSED}$ (lines 5, 5 and 5). Moreover,
the guard at line 5 and line 5 guarantee that the proposed value $x$ is unique
for view $v$.

We next prove that all processes in $\mathcal{S}$ accept the proposal $x$ made
by $p_{l}$ in view $v$. Indeed, pick an arbitrary process
$p_{j}\in\mathcal{S}$. By Proposition E.5,
$p_{j}.\mathsf{M2A}(t_{pl}+\Delta)[l]=p_{l}.\mathsf{M2A}(t_{pl})[l]$. Thus,
the precondition at line 5 is satisfied at $p_{j}$ at a time $t_{aj}$ such
that $t_{aj}\leq t_{pl}+\Delta\leq E_{\rm first}^{\mathcal{S}}(v)+d+2\Delta$.
Therefore, by $t_{aj}$ the process $p_{j}$ sets $\mathsf{M2B}[j]=(v,x)$ and
$\mathsf{phase}={\tt ACCEPTED}$ (lines 5 and 5).

Finally, we prove that $p_{i}$ decides in view $v$. Indeed, pick an arbitrary
process $p_{j}\in\mathcal{S}$. By Proposition E.5,
$p_{i}.\mathsf{M2B}(t_{aj}+\Delta)[j]=p_{j}.\mathsf{M2B}(t_{aj})[j]=(v,x)$.
Because no process enters a view $>v$ until after $T$, the value of
$p_{i}.\mathsf{M2B}[j]$ remains unchanged from $t_{aj}+\Delta$ until $T$.
Then, since $p_{j}$ was picked arbitrarily, by $\max\\{t_{aj}\mid
p_{j}\in\mathcal{S}\\}+\Delta$ the array $p_{i}.\mathsf{M2B}$ contains
$|\mathcal{S}|>\frac{n}{2}$ entries equal to $(v,x)$. Thus, the precondition
at line 5 is satisfied at $p_{i}$ at a time $t_{di}$ such that $t_{di}\leq
E_{\rm first}^{\mathcal{S}}(v)+d+3\Delta=T$. Therefore, by $t_{di}$ the
process $p_{i}$ stops the timer
$\mathsf{decision\texttt{\textunderscore}timer}$ (line 5) before it expires,
which contradicts the fact that
$\mathsf{decision\texttt{\textunderscore}timer}$ expires at $p_{i}$ while in
$v$.

Finally, we prove the liveness of the algorithm in Figure 5, from which
Theorem 4.12 follows.

######  Theorem E.8.

Let $\mathcal{F}$ be such that for all $f\in\mathcal{F}$, the graph
${\mathcal{G}}\setminus{f}$ contains a connected core $\mathcal{S}_{f}$, and
let $\tau:\mathcal{F}\rightarrow 2^{\mathcal{P}}$ be such that $\forall
f\in\mathcal{F}.\ \tau(f)=\mathcal{S}_{f}$. Then the algorithm in Figure 5 is
$(\mathcal{F},\tau)$-wait-free over the model $\mathcal{M}_{{\rm PEF}}$
(partially synchronous / eventually reliable / flaky).

######  Proof E.9.

By contradiction, assume there exists $f\in\mathcal{F}$, $p_{j}\in\tau(f)$ and
an $f$-compliant fair execution of the algorithm in Figure 5 such that $p_{j}$
invokes $\mathsf{propose}$ at a time $t_{pj}$ but that the operation never
returns. Let $\mathcal{S}=\tau(f)$. We first prove that in this case the
protocol keeps moving through views forever.

######  Claim 1.

Every view is entered by some process in $\mathcal{S}$.