Department of Computer Science, Technion,
<EMAIL_ADDRESS>Department of Computer
Science, Technion<EMAIL_ADDRESS>Department of Computer
Science, Technion<EMAIL_ADDRESS>Hagit Attiya, Sweta
Kumari and Noa Schiller [100]Theory of computation Distributed computing
models [100]Theory of computation Concurrent algorithms [100]Computing
methodologies Distributed algorithms

# Optimal Resilience in Systems that Mix
Shared Memory and Message Passing

Hagit Attiya  Sweta Kumari  Noa Schiller

###### Abstract

We investigate the minimal number of failures that can _partition_ a system
where processes communicate both through shared memory and by message passing.
We prove that this number precisely captures the resilience that can be
achieved by algorithms that implement a variety of shared objects, like
registers and atomic snapshots, and solve common tasks, like randomized
consensus, approximate agreement and renaming. This has implications for the
_m &m-model_ of [5] and for the hybrid, cluster-based model of [29, 32].

###### keywords:

fault resilience, m&m model, cluster-based model, randomized consensus,
approximate agreement, renaming, register implementations, atomic snapshots

##  1 Introduction

Some distributed systems combine more than one mode of communication among
processes, allowing them both to send messages among themselves and to access
shared memory. Examples include recent technologies such as _remote direct
memory access_ (_RDMA_) [2, 3, 4], _disaggregated memory_ [31], and _Gen-Z_
[1]. In these technologies, the crash of a process does not prevent access to
its shared memory by other processes. Under these technologies, it is
infeasible to share memory among a large set of processes, so memories are
shared by smaller, strict subsets of processes.

Systems mixing shared memory and message passing offer a major opportunity
since information stored in shared variables remains available even after the
failure of the process who stored it. Mixed systems are expected to withstand
more process failures than pure message-passing systems, as captured by the
_resilience_ of a problem—the maximal number of failures that an algorithm
solving this problem can tolerate. This is particularly the case in an
_asynchronous_ system. At one extreme, when all processes can access the same
shared memory, many problems can be solved even when all processes but one
fail. Such _wait-free_ algorithms exist for implementing shared objects and
solving tasks like randomized consensus, approximate agreement and renaming.
At the other extreme, when processes only communicate by message passing, the
same problems require that at least a majority of processes do not fail [7, 8,
18]. Thus, typically, shared-memory systems are $(n-1)$-resilient, and pure
message-passing systems are $\lfloor{(n-1)/2}\rfloor$-resilient, where $n$ is
the number of processes.

The resilience in systems that mix shared memory and message passing falls in
the intermediate range, between $\lfloor{(n-1)/2}\rfloor$ and $n-1$. It is,
however, challenging to solve specific problems with the best-possible
resilience in a particular system organization: the algorithm has to
coordinate between non-disjoint sets of processes that have access to
different regions of the shared memory. On the other hand, bounding the
resilience requires to take into account the fact that processes might be able
to communicate _indirectly_ through shared memory accesses of third-party
processes.

This paper explores the _optimal_ resilience in systems that provide message-
passing support between all pairs of processes, and access to shared memory
between subsets of processes. We do this by studying the minimal number of
failures that can _partition_ the system, depending on its structure, i.e.,
how processes share memory with each other. We show that the partitioning
number exactly characterizes the resilience, that is, a host of problems can
be solved in the presence of $<f$ crash failures, if and only if $f$ is the
minimal number of failures that partition the system.

A key step is to focus on the implementation of a _single-writer multi-reader
register_ shared among all processes, in the presence of $f$ crash failures. A
read or a write operation takes $O(1)$ round-trips, and requires $O(n)$
messages. Armed with this implementation, well-known shared-memory algorithms
can be employed to implement other shared objects, like _multi-writer multi-
reader registers_ and _atomic snapshots_ , or to solve fundamental problems,
such as _randomized consensus_ , _approximate agreement_ and _renaming_.
Because the register implementation is efficient, these algorithms inherit the
good efficiency of the best-known shared-memory algorithm for each of these
problems.

Going through a register simulation, instead of solving consensus, approximate
agreement or renaming from scratch, does not deteriorate their resilience. One
of our key contributions is to show that the resilience achieved in this way
is optimal, by proving that these problems cannot be solved in the presence of
$f$ crash failures, if $f$ failures can partition the system.

We consider memories with access restrictions and model mixed systems by
stating which processes can read from or write to each memory. (Note that
every pair of processes can communicate using messages.) Based on this
concept, we define $f_{opt}$ to be the largest number of failures that do not
partition the system. We prove that $f$-resilient registers and snapshot
implementations, and $f$-resilient solutions to randomized consensus,
approximate agreement and renaming, exist if and only if $f\leq f_{opt}$.

One example of a mixed model is the _message-and-memory_ model [5], in short,
the _m &m_ model. In the _general_ m&m model [5], the shared-memory
connections are defined by (not necessarily disjoint) subsets of processes,
where each subset of processes share a memory. Most of their results, however,
are for the _uniform_ m&m model, where shared-memory connections can be
induced by an undirected graph, whose vertices are the processes. Each process
has an associated shared memory that can be accessed by all its neighbors in
the _shared-memory graph_ (see Section 5). They present bounds on the
resilience for solving randomized consensus in the uniform model. Their
algorithm is based on Ben-Or’s exponential algorithm for the pure message-
passing model [15]. The algorithm terminates if the nonfaulty processes and
their neighbors (in the shared-memory graph) are a majority of the processes.
They also prove an upper bound on the number of failures a randomized
consensus algorithm can tolerate in the uniform m&m model. We show that in the
uniform m&m model, this bound is equivalent to the partitioning bound
($f_{opt}$) proved in our paper (Theorem 5.12 in Section 5). We further show
that this bound _does not match the resilience of their algorithm_ , whose
resilience is strictly smaller than $f_{opt}$, for some shared-memory graphs.

In the special case where the shared memory _has no access restrictions_ , our
model is dual to the general m&m model, i.e., it captures the same systems as
the general m&m model. However, rather than listing which processes can access
a memory, we consider the flipped view: we consider for each process, the
memories it can access. We believe this makes it easier to obtain some
extensions, for example, for memories with access restrictions.

Hadzilacos, Hu and Toueg [24] present an implementation of a SWMR register in
the general m&m model. The resilience of their algorithm is shown to match the
maximum resilience of an SWMR register implementation in the m&m model. Our
results for register implementations are adaptations of their results. For the
general m&m model specified by the set of process subsets $L$, they define a
parameter $f_{L}$ and show that it is the maximum number of failures tolerated
by an algorithm implementing a SWMR register [24] or solving randomized
consensus [25]. For memories without access restrictions, $f_{L}$ is equal to
$f_{opt}$. Their randomized consensus algorithm is based on the simple
algorithm of [6] and inherits its exponential expected step complexity.

Another example of a model that mixes shared memory and message passing is the
hybrid model of [29, 32]. In this model, which we call _cluster-based_ ,
processes are partitioned into disjoint _clusters_ , each with an associated
shared memory; all processes in the cluster (and only them) can read from and
write to this shared memory. Two randomized consensus algorithms are presented
for the cluster-based model [32]. Their resilience is stated as an operational
property of executions: the algorithm terminates if the clusters of responsive
processes contain a majority of the processes. We prove (Lemma 6.2 in Section
6) that the optimal resilience we state in a closed form for the cluster-based
model is equal to their operational property.

Our model is general and captures all these models within a single framework,
by precisely specifying the shared-memory layout. The tight bounds in this
general model provide the exact resilience of any system that mix shared
memory and message passing.

##  2 Modelling Systems that Mix Shared Memory and Message Passing

We consider $n$ asynchronous processes $p_{1},\dots,p_{n}$, which communicate
with each other by sending and receiving messages, over a complete
communication network of asynchronous reliable links. In addition, there are
$m$ shared memories $M=\\{\mu_{1},...,\mu_{m}\\}$, which can be accessed by
subsets of the processes. A memory $\mu\in M$ has access restrictions, where
$R_{\mu}$ denotes all the processes that can read from the memory and
$W_{\mu}$ denotes all the processes that can write to the memory. The set of
memories a process $p$ can read from is denoted $R_{p}$, i.e.,
$R_{p}=\\{\mu\in{M}:p\in{R_{\mu}}\\}$. The set of memories $p$ can write to is
denoted $W_{p}$, i.e., $W_{p}=\\{\mu\in{M}:p\in{W_{\mu}}\\}$. We assume the
network allows nodes to send the same message to all nodes; message delivery
is FIFO. A process $p$ can _crash_ , in which case it stops taking steps;
messages sent by a crashed process may not be delivered at their recipients.
We assume that the shared memory does not fail, as done in prior work [5, 24,
29, 32].

######  Definition 2.1.

If there is a shared memory $\mu\in{M}$ that $p$ can read from and $q$ can
write to, then we denote $p\rightarrow q$. If $p\rightarrow q$ and
$q\rightarrow p$, then we denote $p\leftrightarrow q$.

Since a process can read what it writes to its local memory, this relation is
_reflexive_ , i.e., for every process $p$, $p\rightarrow p$.

######  Definition 2.2.

Let $P$ and $Q$ be two sets of processes. Denote $P\rightarrow Q$ if some
process $p\in P$ can read what a process $q\in Q$ writes, i.e., $p\rightarrow
q$. If $P\rightarrow Q$ and $Q\rightarrow P$, then we denote $P\leftrightarrow
Q$.

######  Definition 2.3.

A system is _$f$ -partitionable_ if there are two sets of processes $P$ and
$Q$, both of size $n-f$, such that $P\not\leftrightarrow Q$. Namely, the
failure of $f$ processes can partition (disconnect) two sets of $n-f$
processes.
Denote by $f_{opt}$ the largest integer $f$ such that $P\leftrightarrow Q$,
for every pair of sets of processes $P$ and $Q$, each of size $n-f$.

Clearly, a system is $f$-partitionable if and only if $f>f_{opt}$. Note that
$f_{opt}\geq{\lfloor{(n-1)/2}\rfloor}$. In the pure message-passing model,
without shared memory, $p\rightarrow q$ if and only if $p=q$; hence,
$f_{opt}=\lfloor{(n-1)/2}\rfloor$.

The special case of shared memory _without access restrictions_ is when for
every memory $\mu\in M$, $R_{\mu}=W_{\mu}$, and all processes that can read
from a memory can also write to it. In this case, the $\rightarrow$ relation
is _symmetric_ , i.e., for every pair of processes $p$ and $q$, if
$p\rightarrow q$ then $q\rightarrow p$. Therefore, for every two processes $p$
and $q$, $p\leftrightarrow q$. Later, we discuss two models without access
restrictions, the m&m model (Section 5) and the cluster-based model (Section
6).

For a set of processes $P$, $\overset{\rightarrow}{P}$ are the processes that
some process in $P$ can read what they write to the shared memory, i.e.,
$\overset{\rightarrow}{P}=\\{q:\exists{p\in{P}},p\rightarrow q\\}$.

######  Definition 2.4.

$f_{maj}$ is the largest integer $f$ such that for every set $P$ of $n-f$
processes, $|{\overset{\rightarrow}{P}}|>\lfloor{n/2}\rfloor$. That is,
$f_{maj}$ is the largest number of failures that still allows the remaining
(nonfaulty) processes to communicate with a majority of the processes.

######  Lemma 2.5.

$f_{opt}\leq f_{maj}$.

######  Proof 2.6.

Assume, by way of contradiction, that there is set of $n-f_{opt}$ processes,
$P$, such that $|{\overset{\rightarrow}{P}}|\leq{\lfloor{n/2}\rfloor}$. Note
that $f_{opt}\neq{\lfloor{(n-1)/2}\rfloor}$, otherwise
$n-f_{opt}>\lfloor{n/2}\rfloor$ and hence,
$|{\overset{\rightarrow}{P}}|>{\lfloor{n/2}\rfloor}$, which is a
contradiction. Let $Q$ be a set of $n-f_{opt}$ processes not in
$\overset{\rightarrow}{P}$. This set exists since
$n-|\overset{\rightarrow}{P}|\geq\lfloor{n/2}\rfloor$ and
$n-f_{opt}<n-\lfloor{(n-1)/2}\rfloor={\lfloor{n/2}\rfloor}+1$ implies that
$n-f_{opt}\leq{\lfloor{n/2}\rfloor}$. By definition of
$\overset{\rightarrow}{P}$, $P\not\rightarrow Q$, contradicting the definition
of $f_{opt}$.

The converse direction does not necessarily hold, as discussed for the m&m
model and the cluster-based model.

##  3 Implementing a Register in a Mixed System

This section shows that a register can be implemented in the presence of $f$
failures, if and only if the system is not $f$-partitionable, that is, $f\leq
f_{opt}$. A single-writer multi-reader (SWMR) register $R$ can be written by a
single writer process $w$, using a procedure Write, and can be read by all
processes $p_{1},\dots,p_{n}$, using a procedure Read. A register is _atomic_
[30] if any execution of Read and Write operations can be linearized [28].
This means that there is a total order of all completed operations and some
incomplete operations, that respects the real-time order of non-overlapping
operations, in which each Read operation returns the value of the last
preceding Write operation (or the initial value of the register, if there is
no such Write).

###  3.1 Implementing an Atomic Register in a Non-Partitionable System

The algorithm appears in Algorithm 1; for simplicity of presentation, a
process sends each message also to itself and responds with the appropriate
response. This is an adaptation of the register implementation of [24] in the
m&m model.

All the message communication between the processes is done in msg_exchange(),
where a process simply send a message and wait for $n-f$ acknowledgement. This
modular approach allows us to replace the communication pattern according to
the specific shared-memory layout. For example, Section 6 shows that in the
cluster-based model this communication pattern can be changed to wait for less
than $n-f$ processes.

Algorithm 1 Atomic SWMR register implementation ($w$ is the single writer).

1:Local Variables:

2:w-sqno: int, initially 0 $\triangleright$ write sequence number

3:r-sqno: int, initially 0 $\triangleright$ read sequence number

4:last-sqno: int, initially 0 $\triangleright$ last write sequence number
observed

5:counter: int, initially 0 $\triangleright$ number of replies/acks received
so far

6:Shared Variables:

7:for each process $p$ and memory $\mu\in{W_{p}}$:

8: Rμ[p]: $\langle$int, int$\rangle$, initially $\langle 0,v_{0}\rangle$
$\triangleright$ writable by $p$ and readable by all processes that can read
from $\mu$, i.e., all the processes in $R_{\mu}$

9:

1: Write(v) — Code for the writer $w$:

2:w-sqno = w-sqno \+ 1 $\triangleright$ increment the write sequence number

3:acks = msg_exchange$\langle$W, w-sqno, v$\rangle$

4:return

5:

6: Code for any process p:

7:Upon receipt of a $\langle$W/WB, sqno, v$\rangle$ message from process w/q:

8:if (sqno $>$ last-sqno) then

9: last-sqno = sqno

10: for each $\mu\in{W_{p}}$ do $\triangleright$ write value and sequence
number to every register $p$ can write to

11: Rμ[p] = $\langle$sqno, v$\rangle$

12:send $\langle$Ack-W/Ack-WB, sqno$\rangle$ to process w/q

13:

14: Read() — Code for the reader $q$:

15:r-sqno = r-sqno \+ 1 $\triangleright$ increment the read sequence number

16:set_of_tuples = msg_exchange$\langle$R, r-sqno, $\bot$$\rangle$

17:$\langle$seq, val$\rangle$ = max(set_of_tuples) $\triangleright$ maximum
$\langle$seq, val$\rangle$

18:acks = msg_exchange$\langle$WB, seq, val$\rangle$$\triangleright$ write
back

19:return val

20:

21: Code for any process p:

22:Upon receipt of a $\langle$R, r-sqno, -$\rangle$ message from process q:

23:$\langle$w-seq, w-val$\rangle$ = max{$\langle$seq, val$\rangle$ :
$\mu\in{R_{p}\cap{W_{q}}}$ and Rμ[q] = $\langle$seq, val$\rangle$}
$\triangleright$ find val with maximum seq

24:send $\langle$Ack-R, r-sqno, $\langle$w-seq, w-val$\rangle$$\rangle$ to
process q

25:

26: msg_exchange$\langle$m, seq, val$\rangle$: returns set of responses

27:send $\langle$m, seq, val$\rangle$ to all processes

28:responses = $\emptyset$

29:repeat

30: wait to receive a message $m$ of the form $\langle$Ack-m, seq, -$\rangle$

31: counter = counter \+ 1

32: responses = responses $\cup$ {$m$}

33:until counter$\geq n-f$

34:return(responses)

For each process $p$ and memory $\mu\in W_{p}$ there is a shared SWMR register
$R_{\mu}[p]$, writable by $p$ and readable by every process that can read from
$\mu$, i.e., every process in $R_{\mu}$. For simplicity, we assume that each
process $p$ has a shared memory that it can read from and write to, i.e., a
SWMR register that $p$ can both write to and read from. This assumption can be
made since this register can be in the process’s local memory. In Write($v$),
the writer $w$ increments its local write sequence number w-sqno and calls
msg_exchange(). This procedure sends a message of type W with value $v$ and
w-sqno to all processes. On receiving a write message from $w$, $p$ checks if
the write value is more up-to-date than the last value it has observed, by
checking if w-sqno is larger than last-sqno. If so, $p$ updates last-sqno to
be w-sqno and writes the value $v$ and sequence number w-sqno to all the
registers it can write to. When done, the process sends an acknowledgment to
the writer $w$. Once $w$ receives $n-f$ acknowledgments, it returns
successfully.

In Read, a reader process $q$ increments its local read sequence number r-sqno
and calls msg_exchange(). This procedure sends a message of type R and r-sqno
to all processes. On receiving a read message from $q$, a process $p$ reads
all the registers it can read and finds the maximum sequence number and value
stored in them and sends this pair to the reader $q$. Once $q$ receives $n-f$
acknowledgments, it finds the value val with maximum sequence number seq among
the responses (i.e., it selects the most up-to-date value). Then, $q$ calls
msg_exchange(), with message type WB (write back) and value val and seq to
update other readers. On receiving a write back message from $q$, each process
$p$ handles WB like W message, checking if w-sqno is larger than last-sqno and
if so updating last-sqno and all the registers it can write to. When done, the
process sends an acknowledgment to $q$. Once $q$ receives $n-f$
acknowledgments, it returns $val$ successfully.

The communication complexities of read and write operations are dominated by
the cost of a msg_exchange(), invoked once in a write and twice in a read.
This procedure takes one round-trip and $O(n)$ messages, like the algorithm
for the pure message-passing model [7]. The number of shared SWMR registers
depends on the shared-memory topology and is ${\rho=\sum_{\text{process
$p$}}{|W_{p}|}}$, as every process has a single register in each memory it can
write to. The number of accesses to the shared memory is
${\sigma=\sum_{\text{process $p$}}{\sum_{\mu\in R_{p}}{|W_{\mu}|}}}$, as every
process reads all the registers it can read from. Note that $\sigma\leq
n\rho$, since each process reads at most $\rho$ registers. Formally, since
$p\in W_{\mu}\Leftrightarrow\mu\in W_{p}$, $\rho=\sum_{\text{process
$p$}}{|W_{p}|}=\sum_{\mu\in M}{|W_{\mu}|}$. Hence,

$\sigma=\sum_{\text{process $p$}}{\sum_{\mu\in
R_{p}}{|W_{\mu}|}}\leq\sum_{\text{process $p$}}{\sum_{\mu\in
M}{|W_{\mu}|}}=\sum_{\text{process $p$}}{\rho}=n\rho\leavevmode\nobreak\ .$

###  3.2 Correctness of the Algorithm

We argue that Algorithm 1 is correct when the system is not $f$-partitionable.
The only statement that could prevent the completion of a Write or a Read is
waiting for $n-f$ responses (Line 33). Since at most $f$ processes may crash,
the wait statement eventually completes, implying the next lemma.

######  Lemma 3.1.

A Write or Read invoked by a process that does not crash completes.

######  Lemma 3.2.

Let $t_{2}$ be the largest sequence number returned in a read msg_exchange by
reader $p_{j}$, and assume that the msg_exchange starts after the completion
of a write msg_exchange, either by the writer $w$ or in a write back by reader
$p_{i}$, with sequence number $t_{1}$, then, $t_{1}$ $\leq$ $t_{2}$.

######  Proof 3.3.

Let $P$ be the set of processes that respond in the write msg_exchange, and
let $P^{\prime}$ be the set of processes that respond in the read
msg_exchange. By Line 33, $|P|,|P^{\prime}|\geq n-f$. Since the system is not
$f$-partitionable, $P\leftrightarrow P^{\prime}$. Thus, there are processes
$p\in{P}$ and $p^{\prime}\in{P^{\prime}}$ such that $p^{\prime}\rightarrow p$,
and there is a shared memory $\mu\in{W_{p}\cap{R_{p^{\prime}}}}$ that $p$ can
write to and $p^{\prime}$ can read from.

Upon receiving a write message (W or WB) with sequence number $t_{1}$, $p$
compares last-sqno with $t_{1}$ (Line 8). If $t_{1}$ is greater than last-
sqno, then $p$ updates all the registers it can write to. In particular, it
updates $\textit{R}_{\mu}[p]$ with the value associated with sequence number
$t_{1}$ (Line 11), before responding. If $\textit{last-sqno}\geq t_{1}$, by
the update in lines 8-11 and the fact that the shared registers are SWMR
registers, $\textit{R}_{\mu}[p]=\langle\textit{last-sqno},-\rangle$. Hence,
$\textit{R}_{\mu}[p]\geq t_{1}$ when $p$ sends a write response
$\langle\text{Ack-W},t_{1}\rangle$.

Upon receiving a read message from $p_{j}$, $p^{\prime}$ reads all the
registers it can read, including those in $\mu$, and selects the value
associated with the maximum sequence number. In particular, $p^{\prime}$ reads
$\textit{R}_{\mu}[p]$, and since this read happens after $p$ sends the write
response, $p^{\prime}$ reads a value larger than or equal to $t_{1}$. Thus,
$p^{\prime}$ sets $\textit{w-sqno}_{p^{\prime}}$ to a value larger or equal to
$t_{1}$, before sending a read response
$\langle\text{Ack-R},\textit{r-sqno},\langle\textit{w-sqno}_{p^{\prime}},\textit{val}\rangle\rangle$
to $p_{j}$. Since $p_{j}$ picks the value associated with the maximum sequence
number $t_{2}$, it follows that $t_{2}\geq\textit{w-sqno}_{p^{\prime}}\geq
t_{1}$.

We show that the algorithm implements an atomic register, by explicitly
ordering all completed reads and all invoked writes (even if they are
incomplete). Note that values written by the writer $w$ have distinct write
sequence numbers, and are different from the initial value of the register,
denoted $v_{0}$; the value of the $k^{th}$ write operation is denoted $v_{k}$,
$k\geq 1$.

Writes are ordered by the order they are invoked by process $w$; if the last
write is incomplete, we place this write at the end. Since only one process
invokes write, this ordering is well-defined and furthermore, the values
written appear in the order $v_{1},v_{2},\ldots$.

Next, we consider reads in the order they complete; note that this means that
non-overlapping operations are considered in their order in the execution. A
read that returns the value $v_{k-1}$, $k\geq 0$, is placed before the $k$-th
write in the ordering, if this write exists, and at the end of the ordering,
otherwise. For $k=0$, this means that the read is placed before the first
write, which may be at the end of the order, if there is no write.

Lemma 3.2 implies that this order respects the real-time order of non-
overlapping operations. Together with Lemma 3.1, this implies:

######  Theorem 3.4.

If a system is not $f$-partitionable then Algorithm 1 implements an atomic
SWMR register, in the presence of $f$ failures.

###  3.3 Impossibility of Implementing a Register in a Partitionable System

The impossibility proof holds even if only _regular_ register [30] is
implemented. In a regular register, a read should return the value of a Write
operation that either overlaps it, or immediately precedes it. The proof is
similar to the one in [24], where they show that a SWMR register cannot be
implemented in the m&m model if more than $f_{L}$ processes may fail, but it
is adapted to handle access restrictions.

To carry out the impossibility proof (and later one), we need additional
definitions. A _configuration_ $C$ is a tuple with a state for each process, a
value for each shared register, and a set of messages in transit (sent but not
received) between any pair of processes. A _schedule_ is a sequence of process
identifiers. For a set of processes $P$, a schedule is _$P$ -free_ if no
process from $P$ appears in the schedule; a schedule is _$P$ -only_ if only
processes from $P$ appear in the schedule. An _execution_ $\alpha$ is an
alternating sequence of configurations and _events_ , where each event is a
step by a single process that takes the system from the preceding
configuration to the following configuration. In a step, a process either
accesses the shared memory (read or write) or receives and sends messages.
Additionally, a step may involve the invocation of a higher-level operation. A
schedule is associated with the execution in a natural way; this induces
notions of $P$-free and $P$-only executions.

######  Theorem 3.5.

If a system is $f$-partitionable then for at least $n-f$ processes $p$, there
is no implementation of a regular SWMR register with writer $p$ in the
presence of $f$ failures.

######  Proof 3.6.

Assume, by way of contradiction, that there is an implementation of a regular
register $R$ that tolerates $f$ failures. Since the system is
$f$-partitionable, there are two disjoint sets of processes $P$ and
$P^{\prime}$, each of size $n-f$, such that $P^{\prime}\not\rightarrow P$.
This means that there are no two processes $p\in{P}$ and
$p^{\prime}\in{P^{\prime}}$, such that $p^{\prime}$ can read from a memory and
$p$ can write to that same memory. Let $Q$ be the set of nodes not in $P\cup
P^{\prime}$. Since $|P|,|P^{\prime}|=n-f$, it follows that $|P\cup
Q|=|P^{\prime}\cup Q|=f$. Therefore, the implementation terminates in every
execution in which all processes in $P\cup Q$ or in $P^{\prime}\cup Q$ crash,
i.e., in $(P\cup Q)$-free executions and in $(P^{\prime}\cup Q)$-free
executions.

Assume that the writer $w$ is in $P$.

To prove the theorem, we execute a write operation by $w$, followed by a read
operation by some process in $P^{\prime}$, while partitioning them. Namely, we
delay all messages sent from $P$ until the read completes. The processes in
$P^{\prime}$ cannot access any of the shared memories that processes in $P$
write to, implying that the read operation is unaware of the write operation,
violating the register specification. Formally, this is done by constructing
three executions.

The first execution, $\alpha_{1}$, is a $(P^{\prime}\cup Q)$-free execution.
At time $0$, the writer $w$ invokes a Write($v$) operation, $v\neq v_{0}$ (the
initial value of the implemented register). Since at most $f$ processes fail
in the execution $\alpha_{1}$, and the implementation tolerates $f$ failures,
the write must complete at some time $t_{w}^{e}$.

The second execution, $\alpha_{2}$, is a $(P\cup Q)$-free execution. At some
time $t_{r}^{s}>t_{w}^{e}$, a process $q\in P^{\prime}$ invokes a Read
operation. Since at most $f$ processes fail in the execution $\alpha_{2}$, and
the implementation tolerates $f$ failures, the read completes at some time
$t_{r}^{e}$. Since there is no write in $\alpha_{2}$, the read returns
$v_{0}$.

Finally, the third execution $\alpha_{3}$ merges $\alpha_{1}$ and
$\alpha_{2}$. The execution is identical to $\alpha_{1}$ from time 0 to
$t_{w}^{e}$ and to $\alpha_{2}$ from time $t_{r}^{s}$ to $t_{r}^{e}$. All
messages sent from processes in $P$ to processes in $P^{\prime}$ and from
processes in $P^{\prime}$ to processes in $P$ are delivered after time
$t_{r}^{e}$. Processes in $Q$ take no steps in $\alpha_{3}$. Since $q$ does
not receive any messages from a process in $P$, and since processes in
$P^{\prime}$ cannot read what processes in $P$ write to the shared memory, $q$
returns $v_{0}$ as in $\alpha_{2}$, violating the specification of a regular
register. Since the writer can be any process in the set $P$, there are at
least $n-f$ processes for which the theorem holds.

Note that even when the system is $f$-partitionable there could be writers for
which a SWMR register can be implemented. A simple example is when we have
single memory $\mu$, writable by some process $w$ and readable by all
processes. A SWMR register writable by $w$ and readable by all the other
processes can be trivially implemented, regardless of whether the system is
partitionable. However, a SWMR register writable by other processes cannot be
implemented.

If the shared memory is without access restrictions, the $\rightarrow$
relation is symmetric, which implies the next observation:

######  Observation 1.

If a system is $f$-partitionable and the shared memory has no access
restrictions then there is no implementation of a regular SWMR register in the
presence of $f$ failures, for any writer $p$.

Since all the processes can write to a MWMR register, we can show the
following theorem , with the same proof as Theorem 3.5.

######  Theorem 3.7.

If a system is $f$-partitionable then there is no implementation of a regular
MWMR register in the presence of $f$ failures.

##  4 Solving Other Problems in Mixed Systems

###  4.1 Constructing Other Read/Write Registers

The atomic SWMR register presented in the previous section can be used as a
basic building block for implementing other shared-memory objects. Recall that
if a system is not $f$-partitionable (i.e., $f\leq f_{opt}$), a SWMR register
can be implemented so that each operation takes $O(1)$ time, $O(n)$ messages,
$O(\rho)$ SWMR shared-memory registers and $O(\sigma)$ SWMR shared-memory
accesses. Given a shared-memory algorithm that uses $O(r)$ SWMR registers and
has $O(s)$ step complexity, it can be simulated with $O(s)$ round-trips,
$O(ns)$ messages, and $O(\sigma s)$ shared-memory accesses. The simulation
requires $O(\rho r)$ SWMR shared-memory registers. (Recall that
$\rho=\sum_{\text{process $p$}}|W_{p}|$ and $\sigma=\sum_{\text{process
$p$}}{\sum_{\mu\in R_{p}}{|W_{\mu}|}}$.)

An atomic _multi-writer multi-reader_ (MWMR) register can be built from atomic
SWMR registers [34]; each read or write requires $O(n)$ round-trips,
$O(n^{2})$ messages, $O(\rho n)$ SWMR shared registers and $O(\alpha n)$
shared-memory accesses.

Atomic snapshots can also be implemented using SWMR registers [13]; each scan
or update takes $O(n\log n)$ round-trips, $O(n^{2}\log n)$ messages, $O(\rho
n)$ SWMR shared registers and $O(\sigma n\log n)$ shared-memory accesses.

###  4.2 Batching

A simple optimization is _batching_ of read requests, namely reading the
registers of several processes simultaneously. Batching is useful when each
process replicates a register for each other process—not for just one writer.
A process $p$ writes the value $v$ using Writep($v$). In Collect(), a process
$p$ sends read requests for all these registers together instead of sending
$n$ separate read requests (for the registers of all processes), one after the
other. When a process $q$ receives the batched request from $p$, it replies
with a vector containing the values of all registers in a single message,
rather than sending them separately. Process $p$ waits for vectors from $n-f$
processes, and picks from them the latest value for each other process.
Finally, the reader does a write-back of this vector. An invocation of
Collect() returns a vector $V$ with $n$ components, one for each process. Each
component contains a pair of a value with a sequence number. For every process
$p_{i}$, $V[i]$ is the entry in the vector corresponding to $p_{i}$’s value. A
vector $V_{1}$ _precedes_ a vector $V_{2}$ if the sequence number of each
component of $V_{1}$ is smaller than or equal to the corresponding component
of $V_{2}$. Pseudocode for the algorithm appears in Algorithm 2.

Algorithm 2 Batching, code for process $p$.

1:Local Variables:

2:w-sqno: int, initially 0 $\triangleright$ write sequence number

3:r-sqno: int, initially 0 $\triangleright$ read sequence number

4:val: vector of size $n$, with all entries initially $0$

5:for each $i\in[n]$:

6: last-sqno[$i$]: int, initially 0 $\triangleright$ last write sequence
number observed

7:Shared Variables:

8:for each process $p$, memory $\mu\in{W_{p}}$ and $i\in[n]$:

9: Rμ[p][$i$]: $\langle$int, int$\rangle$, initially $\langle 0,v_{0}\rangle$
$\triangleright$ writable by $p$ and readable by all processes that can read
from $\mu$, i.e., all the processes in $R_{\mu}$

10:

1: writei(sqno, v): $\triangleright$ helper function that writes the value of
process $p_{i}$ to the shared memory

2:if (sqno $>$ last-sqno[$i$]) then

3: last-sqno[$i$] = sqno

4: for each $\mu\in{W_{p}}$ do $\triangleright$ write value and sequence
number to every register $p$ can write to

5: Rμ[p][$i$] = $\langle$sqno, v$\rangle$

6:

7: Writep(v):

8:w-sqno = w-sqno \+ 1 $\triangleright$ increment the write sequence number

9:acks = msg_exchange$\langle$W, w-sqno, v$\rangle$

10:return

11:

12:Upon receipt of a $\langle$W, sqno, v$\rangle$ message from process pi:

13:writei(sqno, v)

14:send $\langle$Ack-W, sqno$\rangle$ to process pi

15:

16: Collect():

17:r-sqno = r-sqno \+ 1 $\triangleright$ increment the read sequence number

18:set_of_tuples = msg_exchange$\langle$R, r-sqno, $\bot$$\rangle$

19:for each $i\in[n]$ do

20: set_of_tuplesi = set_of_tuples[$i$] $\triangleright$ all the tuples
received for process $p_{i}$

21: $\langle$seqi, vali$\rangle$ = max(set_of_tuplesi) $\triangleright$
maximum $\langle$seq, val$\rangle$ recieved for process $p_{i}$

22: val[$i$] = $\langle$seqi, vali$\rangle$

23:acks = msg_exchange$\langle$WB, r-sqno, val$\rangle$$\triangleright$ write
back

24:return val

25:

26:Upon receipt of a $\langle$R, r-sqno, -$\rangle$ message from process q:

27:for each $i\in[n]$ do

28: $\langle$w-seqi, w-vali$\rangle$ = max{$\langle$w-seq, w-val$\rangle$ :
$\mu\in{R_{p}\cap{W_{q}}}$ and Rμ[q][$i$] = $\langle$w-seq, w-val$\rangle$}

29: val[$i$] = $\langle$w-seqi, w-vali$\rangle$

30:send $\langle$Ack-R, r-sqno, val$\rangle$ to process q

31:

32:Upon receipt of a $\langle$WB, sqno, val$\rangle$ message from process q:

33:for each $i\in[n]$ do

34: $\langle$seq, v$\rangle$ = val[$i$]

35: writei(seq, v)

36:send $\langle$Ack-WB, sqno$\rangle$ to process q

Batching provides a _regular collect_ [11], as stated in the next lemmas,
which we bring without proof, as they are similar to the SWMR register
correctness proofs (Section 3.2).

######  Lemma 4.1.

Let $t_{2}$ be the largest sequence number returned in a read msg_exchange for
the value of process $p_{i}$ in a Collect operation by reader $r$, and assume
that the msg_exchange starts after the completion of a write msg_exchange in a
Write${}_{p_{i}}$ operation by process $p_{i}$ with sequence number $t_{1}$,
then, $t_{1}$ $\leq$ $t_{2}$.

######  Lemma 4.2.

For every $1\leq i\leq n$, let $t_{i}$ be the largest sequence number returned
in a read msg_exchange for the value of process $p_{i}$ in a Collect operation
by reader $r$, and assume that the msg_exchange starts after the completion of
a write back msg_exchange writing the value val, then seqi $\leq$ $t_{i}$,
where $\langle$seqi, -$\rangle$ = val[$i$].

######  Lemma 4.3.

Let V1 be a vector returned by a Collect operation $c_{1}$, and let V2 be a
vector returned by a Collect operation $c_{2}$, such that $c_{1}$ returns
before the invocation of $c_{2}$, then $V_{1}$ precedes $V_{2}$.

Batching reduces the number of round-trips and messages, and shared-memory
registers and accesses, but increases the size of messages and registers. With
batching, an operation on a MWMR register requires $O(1)$ round-trips, $O(n)$
messages, $O(\rho)$ SWMR shared registers and $O(\alpha)$ shared-memory
accesses, when each process saves all the writers values in a single SWMR
register. Batching can also be applied to atomic snapshots, so that each scan
or update takes $O(\log n)$ round-trips, $O(n\log n)$ messages, $O(\rho)$ SWMR
shared registers and $O(\sigma\log n)$ shared-memory accesses. These results
are summarized in Table 1.

| time | no. messages | no. registers | shared-memory accesses
---|---|---|---|---
SWMR atomic register | $O(1)$ | $O(n)$ | $O(\rho)$ | $O(\sigma)$
MWMR atomic register [34] | $O(1)$ | $O(n)$ | $O(\rho)$ | $O(\sigma)$
atomic snapshot [13] | $O(\log n)$ | $O(n\log n)$ | $O(\rho)$ | $O(\sigma\log n)$
Table 1: Complexity bounds for simulated data structures (with batching) in
non-partitionable systems

Regular collects can be used in the following building block, where a process
repeatedly call collect, and returns a vector of values if it has received it
_twice_ (in two consecutive collects). Two vectors are the same if they
contain the same sequence numbers in each component. Process $p$ can write the
value $v$ using procedure Writep($v$), and repeatedly double collect all the
processes current values using the procedure SDC(). An invocation of SDC()
returns a vector $V$ with $n$ components, one for each process. Each component
contains a pair of a value with a sequence number. Pseudocode for this
procedure appears in Algorithm 3.

Algorithm 3 Building block implementation, code for process $p$.

1: SDC():

2:V1 = Collect()

3:while true do

4: V2 = V1; V1 = Collect()

5: if V1 = V2 then

6: return V1

The next lemma is easy to prove if writes are atomic, but it holds even
without this assumption.

######  Lemma 4.4.

If $V_{1}$ and $V_{2}$ are vectors returned by two pairs of successful double
collects by processes $p_{i_{1}}$ and $p_{i_{2}}$, respectively, then either
$V_{1}$ precedes $V_{2}$ or $V_{2}$ precedes $V_{1}$.

######  Proof 4.5.

Note that either the first collect of $p_{i_{1}}$ completes before the second
collect of $p_{i_{2}}$ starts or the first collect of $p_{i_{2}}$ completes
before the second collect of $p_{i_{1}}$ starts. We consider the first case,
as the second one is symmetric. Consider the sequence numbers $s_{1}$ and
$s_{2}$ in $V_{1}[j]$ and $V_{2}[j]$, for any process $p_{j}$. Since the first
collect of $p_{i_{1}}$ completes before the second collect of $p_{i_{2}}$
starts, the regularity of collect ensures that $s_{1}\leq s_{2}$.

This building block may not terminate (even if the system is not
$f$-partitionable), due to continuous writes. However, if two consecutive
collects are not equal then some sequence number was incremented, i.e., a
write by some process is in progress.

###  4.3 Approximate Agreement

In the _approximate agreement_ problem with parameter $\epsilon>0$, all
processes start with a real-valued input and must decide on an output value,
so any two decision values are in distance at most $\epsilon$ from each other
(_agreement_), and any decision value is in the range of all initial values
(_validity_).

There is a wait-free algorithm for the approximate agreement problem in the
shared-memory model, which uses only SWMR registers [12]. This algorithm can
be simulated if the system is not $f$-partitionable, and at most $f$ processes
fail. Similarly to randomized consensus, it can be shown that this problem is
unsolvable in partitionable systems.

######  Theorem 4.6.

If a system is $f$-partitionable then approximate agreement is unsolvable in
the presence of $f$ failures.

######  Proof 4.7.

Assume, by way of contradiction, that there is an approximate agreement
algorithm. Since the system is $f$-partitionable, there are two disjoint sets
of processes $P$ and $P^{\prime}$, each of size $n-f$, such that
$P\not\leftrightarrow P^{\prime}$. Assume, without loss of generality, that
$P^{\prime}\not\rightarrow P$. This means that any process in ${P^{\prime}}$
cannot read memories that processes in $P$ can write to. Let $Q$ be the
processes not in $P\cup P^{\prime}$. Since $|P|,|P^{\prime}|=n-f$, it follows
that $|P\cup Q|=|P^{\prime}\cup Q|=f$.

To prove the theorem, we construct three executions.

The first execution, $\alpha_{1}$, is a $(P^{\prime}\cup Q)$-free execution,
in which all processes in $P$ have initial value $0$. Since at most $f$
processes fail in the execution and the implementation can tolerate $f$
failures, all processes in $P$ must eventually terminate by some time $t_{1}$.
By validity, every process in $P$ decides $0$.

The second execution, $\alpha_{2}$, is a $(P\cup Q)$-free execution, in which
all processes in $P^{\prime}$ have initial value $2\epsilon$. Since at most
$f$ processes fail in the execution and the implementation can tolerate $f$
failures, all processes in $P^{\prime}$ must eventually terminate by some time
$t_{2}$. By validity, every process in $P$ decides $2\epsilon$.

The third and final execution, $\alpha_{3}$, combines $\alpha_{1}$ and
$\alpha_{2}$. The initial value of processes in $P$ is $0$, and the initial
value of processes in $P^{\prime}$ is $2\epsilon$. Processes in $Q$ have
arbitrary initial values, and they take no steps in $\alpha_{3}$. The
execution is identical to $\alpha_{1}$ from time $0$ until time $t_{1}$, and
to $\alpha_{2}$ from this time until time $t_{1}+t_{2}$. All messages sent
between processes in $P$ and processes in $P^{\prime}$ are delivered after
time $t_{1}+t_{2}$.

Since processes in $P^{\prime}$ do not take steps in $\alpha_{3}$ until time
$t_{1}$, all processes in $P$ decides $0$ until this time, as in execution
$\alpha_{1}$. Processes in $P^{\prime}$ cannot communicate with processes in
$P$, either by messages or read what they wrote to the shared memory,
therefore all processes in $P^{\prime}$ decides $2\epsilon$, as in execution
$\alpha_{2}$. Since $|0-2\epsilon|>\epsilon$, this violates the agreement
property.

###  4.4 Renaming

In the _$M$ -renaming_ problem, processes start with unique _original_ names
from a large namespace $\\{1,...,N\\}$, and the processes pick distinct _new_
names from a smaller namespace $\\{1,...,M\\}$ ($M<N$). To avoid a trivial
solution, in which a process $p_{i}$ picks its index $i$ as the new name, we
require _anonymity_ : a process $p_{i}$ with original name $m$ performs the
same as process $p_{j}$ with original name $m$.

Employing the SWMR register simulation in a $(2n-1)$-renaming algorithm [10]
yields an algorithm that requires $O(n\log n)$ round-trips, $O(n^{2}\log n)$
messages, $O(\rho n^{4})$ shared registers and $O(\sigma n\log n)$ shared-
memory accesses. The number of registers can be reduced to $O(\rho)$, at the
cost of increasing their size.

This algorithm assumes that the system is not $f$-partitionable and at most
$f$ processes fail. The next theorem shows that this is a necessary condition.

######  Theorem 4.8.

If a system is $f$-partitionable then renaming is unsolvable in the presence
of $f$ failures.

######  Proof 4.9.

Assume, by way of contradiction, that there is a renaming algorithm. Since the
system is $f$-partitionable, there are two disjoint sets of processes $P$ and
$P^{\prime}$, each of size $n-f$, such that $P^{\prime}\not\rightarrow P$.
Denote $P=\\{p_{i_{1}},...,p_{i_{n-f}}\\}$ and
$P^{\prime}=\\{p^{\prime}_{i_{1}},...,p^{\prime}_{i_{n-f}}\\}$. Let $Q$ be the
set of processes not in $P\cup P^{\prime}$. Since $|P|,|P^{\prime}|=n-f$, we
have that $|P\cup Q|=|P^{\prime}\cup Q|=f$.

Given a vector $I$ of $n-f$ original names, denote by $\alpha(I,P)$ the
$P$-only execution in which processes in $P$ have original names $I$:
processes in ($P^{\prime}\cup Q$) crash and take no step, and processes in $P$
are scheduled in round-robin. Since at most $f$ processes fail in
$\alpha(I,P)$, eventually all processes in $P$ pick distinct new names, say by
time $t(I)$. Note that by anonymity, the same names are picked in the
execution $\alpha(I,P^{\prime})$, in which $p^{\prime}_{i_{j}}$ starts with
the same original name as $p_{i_{j}}$ and takes analogous steps.

Consider $\alpha(I_{i},P)$, for any possible set of original names. The
original name space can be picked to be big enough to ensure that for two
_disjoint_ name assignments, $I_{1}$ and $I_{2}$, some process $p_{i_{j}}\in
P$ decides the same new name $r$ in the executions $\alpha(I_{1},P)$ and
$\alpha(I_{2},P)$.

Denote $\alpha_{1}=\alpha(I_{1},P)$ and $\alpha_{2}=\alpha(I_{2},P^{\prime})$,
namely, the execution in which processes in $P^{\prime}$ replace the
corresponding processes from $P$. The anonymity assumption ensures that
$p_{i_{j}}^{\prime}$ decides on $r$, just as $p_{i_{j}}$ decides on $r$ in
$\alpha(I_{1},P)$ and $\alpha(I_{2},P)$.

The execution $\alpha_{3}$ combines $\alpha_{1}$ and $\alpha_{2}$, as follows.
Processes in $Q$ take no steps in $\alpha_{3}$. The original names of
processes in $P$ are $I_{1}$, and original names of processes in $P^{\prime}$
are $I_{2}$. The execution is identical to $\alpha_{1}$ from time 0 until time
$t(I_{1})$, and to $\alpha_{2}$ from this time until time $t(I_{1})+t(I_{2})$.
All messages sent from processes in $P$ to processes in $P^{\prime}$ and from
processes in $P^{\prime}$ to processes in $P$ are delivered after time
$t(I_{1})+t(I_{2})$.

In $\alpha_{3}$, processes in $P$ do not receive messages from processes in
$P^{\prime}\cup Q$. Furthermore, $P^{\prime}\not\rightarrow P$; i.e.,
processes in $P^{\prime}$ cannot read what processes in $P$ wrote to the
shared memory. Hence, $\alpha_{3}$ is indistinguishable to $p_{i_{j}}$ from
$\alpha_{1}$, and hence, it picks new name $r$. Similarly, $\alpha_{3}$ is
indistinguishable to $p^{\prime}_{i_{j}}$ from $\alpha_{2}$, and hence, it
also picks new name $r$, which contradicts the uniqueness of new names.

###  4.5 Consensus

In the _consensus_ problem, a process starts with an input value and decides
on an output value, so that all processes decide on the same value
(_agreement_), which is the input value of some process (_validity_).

With a standard _termination_ requirement, it is well known that consensus
cannot be solved in an asynchronous system [22]. This result holds whether
processes communicate through shared memory or by message passing, and even if
only a single process fails. However, consensus can be solved if the
termination condition is weakened, either to be required only with high
probability (_randomized consensus_), or to hold when it is possible to
eventually detect failures (using a _failure detector_), or to happen only
under fortunate situations.

There are numerous shared-memory randomized consensus algorithms, which rely
on read / write registers, or objects constructed out of them. Using these
algorithms together with linearizable register implementations is not obvious
since linearizability does not preserve _hyperproperties_ [23, 9]. It has been
shown [25] that the ABD register implementation [7] is not _strongly
linearizable_ [23]. This extends to the mixed-model register implementations,
as ABD is a special case of them.

Hadzilacos et al. [26] have proved that the simple randomized consensus
algorithm of [6] works correctly with _regular_ registers, and used it to
obtain consensus in m&m systems [25]. Their algorithm inherits exponential
complexity from the simple algorithm of [6], which employs independent coin
flips by the processes.

A _weak shared coin_ ensures that, for every value $v\in\\{-1,1\\}$, all
processes obtain the value $v$ with probability $\delta>0$; $\delta$ is called
the _agreement parameter_ of the coin. Using a weak shared coin with a
constant agreement parameter in the algorithm of [6], yields an algorithm with
constant number of rounds. Thus, randomized consensus inherits the complexity
of the weak shared coin.

Here, we explain how to use SDC() to emulate the weak shared coin of [6],
following [14]. This holds when there are at most $f$ failures, if the system
is not $f$-partitionable.

Algorithm 4 Weak shared coin, based on [6]

1:Local Variables:

2:my-counter: int, initially 0

3:$V$: vector of size $n$, with all entries initially $0$

4:

1: Coin() — Code for process $p$:

2:while true do

3: my-counter = my-counter \+ flip()

4: Writep(my-counter)

5: $V$ = SDC()

6: if $\text{sum}(V)\geq c\cdot n$ then return 1

7: else if $\text{sum}(V)\leq-c\cdot n$ then return -1

In Algorithm 4, a process flips a coin using a local function flip(), which
returns the value 1 or -1, each with probably 1/2. Invoking flip() is a single
atomic step. After each flip, a process writes its outcome in an individual
cumulative sum. Then it calls SDC() to obtain a vector $V$ with the individual
cumulative sums of all processes. (We assume that the initial value in each
component is $0$.) The process then checks the absolute value of the total sum
of the individual cumulative sums, denoted sum($V$). If it is at least $c\cdot
n$ for some constant $c>1$, then the process returns its sign.

Intuitively, the only way the adversary can create disagreement on the outcome
of the shared coin is by preventing as many processors as possible to move the
counter in the unwanted direction. We will show that the adversary cannot
“hide” more than $n-1$ coin flips. (This was originally proved when processes
use atomic writes [6]; here, we show it holds even when writes are not
atomic.) Therefore, after the cumulative sum is big or small enough the
adversary can no longer affect the outcome of the shared coin, and cannot
prevent the processes from terminating.

Fix an execution $\alpha$ of the weak shared coin. Let $H$ and $T$ be the
number of 1 and -1 (respectively) flipped by all processes after some prefix
of the execution. These numbers are well-defined since the local coin flips
are atomic.

######  Lemma 4.10.

If $H-T<-(c+1)\cdot n$ (respectively, $H-T>(c+1)\cdot n$) after some prefix
$\alpha^{\prime}$ of the execution, then a process that invokes SDC() in
$\alpha^{\prime}$ and completes it, returns $-1$ (respectively, 1) from
Coin().

######  Proof 4.11.

We consider the first case; the other case is symmetric. Assume
$H-T<-(c+1)\cdot n$ after an execution prefix $\alpha^{\prime}$. Consider the
processes invoking SDC() after $\alpha^{\prime}$, in the order their SDC()
return. Let $p_{j_{i}}$, $i\geq 1$, be the $i$th process in this order, and
let $V_{i}$ be the vector returned by its SDC(). We prove, by induction on
$i$, that $\text{sum}(V_{i})\leq-c\cdot n$, and hence, $p_{j_{i}}$ returns
$-1$. (See Figure 1.)

In the base case, $i=1$. Since a process invokes SDC() after every write,
there can be at most $n$ writes by all processes after $\alpha^{\prime}$ and
before the return of SDC() by $p_{j_{1}}$. These writes can be of flips tossed
in $\alpha^{\prime}$, or flips tossed after $\alpha^{\prime}$. The value
$p_{j_{1}}$ returns in $V_{1}[k]$ can be different than the local value of my-
counter at $p_{k}$ after $\alpha^{\prime}$ in one of two cases:

  1. 1.

If $p_{k}$ tossed a coin in $\alpha^{\prime}$, and the write of this coin does
not complete before SDC() by $p_{j_{1}}$ returned and $V_{1}$ does not contain
this value.

  2. 2.

If $p$ tossed a coin after $\alpha^{\prime}$, and $V_{1}$ contains this value.
Hence, the write of this coin has started before SDC() by $p_{j_{1}}$ returns.

Since there is at most one write by process $p_{k}$ after $\alpha^{\prime}$
until the SDC() by $p_{j_{1}}$ returns, the regularity of collect implies that
$p_{j_{1}}$ reads a value different by at most 1 from the value of $p_{k}$’s
counter after $\alpha^{\prime}$. Therefore, $p_{j_{1}}$ reads a value bigger
by at most $n$ from the value of $H-T$ after $\alpha^{\prime}$ and
$\text{sum}(V_{1})<-c\cdot n$, thus $p_{j_{1}}$ decides -1 in Line 7.

Inductive step: Assume that for $i>1$, processes $p_{j_{1}},...,p_{j_{i-1}}$
decide after their SDC() invocation returns. These processes have at most one
write after $\alpha^{\prime}$ and before they invoke SDC(). By the induction
hypothesis, they return from Coin() after their SDC() invocation returns.
Therefore, these process have no additional writes after $\alpha^{\prime}$.
For any other process $p_{k}$, there is at most one write after
$\alpha^{\prime}$ until the SDC() by $p_{j_{i}}$ returns, since there must be
a SDC() operation by $p_{k}$ between any two writes by this process.
Therefore, there are at most $n$ writes after $\alpha^{\prime}$ until
$p_{j_{i}}$ returns from SDC(). It follows that $p_{j_{i}}$ reads at most $n$
additional values from $H-T$ and returns $-1$ from Coin().

$\beta^{\prime}$${\displaystyle\boldsymbol{H-T>(c-1)\cdot n}}$$p_{j_{1}}\
\text{incovation returns}$$p_{j_{i}}\ \text{incovation returns}$$...$ each
process can have at most one write $p_{j_{1}}\ \text{decides and stops
writing}$$p_{j_{i}}\ \text{decides and stops writing}$$p_{j_{i}}\ \text{can
have at most one write}$each process can have at most one write

Figure 1: Illustration of Lemma 4.10

######  Lemma 4.12.

If process $p$ returns 1 (respectively, -1) from the shared coin, then
$H-T>(c-1)\cdot n$ (respectively, $H-T<-(c-1)\cdot n$) at some point during
its last call to SDC().

######  Proof 4.13.

We consider the first case; the other case is symmetric. Consider the last
pair of collects in the last SDC() invocation before process $p$ returns, and
assume they return a vector $V$. Assume $p$ misses a write by some process
$p_{k}$ that overlaps the first collect, i.e., the sequence number of this
write is smaller than the corresponding sequence number in $V$. Then $p_{k}$’s
write overlaps $p$’s first collect, and it returns after the second collect
starts. (Otherwise, the regularity of collect implies that the second collect
returns this write by $p_{k}$, or a later one, contradicting the fact it is
equal to the first collect.) Therefore, each process has at most one write
that overlaps the first collect and is missed by the first collect.

$V[k]$ is different from the local value of my-counter at $p_{k}$ when the
first collect completes, if either $p_{k}$ did not start a write for a tossed
coin or a write by $p_{k}$ is pending at this point. In the first case, $p$
reads all $p_{k}$’s previous writes. In the second case, $p$ reads all
previous writes by $p_{k}$, except maybe the pending write. Thus, from the
regularity of collect, the value of $p_{k}$ read by $p$ differs by at most 1
from its value when the first collect of $p$ completes. Therefore, the sum of
$V$ differs by at most $n-1$ values from the value of $H-T$ when the first
collect completes. Since $p$ returns 1, $\text{sum}(V)\geq c\cdot n$, and
hence, $H-T>(c-1)\cdot n$ when the first collect of $p$ completes.

######  Lemma 4.14.

The agreement parameter of the weak shared coin algorithm is $(c-1)/2c$.

######  Proof 4.15.

We show that with probability $(c-1)/2c$ all the processes decide -1; the
proof for 1 is analogous. Lemma 4.12 implies that $H-T$ reaches $(c-1)\cdot n$
before a process decides 1. By Lemma 4.10, after $H-T$ drops below
$-(c+1)\cdot n$ there are at most $n$ more SDC() invocations in the execution.
Therefore, there are at most $n$ more writes in the rest of the execution.
After every coin flip there is a write by the process tossing the coin. As
there are at most $n$ additional writes, there are also at most $n$ more coin
flips in the rest of the execution. Thus, $H-T<-c\cdot n<(c-1)\cdot n$ until
the end of the execution. It follows that no process can decide 1 if $H-T$
drops below $-(c+1)\cdot n$ before reaching $(c-1)\cdot n$. In addition, all
processes eventually decide -1, since otherwise, a process that has not
decided earlier invokes a SDC() operation.

In the worst case, the adversary can make some undecided process decide 1 if
$H-T$ reaches $(c-1)\cdot n$. Viewing the value of $H-T$ as a random walk
[20], starting at the origin with the absorbing barriers at $-(c+1)\cdot n$
(all decide -1) and at $(c-1)\cdot n$ (some may decide 1). By a classical
result of random walk theory, the probability of reaching $-(c+1)\cdot n$
before $(c-1)\cdot n$ is

$\frac{(c-1)\cdot n}{(c+1)\cdot n+(c-1)\cdot n}=\frac{(c-1)\cdot
n}{2cn}=\frac{c-1}{2c}.$

The next theorem can be proved along similar lines to [6].

######  Theorem 4.16.

For a constant $c>1$, the expected number of coin flips in an execution of the
weak shared coin is $O(n^{2})$.

Since the expected number of coin flips is $O(n^{2})$, the expected number of
write and building block invocations is also $O(n^{2})$. The total number of
collect operations in these building block invocations for all the processes
is $O(n^{3})$ in expectation. This is because a double collect fails only when
another coin is written, and thus each write can cause at most $n-1$ double
collects to fail. Therefore, there are at most $O(n^{3})$ failed double
collects and $O(n^{2})$ successful double collects, all part of $O(n^{2})$
building block invocations by all the processes. Therefore, the weak shared
coin requires $O(n^{3})$ round-trips, $O(n^{4})$ messages and $O(\sigma
n^{3})$ shared-memory accesses in expectation and uses $O(\rho)$ registers.
Plugging the weak shared coin in the overall algorithm of [6], proved to be
correct by [26], yields a randomized consensus algorithm with the same
expected complexities as the weak shared coin.

######  Theorem 4.17.

Randomized consensus can be solved in the presence of $f$ failures if the
system in not $f$-partitionable. The algorithm takes $O(n^{3})$ round-trips,
$O(n^{4})$ messages and $O(\sigma n^{3})$ shared-memory accesses in
expectation and uses $O(\rho)$ registers.

Next, we prove that randomized consensus cannot be solved in a partitionable
system, by considering the more general problem of _non-deterministic
$f$-terminating_ consensus, an extension of _non-deterministic solo
termination_ [21]. This variant of consensus has the usual validity and
agreement properties, with the following termination property:

Non-deterministic $f$-termination:

For every configuration $C$, process $p$ and set $F$ of at most $f$ processes,
such that $p\notin F$, there is an $F$-free execution in which process $p$
terminates.

######  Theorem 4.18.

If a system is $f$-partitionable then non-deterministic $f$-terminating
consensus is unsolvable.

######  Proof 4.19.

Assume, by way of contradiction, that there is an non-deterministic
$f$-terminating consensus algorithm. Since the system is $f$-partitionable,
there are two disjoint sets of processes $P$ and $P^{\prime}$, each of size
$n-f$, such that $P^{\prime}\not\rightarrow P$. Therefore, there are no two
processes $p\in{P}$ and $p^{\prime}\in{P^{\prime}}$ so that $p^{\prime}$ can
read from a memory and $p$ can write to that same memory. Let $Q$ be the
processes not in $P\cup P^{\prime}$. Since $|P|,|P^{\prime}|=n-f$, it follows
that $|P\cup Q|=|P^{\prime}\cup Q|=f$.

To prove the theorem, we construct three executions. Consider an initial
configuration, in which all processes in $P$ have initial value $0$. Since
$|P^{\prime}\cup Q|=f$, non-deterministic $f$-termination implies there is a
$(P^{\prime}\cup Q)$-free execution, in which some process $p\in P$
terminates, say by time $t_{1}$. Call this execution $\alpha_{1}$, and note
that only processes in $P$ take steps in $\alpha_{1}$. By validity, $p$
decides 0.

In a similar manner, we can get a $(P\cup Q)$-free execution, $\alpha_{2}$, in
which initial values of all the processes in $P^{\prime}$ are 1, and by non-
deterministic $f$-termination, some process $p^{\prime}\in P^{\prime}$ decides
on 1, say by time $t_{2}$. Note that only processes in $P^{\prime}$ take steps
in $\alpha_{2}$.

Finally, the third execution $\alpha_{3}$ combines $\alpha_{1}$ and
$\alpha_{2}$. The initial value of processes in $P$ is 0, and the initial
value of processes in $P^{\prime}$ is 1. Processes in $Q$ have arbitrary
initial values, and they take no steps in $\alpha_{3}$. The execution is
identical to $\alpha_{1}$ from time 0 until time $t_{1}$, and to $\alpha_{2}$
from this time until time $t_{1}+t_{2}$. All messages sent between processes
in $P$ and processes in $P^{\prime}$ are delivered after time $t_{1}+t_{2}$.
Since processes in $P^{\prime}$ do not take steps in $\alpha_{3}$ until time
$t_{1}$, all processes in $P$ decides $0$, as in $\alpha_{1}$. Processes in
$P^{\prime}$ cannot receive messages from processes in $P$ or read what
processes in $P$ write to the shared memory, therefore all processes in
$P^{\prime}$ decides 1, as in execution $\alpha_{2}$, violating the agreement
property.

##  5 The M&M Model

In the m&m model [5, 24], the shared memory connections are defined by a
shared-memory domain $L$, which is a collection of sets of processes. For each
set $S\in L$, all the processes in the set may share any number of registers
among them. Our model when the shared memory has no access restrictions is a
dual of the general m&m model, and they both capture the same systems. We say
that $L$ is _uniform_ if it is induced by an undirected _shared-memory graph_
$G=(V,E)$, where each vertex in $V$ represents a process $p$. For every
process $p$, $S_{p}=\\{p\\}\cup\\{q:(p,q)\in{E}\\}$, then
$L=\\{S_{p}:\text{$p$ is a process}\\}$. In the uniform m&m model each memory
is associated with a process $p$, and all the processes in $S_{p}$ may access
it. That is, a process can access its own memory and the memories of its
neighbors.

In the m&m model, there are no access restrictions on the shared memory.
Hence, for every process $p$, $|R_{p}|=|W_{p}|=|S_{p}|$. Therefore,
$\rho=\sum_{\text{process $p$}}{|S_{p}|}=\sum_{\text{process
$p$}}{d(p)+1}=2|E|+n=O(n^{2})$ and $\sigma=O(n^{3})$, where $d(p)$ is the
degree of process $p$ in the graph. Substituting into the algorithms presented
in Section 4, we obtain polynomial complexity for all of them, including a
polynomial randomized consensus algorithm. In the general m&m model, $\rho$
and $\sigma$ are unbounded.

######  Definition 5.1 ([24]).

Given a shared-memory domain $L$ , $f_{L}$ is the largest integer $f$ such
that for all process subsets $P$ and $P^{\prime}$ of size $n-f$ each, either
$P\cap{P^{\prime}}\neq{\emptyset}$ or there is a set $S\in L$ that contains
both a process from $P$ and a process from $P^{\prime}$.

Hadzilacos, Hu and Toueg [24] show that an SWMR register can be implemented in
the m&m model if and only if at most $f_{L}$ process may fail. Therefore in
the m&m model, $f_{opt}=f_{L}$. We can see the connection between the two
definitions by observing that, in this model, $p\leftrightarrow q$ if $p=q$ or
there is a set $S\in L$ such that $p,q\in S$. We simply write
$\leftrightarrow$, since the shared memory has no access restrictions.

The _square_ of a graph $G=(V,E)$ is the graph $G^{2}=(V,E^{2})$, where

$E^{2}=E\cup\\{(u,v):\text{$\exists{w\in E}$ such that $(u,w)\in E$ and
$(w,v)\in E$}.$

I.e., there is an edge in $G^{2}$ between every two vertices that are in
distance at most 2 in the graph $G$.

######  Definition 5.2 ([24]).

Given an undirected graph $G=(V,E)$, $f_{G}$ is the largest integer $f$ such
that for all subsets $P$ and $P^{\prime}$ of $V$ of size $n-f$ each, either
$P\cap{P^{\prime}}\neq{\emptyset}$ or $G^{2}$ has an edge $(u,v)$ such that
$u\in{P}$ and $v\in{P^{\prime}}$.

In the uniform m&m model, $f_{L}=f_{G}=f_{opt}$ [24], and $p\leftrightarrow q$
if $p=q$ or $(p,q)$ is an edge in $G^{2}$.

######  Observation 2.

In the uniform m&m model, $f_{opt}=f_{G}$.

Lemma 2.5 proves that $f_{opt}\leq f_{maj}$. The next lemma shows a graph with
$n=9$, where $f_{opt}<f_{maj}$. Thus, the converse inequality does not
necessarily hold in the uniform m&m model. Hence, it also does not hold in the
general m&m model.

######  Lemma 5.3.

There is a shared-memory graph such that $f_{opt}<f_{maj}$ in the uniform m&m
model.

######  Proof 5.4.

In the uniform m&m model $f_{G}=f_{opt}$. Consider the graph $G$ presented in
Figure 3 with $n=9$. For every set of processes $P$ of size $n-7=2$,
$|{\overset{\rightarrow}{P}}|\geq{5}>4=\lfloor{n/2}\rfloor$, therefore,
$f_{maj}=7$. We next show that $f_{opt}<7$. Consider the following subsets,
$P=\\{p_{7},p_{9}\\}$ and $Q=\\{p_{3},p_{5}\\}$, both of size $n-f_{maj}$.
$P\cap{Q}=\emptyset$ and
$(p_{7},p_{3}),(p_{7},p_{5}),(p_{9},p_{3}),(p_{9},p_{5})\notin{G^{2}}$, thus,
$f_{opt}=f_{G}<7=f_{maj}$ and we get that $f_{opt}\neq{f_{maj}}$ in the m&m
model.

$p_{2}$$p_{8}$$p_{9}$$p_{1}$$p_{5}$$p_{4}$$p_{6}$$p_{7}$$p_{3}$

Figure 2: Counter example

$p_{1}$$p_{2}$$p_{3}$$p_{4}$$p_{5}$

Figure 3: Counter example for $n=5$

######  Definition 5.5 ([5]).

A process $p$ _represents_ itself and all its neighbors, that is,
$\\{p\\}\cup\\{q:(p,q)\in E\\}$. A set of processes $P$ represents the union
of all the processes represented by processes in $P$.

Aguilera et al. [5] present a randomized consensus algorithm, called HBO,
which is based on Ben-Or’s algorithm [15]. Like Ben-Or’s algorithm, HBO has
exponential time and message complexities. HBO assumes that the nonfaulty
processes represent a majority of the processes. Below, we show that the
resilience of the HBO algorithm is not optimal. We first capture the condition
required for the correctness of the HBO algorithm, with the next definition.

######  Definition 5.6.

$f_{\text{m\&m}}$ is the largest integer $f$ such that every set $P$ of $n-f$
processes represents a majority of the processes.

######  Lemma 5.7.

$f_{\text{m\&m}}\leq{f_{opt}}$.

######  Proof 5.8.

Consider two sets of processes $P$ and $Q$, each of size $n-f_{\text{m\&m}}$.
Hence, both $P$ and $Q$ represent more than $\lfloor{n/2}\rfloor$ processes,
and hence, they represent a common process $w$. We consider three cases, and
show that in all cases, $P\leftrightarrow Q$, implying that
$f_{\text{m\&m}}\leq f_{opt}$.

If $w\in P\cap Q$ then $P\cap Q\neq{\emptyset}$ and $P\leftrightarrow Q$.

If $w\in{P}$ and $w\notin{Q}$ (the case $w\in{Q}$ and $w\notin{P}$ is
symmetric). Since $Q$ represents $w$, there is a processes $q\in{Q}$ such that
$(w,q)\in{G}$, and hence, $(w,q)$ is also an edge in $G^{2}$. Therefore,
$w\leftrightarrow q$ and $P\leftrightarrow Q$.

Finally, if $w\notin P$ and $w\notin Q$, then since both sets $P$ and $Q$
represent $w$, there is a process $p\in{P}$ such that $(p,w)\in{G}$ and and
process $q\in{Q}$ such that $(w,q)\in{G}$. Thus, $(p,q)\in{G^{2}}$ and
$P\leftrightarrow Q$.

######  Lemma 5.9.

For every $n>4$, there is a shared-memory graph $G$, such that
$f_{\text{m\&m}}<f_{opt}$ in the uniform m&m model.

######  Proof 5.10.

We show a shared-memory graph $G$ and a set of $n-f_{opt}$ processes $P$ that
represents at most $\leq\lfloor{n/2}\rfloor$ processes. The graph $G$ is the
star graph over $n$ vertices, and has edges
$\\{(p_{1},p_{2})\\}\cup{\\{(p_{2},p_{i}):3\leq{i}\leq{n})\\}}$. (See Figure
3, for $n=5$.) Clearly, there is a path of length $\leq 2$ between every pair
of vertices, and therefore, $G^{2}$ is a full graph. From the definition of
$f_{G}$, $f_{G}=n-1$. Let $P=\\{p_{1}\\}$, note that $|P|=1=n-f_{G}$. $P$
represents exactly $|S_{p_{1}}|=2\leq\lfloor{n/2}\rfloor$ processes.

Lemma 5.7 and Lemma 5.9 imply that requiring at least $n-f_{\text{m\&m}}$
nonfaulty processes is strictly stronger than requiring $n-f_{opt}$ nonfaulty
processes. Therefore, the HBO algorithm does not have optimal resilience.
Intuitively this happens since HBO does not utilize all the shared-memory
connections that are embodied in $G^{2}$. Thus, our algorithm (Section 4.5),
has better resilience than HBO, which we show is optimal, in addition to
having polynomial complexity.

Aguilera et al. [5] also present a lower bound on the number of failures any
consensus algorithm can tolerate in the m&m model. To state their bound,
consider a graph $G=(V,E)$, and let $B$, $S$ and $T$ be a partition of $V$.
$(B,S,T)$ is an _SM-cut_ in $G$ if $B$ can be partitioned into two disjoint
sets $B_{1}$ and $B_{2}$, such that for every $b_{1}\in B_{1}$, $b_{2}\in
B_{2}$, $s\in S$ and $t\in T$, we have that $(s,t),(b_{1},t),(b_{2},s)\notin
E$.

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

Consensus cannot be solved in the uniform m&m model in the presence of $f$
failures if there is a SM-cut $(B,S,T)$ such that $|S|\geq n-f$ and $|T|\geq
n-f$.

Although the resilience of HBO is not optimal, we show that this lower bound
on resilience is optimal, by proving that if a system is $f$-partitionable
then the condition in Theorem 5.11 holds. By Theorem 4.18, these two
conditions are equal in the m&m model.

######  Theorem 5.12.

In the uniform m&m model, if the system is $f$-partitionable then there is an
SM-cut $(B,S,T)$ with $|S|\geq n-f$ and $|T|\geq n-f$.

######  Proof 5.13.

Since the system is $f$-partitionable, there are two disjoint sets of
processes $S$ and $T$, each of size $n-f$, such that $S\not\leftrightarrow T$.
Since $f_{opt}=f_{G}$, $S\cap T=\emptyset$ and there is no edge $(u,v)$ in
$G^{2}$, where $u\in S$ and $v\in T$. Let $B^{\prime}_{1}=\\{u:(u,v)\in E,v\in
S\\}\setminus{S}$ and $B_{2}=\\{u:(u,v)\in E,v\in T\\}\setminus{T}$.
Obviously, $B^{\prime}_{1}\cap S=\emptyset$ and $B_{2}\cap T=\emptyset$.
$B^{\prime}_{1}\cap T=\emptyset$ and $B_{2}\cap S=\emptyset$, since there is
no edge in $G$ between a vertex in $S$ and a vertex in $T$. Assume, towards a
contradiction, that $B^{\prime}_{1}\cap B_{2}\neq\emptyset$. Hence, there is a
vertex $u$ such that $u\in B^{\prime}_{1}\cap B_{2}$. Since $u\in
B^{\prime}_{1}$ then there is some vertex $s\in S$ such that $(s,u)$ is part
of $G$. Similarly, there is some vertex $t\in T$ such that $(u,t)$ is in $E$.
This implies that the graph $G$ contains the path $s-u-t$, contradicting the
fact that there is no edge between $S$ and $T$ in $G^{2}$. This also implies
that there is no edge between a vertex in $T$ and a vertex in
$B^{\prime}_{1}$, or between a vertex in $S$ and a vertex in $B_{2}$. Let
$B_{1}=B^{\prime}_{1}\cup(V\setminus(S\cup T\cup B_{2}))$, as we showed that
$S$, $T$, $B^{\prime}_{1}$ and $B_{2}$ are disjoint then $S$, $T$, $B_{1}$ and
$B_{2}$ are a disjoint partition of $V$. For every $b_{1}\in B_{1}$, $b_{2}\in
B_{2}$, $s\in S$ and $t\in T$, $(s,t)$ ,$(b_{1},t)$ and $(b_{2},s)$ are not in
$E$. Hence, $(B,S,T)$ is a SM-cut, when $B=B_{1}\cup B_{2}$.

##  6 The Cluster-Based Model

In the hybrid, _cluster-based_ model of [29, 32], processes are partitioned
into $m$, $1\leq m\leq n$, non-empty and disjoint subsets
$P_{1},\ldots,P_{m}$, called _clusters_. Each cluster has an associated shared
memory; only processes of this cluster can (atomically) read from and write to
this shared memory. The set of processes in the cluster of $p$ is denoted
$\textit{cluster}[p]$. As in the m&m model, there are no access restrictions
on the shared memory. Hence, $|R_{p}|=|W_{p}|=1$ for every process $p$, and
therefore, $\rho=n$ and $\sigma=O(n^{2})$.

In the cluster-based model, $p\leftrightarrow q$ if and only if $p$ and $q$
are in the same cluster.

If $p\leftrightarrow q$ and $q\leftrightarrow w$, for some processes $p$, $q$
and $w$, then $p$ and $q$ are in the same cluster and $q$ and $w$ are in the
same cluster. Since clusters are disjoint, it follows that $p$ and $w$ are in
the same cluster, implying that

######  Observation 3.

In the cluster-based model, $\leftrightarrow$ is transitive.

######  Definition 6.1.

$f_{\text{cluster}}$ is the largest integer $f$ such that for all sets of
processes $P$ and $P^{\prime}$, each of size $(n-f)$, either $P\cap
P^{\prime}\neq\emptyset$ or some cluster contains a process in $P$ and a
process in $P^{\prime}$.

######  Observation 4.

In the cluster-based model $f_{opt}=f_{\text{cluster}}$.

######  Lemma 6.2.

In the cluster-based model, $f_{opt}=f_{maj}$.

######  Proof 6.3.

Since $f_{opt}\leq f_{maj}$, by Lemma 2.5, we only need to show that
$f_{maj}\leq f_{opt}$.

Consider two sets of processes $P$ and $Q$, both of size $n-f_{maj}$, then
$|{\overset{\rightarrow}{P}}|>\lfloor{n/2}\rfloor$ and
$|{\overset{\rightarrow}{Q}}|>\lfloor{n/2}\rfloor$. Therefore, there is a
process $w\in\overset{\rightarrow}{P}\cap\overset{\rightarrow}{Q}$. Since
$w\in{\overset{\rightarrow}{P}}$, there is a process $p\in{P}$ such that
$p\leftrightarrow w$, and since $w\in{\overset{\rightarrow}{Q}}$, there is a
process $q\in{Q}$ such that $q\leftrightarrow w$. Since $\leftrightarrow$ is
symmetric and by Observation 3, it is also transitive, it follows that
$p\leftrightarrow q$ and thus, $P\leftrightarrow Q$.

######  Lemma 6.4.

In the cluster-based model, for every two sets of processes, $P$ and $Q$, and
$f\leq f_{opt}$, if $|\overset{\rightarrow}{P}|\geq n-f$ and
$|\overset{\rightarrow}{Q}|\geq n-f$ then $P\leftrightarrow Q$.

######  Proof 6.5.

By the assumptions, $|\overset{\rightarrow}{P}|\geq n-f_{opt}$ and
$|\overset{\rightarrow}{Q}|\geq n-f_{opt}$. By definition,
$\overset{\rightarrow}{P}\leftrightarrow\overset{\rightarrow}{Q}$, implying
that there are two processes $p\in\overset{\rightarrow}{P}$ and
$q\in\overset{\rightarrow}{Q}$ such that $p\leftrightarrow q$. In the cluster-
based model, this means that processes $p$ and $q$ are in some common $P_{i}$.
Since $p\in\overset{\rightarrow}{P}$, there is some process $p^{\prime}\in P$
such that $p^{\prime}\leftrightarrow p$, Since $q\in\overset{\rightarrow}{Q}$,
there is some process $q^{\prime}\in Q$ such that $q^{\prime}\leftrightarrow
q$. Since $\leftrightarrow$ is symmetric and transitive, By Observation 3,
$p^{\prime}$ and $q^{\prime}$ are also in $P_{i}$, and hence,
$p^{\prime}\leftrightarrow q^{\prime}$.

Raynal and Cao [32] present two randomized consensus algorithms for the
cluster-based model. One is also based on Ben Or’s algorithm [15], using local
coins, and the other is based on an external common coin (whose implementation
is left unspecified). These algorithms terminate in an execution if there are
distinct clusters whose total size is (strictly) larger than $n/2$, each
containing at least one nonfaulty process. Clearly, if $f\leq f_{maj}$, this
condition holds for every execution with at most $f$ failures. Lemma 2.5 shows
that $f_{opt}\leq f_{maj}$, the condition holds if there are at most $f\leq
f_{opt}$ failures. Lemma 6.2 implies that these two definitions are equivalent
by proving that $f_{opt}=f_{maj}$. This means that the maximum resilience
guaranteeing that every two sets of nonfaulty processes can communicate is
equal to the one guaranteeing that every set of nonfaulty processes can
communicate with a majority of the processes.

In the cluster-based model, if a process $p\in P_{i}$ does not crash then all
other processes receive the information from all the processes of $P_{i}$, as
if none of them crashed. For this reason, we say that $p$ represents all
processes in $P_{i}$ (note that this definition is different than Definition
5.5). If a process $q$ receives messages from processes representing $k$
clusters $P_{1},\ldots,P_{k}$, such that $|P_{1}|+\cdots+|P_{k}|>n/2$, then it
has received information from a majority of the processes. This observation
does not change the resilience threshold, i.e., the maximal number of failures
that can be tolerated, but allows to wait for a smaller number of messages,
thereby, making the algorithm execute faster. Lemma 6.4 proves that every two
sets of processes representing at least $n-f_{opt}$ processes can communicate.
Therefore, instead of waiting for a majority of represented processes, as is
done in [32], it suffices to wait for $n-f_{opt}$ represented processes.
Algorithm 5 shows this improvement to the SWMR register implementation
presented in Algorithm 1, by replacing the communication pattern,
msg_exchange(). Since $n-f_{opt}\leq\lfloor{n/2}\rfloor+1$, this means that in
some cases it suffices to wait for fewer than a majority of represented
processes.

Algorithm 5 msg_exchange procedure in the cluster-based model

1: msg_exchange$\langle$m, seq, val$\rangle$: returns set of responses

2:send $\langle$m, seq, val$\rangle$ to all processes

3:responses = $\emptyset$ ; represented = $\emptyset$

4:repeat

5: wait to receive a message $m$ of the form $\langle$Ack-m, seq, -$\rangle$
from process $q$

6: represented = represented $\cup$ cluster$[q]$

7: responses = responses $\cup$ {$m$}

8:until $\textit{|represented|}\geq n-f$

9:return(responses)

This is not the case in the m&m model. For example, in the graph of Figure 3,
$n=9$ and $f_{opt}=6$. For $P=\\{p_{7},p_{9}\\}$,
$\overset{\rightarrow}{P}=\\{p_{1},p_{6},p_{7},p_{8},p_{9}\\}$, and for
$Q=\\{p_{3},p_{5}\\}$,
$\overset{\rightarrow}{Q}=\\{p_{1},p_{2},p_{3},p_{4},p_{5}\\}$, so
$|\overset{\rightarrow}{P}|=|\overset{\rightarrow}{Q}|=5>n/2$, but
$P\not\leftrightarrow Q$. Therefore, even though the system is not
$f$-partitionable, and Lemma 2.5 guarantees that the set of non-faulty
processes can communicate with a majority of the processes, it does not
suffice to wait for more than $n/2$ represented processes. (Recall that by
Definition 5.5, a process represents all the processes it can communicate with
using shared memory)

##  7 Discussion

This paper studies the optimal resilience for various problems in mixed
models. Our approach builds on simulating a SWMR register, which allows to
investigate the resilience of many problems, like implementing MWMR registers
and atomic snapshots, or solving randomized consensus, approximate agreement
and renaming. Prior consensus algorithms for mixed models [5, 32] start from a
pure message-passing algorithm and then try to exploit the added power of
shared memory. In contrast, we start with a shared-memory consensus algorithm
and systematically simulate it in the mixed model. This simplifies the
algorithms and improves their complexity, while still achieving optimal
resilience.

It would be interesting to investigate additional tasks and objects. An
interesting example is _$k$ -set consensus_ [19], in which processes must
decide on at most $k$ different values. This is trivial for $k=n$ and reduces
to consensus, for $k=1$. For the pure message-passing model, there is a
$k$-set consensus algorithm [19], when the number of failures $f<k$. This
bound is necessary for solving the problem in shared memory systems [17, 27,
33]. Since resilience in a mixed system cannot be better than in the shared-
memory model, it follows that $f<k$ is necessary and sufficient for any mixed
model. Thus, when $f_{opt}<k-1$, a system can be $f$-partitionable and still
offer $f$-resilience for $k$-set consensus.111 There is a lower bound of
$k>\frac{n-1}{n-f}$ for pure message-passing systems, proved using a
partitioning argument [16]. It might seem that adding shared memory will allow
to reduce this bound, however, this is not the case, since for the relevant
ranges of $k$ ($1<k<n$), the bound on the number of failures implied from this
bound is at least $k$.

The weakest failure detector needed for implementing a register in the
cluster-based model is strictly weaker than the weakest failure detector
needed in the pure message-passing model [29]. This aligns with the improved
resilience we can achieve in a mixed model compared to the pure message-
passing model. It is interesting to explore the precise improvement in
resilience achieved with specific failure detectors and other mixed models.

We would also like to study systems where the message-passing network is not a
clique.

#### Acknowledgements:

We thank Vassos Hadzilacos, Xing Hu, Sam Toueg and the anonymous reviewers for
helpful comments. This research was supported by ISF grant 380/18.

## References

  * [1] Gen-Z draft core specification.  https://genzconsortium.org/specification/gen-z-core-specification-1-1-draft/.  Accessed: 2020-08-26.
  * [2] InfiniBand.  https://www.infinibandta.org/about-infiniband/.  Accessed: 2020-08-26.
  * [3] iWARP.  https://en.wikipedia.org/wiki/IWARP.  Accessed: 2020-08-26.
  * [4] RDMA over converged ethernet.  https://en.wikipedia.org/wiki/RDMA_over_Converged_Ethernet.  Accessed: 2020-08-26.
  * [5] Marcos K. Aguilera, Naama Ben-David, Irina Calciu, Rachid Guerraoui, Erez Petrank, and Sam Toueg.  Passing messages while sharing memory.  In PODC, page 51–60, 2018.
  * [6] James Aspnes and Maurice Herlihy.  Fast randomized consensus using shared memory.  Journal of Algorithms, 11(3):441–461, September 1990.
  * [7] Hagit Attiya, Amotz Bar-Noy, and Danny Dolev.  Sharing memory robustly in message-passing systems.  Journal of the ACM, 42(1):124–142, January 1995.
  * [8] Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rüdiger Reischuk.  Renaming in an asynchronous environment.  Journal of the ACM, 37(3):524–548, 1990.
  * [9] Hagit Attiya and Constantin Enea.  Putting strong linearizability in context: Preserving hyperproperties in programsthat use concurrent objects.  In DISC, pages 2:1–2:17, 2019.
  * [10] Hagit Attiya and Arie Fouren.  Adaptive and efficient algorithms for lattice agreement and renaming.  SIAM J. Comput., 31(2):642–664, 2001.  doi:10.1137/S0097539700366000.
  * [11] Hagit Attiya, Arie Fouren, and Eli Gafni.  An adaptive collect algorithm with applications.  Distributed Computing, 15(2):87–96, 2002.
  * [12] Hagit Attiya, Nancy A. Lynch, and Nir Shavit.  Are wait-free algorithms fast?  J. ACM, 41(4):725–763, 1994.  doi:10.1145/179812.179902.
  * [13] Hagit Attiya and Ophir Rachman.  Atomic snapshots in $O(n\log n)$ operations.  SIAM J. Comput., 27(2):319–340, 1998.
  * [14] Amotz Bar-Noy and Danny Dolev.  A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment.  Math. Syst. Theory, 26(1):21–39, 1993.  doi:10.1007/BF01187073.
  * [15] Michael Ben-Or.  Another advantage of free choice: Completely asynchronous agreement protocols.  In PODC, pages 27–30, 1983.
  * [16] Martin Biely, Peter Robinson, and Ulrich Schmid.  Easy impossibility proofs for $k$-set agreement in message passing systems.  In OPODIS, pages 299–312, 2011.
  * [17] Elizabeth Borowsky and Eli Gafni.  Generalized FLP impossibility result for t-resilient asynchronous computations.  In STOC, pages 91–100, 1993.
  * [18] Gabriel Bracha and Sam Toueg.  Asynchronous consensus and broadcast protocols.  Journal of the ACM, 32(4):824–840, 1985.
  * [19] Soma Chaudhuri.  More choices allow more faults: Set consensus problems in totally asynchronous systems.  Inf. Comput., 105(1):132–158, 1993.  doi:10.1006/inco.1993.1043.
  * [20] Willliam Feller.  An Introduction to Probability Theory and its Applications, volume 1.  John Wiley & Sons, 1957.
  * [21] Faith E. Fich, Maurice Herlihy, and Nir Shavit.  On the space complexity of randomized synchronization.  Journal of the ACM, 45(5):843–862, 1998.  doi:10.1145/290179.290183.
  * [22] Michael J. Fischer, Nancy A. Lynch, and Mike Paterson.  Impossibility of distributed consensus with one faulty process.  Journal of the ACM, 32(2):374–382, 1985.  doi:10.1145/3149.214121.
  * [23] Wojciech Golab, Lisa Higham, and Philipp Woelfel.  Linearizable implementations do not suffice for randomized distributed computation.  In STOC, page 373–382, 2011.
  * [24] Vassos Hadzilacos, Xing Hu, and Sam Toueg.  Optimal register construction in m&m systems.  In OPODIS, pages 28:1–28:16, 2019.
  * [25] Vassos Hadzilacos, Xing Hu, and Sam Toueg.  Optimal register construction in m&m systems (version 3).  CoRR, abs/1906.00298, 2020.  URL: http://arxiv.org/abs/1906.00298.
  * [26] Vassos Hadzilacos, Xing Hu, and Sam Toueg.  Randomized consensus with regular registers.  CoRR, abs/2006.06771, 2020.  URL: http://arxiv.org/abs/2006.06771.
  * [27] Maurice Herlihy and Nir Shavit.  The asynchronous computability theorem for t-resilient tasks.  In STOC, pages 111–120, 1993.
  * [28] Maurice P. Herlihy and Jeannette M. Wing.  Linearizability: A correctness condition for concurrent objects.  ACM Transactions on Programming Languages and Systems, 12(3):463–492, July 1990.
  * [29] Damien Imbs and Michel Raynal.  The weakest failure detector to implement a register in asynchronous systems with hybrid communication.  Theor. Comput. Sci., 512:130–142, 2013.  doi:10.1016/j.tcs.2012.06.030.
  * [30] Leslie Lamport.  On interprocess communication—part I: Basic formalism.  Distributed Computing, pages 77–85, 1986.
  * [31] Kevin Lim, Jichuan Chang, Trevor Mudge, Parthasarathy Ranganathan, Steven K. Reinhardt, and Thomas F. Wenisch.  Disaggregated memory for expansion and sharing in blade servers.  SIGARCH Comput. Archit. News, 37(3):267–278, June 2009.  doi:10.1145/1555815.1555789.
  * [32] Michel Raynal and Jiannong Cao.  One for all and all for one: Scalable consensus in a hybrid communication model.  In ICDCS, pages 464–471, 2019.
  * [33] Michael E. Saks and Fotios Zaharoglou.  Wait-free $k$-set agreement is impossible: the topology of public knowledge.  In STOC, pages 101–110, 1993.
  * [34] Paul M. B. Vitányi and Baruch Awerbuch.  Atomic shared register access by asynchronous hardware.  In FOCS, pages 233–243, 1986.