# Determining Recoverable Consensus Numbers

Sean Ovens
University of Waterloo
<EMAIL_ADDRESS>

###### Abstract

Herlihy’s wait-free consensus hierarchy classifies the power of object types
in asynchronous shared memory systems where processes can permanently crash
(i.e. stop taking steps). In this hierarchy, a type has consensus number $n$
if objects of that type can be used along with (read/write) registers to solve
consensus among $n$ processes that can permanently crash, but not among $n+1$
or more processes. In systems where processes can recover after crashing, the
power of an object type to solve consensus may be different. Golab’s
recoverable consensus hierarchy classifies the power of object types in such a
system. In the recoverable consensus hierarchy, a type has recoverable
consensus number $n$ if objects of that type can be used along with registers
to solve consensus among $n$ processes that can recover after crashing, but
not among $n+1$ or more processes. In this paper, we prove that the
recoverable consensus hierarchy of deterministic, readable types is robust,
i.e., if consensus can be solved among $n$ processes that can recover after
crashing using a collection of objects of deterministic, readable types, then
one of these types has recoverable consensus number at least $n$. This is
important for comparing the relative computational power of different
deterministic, readable types, because it implies that one cannot combine
various objects to obtain an algorithm that is better at solving recoverable
consensus than any of the individual object types. Our result can be used to
show that, for all $n\geq 4$, there exists a readable type with consensus
number $n$ and recoverable consensus number $n-2$. We also show that, for all
$n>n^{\prime}\geq 1$, there exists a non-readable type that has consensus
number $n$ and recoverable consensus number $n^{\prime}$.

##  1 Introduction

Consensus has been crucial in developing our understanding of what can be
implemented using various combinations of shared object types. In the
consensus problem, processes begin with private inputs and attempt to
collectively agree on a single output, which must be equal to one of the
inputs. A solution to consensus is wait-free if every process terminates
within a finite number of its own steps. The wait-free consensus hierarchy
[10] can be used to compare the relative computational power of various types
in asynchronous shared memory models. It also allows us to reason about what
can be implemented in a wait-free manner using certain types; if
$\mathcal{T}_{1}$ has consensus number $n$ and $\mathcal{T}_{2}$ has consensus
number $m<n$, then it is impossible to use objects of $\mathcal{T}_{2}$ along
with registers to implement an object of $\mathcal{T}_{1}$ in a wait-free
manner for more than $m$ processes. Furthermore, Herlihy [10] showed that
$n$-process consensus is universal for systems with $n$ processes in the
following sense: every object has an $n$-process wait-free implementation
using objects with consensus number at least $n$ along with registers.

In this paper, we study Golab’s [8] recoverable consensus hierarchy, which
classifies the power of objects to solve consensus among processes that can
recover after crashing. When a process crashes, its local variables (including
its program counter) are all reset to their initial values. However, all
shared objects retain their values in the wake of a crash. This is a standard
asynchronous shared memory model for systems containing non-volatile main
memory [8, 2, 9, 5], which retains its state when it loses power. A
recoverable consensus algorithm satisfies recoverable wait-freedom if a
process that executes its algorithm starting from its initial state either
crashes or outputs a value after a finite number of its own steps. Therefore,
unlike a wait-free consensus algorithm, infinitely long executions are
admissible as long as each process that takes infinitely many steps also
crashes infinitely often. Notice that a recoverable consensus algorithm solves
wait-free consensus if process crashes are permanent. Therefore, the consensus
number of any type is greater than or equal to its recoverable consensus
number.

There are two main kinds of crashes that have been considered. With
simultaneous crashes, all of the processes always crash at the same time.
Simultaneous crashes could be used to model power failures in multiprocessing
systems, for example. It is known that the consensus number of an object is
the same as its recoverable consensus number if all crashes are simultaneous
[8, 5]. Therefore, in this paper we focus on individual crashes, where any
process can crash at any time. This may be more realistic for modelling
crashes in distributed systems where processes may reside on physically
distinct machines. Golab [8] showed that the recoverable wait-free consensus
hierarchy with individual crashes is different from Herlihy’s [12] wait-free
consensus hierarchy by proving that test-and-set objects, which have consensus
number $2$, cannot be used along with registers to solve recoverable wait-free
consensus between $2$ processes if individual crashes are allowed.

Like wait-free consensus, recoverable consensus is known to be universal;
Berryhill, Golab, and Tripunitara [4] showed that Herlihy’s [10] universal
construction also works in the recoverable setting with simultaneous crashes
by placing part of the data structure in non-volatile memory. Even when
processes can crash individually, Delporte-Gallet, Fatourou, Fauconnier, and
Ruppert [5] showed that recoverable consensus is universal. More specifically
any object can be implemented in a recoverable wait-free manner using objects
with recoverable consensus number at least $n$ along with registers.
Implementations obtained by this construction provide detectability [7];
roughly speaking, if an operation $op$ is interrupted by a crash, then the
process $p_{i}$ that invoked $op$ can tell upon recovery whether $op$
linearized or not before the crash and, if it did, $p_{i}$ can determine its
response.

Delporte-Gallet, Fatourou, Fauconnier, and Ruppert [5] recently studied the
relationship between the solvability of wait-free consensus and recoverable
wait-free consensus. In particular, they focused on object types that are
_deterministic_ and _readable_. A type is _deterministic_ if, for any object
and any operation of that type, when the operation is applied to the object,
its response and the resulting value of the object is uniquely determined by
the object’s current value and the operation that was applied. A type is
_readable_ if it supports an operation that returns its current value and does
not change its value. The authors defined a characterization of deterministic,
readable objects that can be used along with registers to solve recoverable
wait-free consensus among $n$ processes: Informally, a type is called
$n$-recording if there exist a value $u$, $n$ operations
$o_{0},\ldots,o_{n-1}$ assigned to processes $p_{0},\ldots,p_{n-1}$,
respectively, and a partition of the processes into two teams such that, if
some subset of the processes apply their operations to an object of that type
with initial value $u$, then the resulting value of the object records the
team of the first process to apply its operation. They showed that objects of
any $n$-recording, deterministic, readable type can be used, along with
registers, to solve recoverable wait-free consensus among $n$ processes. In
other words, the recoverable consensus number of any $n$-recording,
deterministic, readable type is at least $n$. Furthermore, they showed that
any deterministic, readable type $\mathcal{T}$ with consensus number $n\geq 4$
is $(n-2)$-recording. Therefore, the recoverable consensus number of
$\mathcal{T}$ is between $n-2$ and $n$. Before our work, it was unknown
whether there exists a type that has consensus number $n$ and recoverable
consensus number $n-2$.

Delporte-Gallet, Fatourou, Fauconnier, and Ruppert [5] also nearly proved that
$n$-recording is necessary for solving recoverable wait-free consensus among
$n$ processes. More specifically, they showed that if recoverable wait-free
consensus can be solved among $n$ processes using objects of types
$\mathcal{T}_{0},\mathcal{T}_{1},\mathcal{T}_{2},\ldots$, then at least one of
these types $\mathcal{T}_{i}$ is $(n-1)$-recording. Until our results, it
remained open to determine whether at least one of the types $\mathcal{T}_{i}$
is $n$-recording. For all $n\geq 4$, the authors also defined a deterministic,
readable type $\mathcal{X}_{n}$ that has consensus number $n$, is
$(n-2)$-recording, and is not $(n-1)$-recording. Hence, the recoverable
consensus number of $\mathcal{X}_{n}$ is at most $n$ and at least $n-2$.

Unlike recoverable wait-free consensus, there is a known condition that
characterizes deterministic, readable types that can solve wait-free consensus
among $n$ processes: Ruppert [15] showed that a deterministic, readable type
has consensus number at least $n$ if and only if it is $n$-discerning. It is
possible to decide whether a type is $n$-discerning in a finite amount of
time, as long as the type has finite numbers of values and operations.
Furthermore, Ruppert showed that if wait-free consensus can be solved using
objects of types $\mathcal{T}_{0},\mathcal{T}_{1},\mathcal{T}_{2},\ldots$,
then at least one of these types $\mathcal{T}_{i}$ is $n$-discerning. In other
words, it is impossible to have a set of deterministic, readable types whose
power to solve wait-free consensus exceeds the power of any individual type in
the set. This property of the wait-free consensus hierarchy of readable types
is called _robustness_.

Robustness is a desirable property because it allows us to determine the power
of a system containing many different types by studying the power of the
individual types. Robust wait-free hierarchies were first studied by Jayanti
[13], who showed that a restricted version of the wait-free consensus
hierarchy is not robust; the restricted version of the hierarchy classifies
types based on the number of processes among which a single object of that
type (along with infinitely many registers) can solve wait-free consensus.
Schenk [16] and Lo and Hadzilacos [14] later showed that the
unrestricted11todo: 1is this the right word? wait-free consensus hierarchy is
not robust if non-deterministic objects are allowed. On the other hand,
Herlihy and Ruppert [11] showed that the consensus hierarchy is robust for the
set of all deterministic object types that can be accessed at most once by
each process.

This paper presents the following contributions. Our main result is that the
recoverable consensus hierarchy is robust for the set of all deterministic,
readable types. To prove this, we show that if objects of deterministic types
$\mathcal{T}_{0},\mathcal{T}_{1},\mathcal{T}_{2},\ldots$ can be used along
with registers to solve recoverable wait-free consensus among $n$ processes,
then at least one of these types $\mathcal{T}_{i}$ is $n$-recording. By the
result of [5] mentioned previously, if $\mathcal{T}_{i}$ is deterministic and
readable, then objects of $\mathcal{T}_{i}$ along with registers can be used
to solve recoverable wait-free consensus among $n$ processes. Furthermore, our
result implies that the type $\mathcal{X}_{n}$ has recoverable consensus
number $n-2$. In our proof, we adapt the idea of a valency argument to the
recoverable setting. Previous work on recoverable consensus has attempted to
do the same by considering only executions in which a fixed set of processes
do not crash, and then constructing such an execution in which at least one of
these processes takes an infinite number of steps without outputting a value.
Our proof generalizes this approach by only considering executions in which
the maximum number of times each process $p_{i}$ can crash is proportional to
the number of steps taken by processes $p_{0},\ldots,p_{i-1}$ with lower
identifiers. More specifically, the number of times process $p_{i}$ crashes is
$f(n)$ times the number of steps taken by $p_{0},\ldots,p_{i-1}$, for some
function $f$. In particular, $p_{0}$ never crashes. Intuitively, processes
with smaller identifiers have higher priority in the sense that they are
allowed to crash less often than processes with larger identifiers. This way,
we avoid fixing a set of processes that do not crash, but in any infinitely
long execution, some process takes infinitely many steps without crashing. We
believe that this approach could be used to obtain other impossibility and
complexity results for recoverable algorithms.

Next, we show that the power to solve consensus of objects that do not support
a read operation can decrease arbitrarily when crash recovery is possible.
More specifically, we show that, for all $n>n^{\prime}\geq 1$, there exists a
deterministic type $\mathcal{T}_{n,n^{\prime}}$ with consensus number $n$ and
recoverable consensus number $n^{\prime}$. It remains open to determine
whether the recoverable consensus hierarchy is robust for the set of all
deterministic objects.

We discuss our model of computation in Section 2. Section 3 contains our proof
that the recoverable consensus hierarchy of deterministic, readable objects is
robust. In Section 4, we define the type $\mathcal{T}_{n,n^{\prime}}$ and
prove that it has consensus number $n$ and recoverable consensus number
$n^{\prime}$. Finally, we conclude with a brief discussion of future
directions in Section 5.

##  2 Model

We use a standard asynchronous shared memory model in which $n$ processes
$p_{0},\ldots,p_{n-1}$ communicate using shared _objects_. The number $i$ is
called process $p_{i}$’s _identifier_. Each object has a _type_ , which
defines a set of _values_ , a set of _operations_ that can be applied to an
object of the type, and a set of _responses_ that these operations can return.
Every type has a _sequential specification_ that defines, for each value $v$
and each operation $op$ of the type, the response to that operation and a
resulting value when $op$ is applied to an object of the type with value $v$.
In this paper, we consider only _deterministic_ types where, for any value $v$
and any operation $op$ of the type, there is exactly one possible response to
$op$ and exactly one possible resulting value when $op$ is applied to an
object of the type with value $v$. A type is _readable_ if it supports the
_Read_ operation; when applied to an object, the _Read_ operation returns the
current value of the object without changing its value.

In a _task_ , each process begins with an input value from some domain and the
processes produce output values such that the set of all output values
satisfies some specification. In the _consensus_ task, processes begin with
input values from $\\{0,1\\}$ and the processes that produce output values
must satisfy the following properties:

  * •

_Agreement_ : no two processes output different values.

  * •

_Validity_ : every output is the input of some process.

A _configuration_ of a consensus algorithm consists of a state for each
process and a value for each object. An _output state_ of a process denotes
the value that process outputs when it enters the state. An _algorithm_
defines a set of objects, an initial value for each of these objects, and an
initial state for each process. Furthermore, for every state of every process,
an algorithm defines the next step that process will apply. A _step_ can be an
operation applied to some object or a no op. When a process takes a step that
applies an operation to an object in a configuration, its operation returns a
response which depends on the operation that was applied, the value of the
object in the configuration, and the sequential specification of the object’s
type. Immediately after applying the operation, the process performs some
local computation and possibly updates its state, resulting in a new
configuration. If a process takes a step when it is in an output state, that
step is always a no op, which leaves the configuration unchanged. In an
_initial configuration_ , every process is in its initial state and every
object has its initial value. We use $\textit{value}(O,C)$ to denote the value
of the object $O$ in the configuration $C$. If $v\in\\{0,1\\}$, then we use
$\bar{v}$ to denote $1-v$.

An _execution_ consists of an alternating sequence of configurations and
_events_ , each of which is either a step or a crash of some process. When a
process crashes, it is reset to its initial state. Every execution begins with
a configuration, and every finite execution ends with a configuration. Each
event in an execution is applied in the configuration that precedes it, which
results in the configuration that follows the step. If $C$ is a configuration
and $\alpha$ is a finite execution starting from $C$, then we use $C\alpha$ to
denote the configuration at the end of $\alpha$. If $C^{\prime}=C\alpha$, then
we say $C^{\prime}$ is _reachable from $C$ via $\alpha$_. If $\alpha$ is a
finite execution starting from $C$ and $\beta$ is an execution starting from
$C\alpha$, then we use $\alpha\beta$ to denote the execution obtained by
removing the first configuration from $\beta$ and appending the resulting
sequence to $\alpha$. An _empty execution_ contains no steps. When a process
$p_{i}$ takes a step leading to a configuration $C^{\prime}$ in which $p_{i}$
has an output state corresponding to the value $v$, we say that $p_{i}$
outputs $v$ in that step. Furthermore, for every execution $\alpha^{\prime}$
starting from $C^{\prime}$ (including the empty execution from $C^{\prime}$),
we say that $p_{i}$ has output the value $v$ in $C^{\prime}\alpha^{\prime}$.
In the context of consensus, we say that $p_{i}$ has _decided_ the value $v$
in $C^{\prime}\alpha^{\prime}$. A _solo-terminating_ execution of some process
$p_{i}$ contains only steps by $p_{i}$ and ends with a configuration in which
$p_{i}$ has output a value. An execution is produced by an _adversary_ , who
decides which process will take the next step in each configuration. The
adversary also decides if and when processes crash.

A _schedule_ is a sequence of processes and crashes. We use $c_{i}$ to denote
a crash by process $p_{i}$. The _schedule of an execution_ is the sequence of
processes that take steps and crashes that occur in that execution. If
$\sigma$ is a schedule and $C$ is a configuration, then we use
$\textit{exec}(C,\sigma)$ to denote the execution constructed by performing
the steps and crashes in $\sigma$, starting with the configuration $C$. We use
$C\sigma$ to denote the final configuration in $\textit{exec}(C,\sigma)$. For
example, $Cp_{i}p_{j}c_{i}$ is the configuration that results when $p_{i}$
takes its next step in $C$, then $p_{j}$ takes its next step, and then $p_{i}$
crashes. If $\alpha$ is an execution starting from $C$ and $\sigma$ is a
schedule, then we use $\alpha\sigma$ to denote the execution
$\alpha\;\textit{exec}(C\alpha,\sigma)$.

The configurations $C$ and $C^{\prime}$ are _indistinguishable_ to a set of
processes $\mathcal{Q}$, denoted by
$C\mathrel{\overset{\mathcal{Q}}{\scalebox{1.5}[1.0]{$\sim$}}}C^{\prime}$, if
every process in $\mathcal{Q}$ has the same state in $C$ and $C^{\prime}$.
Consider two executions $\alpha$ and $\alpha^{\prime}$ from $C$ and
$C^{\prime}$, respectively. The executions $\alpha$ and $\alpha^{\prime}$ are
_indistinguishable_ to $\mathcal{Q}$ if
$C\mathrel{\overset{\mathcal{Q}}{\scalebox{1.5}[1.0]{$\sim$}}}C^{\prime}$,
$\alpha$ and $\alpha^{\prime}$ contain only events by $\mathcal{Q}$, the
objects accessed by $\alpha$ and $\alpha^{\prime}$ have the same values in $C$
and $C^{\prime}$, and the schedules of $\alpha$ and $\alpha^{\prime}$ are the
same. If
$C\mathrel{\overset{\mathcal{Q}}{\scalebox{1.5}[1.0]{$\sim$}}}C^{\prime}$ and
$\alpha$ is an execution from $C$ containing only events by $\mathcal{Q}$, and
all of the objects accessed by $\mathcal{Q}$ have the same values in $C$ and
$C^{\prime}$, then there exists an execution $\alpha^{\prime}$ from
$C^{\prime}$ containing only events by $\mathcal{Q}$ such that
$\alpha\mathrel{\overset{\mathcal{Q}}{\scalebox{1.5}[1.0]{$\sim$}}}\alpha^{\prime}$
[3].

In a _wait-free_ consensus algorithm, every process outputs a value after
taking a finite number of steps. A type has _consensus number $n$_ if there is
a wait-free consensus algorithm for $n$ processes using objects of that type
along with registers, but there is no such algorithm for $n+1$ or more
processes. _Recoverable wait-freedom_ is a progress condition requiring that
every process either crashes or outputs a value after taking a finite number
of steps from its initial state. A consensus algorithm that satisfies
recoverable wait-freedom is called a _recoverable wait-free consensus
algorithm_. A type has _recoverable consensus number $n$_ if there is a
recoverable wait-free consensus algorithm for $n$ processes using objects of
that type along with registers, but there is no such algorithm for $n+1$ or
more processes.

For all $\mathcal{P}^{\prime}\subseteq\\{p_{0},\ldots,p_{n-1}\\}$, define
$\mathcal{S}(\mathcal{P}^{\prime})$ as the set of schedules that contain at
most one instance of every process in $\mathcal{P}^{\prime}$. For instance,
$\mathcal{S}\bigl{(}\\{p_{0},p_{2}\\}\bigr{)}=\bigl{\\{}\langle\rangle,p_{0},p_{2},p_{0}p_{2},p_{2}p_{0}\bigr{\\}}$,
where $\langle\rangle$ denotes the empty schedule. The following definition is
adapted from Ruppert [15]. A deterministic type $\mathcal{T}$ is _$n$
-discerning_ if there exist

  * •

a value $u$ of $\mathcal{T}$,

  * •

a partition of the processes $\\{p_{0},\ldots,p_{n-1}\\}$ into two nonempty
sets $T_{0}$ and $T_{1}$, and

  * •

an operation $o_{i}$ of type $\mathcal{T}$ for each process $p_{i}$

such that, for all $j\in\\{0,\ldots,n-1\\}$, $R_{0,j}\cap R_{1,j}=\emptyset$,
where $R_{x,j}$ is the set of pairs $(r,v)$ for which there is a schedule of
processes $\sigma\in\mathcal{S}\bigl{(}\\{p_{0},\ldots,p_{n-1}\\}\bigr{)}$
where $p_{j}\in\sigma$, the first process in $\sigma$ is in $T_{x}$, and, if
the processes in $\sigma$ apply their operations in order on an object of
$\mathcal{T}$ with initial value $u$, then $r$ is the response of $p_{j}$’s
operation $o_{j}$ and $v$ is the resulting value of the object. Ruppert proved
that a deterministic, readable type has consensus number $n$ if and only if it
is $n$-discerning.

The next definition is adapted from Delporte-Gallet, Fatourou, Fauconnier, and
Ruppert [5]. A deterministic type $\mathcal{T}$ is _$n$ -recording_ if there
exist

  * •

a value $u$ of $\mathcal{T}$,

  * •

a partition of the processes $\\{p_{0},\ldots,p_{n-1}\\}$ into two nonempty
sets $T_{0}$ and $T_{1}$, and

  * •

an operation $o_{i}$ of type $\mathcal{T}$ for each process $p_{i}$

such that the following two properties are satisfied:

  * •

$U_{0}\cap U_{1}=\emptyset$, where $U_{x}$ is the set of values $v$ for which
there is a schedule of processes
$\sigma\in\mathcal{S}\bigl{(}\\{p_{0},\ldots,p_{n-1}\\}\bigr{)}$ where the
first process in $\sigma$ is in $T_{x}$ and, if the processes in $\sigma$
apply their operations in order on an object of $\mathcal{T}$ with initial
value $u$, then $v$ is the resulting value of the object, and

  * •

if $u\in U_{x}$, then $|T_{\bar{x}}|=1$.

##  3 $n$-Recording is Necessary for Readable Types

In this section we prove that, for any $n\geq 2$, if there is an $n$-process
recoverable wait-free consensus algorithm using objects with deterministic
types $\mathcal{T}_{0},\mathcal{T}_{1},\mathcal{T}_{2}\ldots$, then at least
one of these types $\mathcal{T}_{i}$ is $n$-recording. Note that this applies
to any deterministic types, not just readable ones. Theorem 8 of [5] says
that, if a deterministic, readable type $\mathcal{T}$ is $n$-recording, then
the recoverable consensus number of $\mathcal{T}$ is at least $n$. Combining
this with our result proves that the recoverable wait-free consensus hierarchy
is robust for the set of all deterministic, readable types.

We use a valency argument to obtain our result in this section. Valency
arguments were first used by Fischer, Lynch, and Paterson [6] to show that
solving wait-free binary consensus among $2$ or more processes is impossible
in the asynchronous message passing model, even if only $1$ process may crash.
They define a configuration as bivalent if, for all $v\in\\{0,1\\}$, there
exists an execution from that configuration in which $v$ is decided by some
process. If a configuration is not bivalent, then it is univalent. A valency
argument may also be used to show that solving wait-free binary consensus
among $2$ or more processes is impossible in the asynchronous shared memory
model using only registers as follows. First, using validity, it can be argued
that any initial configuration in which some process has input $0$ and another
has input $1$ must be bivalent. Let $C$ be a bivalent initial configuration.
Since the algorithm is wait-free, there must be an execution from $C$ that
leads to a critical configuration $C^{\prime}$, that is, a bivalent
configuration such that, if any process takes a step in that configuration,
then the resulting configuration is univalent. Since $C^{\prime}$ is bivalent,
there must be a process $p_{0}$ such that every execution from
$C^{\prime}p_{0}$ decides $0$ and a process $p_{1}$ such that every execution
from $C^{\prime}p_{1}$ decides $1$. Using a case analysis on which register
$p_{0}$ and $p_{1}$ are poised to access in $C^{\prime}$ and which operation
they are poised to apply, it can be shown that $C^{\prime}p_{0}$ and
$C^{\prime}p_{1}$ must have the same valency, which is a contradiction.

As noted by Golab [8], valency arguments are more difficult to apply when
processes may recover after crashing because infinitely long executions in
which no process decides are permissible as long as every process that takes
infinitely many steps in the execution also crashes infinitely often.
Furthermore, if we construct a “critical” configuration $C^{\prime}$ by
considering only crash-free executions, then it might be the case that, for
every process $p_{i}$, the configuration $C^{\prime}p_{i}$ is $v$-univalent;
in other words, any execution from $C^{\prime}$ in which $\bar{v}$ is decided
begins with a crash. To get around this, previous authors [8, 5] have
considered executions in which only a fixed set of processes may crash. We
generalize this approach by considering executions in which the number of
crashes that a process may experience is proportional the number of steps
taken by processes with smaller identifiers.

Consider a recoverable wait-free consensus algorithm for the $n\geq 2$
processes $p_{0},\ldots,p_{n-1}$ using objects of deterministic types
$\mathcal{T}_{0},\mathcal{T}_{1},\mathcal{T}_{2},\ldots$. Define
$\mathcal{P}=\\{p_{0},\ldots,p_{n-1}\\}$ as the set of all processes.

We now define our notion of valency. Let $\mathcal{A}$ be a set of executions
from some configuration $C$. Consider any execution $\alpha\in\mathcal{A}$. A
set of processes $\mathcal{P}^{\prime}\subseteq\mathcal{P}$ is _bivalent in
$\alpha$ with respect to $\mathcal{A}$_ if, for all $v\in\\{0,1\\}$, there
exists an execution $\beta$ from $C\alpha$ containing only steps by processes
in $\mathcal{P}^{\prime}$ such that $\alpha\beta\in\mathcal{A}$ and some
process has decided $v$ in $C\alpha\beta$. $\mathcal{P}^{\prime}$ is _$v$
-univalent in $\alpha$ with respect to $\mathcal{A}$_ if
$\alpha\in\mathcal{A}$ and, for every execution $\beta$ from $C\alpha$
containing only steps by processes in $\mathcal{P}^{\prime}$ such that
$\alpha\beta\in\mathcal{A}$, if some process has decided a value in
$C\alpha\beta$, then that value is $v$. If the set of all processes
$\mathcal{P}$ is bivalent (resp. $v$-univalent) in $\alpha$ with respect to
$\mathcal{A}$, then we say $\alpha$ is _bivalent (resp. $v$-univalent) with
respect to $\mathcal{A}$_. If $\alpha$ is $v$-univalent with respect to
$\mathcal{A}$ for some $v\in\\{0,1\\}$, then we say $\alpha$ is _univalent
with respect to $\mathcal{A}$_. If $\mathcal{P^{\prime}}$ is bivalent (resp.
$v$-univalent) in the empty execution from $C$ with respect to $\mathcal{A}$,
then we say $\mathcal{P}^{\prime}$ is _bivalent (resp. $v$-univalent) in $C$
with respect to $\mathcal{A}$_. If $\mathcal{P}$ is bivalent (resp.
$v$-univalent) in $C$ with respect to $\mathcal{A}$, then we say $C$ is
_bivalent (resp. $v$-univalent) with respect to $\mathcal{A}$_.

The execution $\alpha$ is _critical with respect to $\mathcal{A}$_ if $\alpha$
is bivalent with respect to $\mathcal{A}$, and, for every nonempty execution
$\beta$ such that $\alpha\beta\in\mathcal{A}$, $\alpha\beta$ is univalent with
respect to $\mathcal{A}$. If $\alpha$ is critical with respect to
$\mathcal{A}$, then we say that process $p_{i}$ is _on team $v$ in $C\alpha$
with respect to $\mathcal{A}$_ if $\alpha p_{i}$ is $v$-univalent with respect
to $\mathcal{A}$. When $\mathcal{A}$ is clear from context, we will simply say
$p_{i}$ is _on team $v$ in $C\alpha$_.

Notice that we have defined valency and criticality as properties of
executions rather than configurations (except that the valency of a
configuration is defined with respect to a set of executions from itself). We
do this because not all executions leading to a certain configuration may be
in the set of executions considered. For example, consider a set of executions
$\mathcal{A}$ from a configuration $C$. Suppose that $\alpha\in\mathcal{A}$ is
bivalent with respect to $\mathcal{A}$ and let $C^{\prime}=C\alpha$. Now
suppose there exists some different execution $\beta$ such that
$C^{\prime}=C\beta$. (Recall that a configuration consists only of the states
of all processes and the values of all objects, so multiple different
executions can lead from $C$ to $C^{\prime}$.) Even though $\alpha$ and
$\beta$ both end in the configuration $C^{\prime}$, it is not necessarily true
that $\beta$ is bivalent with respect to $\mathcal{A}$. In particular, it
might true that $\beta\not\in\mathcal{A}$, in which case the valency of
$\beta$ with respect to $\mathcal{A}$ is undefined.

Let $C$ be some initial configuration in which some process $p_{i}$ has input
$0$ and another process $p_{j}$ has input $1$. Consider an initial
configuration $B_{0}$ in which every process has input $0$ and another initial
configuration $B_{1}$ in which every process has input $1$. Then
$C\mathrel{\overset{p_{i}}{\scalebox{1.5}[1.0]{$\sim$}}}B_{0}$,
$C\mathrel{\overset{p_{j}}{\scalebox{1.5}[1.0]{$\sim$}}}B_{1}$, and all of the
objects have the same values in $C$, $B_{0}$, and $B_{1}$. By validity,
$p_{i}$ decides $0$ in its solo-terminating execution from $B_{0}$ and $p_{j}$
decides $1$ in its solo-terminating execution from $B_{1}$. Therefore, $p_{i}$
decides $0$ in its solo-terminating execution from $C$ and $p_{j}$ decides $1$
in its solo-terminating execution from $C$. Hence, $C$ is bivalent with
respect to any set of executions from $C$ that contain the solo-terminating
executions of $p_{i}$ and $p_{j}$ from $C$. This gives us the following
observation.

######  Observation 1.

Let $C$ be an initial configuration of an algorithm in which some process
$p_{i}$ has input $0$ and another process $p_{j}$ has input $1$. Then $C$ is
bivalent with respect to any set of executions from $C$ that contains the
solo-terminating executions by $p_{i}$ and $p_{j}$ from $C$.

Consider some set of processes $\mathcal{P}^{\prime}\subseteq\mathcal{P}$ and
an execution $\alpha\in\mathcal{A}$ such that $\mathcal{P}^{\prime}$ is
univalent in $\alpha$ with respect to $\mathcal{A}$. Let $\beta,\gamma$ be any
executions containing only steps by $\mathcal{P}^{\prime}$ such that
$\alpha\beta,\alpha\beta\gamma\in\mathcal{A}$. If $\mathcal{P}^{\prime}$ is
$v$-univalent in either $\alpha$ or $\alpha\beta$ with respect to
$\mathcal{A}$ and some process has decided a value in $C\alpha\beta\gamma$,
then that value must be $v$ by definition of $v$-univalent. Hence,
$\mathcal{P}^{\prime}$ is $v$-univalent is both $\alpha$ and $\alpha\beta$
with respect to $\mathcal{A}$. We formalize this in the following observation.

######  Observation 2.

Let $\mathcal{P}^{\prime}\subseteq\mathcal{P}$, $\alpha\in\mathcal{A}$,
$\alpha\beta\in\mathcal{A}$, and suppose that $\mathcal{P}$ is univalent in
$\alpha$ with respect to $\mathcal{A}$ and $\beta$ contains only steps by
$\mathcal{P}^{\prime}$. Then $\mathcal{P}^{\prime}$ is $v$-univalent in
$\alpha$ with respect to $\mathcal{A}$ if and only if $\mathcal{P}^{\prime}$
is $v$-univalent in $\alpha\beta$ with respect to $\mathcal{A}$.

We now define the set of executions we use to perform our valency argument. As
mentioned earlier, in the executions we consider, the maximum number of
crashes allowed by any process $p_{i}$ is proportional to the number of steps
by processes $p_{0},\ldots,p_{i-1}$.

More formally, for any configuration $C$ and any nonnegative integer $z$,
define $\mathcal{E}_{z}(C)$ as the set of all executions $\alpha$ from $C$
that contain no crashes by $p_{0}$ and in which, for every process
$p_{i}\in\\{p_{1},\ldots,p_{n-1}\\}$, the number of crashes by $p_{i}$ is no
greater than $zn$ times the number of steps collectively taken by
$p_{0},\ldots,p_{i-1}$ in $\alpha$. Define
$\mathcal{E}^{\star}_{z}(C)\subset\mathcal{E}_{z}(C)$ as the set of all
executions $\alpha$ from $C$ that contain no crashes by $p_{0}$ and in which,
for every process $p_{i}\in\\{p_{1},\ldots,p_{n-1}\\}$ and every prefix
$\alpha^{\prime}$ of $\alpha$, the number of crashes by $p_{i}$ is no greater
than $zn$ times the number of steps collectively taken by
$p_{0},\ldots,p_{i-1}$ in $\alpha^{\prime}$.

Notice that $\mathcal{E}^{\star}_{z}(C)$ is prefix-closed but
$\mathcal{E}_{z}(C)$ is not. For example, if $n=2$, then
$\textit{exec}(C,p_{1}c_{1}p_{0})\in\mathcal{E}_{1}(C)$ but
$\textit{exec}(p_{1}c_{1}p_{0})\not\in\mathcal{E}^{\star}_{1}(C)$ because the
number of crashes by $p_{1}$ in $\textit{exec}(p_{1}c_{1})$ is greater than
$2$ times the number of steps taken by $p_{0}$ in that execution.

The following two observations follow from the the definitions of
$\mathcal{E}_{z}$ and $\mathcal{E}^{\star}_{z}$.

######  Observation 3.

For any configuration $C$, any integer $z>0$, and any
$\mathcal{A}\in\\{\mathcal{E}_{z},\mathcal{E}^{\star}_{z}\\}$, if
$\alpha\in\mathcal{A}(C)$ and $\beta\in\mathcal{A}(C\alpha)$, then
$\alpha\beta\in\mathcal{A}(C)$.

######  Observation 4.

For any configuration $C$, any integer $z>0$, any
$\mathcal{A}\in\\{\mathcal{E}_{z},\mathcal{E}^{\star}_{z}\\}$, and any
execution or schedule $\sigma$ that contains no crashes, if
$\alpha\in\mathcal{A}(C)$, then $\alpha\sigma\in\mathcal{A}(C)$.

Consider a configuration $C$,
$\mathcal{A}\in\\{\mathcal{E}_{z},\mathcal{E}^{\star}_{z}\\}$, and
$\alpha\in\mathcal{A}(C)$ such that $\mathcal{P}^{\prime}\subseteq\mathcal{P}$
is $v$-univalent in $\alpha$ with respect to $\mathcal{A}(C)$. Also consider
any configuration $C^{\prime}$ such that $C^{\prime}$ and $C\alpha$ are
indistinguishable to $\mathcal{P}^{\prime}\subseteq\mathcal{P}$ and all of the
objects have the same values in $C^{\prime}$ and $C\alpha$. Let
$\beta^{\prime}\in\mathcal{A}(C^{\prime})$ be an execution that contains only
steps by $\mathcal{P}^{\prime}$. Then there exists an execution $\beta$ from
$C\alpha$ containing only steps by $\mathcal{P}^{\prime}$ such that $\beta$
and $\beta^{\prime}$ are indistinguishable to $\mathcal{P}^{\prime}$.
Furthermore, since $\beta^{\prime}\in\mathcal{A}(C^{\prime})$, we must also
have $\beta\in\mathcal{A}(C\alpha)$ by the definitions of $\mathcal{E}_{z}$
and $\mathcal{E}^{\star}_{z}$. By Observation 3, we have
$\alpha\beta\in\mathcal{A}(C)$. Since $\alpha$ is $v$-univalent with respect
to $\mathcal{A}(C)$, if any process has decided a value in $C\alpha\beta$,
then that value is $v$. Therefore, if any process has decided a value in
$C^{\prime}\beta^{\prime}$, then that value is $v$. Thus,
$\mathcal{P}^{\prime}$ is $v$-univalent in $C^{\prime}$ with respect to
$\mathcal{A}(C^{\prime})$. We formalize this below.

######  Observation 5.

For any $\mathcal{P}^{\prime}\subseteq\mathcal{P}$, any configuration $C$, any
integer $z>0$, any
$\mathcal{A}\in\\{\mathcal{E}_{z},\mathcal{E}^{\star}_{z}\\}$, and any
$\alpha\in\mathcal{A}(C)$, if $\mathcal{P}^{\prime}$ is $v$-univalent in
$\alpha$ with respect to $\mathcal{A}(C)$, then for any configuration
$C^{\prime}$ such that
$C^{\prime}\mathrel{\overset{\mathcal{P}^{\prime}}{\scalebox{1.5}[1.0]{$\sim$}}}C\alpha$
and all of the objects have the same values in $C^{\prime}$ and $C\alpha$,
$\mathcal{P}^{\prime}$ is $v$-univalent in $C^{\prime}$ with respect to
$\mathcal{A}(C^{\prime})$.

In the following lemma, we will show that if $C$ is bivalent with respect to
$\mathcal{E}^{\star}_{z}(C)$ for some integer $z>0$, then we can construct an
execution $\alpha\in\mathcal{E}^{\star}_{z}(C)$ that is critical with respect
to $\mathcal{E}^{\star}_{z}(C)$, similar to known valency arguments for
consensus. We will also prove a slightly different property: for any
$z^{\prime}\geq z$, there is an execution
$\beta\in\mathcal{E}_{z^{\prime}}(C)$ such that $C\beta$ is bivalent with
respect to $\mathcal{E}^{\star}_{z}(C\beta)$ and, for every execution $\gamma$
such that $\beta\gamma\in\mathcal{E}_{z^{\prime}}(C)$, the configuration
$C\beta\gamma$ is univalent with respect to
$\mathcal{E}^{\star}_{z}(C\beta\gamma)$. In other words, it is not possible to
infinitely extend an execution in $\mathcal{E}_{z^{\prime}}(C)$ while keeping
the resulting configuration $C^{\prime}$ bivalent with respect to
$\mathcal{E}^{\star}_{z}(C^{\prime})$. While this is different from our
definition of a critical execution, the proof that
$\beta\in\mathcal{E}_{z^{\prime}}(C)$ exists is largely the same as the proof
that $\alpha\in\mathcal{E}^{\star}_{z}(C)$ exists. We formally prove the
existence of these executions in the following lemma.

######  Lemma 6.

Let $C$ be a configuration that is bivalent with respect to
$\mathcal{E}^{\star}_{z}(C)$, for some integer $z>0$. Then

  1. (a)

there exists a finite execution $\alpha\in\mathcal{E}^{\star}_{z}(C)$ such
that $\alpha$ is critical with respect to $\mathcal{E}^{\star}_{z}(C)$, and

  2. (b)

for any $z^{\prime}\geq z$, there exists a finite execution
$\beta\in\mathcal{E}_{z^{\prime}}(C)$ such that $C\beta$ is bivalent with
respect to $\mathcal{E}^{\star}_{z}(C\beta)$ and, for every nonempty finite
execution $\gamma$ such that $\beta\gamma\in\mathcal{E}_{z^{\prime}}(C)$, the
configuration $C\beta\gamma$ is univalent with respect to
$\mathcal{E}^{\star}_{z}(C\beta\gamma)$.

###### Proof.

Suppose that either (a) or (b) is false. We proceed by constructing infinitely
many executions $\gamma_{0},\gamma_{1},\gamma_{2},\ldots$ starting from $C$
such that $\gamma_{i}$ is a proper prefix of $\gamma_{i+1}$ for all $i$. If
(a) is false, then $\gamma_{i}\in\mathcal{E}^{\star}_{z}(C)$ and $\gamma_{i}$
is bivalent with respect to $\mathcal{E}^{\star}_{z}(C)$ for all $i$. On the
other hand, if (b) is false, then $\gamma_{i}\in\mathcal{E}_{z^{\prime}}(C)$
and $C\gamma_{i}$ is bivalent with respect to
$\mathcal{E}^{\star}_{z}(C\gamma_{i})$ for all $i$. In either case, define
$\gamma_{0}$ as the empty execution from $C$.

Now let $i>0$ and suppose that we have constructed the execution
$\gamma_{i-1}$. If (a) is false, then the execution $\gamma_{i-1}$ is not
critical with respect to $\mathcal{E}^{\star}_{z}(C)$. Since $\gamma_{i-1}$ is
bivalent with respect to $\mathcal{E}^{\star}_{z}(C)$, there exists a nonempty
execution $\delta$ from $C\gamma_{i-1}$ such that
$\gamma_{i-1}\delta\in\mathcal{E}^{\star}_{z}(C)$ and $\gamma_{i-1}\delta$ is
bivalent with respect to $\mathcal{E}^{\star}_{z}(C)$. Define
$\gamma_{i}=\gamma_{i-1}\delta$.

Otherwise, (b) is false. Then $C\gamma_{i-1}$ is bivalent with respect to
$\mathcal{E}^{\star}_{z}(C\gamma_{i-1})$ and
$\gamma_{i-1}\in\mathcal{E}_{z^{\prime}}(C)$. Hence, by the negation of (b),
there exists a nonempty execution $\delta$ from $C\gamma_{i-1}$ such that
$\gamma_{i-1}\delta\in\mathcal{E}_{z^{\prime}}(C)$ and $C\gamma_{i-1}\delta$
is bivalent with respect to $\mathcal{E}^{\star}_{z}(C\gamma_{i-1}\delta)$.
Define $\gamma_{i}=\gamma_{i-1}\delta$. This completes the construction.

Since $\gamma_{i}$ is a proper prefix of $\gamma_{i+1}$, for all $i$, the
executions $\gamma_{0},\gamma_{1},\gamma_{2},\ldots$ are strictly increasing
in length. For all $i$, define $\alpha_{i}$ as the nonempty execution from
$C\gamma_{i}$ to $C\gamma_{i+1}$, that is,
$\gamma_{i+1}=\gamma_{i}\alpha_{i}$. More generally, for any $j>i$, we have
$\gamma_{j}=\gamma_{i}\alpha_{i}\alpha_{i+1}\ldots\alpha_{j-1}$. Since each
$\alpha_{i}$ is nonempty, there must exist a process $p_{k}$ such that, for
every $i\geq 0$, there exists a $j\geq i$ such that $p_{k}$ either takes a
step or crashes in $\alpha_{j}$. Let $p_{k}$ be the process with the minimum
identifier for which this property holds. Then there is an $m\geq 0$ such that
$p_{0},\ldots,p_{k-1}$ neither take a step nor crash in $\alpha_{m^{\prime}}$,
for all $m^{\prime}\geq m$. Let $t$ be the number of steps taken collectively
by $p_{0},\ldots,p_{k-1}$ in $\gamma_{m}$, and let $f$ be the number of times
that $p_{k}$ crashes in $\gamma_{m}$. Since $z^{\prime}\geq z$, we know that
$\mathcal{E}^{\star}_{z}(C)\subset\mathcal{E}_{z^{\prime}}(C)$ for all $C$, so
$\gamma_{m},\gamma_{m+1},\ldots\in\mathcal{E}_{z^{\prime}}(C)$. Hence, process
$p_{k}$ crashes no more than $z^{\prime}nt-f$ times in
$\alpha_{m}\alpha_{m+1}\ldots$. Therefore, there exists an $\ell\geq m$ such
that $p_{k}$ does not crash in $\alpha_{\ell}\alpha_{\ell+1}\ldots$. Hence,
$p_{k}$ takes infinitely many steps without crashing in
$\alpha_{\ell}\alpha_{\ell+1}\ldots$. By recoverable wait-freedom, there
exists an $r\geq\ell$ such that $p_{k}$ has decided in $C\gamma_{r}$. However,
in case (a) is false, $\gamma_{r}$ is bivalent with respect to
$\mathcal{E}^{\star}_{z}(C)$, and in case (b) is false, $\gamma_{r}$ is
bivalent with respect to $\mathcal{E}^{\star}_{z}(C\gamma_{r})$. In either
case, there exists an execution $\beta_{\bar{v}}$ from $C\gamma_{r}$ such that
some process has decided $\bar{v}$ in $C\gamma_{r}\beta_{\bar{v}}$. This
contradicts agreement.

∎

We will now prove some useful properties about critical executions. For the
following five lemmas, let $C$ be a configuration, let $z\geq 1$ be an
integer, and let $\alpha\in\mathcal{E}_{z}^{\star}(C)$ such that $\alpha$ is
critical with respect to $\mathcal{E}^{\star}_{z}(C)$. We proceed by proving
that there is at least one process on each team in $C\alpha$.

######  Lemma 7.

There is at least one process on team $0$ in $C\alpha$ and at least one
process on team $1$ in $C\alpha$.

###### Proof.

Observation 4 implies that $\alpha p_{0}\in\mathcal{E}^{\star}_{z}(C)$. Hence,
$p_{0}$ is on some team $v\in\\{0,1\\}$ in $C\alpha$. Then $\alpha p_{0}$ is
$v$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$. Let $\delta$ be
$p_{0}$’s solo-terminating execution from $C\alpha p_{0}$. Observation 4
implies that $\alpha p_{0}\delta\in\mathcal{E}^{\star}_{z}(C)$, so $p_{0}$ has
decided $v$ in $C\alpha p_{0}\delta$.

Consider any $i\in\\{1,\ldots,n-1\\}$ such that $\alpha
c_{i}\in\mathcal{E}^{\star}_{z}(C)$. Since $C\alpha$ is critical with respect
to $\mathcal{E}^{\star}_{z}(C)$, the configuration $C\alpha c_{i}$ is
univalent with respect to $\mathcal{E}^{\star}_{z}(C)$. Since $\alpha
c_{i}\in\mathcal{E}^{\star}_{z}(C)$, we also have $\alpha
c_{i}p_{0}\in\mathcal{E}^{\star}_{z}(C)$ by Observation 4. Hence, $C\alpha
c_{i}p_{0}$ is also univalent with respect to $\mathcal{E}^{\star}_{z}(C)$ by
Observation 2.

Notice that $C\alpha
p_{0}\mathrel{\overset{p_{0}}{\scalebox{1.5}[1.0]{$\sim$}}}C\alpha c_{i}p_{0}$
and all of the objects have the same values in these two configurations.
Hence, $p_{0}$ decides $v$ in its solo-terminating execution from $C\alpha
c_{i}p_{0}$. Equivalently, $p_{0}$ decides $v$ in its solo-terminating
execution from $C\alpha c_{i}$. Let $\gamma$ be $p_{0}$’s solo-terminating
execution from $C\alpha c_{i}$. By Observation 4, $\alpha
c_{i}\gamma\in\mathcal{E}_{z}^{\star}(C)$. Since $p_{0}$ decides $v$ in
$\gamma$ and $\alpha c_{i}$ is univalent with respect to
$\mathcal{E}_{z}^{\star}(C)$, Observation 2 implies that $\alpha c_{i}$ is
$v$-univalent with respect to $\mathcal{E}_{z}^{\star}(C)$.

Since $\alpha$ is critical with respect to $\mathcal{E}^{\star}_{z}(C)$, it is
bivalent with respect to $\mathcal{E}^{\star}_{z}(C)$. Hence, there exists an
execution $\beta_{\bar{v}}$ such that
$\alpha\beta_{\bar{v}}\in\mathcal{E}^{\star}_{z}(C)$ and some process has
decided $\bar{v}$ in $C\alpha\beta_{\bar{v}}$. Since $\alpha p_{0}$ and
$\alpha c_{i}$ are $v$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$
for all $i\in\\{1,\ldots,n-1\\}$ such that $\alpha
c_{i}\in\mathcal{E}^{\star}_{z}(C)$, the execution $\beta_{\bar{v}}$ begins
with a step by some process $p_{j}\neq p_{0}$. Hence, $p_{j}$ is on team
$\bar{v}$ in $C\alpha$. ∎

Notice that, since $\alpha$ is critical with respect to
$\mathcal{E}^{\star}_{z}(C)$, we know that $\alpha$ is bivalent with respect
to $\mathcal{E}^{\star}_{z}(C)$ by definition of critical. It takes slightly
more effort to show that $C\alpha$ is bivalent with respect to
$\mathcal{E}^{\star}_{z}(C\alpha)$, which we do in the following lemma.

######  Lemma 8.

$C\alpha$ is bivalent with respect to $\mathcal{E}^{\star}_{z}(C\alpha)$.

###### Proof.

By Lemma 7, there is a process $p_{i}$ on team $0$ in $C\alpha$ and a process
$p_{j}$ on team $1$ in $C\alpha$. Let $\delta_{i}$ be $p_{i}$’s solo-
terminating execution from $C\alpha p_{i}$, and let $\delta_{j}$ be $p_{j}$’s
solo-terminating execution from $C\alpha p_{j}$. Since $p_{i}$ is on team $0$
in $C\alpha$ and $p_{j}$ is on team $1$ in $C\alpha$, the execution $\alpha
p_{i}$ is $0$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$ and
$\alpha p_{j}$ is $1$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$.
Observation 4 implies that $\alpha
p_{i}\delta_{i}\in\mathcal{E}^{\star}_{z}(C)$ and $\alpha
p_{j}\delta_{j}\in\mathcal{E}^{\star}_{z}(C)$. Since $\alpha p_{i}$ is
$0$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$ and $\alpha p_{j}$
is $1$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$, $p_{i}$ has
decided $0$ in $C\alpha p_{i}\delta_{i}$ and $p_{j}$ has decided $1$ in
$C\alpha p_{j}\delta_{j}$. Observation 4 implies that
$\delta_{i},\delta_{j}\in\mathcal{E}^{\star}_{z}(C\alpha)$. Hence, $C\alpha$
is bivalent with respect to $\mathcal{E}^{\star}_{z}(C\alpha)$. ∎

We now prove that every process is poised to access the same object in
$C\alpha$. The proof of this is essentially identical to typical proofs of the
same property for wait-free consensus algorithms.

######  Lemma 9.

Every process is poised to apply an operation to the same object in $C\alpha$.

###### Proof.

By Lemma 7, there is a process that is on team $0$ in $C\alpha$ and there is a
process that is on team $1$ in $C\alpha$. Let $p_{i}$ be any process that is
on team $0$ in $C\alpha$ and let $p_{j}$ be any process that is on team $1$ in
$C\alpha$. If $p_{i}$ and $p_{j}$ are poised to access different objects in
$C\alpha$, then $C\alpha p_{i}p_{j}=C\alpha p_{j}p_{i}$. Hence, $p_{i}$
decides the same value in its solo-terminating executions from $C\alpha
p_{i}p_{j}$ and $C\alpha p_{j}p_{i}$. Since $\alpha p_{i}$ is $0$-univalent
with respect to $\mathcal{E}^{\star}_{z}(C)$ and $\alpha
p_{i}p_{j}\in\mathcal{E}^{\star}_{z}(C)$ by Observation 4, $\alpha p_{i}p_{j}$
is also $0$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$ by
Observation 2. Hence, $p_{i}$ decides $0$ in its solo-terminating execution
from $C\alpha p_{i}p_{j}$. Therefore, $p_{i}$ also decides $0$ in its solo-
terminating execution from $C\alpha p_{j}p_{i}$. However, since $\alpha p_{j}$
is $1$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$ and $\alpha
p_{j}p_{i}\in\mathcal{E}^{\star}_{z}(C)$ by Observation 4, the execution
$\alpha p_{j}p_{i}$ is also $1$-univalent with respect to
$\mathcal{E}^{\star}_{z}(C)$ by Observation 2. This is a contradiction. ∎

For the following two lemmas, let $O$ be the object that every process is
poised to access in $C\alpha$. Such an object exists by Lemma 9.

In the next lemma we will show that, if there are two nonempty schedules
$\sigma,\tau\in\mathcal{S}(\mathcal{P})$ beginning with processes on different
teams such that $\sigma$ and $\tau$ change $O$ to the same value when applied
in $C\alpha$, then either $\sigma=p_{n-1}$ or $\tau=p_{n-1}$. To see why this
is true, notice that $p_{n-1}$ cannot distinguish between $C\alpha\sigma
c_{n-1}$ and $C\alpha\tau c_{n-1}$ and all of the objects have the same values
in these two configurations, so $p_{n-1}$ decides the same value in its solo-
terminating executions from these two configurations. If neither
$\sigma=p_{n-1}$ nor $\tau=p_{n-1}$, then both $\sigma$ and $\tau$ contain a
process with a lower identifier than $p_{n-1}$. Since $z\geq 1$, this implies
that $\alpha\sigma c_{n-1},\alpha\tau c_{n-1}\in\mathcal{E}^{\star}_{z}(C)$.
Hence, $\alpha\sigma c_{n-1}$ and $\alpha\tau c_{n-1}$ have different
valencies with respect to $\mathcal{E}^{\star}_{z}(C)$. This leads to a
contradiction. We formalize this in the following lemma.

######  Lemma 10.

Suppose that $p_{n-1}$ is on team $\bar{v}$ in $C\alpha$. If there is a
process $p_{i}$ that is on team $v$ in $C\alpha$, a process $p_{j}$ that is on
team $\bar{v}$ in $C\alpha$, an
$R_{i}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{i}\\}\bigr{)}$, and an
$R_{j}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{j}\\}\bigr{)}$ such that
$\textit{value}(O,C\alpha p_{i}R_{i})=\textit{value}(O,C\alpha p_{j}R_{j})$,
then $p_{j}=p_{n-1}$ and $R_{j}=\langle\rangle$.

###### Proof.

To obtain a contradiction, suppose that $p_{j}\neq p_{n-1}$ or
$R_{j}\neq\langle\rangle$. Notice that $C\alpha
p_{i}R_{i}c_{n-1}\mathrel{\overset{p_{n-1}}{\scalebox{1.5}[1.0]{$\sim$}}}C\alpha
p_{j}R_{j}c_{n-1}$ and all of the objects have the same values in $C\alpha
p_{i}R_{i}c_{n-1}$ and $C\alpha p_{j}R_{j}c_{n-1}$. Hence, $p_{n-1}$ decides
the same value in its solo-terminating executions from $C\alpha
p_{i}R_{i}c_{n-1}$ and $C\alpha p_{j}R_{j}c_{n-1}$. Since $z\geq 1$ and the
schedules $p_{i}R_{i}$ and $p_{j}R_{j}$ both contain a process with a smaller
identifier than $p_{n-1}$, we have
$\textit{exec}(C\alpha,p_{i}R_{i}c_{n-1}),\textit{exec}(C\alpha,p_{j}R_{j}c_{n-1})\in\mathcal{E}^{\star}_{z}(C\alpha)$.
Since $\alpha\in\mathcal{E}^{\star}_{z}(C)$, Observation 3 implies that
$\alpha p_{i}R_{i}c_{n-1},\alpha
p_{j}R_{j}c_{n-1}\in\mathcal{E}^{\star}_{z}(C)$. Since $\alpha p_{i}$ is
$v$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$ and $\alpha p_{j}$
is $\bar{v}$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$, it must
be true that $\alpha p_{i}R_{i}c_{n-1}$ is $v$-univalent with respect to
$\mathcal{E}^{\star}_{z}(C)$ and $\alpha p_{j}R_{j}c_{n-1}$ is
$\bar{v}$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$. Hence,
$p_{n-1}$ decides different values in its solo-terminating executions from
$C\alpha p_{i}R_{i}c_{n-1}$ and $C\alpha p_{j}R_{j}c_{n-1}$. This is a
contradiction. ∎

For all $v\in\\{0,1\\}$, define $T_{v}$ as the set of all processes on team
$v$ in $C\alpha$. Furthermore, define
$U_{v}=\bigl{\\{}\textit{value}(O,C\alpha\sigma):\sigma=p_{i_{v}}\sigma^{\prime},\>p_{i_{v}}\in
T_{v},\>\sigma^{\prime}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{i_{v}}\\}\bigr{)}\bigr{\\}}$.
The configuration $C\alpha$ is _$v$ -hiding_ if $U_{0}\cap U_{1}=\emptyset$
and _value_ $(O,C\alpha)\in U_{v}$. Intuitively, $C\alpha$ is $v$-hiding if it
is not possible for the two teams to change $O$ to the same value, but team
$v$ can be hidden in the sense that a schedule beginning with a step by a
process on team $v$ can result in $O$ having the same value that it did in
$C\alpha$.

The configuration $C\alpha$ is _$n$ -recording_ if $U_{0}\cap U_{1}=\emptyset$
and, if _value_ $(O,C\alpha)\in U_{v}$ for some $v\in\\{0,1\\}$, then
$|T_{\bar{v}}|=1$. Notice that, if there exists an $n$-recording configuration
in which all of the processes are poised to access an object $O$ of type
$\mathcal{T}$, then $\mathcal{T}$ is $n$-recording. For any
$k\in\\{1,\ldots,n-1\\}$, let $\lambda_{k}$ denote the schedule
$c_{k}c_{k+1}\ldots c_{n-1}$. The next observation follows from the
definitions of $v$-hiding and $n$-recording.

######  Observation 11.

$C\alpha$ is either $n$-recording, $v$-hiding for some $v\in\\{0,1\\}$, or
there exists a process $p_{i}$ on team $0$ in $C\alpha$, a process $p_{j}$ on
team $1$ in $C\alpha$, an
$R_{i}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{i}\\}\bigr{)}$, and an
$R_{j}\in\mathcal{S}\big{(}\mathcal{P}-\\{p_{j}\\}\bigr{)}$ such that
$\textit{value}(O,C\alpha p_{i}R_{i})=\textit{value}(O,C\alpha p_{j}R_{j})$.

For the following lemma, suppose that there exists a process $p_{i}$ on team
$v$ in $C\alpha$ and an
$R_{i}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{i}\\}\bigr{)}$ such that
$\textit{value}(O,C\alpha p_{i}R_{i})=\textit{value}(O,C\alpha X)$, where
either $X=p_{n-1}$ and $p_{n-1}$ is on team $\bar{v}$ in $C\alpha$ or
$X=\langle\rangle$. Notice that if $X=\langle\rangle$, then $C\alpha$ is
$v$-hiding. Let $p_{\ell}$ be the process with the smallest identifier among
$p_{i}$ and the processes in $R_{i}$. In the following lemma, we show that if
$\ell<n-1$ and the processes $p_{\ell+1},\ldots,p_{n-1}$ crash in $C\alpha X$,
and then these same processes take steps to produce an execution that is
critical with respect to $\mathcal{E}^{\star}_{z}(C\alpha X\lambda_{\ell+1})$,
then the resulting configuration is either $n$-recording or $v$-hiding.

To provide some intuition for this, notice that $\alpha
p_{i}R_{i}\lambda_{\ell+1}\in\mathcal{E}^{\star}_{z}(C)$ because $p_{\ell}\in
p_{i}R_{i}$ has a smaller identifier than any of the processes that crashed in
$\lambda_{\ell+1}$. Therefore, $\alpha p_{i}R_{i}\lambda_{\ell+1}$ is
$v$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$. For this example,
suppose that $X=\langle\rangle$ and, to obtain a contradiction, suppose that
there exists an execution $\alpha^{\prime}$ containing only events by
$p_{\ell+1},\ldots,p_{n-1}$ such that $\alpha^{\prime}$ is critical with
respect to $\mathcal{E}^{\star}_{z}(C\alpha\lambda_{\ell+1})$ and
$C\alpha\lambda_{\ell+1}\alpha^{\prime}$ is $\bar{v}$-hiding. Since $C\alpha
p_{i}R_{i}\lambda_{\ell+1}$ and $C\alpha\lambda_{\ell+1}$ are
indistinguishable to $p_{\ell+1},\ldots,p_{n-1}$ and all of the objects have
the same values in these two configurations, $\\{p_{\ell+1},\ldots,p_{n-1}\\}$
is $v$-univalent in $C\alpha\lambda_{\ell+1}$ with respect to
$\mathcal{E}^{\star}_{z}(C\alpha\lambda_{\ell+1})$ by Observation 5. We can
use this, combined with the fact that $\alpha^{\prime}$ contains only events
by $p_{\ell+1},\ldots,p_{n-1}$, to show that $p_{\ell+1},\ldots,p_{n-1}$ are
on team $v$ in $C\alpha\lambda_{\ell+1}\alpha^{\prime}$ with respect to
$\mathcal{E}_{z}^{\star}(C\alpha\lambda_{\ell+1})$. Define
$C^{\prime}=C\alpha\lambda_{\ell+1}\alpha^{\prime}$. Since $C^{\prime}$ is
$\bar{v}$-hiding, there exists a process $p_{j}$ on team $\bar{v}$ in
$C^{\prime}$ and an
$R_{j}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{j}\\}\bigr{)}$ such that
$\textit{value}(O,C^{\prime}p_{j}R_{j})=\textit{value}(O,C^{\prime})$. Since
$p_{n-1}$ is on team $v$ in $C^{\prime}$, we know that $p_{j}\neq p_{n-1}$.
Therefore, we can show that
$\alpha^{\prime}p_{j}R_{j}c_{n-1}\in\mathcal{E}^{\star}_{z}(C\alpha\lambda_{\ell+1})$.
Hence, $p_{n-1}$ decides $\bar{v}$ in its solo-terminating execution from
$C^{\prime}p_{j}R_{j}c_{n-1}$. Since $p_{n-1}$ cannot distinguish between
$C^{\prime}p_{j}R_{j}c_{n-1}$ and $C^{\prime}c_{n-1}$ and all of the objects
have the same values in these configurations, $p_{n-1}$ decides $\bar{v}$ in
its solo-terminating execution from $C^{\prime}c_{n-1}$ as well.

Since the configurations $C\alpha\lambda_{\ell+1}$ and $C\alpha
p_{i}R_{i}\lambda_{\ell+1}$ are indistinguishable to
$p_{\ell+1},\ldots,p_{n-1}$, all of the objects have the same values in these
two configurations, and $\alpha^{\prime}$ only contains events by
$p_{\ell+1},\ldots,p_{n-1}$, there exists an execution $\gamma$ from $C\alpha
p_{i}R_{i}\lambda_{\ell+1}$ that is indistinguishable from $\alpha^{\prime}$
to $p_{\ell+1},\ldots,p_{n-1}$. Hence, $p_{n-1}$ decides $\bar{v}$ in its
solo-terminating execution from $C\alpha p_{i}R_{i}\lambda_{\ell+1}\gamma
c_{n-1}$. However, since $p_{\ell}$ takes a step in $p_{i}R_{i}$, $\ell<n-1$,
$z\geq 1$, and $n\geq 2$, we can use the definition of
$\mathcal{E}_{z}^{\star}(C)$ to show that $\alpha
p_{i}R_{i}\lambda_{\ell+1}\gamma c_{n-1}\in\mathcal{E}^{\star}_{z}(C)$. Since
$\alpha p_{i}R_{i}\lambda_{\ell+1}$ is $v$-univalent with respect to
$\mathcal{E}^{\star}_{z}(C)$, process $p_{n-1}$ must decide $v$ in its solo-
terminating execution from $C\alpha p_{i}R_{i}\lambda_{\ell+1}\gamma c_{n-1}$.
This is a contradiction. We formalize this argument and consider the other
possible cases in the proof of the following lemma.

######  Lemma 12.

For any $k\in\\{\ell+1,\ldots,n-1\\}$ and any execution
$\alpha^{\prime}\in\mathcal{E}^{\star}_{z}(C\alpha X\lambda_{k})$ that
contains no events by $p_{0},\ldots,p_{k-1}$, if $\alpha^{\prime}$ is critical
with respect to $\mathcal{E}^{\star}_{z}(C^{\prime}X\lambda_{k})$, then
$C\alpha X\lambda_{k}\alpha^{\prime}$ is either $n$-recording or $v$-hiding.

###### Proof.

Notice that the lemma vacuously holds if $\ell=n-1$. To obtain a
contradiction, suppose that there exists some $\ell<n-1$ for which the lemma
does not hold. Then there exists $k\in\\{\ell+1,\ldots,n-1\\}$ and an
execution $\alpha^{\prime}\in\mathcal{E}^{\star}_{z}(C\alpha X\lambda_{k})$
that contains no events by $p_{0},\ldots,p_{k-1}$ such that $\alpha^{\prime}$
is critical with respect to $\mathcal{E}^{\star}_{z}(C\alpha X\lambda_{k})$
and $C\alpha X\lambda_{k}\alpha^{\prime}$ is neither $n$-recording nor
$v$-hiding.

Since $p_{i}$ is on team $v$ in $C\alpha$, we know that $\alpha p_{i}R_{i}$ is
$v$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$. Furthermore, since
$p_{\ell}$ takes a step in $p_{i}R_{i}$, $z\geq 1$, $n\geq 2$, and $\ell<k$,
we know that
$\textit{exec}(C\alpha,p_{i}R_{i}\lambda_{k})\in\mathcal{E}^{\star}_{z}(C\alpha)$
by definition of $\mathcal{E}_{z}^{\star}(C\alpha)$. Since
$\alpha\in\mathcal{E}^{\star}_{z}(C)$, Observation 3 implies that $\alpha
p_{i}R_{i}\lambda_{k}\in\mathcal{E}^{\star}_{z}(C)$. Hence, $\alpha
p_{i}R_{i}\lambda_{k}$ is $v$-univalent with respect to
$\mathcal{E}^{\star}_{z}(C)$ by Observation 2. In particular,
$\\{p_{k},\ldots,p_{n-1}\\}$ is $v$-univalent in $\alpha
p_{i}R_{i}\lambda_{k}$ with respect to $\mathcal{E}^{\star}_{z}(C)$. Notice
that $C\alpha p_{i}R_{i}\lambda_{k}$ and $C\alpha X\lambda_{k}$ are
indistinguishable to $p_{k},\ldots,p_{n-1}$ and all of the objects have the
same values in these two configurations. By Observation 5,
$\\{p_{k},\ldots,p_{n-1}\\}$ is $v$-univalent in $C\alpha X\lambda_{k}$ with
respect to $\mathcal{E}^{\star}_{z}(C\alpha X\lambda_{k})$. Since
$\alpha^{\prime}\in\mathcal{E}^{\star}_{z}(C\alpha X\lambda_{k})$ and
$\alpha^{\prime}$ only contains steps by $p_{k},\ldots,p_{n-1}$, Observation 2
implies that $\\{p_{k},\ldots,p_{n-1}\\}$ is $v$-univalent in
$\alpha^{\prime}$ with respect to $\mathcal{E}^{\star}_{z}(C\alpha
X\lambda_{k})$. In particular, $p_{n-1}$ is on team $v$ in $C\alpha
X\lambda_{k}\alpha^{\prime}$.22todo: 2might need some more detail

Since $C\alpha X\lambda_{k}$ and $C\alpha p_{i}R_{i}\lambda_{k}$ are
indistinguishable to $p_{k},\ldots,p_{n-1}$, all of the objects have the same
values in these two configurations, and $\alpha^{\prime}$ contains only events
by $p_{k},\ldots,p_{n-1}$, there exists an execution $\gamma$ from $C\alpha
p_{i}R_{i}\lambda_{k}$ containing only events by $p_{k},\ldots,p_{n-1}$ that
is indistinguishable from $\alpha^{\prime}$ to $p_{k},\ldots,p_{n-1}$.
Furthermore, since the schedules of $\alpha^{\prime}$ and $\gamma$ consisting
of the events by $p_{k},\ldots,p_{n-1}$ are the same,
$\gamma\in\mathcal{E}^{\star}_{z}(C\alpha p_{i}R_{i}\lambda_{k})$.

Since $\alpha p_{i}R_{i}\lambda_{k}\in\mathcal{E}^{\star}_{z}(C)$ and
$\gamma\in\mathcal{E}^{\star}_{z}(C\alpha p_{i}R_{i}\lambda_{k})$, Observation
3 implies that $\alpha
p_{i}R_{i}\lambda_{k}\gamma\in\mathcal{E}^{\star}_{z}(C)$. By the definition
of $\mathcal{E}^{\star}_{z}(C)$, for every process $p_{r}$ and every prefix
$\gamma^{\prime}$ of $\alpha p_{i}R_{i}\lambda_{k}\gamma$, the number of
crashes by $p_{r}$ is no greater than $zn$ times the number of steps
collectively taken by $p_{0},\ldots,p_{r-1}$ in $\gamma^{\prime}$. We now show
that $\alpha p_{i}R_{i}\lambda_{k}\gamma
c_{n-1}\in\mathcal{E}^{\star}_{z}(C)$. To do so, it suffices to prove that the
number of crashes by $p_{n-1}$ in $\alpha p_{i}R_{i}\lambda_{k}\gamma c_{n-1}$
is no greater than $zn$ times the number of steps collectively taken by
$p_{0},\ldots,p_{n-2}$ in $\alpha p_{i}R_{i}\lambda_{k}\gamma c_{n-1}$. To see
why this is true, first notice that $\alpha\in\mathcal{E}^{\star}_{z}(C)$ and
$\gamma\in\mathcal{E}^{\star}_{z}(C\alpha p_{i}R_{i}\lambda_{k})$. Hence, if
$s$ is the number of steps taken by $p_{0},\ldots,p_{n-2}$ in $\alpha$ and
$\gamma$, then the number of crashes by $p_{n-1}$ in $\alpha$ and $\gamma$ is
at most $zns$. Furthermore, since $p_{\ell}\in p_{i}R_{i}$, the processes
$p_{0},\ldots,p_{n-2}$ take at least $s+1$ steps and $p_{n-1}$ crashes at most
$zns+2$ times in $\alpha p_{i}R_{i}\lambda_{k}\gamma c_{n-1}$. Since $z\geq 1$
and $n\geq 2$, we have $zns+2\leq zns+zn=zn(s+1)$. Therefore, $\alpha
p_{i}R_{i}\lambda_{k}\gamma c_{n-1}\in\mathcal{E}^{\star}_{z}(C)$.

Since $\alpha p_{i}R_{i}$ is $v$-univalent with respect to
$\mathcal{E}^{\star}_{z}(C)$, $\alpha p_{i}R_{i}\lambda_{k}\gamma c_{n-1}$ is
also $v$-univalent with respect to $\mathcal{E}^{\star}_{z}(C)$ by Observation
2. Hence, $p_{n-1}$ decides $v$ in its solo-terminating execution from
$C\alpha p_{i}R_{i}\lambda_{k}\gamma c_{n-1}$.

Define $C^{\prime}=C\alpha X\lambda_{k}\alpha^{\prime}$. Since $C^{\prime}$ is
neither $n$-recording nor $v$-hiding by assumption, Observation 11 implies
that either $C^{\prime}$ is $\bar{v}$-hiding or there exists a process $p_{j}$
on team $v$ in $C^{\prime}$, a process $p_{m}$ on team $\bar{v}$ in
$C^{\prime}$, an $R_{j}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{j}\\}\bigr{)}$,
and an $R_{m}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{m}\\}\bigr{)}$ such that
$\textit{value}(O,C^{\prime}p_{j}R_{j})=\textit{value}(O,C^{\prime}p_{m}R_{m})$.
We proceed by considering these two cases separately.

In the first case, $C^{\prime}$ is $\bar{v}$-hiding. Then there exists a
process $p_{m}$ on team $\bar{v}$ in $C^{\prime}$ and a schedule
$R_{m}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{m}\\}\bigr{)}$ such that _value_
$(O,C^{\prime}p_{m}R_{m})=$ _value_ $(O,C^{\prime})$. Since $p_{n-1}$ is on
team $v$ in $C^{\prime}$, we know that $p_{m}\neq p_{n-1}$, that is, $m<n-1$.
Hence, $p_{m}R_{m}c_{n-1}\in\mathcal{E}^{\star}_{z}(C^{\prime})$. Since
$\alpha^{\prime}\in\mathcal{E}^{\star}_{z}(C\alpha X\lambda_{k})$, Observation
3 implies that
$\alpha^{\prime}p_{m}R_{m}c_{n-1}\in\mathcal{E}^{\star}_{z}(C\alpha
X\lambda_{k})$. Since $p_{m}$ is on team $\bar{v}$ in $C^{\prime}$,
$\alpha^{\prime}p_{m}R_{m}c_{n-1}$ is $\bar{v}$-univalent with respect to
$\mathcal{E}^{\star}_{z}(C\alpha X\lambda_{k})$. Then $p_{n-1}$ decides
$\bar{v}$ in its solo-terminating execution from
$C^{\prime}p_{m}R_{m}c_{n-1}$. Since all of the objects have the same values
in $C^{\prime}c_{n-1}$ and $C^{\prime}p_{m}R_{m}c_{n-1}$ and these two
configurations are indistinguishable to $p_{n-1}$, we know that $p_{n-1}$
decides $\bar{v}$ in its solo-terminating execution from $C^{\prime}c_{n-1}$
as well. Furthermore, $C^{\prime}c_{n-1}$ and $C\alpha
p_{i}R_{i}\lambda_{k}\gamma c_{n-1}$ are indistinguishable to $p_{n-1}$ and
all of the objects have the same values in these configurations. Therefore,
$p_{n-1}$ decides $\bar{v}$ in its solo-terminating execution from $C\alpha
p_{i}R_{i}\lambda_{k}\gamma c_{n-1}$ as well, which is a contradiction.

Now suppose that there exists a process $p_{j}$ on team $v$ in $C^{\prime}$, a
process $p_{m}$ on team $\bar{v}$ in $C^{\prime}$, an
$R_{j}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{j}\\}\bigr{)}$, and an
$R_{m}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{m}\\}\bigr{)}$ such that
$\textit{value}(O,C^{\prime}p_{j}R_{j})=\textit{value}(O,C^{\prime}p_{m}R_{m})$.
Recall that $p_{n-1}$ is on team $v$ in $C^{\prime}$. By Lemma 10,
$p_{j}=p_{n-1}$ and $R_{j}=\langle\rangle$. Hence,
$\textit{value}(O,C^{\prime}p_{n-1})=\textit{value}(O,C^{\prime}p_{m}R_{m})$.
Thus, all of the objects have the same values in $C^{\prime}p_{n-1}c_{n-1}$
and $C^{\prime}p_{m}R_{m}c_{n-1}$ and these two configurations are
indistinguishable to $p_{n-1}$. Since $p_{m}\neq p_{n-1}$, we have $m<n-1$.
Hence,
$\textit{exec}(C^{\prime},p_{m}R_{m}c_{n-1})\in\mathcal{E}^{\star}_{z}(C^{\prime})$.
Since $\alpha^{\prime}\in\mathcal{E}^{\star}_{z}(C\alpha X\lambda_{k})$,
Observation 3 implies that
$\alpha^{\prime}p_{m}R_{m}c_{n-1}\in\mathcal{E}^{\star}_{z}(C\alpha
X\lambda_{k})$. By Observation 2, $\alpha^{\prime}p_{m}R_{m}c_{n-1}$ is
$\bar{v}$-univalent with respect to $\mathcal{E}^{\star}_{z}(C\alpha
X\lambda_{k})$. Hence, $p_{n-1}$ decides $\bar{v}$ in its solo-terminating
executions from $C^{\prime}X\lambda_{k}\alpha^{\prime}p_{m}R_{m}c_{n-1}$ and
$C\alpha X\lambda_{k}\alpha^{\prime}p_{n-1}c_{n-1}$. This implies that
$p_{n-1}$ decides $\bar{v}$ in its solo-terminating execution from $C\alpha
p_{i}R_{i}\lambda_{k}\gamma p_{n-1}c_{n-1}$ as well.

Since $\alpha p_{i}R_{i}\lambda_{k}\gamma
c_{n-1}\in\mathcal{E}^{\star}_{z}(C)$, we know that $\alpha
p_{i}R_{i}\lambda_{k}\gamma p_{n-1}c_{n-1}\in\mathcal{E}^{\star}_{z}(C)$ as
well. Since $\alpha p_{i}R_{i}$ is $v$-univalent with respect to
$\mathcal{E}^{\star}_{z}(C)$, the execution $\alpha
p_{i}R_{i}\lambda_{k}\gamma p_{n-1}c_{n-1}$ is also $v$-univalent with respect
to $\mathcal{E}^{\star}_{z}(C)$ by Observation 2. Therefore, $p_{n-1}$ decides
$v$ in its solo-terminating execution from $C\alpha
p_{i}R_{i}\lambda_{k}\gamma p_{n-1}c_{n-1}$. This is a contradiction. Hence,
$C^{\prime}=C\alpha X\lambda_{k}\alpha^{\prime}$ is $v$-hiding. ∎

We will now prove our main theorem. To do so, we will consider an arbitrary
recoverable wait-free consensus algorithm using objects with types
$\mathcal{T}_{0},\mathcal{T}_{1},\mathcal{T}_{2},\ldots$, and we will apply
Lemma 12 to inductively construct a chain of $v$-hiding configurations
$D_{1}^{\prime},\ldots,D_{\ell-1}^{\prime}$ followed by an $n$-recording
configuration $D_{\ell}^{\prime}$. Every configuration $D_{i}^{\prime}$ is
reachable from some configuration $D_{i}$ via an execution $\alpha_{i}$ that
is critical with respect to $\mathcal{E}^{\star}_{1}(D_{i})$. The main idea of
the argument is to force longer and longer suffixes of $p_{0},\ldots,p_{n-1}$
to be on team $v$ in the $v$-hiding configurations, until eventually we either
reach an $n$-recording configuration in which some process $p_{i}$ with $i>0$
is on team $\bar{v}$, or we reach a configuration that is $v$-hiding and in
which only $p_{0}$ is on team $\bar{v}$. Such a configuration is also
$n$-recording.

$C$$D_{0}$$D_{0}^{\prime}$$D_{1}$$D_{1}^{\prime}$$p_{n-1}$ decides
$v$$p_{n-1}$ decides
$v$$\mathrel{\overset{p_{0},\ldots,p_{n-2}}{\scalebox{1.5}[1.0]{$\sim$}}}$$\mathrel{\overset{p_{n-1}}{\scalebox{1.5}[1.0]{$\sim$}}}$$\alpha_{0}p_{i}R_{i}$
is $v$-univalent w.r.t. $\mathcal{E}^{\star}_{1}(D_{0})$$\alpha_{0}p_{n-1}$ is
$\bar{v}$-univalent w.r.t. $\mathcal{E}^{\star}_{1}(D_{0})$$\alpha_{1}$ is
critical w.r.t.
$\mathcal{E}^{\star}_{1}(D_{1})$$\beta$$\alpha_{0}$$p_{n-1}$$c_{n-1}$$\alpha_{1}$$p_{n-1}$-only$p_{n-1}$-only$p_{i}R_{i}$$c_{n-1}$$p_{n-1}$-only
Figure 1: The construction of $D_{1}$ and $D_{1}^{\prime}$ when
$D_{0}^{\prime}$ is neither $n$-recording nor $v$-hiding for any
$v\in\\{0,1\\}$. Any configuration $C$ with a double outline is bivalent with
respect to $\mathcal{E}^{\star}_{1}(C)$.

######  Theorem 13.

If there exists a recoverable wait-free consensus algorithm for $n>1$
processes using objects with deterministic types
$\mathcal{T}_{0},\mathcal{T}_{1},\mathcal{T}_{2},\ldots$, then at least one of
the types $\mathcal{T}_{i}$ is $n$-recording.

###### Proof.

We construct a chain of configurations
$D_{0},D_{0}^{\prime},\ldots,D_{\ell},D_{\ell}^{\prime}$ where $\ell\leq n-1$
and a value $v\in\\{0,1\\}$ such that every process is poised to access the
same object $O$ in $D_{0}^{\prime},\ldots,D_{\ell}^{\prime}$, the
configuration $D_{\ell}^{\prime}$ is $n$-recording, and, for all
$i\in\\{0,\ldots,\ell\\}$,

  1. (a)

$D_{i}$ is bivalent with respect to $\mathcal{E}^{\star}_{1}(D_{i})$,

  2. (b)

$D_{i}^{\prime}$ is reachable from $D_{i}$ via a schedule
$\alpha_{i}\in\mathcal{E}^{\star}_{1}(D_{i})$,

  3. (c)

$\alpha_{i}$ is critical with respect to $\mathcal{E}^{\star}_{1}(D_{i})$,

  4. (d)

if $\ell>i>0$, then $D_{i}^{\prime}$ is $v$-hiding and not $n$-recording,

  5. (e)

$p_{n-i},\ldots,p_{n-1}$ are on team $v$ in $D_{i}^{\prime}$, and

  6. (f)

$D_{i}^{\prime}$ is reachable from $D_{0}$ via an execution $\delta_{i}$
containing only events by $p_{n-i},\ldots,p_{n-1}$ such that, for each process
$p_{k}\in\\{p_{n-i},\ldots,p_{n-1}\\}$, the number of times $p_{k}$ crashes in
$\delta_{i}$ is no more than $ns+i$, where $s$ is the number of steps by
$p_{n-i},\ldots,p_{k-1}$ in $\delta_{i}$.

Since $D_{\ell}^{\prime}$ is $n$-recording and every process is poised to
access $O$ in $D_{\ell}^{\prime}$, this proves that the type of $O$ is
$n$-recording.

We now show how to construct this sequence of configurations. Let $C$ be some
initial configuration in which $p_{0}$ has input $0$ and $p_{1}$ has input
$1$. By Observation 1, $C$ is bivalent with respect to
$\mathcal{E}^{\star}_{1}(C)$. By Lemma 6 (b), there exists a finite execution
$\beta\in\mathcal{E}_{2}(C)$ such that $C\beta$ is bivalent with respect to
$\mathcal{E}^{\star}_{1}(C\beta)$ and, for every nonempty finite schedule
$\gamma$ such that $\beta\gamma\in\mathcal{E}_{2}(C)$, the configuration
$C\beta\gamma$ is univalent with respect to
$\mathcal{E}^{\star}_{1}(C\beta\gamma)$.

Define $D_{0}=C\beta$. Then $D_{0}$ is bivalent with respect to
$\mathcal{E}_{1}^{\star}(D_{0})$, giving us property (a) for $i=0$. Lemma 6
(a) implies that there exists a finite execution
$\alpha_{0}\in\mathcal{E}^{\star}_{1}(D_{0})$ such that $\alpha_{0}$ is
critical with respect to $\mathcal{E}^{\star}_{1}(D_{0})$. Define
$D_{0}^{\prime}=D_{0}\alpha_{0}$. This gives us properties (b) and (c) for
$i=0$. By Lemma 9, every process is poised to access the same object $O$ in
$D_{0}\alpha_{0}$. Properties (d) and (e) hold vacuously for $i=0$.

Since $\alpha_{0}\in\mathcal{E}^{\star}_{1}(D_{0})$ and
$\mathcal{E}^{\star}_{1}(D_{0})\subset\mathcal{E}_{2}(D_{0})$, Observation 3
implies that $\beta\alpha_{0}\in\mathcal{E}_{2}(C)$. Since
$D_{0}^{\prime}=C\beta\alpha_{0}$ is bivalent with respect to
$\mathcal{E}^{\star}_{1}(D_{0}^{\prime})$ by Lemma 8, $\alpha_{0}$ must be
empty by Lemma 6 (b). Define $\delta_{0}=\alpha_{0}$. This gives us property
(f) for $i=0$. If $D_{0}^{\prime}$ is $n$-recording, then define
$D_{\ell}=D_{0}=C\beta$ and $D_{\ell}^{\prime}=D_{0}^{\prime}=C\beta\alpha$.
This completes the construction of $D_{0}$ and $D_{0}^{\prime}$.

Before defining $D_{i}$ and $D_{i}^{\prime}$, we first show how to define
$D_{1}$ and $D_{1}^{\prime}$ in the special case in which $D_{0}^{\prime}$ is
neither $n$-recording nor $v$-hiding for any $v\in\\{0,1\\}$.

### Defining $D_{1}$ and $D_{1}^{\prime}$ when $D_{0}^{\prime}$ is neither
$n$-recording nor $v$-hiding

By Observation 11, there exists a process $p_{i}$ on team $v$ in
$D_{0}^{\prime}$, a process $p_{j}$ on team $\bar{v}$ in $D_{0}^{\prime}$, an
$R_{i}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{i}\\}\bigr{)}$, and an
$R_{j}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{j}\\}\bigr{)}$ such that _value_
$(O,D_{0}^{\prime}p_{i}R_{i})=$ _value_ $(O,D_{0}^{\prime}p_{j}R_{j})$.
Without loss of generality, suppose that $p_{n-1}$ is on team $\bar{v}$. By
Lemma 10, $p_{j}=p_{n-1}$ and $R_{j}=\langle\rangle$. Since $p_{i}$ is on team
$v$ in $D_{0}^{\prime}$ and $p_{n-1}$ is on team $\bar{v}$ in
$D_{0}^{\prime}$, we know that $p_{i}$ and $p_{n-1}$ are different processes,
that is, $i<n-1$. Since $p_{i}$ is on team $v$ in $D_{0}^{\prime}$, it must be
the case that $\alpha_{0}p_{i}R_{i}$ is $v$-univalent with respect to
$\mathcal{E}^{\star}_{1}(D_{0})$. We know that
$p_{i}R_{i}c_{n-1}\in\mathcal{E}^{\star}_{1}(D_{0}^{\prime})$ because $i<n-1$.
By Observation 3, $\alpha p_{i}R_{i}c_{n-1}\in\mathcal{E}^{\star}_{1}(D_{0})$.
Therefore, Observation 2 implies that $\alpha p_{i}R_{i}c_{n-1}$ is
$v$-univalent with respect to $\mathcal{E}^{\star}_{1}(D_{0})$. Then $p_{n-1}$
decides $v$ in its solo-terminating execution from
$D_{0}^{\prime}p_{i}R_{i}c_{n-1}$. Since all of the base objects have the same
values in $D_{0}^{\prime}p_{i}R_{i}c_{n-1}$ and $D_{0}^{\prime}p_{n-1}c_{n-1}$
and these two configurations are indistinguishable to $p_{n-1}$, process
$p_{n-1}$ decides $v$ in its solo-terminating execution from
$D_{0}^{\prime}p_{n-1}c_{n-1}$ as well. Similarly, since all of the objects
have the same values in $D_{0}^{\prime}p_{n-1}$ and
$D_{0}^{\prime}p_{n-1}c_{n-1}$, these two configurations are indistinguishable
to $p_{0}$, and $\alpha p_{n-1}$ is $\bar{v}$-univalent with respect to
$\mathcal{E}^{\star}_{1}(D_{0})$, we know that $p_{0}$ decides $\bar{v}$ in
its solo-terminating execution from $D_{0}^{\prime}p_{n-1}c_{n-1}$. Therefore,
$D_{0}^{\prime}p_{n-1}c_{n-1}$ is bivalent with respect to
$\mathcal{E}^{\star}_{1}(D_{0}^{\prime}p_{n-1}c_{n-1})$. Define
$D_{1}=D_{0}^{\prime}p_{n-1}c_{n-1}$. This gives us property (a) for $i=1$. By
Lemma 6 (a), there exists a finite execution
$\alpha_{1}\in\mathcal{E}^{\star}_{1}(D_{1})$ such that $\alpha_{1}$ is
critical with respect to $\mathcal{E}^{\star}_{1}(D_{1})$. Define
$D_{1}^{\prime}=D_{1}\alpha_{1}$. This gives us properties (b) and (c) for
$i=1$.

We claim that $\alpha_{1}$ contains no steps by $p_{0},\ldots,p_{n-2}$. To
obtain a contradiction, suppose that $\alpha_{1}$ contains at least one step
by some process $p_{0},\ldots,p_{n-2}$. Recall that
$\alpha_{0}\in\mathcal{E}^{\star}_{1}(D_{0})$ and
$\alpha_{1}\in\mathcal{E}^{\star}_{1}(D_{1})$. Hence, if $s$ is the number of
steps taken by $p_{0},\ldots,p_{n-2}$ in $\alpha_{0}$ and $\alpha_{1}$
together, then $p_{n-1}$ crashes at most $ns$ times in these executions. The
processes $p_{0},\ldots,p_{n-2}$ also take $s$ steps in
$\alpha_{0}p_{n-1}c_{n-1}\alpha_{1}$ and $p_{n-1}$ crashes at most $ns+1$
times in this execution. Since some process in $p_{0},\ldots,p_{n-2}$ takes a
step in $\alpha_{1}$, we have $s\geq 1$. Furthermore, $n\geq 2$, and so
$ns+1<2ns$. Then process $p_{n-1}$ crashes at most $2n$ times the number of
steps by $p_{0},\ldots,p_{n-2}$ in $\alpha_{0}p_{n-1}c_{n-1}\alpha_{1}$.
Hence, $\alpha_{0}p_{n-1}c_{n-1}\alpha_{1}\in\mathcal{E}_{2}(D_{0})$. Recall
that $D_{0}=C\beta$, where $\beta\in\mathcal{E}_{2}(C)$. Observation 3 implies
that $\beta\alpha_{0}p_{n-1}c_{n-1}\alpha_{1}\in\mathcal{E}_{2}(C)$.
Furthermore, since $\alpha_{1}$ is critical with respect to
$\mathcal{E}^{\star}_{1}(D_{1})$, the configuration
$D_{1}^{\prime}=C\beta\alpha_{0}p_{n-1}c_{n-1}\alpha_{1}$ is bivalent with
respect to $\mathcal{E}^{\star}_{1}(D_{1}^{\prime})$ by Lemma 8. This
contradicts Lemma 6 (b). Therefore, $\alpha_{1}$ only contains steps by
$p_{n-1}$.

Since $\alpha_{1}$ only contains events by $p_{n-1}$ and $p_{n-1}$ decides $v$
in its solo-terminating execution from $D_{1}$, we know that $p_{n-1}$ decides
$v$ in its solo-terminating execution from $D_{1}^{\prime}=D_{1}\alpha_{1}$ as
well. Hence, $p_{n-1}$ is on team $v$ in $D_{1}^{\prime}$. This gives us
property (e) for $i=1$.

Define $\delta_{1}=\alpha_{0}p_{n-1}c_{n-1}\alpha_{1}$. Since
$\alpha_{1}\in\mathcal{E}^{\star}_{1}(D_{1})$ and $\alpha_{1}$ contains only
steps by $p_{n-1}$, no crashes occur in $\alpha_{1}$. Since $\alpha_{0}$ is
empty, process $p_{n-1}$ crashes exactly once in
$\delta_{1}=\alpha_{0}p_{n-1}c_{n-1}\alpha_{1}$. This gives us property (f)
for $i=1$.

By Lemma 9, every process is poised to access the same object in
$D_{1}^{\prime}$. Since $p_{0},\ldots,p_{n-1}$ are poised to access $O$ in
$D_{0}^{\prime}$ and $p_{0},\ldots,p_{n-2}$ take no steps during
$p_{n-1}c_{n-1}\alpha^{\prime}$, every process is poised to access $O$ in
$D_{1}^{\prime}$ as well. By Lemma 12, $D_{1}^{\prime}$ is either
$n$-recording or $v$-hiding. If $D_{1}^{\prime}$ is $n$-recording, then define
$D_{\ell}=D_{1}$ and $D_{\ell}^{\prime}=D_{1}^{\prime}$. Otherwise,
$D_{1}^{\prime}$ is $v$-hiding and not $n$-recording, which gives us property
(d) for $i=1$. This case is depicted in Figure 1.

$D_{i-1}$$D_{i-1}^{\prime}$$D_{i}$$D_{i}^{\prime}$$p_{j}$ decides
$\bar{v}$$\alpha_{i-1}p_{k}R_{k}$ is $v$-univalent w.r.t.
$\mathcal{E}^{\star}_{1}(D_{i-1})$$\alpha_{i-1}p_{j}$ is $\bar{v}$-univalent
w.r.t. $\mathcal{E}^{\star}_{1}(D_{i-1})$$p_{n-i},\ldots,p_{n-1}$ on team
$v$$\mathrel{\overset{p_{j}}{\scalebox{1.5}[1.0]{$\sim$}}}$$\mathrel{\overset{p_{n-i},\ldots,p_{n-1}}{\scalebox{1.5}[1.0]{$\sim$}}}$$\alpha_{i-1}$$p_{k}R_{k}$$\lambda_{n-i}$$\lambda_{n-i}$$\alpha_{i}$$p_{j}$,
$j<n-i$$p_{j}$-only
Figure 2: The construction of $D_{i}$ and $D_{i}^{\prime}$. Configurations $C$
with a double outline are bivalent w.r.t. $\mathcal{E}^{\star}_{1}(C)$.

### Defining $D_{i}$ and $D_{i}^{\prime}$

Suppose that we have constructed the sequence
$D_{0},D_{0}^{\prime},\ldots,D_{i-1},D_{i-1}^{\prime}$ for some $i\geq 1$.
(Note that in the previous subsection, we covered the case in which
$D_{0}^{\prime}$ is not $v$-hiding, for any $v\in\\{0,1\\}$; therefore, we
only consider the case in which $D_{i-1}^{\prime}$ is $v$-hiding.) Define
$D_{i}=D_{i-1}^{\prime}\lambda_{n-i}$.

By property (e) for $i-1$, all of the processes $p_{n-i+1},\ldots,p_{n-1}$ are
on team $v$ in $D_{i-1}^{\prime}$. Furthermore, if $p_{n-i}$ is the only
process on team $\bar{v}$ in $D_{i-1}^{\prime}$, then $D_{i-1}^{\prime}$ is
$n$-recording, which contradicts property (d) for $i-1$. Hence, there is some
process $p_{j}$ on team $\bar{v}$ in $D_{i-1}^{\prime}$ such that $j<n-i$.

Since $D_{i-1}^{\prime}$ is $v$-hiding by property (d) for $i-1$, there exists
a process $p_{k}$ on team $v$ and an
$R_{k}\in\mathcal{S}\bigl{(}\mathcal{P}-\\{p_{k}\\}\bigr{)}$ such that
$\textit{value}(O,D_{i-1}^{\prime}p_{k}R_{k})=\textit{value}(O,D_{i-1}^{\prime})$.
We claim that $p_{j}\in R_{k}$. To obtain a contradiction suppose that
$p_{j}\not\in R_{k}$. Then $D_{i-1}^{\prime}p_{j}$ and
$D_{i-1}^{\prime}p_{k}R_{k}p_{j}$ are indistinguishable to $p_{j}$.
Furthermore, since all of the objects have the same values in
$D_{i-1}^{\prime}$ and $D_{i-1}^{\prime}p_{k}R_{k}$, all of the objects have
the same values in $D_{i-1}^{\prime}p_{j}$ and
$D_{i-1}^{\prime}p_{k}R_{k}p_{j}$ as well. Therefore, $p_{j}$ decides the same
value in its solo-terminating executions from $D_{i-1}^{\prime}p_{j}$ and
$D_{i-1}^{\prime}p_{k}R_{k}p_{j}$. However, since $p_{k}$ is on team $v$ in
$D_{i-1}^{\prime}$ and $p_{j}$ is on team $\bar{v}$ in $D_{i-1}^{\prime}$, the
execution $\alpha_{i-1}p_{k}R_{k}p_{j}$ is $v$-univalent with respect to
$\mathcal{E}^{\star}_{1}(D_{i-1})$ and $\alpha_{i-1}p_{j}$ is
$\bar{v}$-univalent with respect to $\mathcal{E}^{\star}_{1}(D_{i-1})$.
Therefore, $p_{j}$ decides $v$ in its solo-terminating execution from
$D_{i-1}^{\prime}p_{k}R_{k}p_{j}$ and $\bar{v}$ in its solo-terminating
execution from $D_{i-1}^{\prime}p_{j}$. This is a contradiction. Hence,
$p_{j}\in R_{k}$.

Since $p_{j}\in R_{k}$ and $j<n-i$, we know that
$\textit{exec}(D_{i-1}^{\prime},p_{k}R_{k}\lambda_{n-i})\in\mathcal{E}^{\star}_{1}(D_{i-1}^{\prime})$.
By Observation 3 and the fact that
$\alpha_{i-1}\in\mathcal{E}^{\star}_{1}(D_{i-1})$, it follows that
$\alpha_{i-1}p_{k}R_{k}\lambda_{n-i}\in\mathcal{E}^{\star}_{1}(D_{i-1})$.
Since $\alpha_{i-1}p_{k}R_{k}$ is $v$-univalent with respect to
$\mathcal{E}^{\star}_{1}(D_{i-1})$, Observation 2 implies that
$\alpha_{i-1}p_{k}R_{k}\lambda_{n-i}$ is $v$-univalent with respect to
$\mathcal{E}^{\star}_{1}(D_{i-1})$ as well. Since
$D_{i-1}\alpha_{i-1}p_{k}R_{k}\lambda_{n-i}$ and
$D_{i}=D_{i-1}^{\prime}\lambda_{n-i}$ are indistinguishable to
$p_{n-i},\ldots,p_{n-1}$ and all of the objects have the same values in these
two configurations, Observation 5 implies that $\\{p_{n-i},\ldots,p_{n-1}\\}$
is $v$-univalent in $D_{i}$ with respect to $\mathcal{E}^{\star}_{1}(D_{i})$
as well.

Since $p_{j}$ is on team $\bar{v}$ in $D_{i-1}^{\prime}$, it decides $\bar{v}$
in its solo-terminating execution from $D_{i-1}^{\prime}$. Notice that
$D_{i-1}^{\prime}$ and $D_{i}=D_{i-1}^{\prime}\lambda_{n-i}$ are
indistinguishable to $p_{j}$ and all of the objects have the same values in
these two configurations. Therefore, $p_{j}$ decides $\bar{v}$ in its solo-
terminating execution from $D_{i}$ as well. Hence, $D_{i}$ is bivalent with
respect to $\mathcal{E}^{\star}_{1}(D_{i})$. This gives us property (a) for
$i$. By Lemma 6 (a), there exists a finite schedule $\alpha_{i}$ such that
$\alpha_{i}\in\mathcal{E}^{\star}_{1}(D_{i})$ and $\alpha_{i}$ is critical
with respect to $\mathcal{E}^{\star}_{1}(D_{i})$. Define
$D_{i}^{\prime}=D_{i}\alpha_{i}$. This gives us properties (b) and (c) for
$i$. The construction of $D_{i}$ and $D_{i}^{\prime}$ is depicted in Figure 2.

We claim that the execution $\alpha_{i}$ contains no steps by
$p_{0},\ldots,p_{n-i-1}$. To obtain a contradiction, suppose the claim is
false. By property (f) for $i-1$, $D_{i-1}^{\prime}$ is reachable from $D_{0}$
via an execution $\delta_{i-1}$ containing only events by
$p_{n-i+1},\ldots,p_{n-1}$ such that, for every process
$p_{k}\in\\{p_{n-i+1},\ldots,p_{n-1}\\}$, the number of times $p_{k}$ crashes
in $\delta_{i-1}$ is no more than $ns_{k}+i-1$, where $s_{k}$ is the number of
steps by $p_{n-i},\ldots,p_{k-1}$ in $\delta_{i-1}$. Since
$\alpha_{i}\in\mathcal{E}^{\star}_{1}(D_{i})$, the number of times any process
$p_{k}$ crashes in $\alpha_{i}$ is no more than $ns_{k}^{\prime}$, where
$s_{k}^{\prime}$ is the number of steps by $p_{0},\ldots,p_{k-1}$ in
$\alpha_{i}$. Since each process $p_{n-i},\ldots,p_{n-1}$ crashes exactly once
in $\lambda_{n-i}$, every process $p_{k}\in\\{p_{n-i},\ldots,p_{n-1}\\}$
crashes at most $n(s_{k}+s_{k}^{\prime})+i$ times in
$\delta_{i-1}\lambda_{n-i}\alpha_{i}$. Since $i\leq n-1$ and
$s_{k}^{\prime}\geq 1$ for all $p_{k}\in\\{p_{n-i},\ldots,p_{n-1}\\}$ by
assumption, we have $n(s_{k}+s_{k}^{\prime})+i\leq 2n(s_{k}+s_{k}^{\prime})$.
In other words, the number of crashes by each process
$p_{k}\in\\{p_{n-i},\ldots,p_{n-1}\\}$ in
$\delta_{i-1}\lambda_{n-i}\alpha_{i}$ is no more than $2n$ times the number of
steps taken by $p_{0},\ldots,p_{k-1}$ in
$\delta_{i-1}\lambda_{n-i}\alpha_{i}$. Since $\delta_{i-1}\lambda_{n-i}$
contains no events by $p_{0},\ldots,p_{n-i-1}$ and
$\alpha_{i}\in\mathcal{E}^{\star}_{1}(D_{i})$, the number of crashes by each
process $p_{k}\in\\{p_{0},\ldots,p_{n-i-1}\\}$ in
$\delta_{i-1}\lambda_{n-i}\alpha_{i}$ is no more than $n$ times the number of
steps taken by $p_{0},\ldots,p_{k-1}$ in
$\delta_{i-1}\lambda_{n-i}\alpha_{i}$. Hence,
$\delta_{i-1}\lambda_{n-i}\alpha_{i}\in\mathcal{E}_{2}(D_{0})$. Observation 3
implies that $\beta\delta_{i-1}\lambda_{n-i}\alpha_{i}\in\mathcal{E}_{2}(C)$.
However, Lemma 8 implies that
$D_{i}^{\prime}=C\beta\delta_{i-1}\lambda_{n-i}\alpha_{i}$ is bivalent with
respect to $\mathcal{E}^{\star}_{1}(D_{i}^{\prime})$. This contradicts Lemma 6
(b). Hence, $\alpha_{i}$ contains no steps by $p_{0},\ldots,p_{n-i-1}$. By
definition of $\mathcal{E}^{\star}_{1}(D_{i})$, $\alpha_{i}$ also contains no
crashes by $p_{0},\ldots,p_{n-i-1}$. Therefore, $\alpha_{i}$ contains no
events by $p_{0},\ldots,p_{n-i-1}$.

Define $\delta_{i}=\delta_{i-1}\lambda_{n-i}\alpha_{i}$. Since $\delta_{i}$
has no events by $p_{0},\ldots,p_{n-i-1}$, each process
$p_{k}\in\\{p_{n-i},\ldots,p_{n-1}\\}$ crashes at most
$n(s_{k}+s_{k}^{\prime})+i$ times in $\delta_{i}$, where $s_{k}$ is the number
of steps taken by $p_{n-i},\ldots,p_{n-1}$ in $\delta_{i-1}$ and
$s_{k}^{\prime}$ is the number of steps taken by $p_{n-i},\ldots,p_{n-1}$ in
$\alpha_{i}$. This gives us property (f) for $i$.

By Lemma 12, $D_{i}^{\prime}$ is either $n$-recording or $v$-hiding. If
$D_{i}^{\prime}$ is $n$-recording, then define $D_{\ell}=D_{i}$ and
$D_{\ell}^{\prime}=D_{i}^{\prime}$. Otherwise, $D_{i}^{\prime}$ is $v$-hiding
and not $n$-recording, which gives us property (d) for $i$. Since
$\\{p_{n-i},\ldots,p_{n-1}\\}$ is $v$-univalent in
$D_{i}=D_{i-1}^{\prime}\lambda_{n-i}$ with respect to
$\mathcal{E}^{\star}_{1}(D_{i})$ and $\alpha_{i}$ only contains events by
$p_{n-i},\ldots,p_{n-1}$, Observation 2 implies that
$\\{p_{n-i},\ldots,p_{n-1}\\}$ is $v$-univalent in $\alpha_{i}$ with respect
to $\mathcal{E}^{\star}_{1}(D_{i})$. Therefore, $p_{n-i},\ldots,p_{n-1}$ are
all on team $v$ in $D_{i}^{\prime}$. This gives us property (e) for $i$. This
completes the construction.

∎

Delporte-Gallet, Fatourou, Fauconnier, and Ruppert [5] showed that, if a
deterministic, readable type is $n$-recording, then objects of that type can
be used along with registers to solve recoverable wait-free consensus among
$n$ processes. Their result combined with Theorem 13 gives us the following.

######  Theorem 14.

The recoverable consensus hierarchy is robust for deterministic, readable
types.

##  4 Non-readable Types

For all $n>n^{\prime}\geq 1$, we describe a non-readable type
$\mathcal{T}_{n,n^{\prime}}$ that has consensus number $n$ and recoverable
consensus number $n^{\prime}$. The type $\mathcal{T}_{n,n^{\prime}}$ has three
operations, $op_{0}$, $op_{1}$, and $op_{R}$, and $2n$ values $s$, $s_{\bot}$,
and $s_{x,i}$, where $x\in\\{0,1\\}$ and $i\in\\{1,\ldots,n-1\\}$. Applying
$op_{0}$ to an object of $\mathcal{T}_{n,n^{\prime}}$ with value $s$ returns
$0$ and changes its value to $s_{0,1}$. Similarly, applying $op_{1}$ to an
object of $\mathcal{T}_{n,n^{\prime}}$ with value $s$ returns $1$ and changes
its value to $s_{1,1}$. Applying either $op_{0}$ or $op_{1}$ to an object with
value $s_{x,i}$, for some $x\in\\{0,1\\}$ and $i<n-1$, returns $x$ and changes
its value to $s_{x,i+1}$. Applying either $op_{0}$ or $op_{1}$ to an object
with value $s_{x,n-1}$ returns $x$ and changes the value to $s_{\bot}$. When
the object has value $s_{\bot}$, applying any operation returns $\bot$ and
does not change the value of the object.

The operation $op_{R}$ is similar to _Read_ unless the object has value
$s_{x,i}$ for some $x\in\\{0,1\\}$ and $i>n^{\prime}$. More specifically, when
an object of $\mathcal{T}_{n,n^{\prime}}$ has value $s$, applying $op_{R}$
returns $s$ and does not change the value. Applying $op_{R}$ when the object
has value $s_{x,i}$ where $i\leq n^{\prime}$ returns $s_{x,i}$ and does not
change the value. If $i>n^{\prime}$, then applying $op_{R}$ to an object with
value $s_{x,i}$ returns $\bot$ and changes its value to $s_{\bot}$. The state
machine diagram of type $\mathcal{T}_{5,2}$ is given in Figure 3.

$s$$s_{0,1}$$s_{0,2}$$s_{0,3}$$s_{0,4}$$op_{R}$ returns
$\bot$$s_{1,1}$$s_{1,2}$$s_{1,3}$$s_{1,4}$$s_{\bot}$$op_{0}$ returns
$0$$op_{0},op_{1}$ returns $0$$op_{0},op_{1}$ returns $0$$op_{0},op_{1}$
returns $0$$op_{0},op_{1}$ returns $0$$op_{1}$ returns $1$$op_{0},op_{1}$
returns $1$$op_{0},op_{1}$ returns $1$$op_{0},op_{1}$ returns
$1$$op_{0},op_{1}$ returns $1$$op_{R}$ returns $s_{0,1}$$op_{R}$ returns
$s_{0,2}$$op_{R}$ returns $s_{1,1}$$op_{R}$ returns
$s_{1,2}$$op_{0},op_{1},op_{R}$ returns $\bot$$op_{R}$ returns $s$ Figure 3:
The state machine diagram of the type $\mathcal{T}_{5,2}$.

We now argue that wait-free binary consensus can be solved among $n$ processes
using a single object $O$ of type $\mathcal{T}_{n,n^{\prime}}$. The object $O$
begins with value $s$. A process with input $x\in\\{0,1\\}$ applies $op_{x}$
to $O$ and decides the value returned by the operation. Notice that the first
operation applied to $O$ in the algorithm determines the value returned by the
next $n-1$ operations applied to $O$. Therefore, the algorithm satisfies
agreement. The object $O$ can only have value $s_{v,i}$, for some
$v\in\\{0,1\\}$ and some $i\in\\{1,\ldots,n-1\\}$, if the first operation
applied to $O$ was $op_{v}$. Since a process only applies $op_{v}$ when it has
input $v$, the algorithm satisfies validity. Finally, each process applies
only one operation, so the algorithm satisfies wait-freedom. A standard
valency argument shows that consensus number of $\mathcal{T}_{n,n^{\prime}}$
is at most $n$. We perform this valency argument in the proof of the following
lemma.

######  Lemma 15.

The consensus number of type $\mathcal{T}_{n,n^{\prime}}$ is $n$.

###### Proof.

We already showed that the consensus number of $\mathcal{T}_{n,n^{\prime}}$ is
at least $n$. To complete the proof, we now show that the consensus number of
$\mathcal{T}_{n,n^{\prime}}$ is at most $n$. For this proof, we use standard
definitions of valency. A configuration $C$ is _bivalent_ if, for all
$v\in\\{0,1\\}$, there exists an execution $\beta_{v}$ from $C$ such that some
process has decided $v$ in $C\beta_{v}$. A configuration is _$v$ -univalent_
if, for every execution $\beta$ from $C$ such that some process has decided a
value in $C\beta$, that value is $v$. To obtain a contradiction, suppose that
there is a wait-free algorithm that solves consensus among $n+1$ processes
$p_{0},\ldots,p_{n}$ using instances of $\mathcal{T}_{n,n^{\prime}}$ along
with registers. Let $C$ be a bivalent initial configuration of the algorithm
in which process $p_{0}$ has input $0$ and $p_{1}$ has input $1$. Using a
standard argument, we can show that there is an execution from $C$ that leads
to a _critical_ configuration $C^{\prime}$, that is, the configuration
$C^{\prime}$ is bivalent and $C^{\prime}p_{i}$ is univalent, for all $i$.
Since $n+1>1$, a standard argument shows that every process is poised to
access the same object $O$ of type $\mathcal{T}_{n,n^{\prime}}$ in
$C^{\prime}$. Define $T_{v}$ to be the set of processes $p_{i}$ such that
$C^{\prime}p_{i}$ is $v$-univalent, and define $o_{i}$ as the operation that
$p_{i}$ is poised to apply to $O$ in $C^{\prime}$ for all
$i\in\\{0,\ldots,n\\}$.

First suppose that $o_{i}=op_{R}$ for some $i$, where $p_{i}\in T_{v}$. Then
either $\textit{value}(O,C^{\prime}p_{i})=\textit{value}(O,C^{\prime})$ or
$\textit{value}(O,C^{\prime}p_{i})=s_{\bot}$. In either case,
$\textit{value}(O,C^{\prime}p_{i}p_{j})=\textit{value}(O,C^{\prime}p_{j})$,
where $p_{j}\in T_{\bar{v}}$. Since $n>n^{\prime}\geq 1$, we have $n+1\geq 3$.
Hence, there is a process $p_{k}$ different from $p_{i}$ and $p_{j}$. Then
$C^{\prime}p_{i}p_{j}$ and $C^{\prime}p_{j}$ are indistinguishable to $p_{k}$
and all of the objects have the same values in these two configurations.
Hence, $p_{k}$ decides the same value in its solo-terminating executions from
$C^{\prime}p_{i}p_{j}$ and $C^{\prime}p_{j}$. However, $C^{\prime}p_{i}p_{j}$
is $v$-univalent and $C^{\prime}p_{j}$ is $\bar{v}$-univalent. This is a
contradiction Hence, all of the operations $o_{0},\ldots,o_{n}$ are either
$op_{0}$ or $op_{1}$.

Let $p_{i}\in T_{0}$, $p_{j}\in T_{1}$, and let $p_{k}$ be some process other
than $p_{i}$ and $p_{j}$. Since each operation $o_{0},\ldots o_{n}$ is either
$op_{0}$ or $op_{1}$, for any schedule $\sigma$ containing all $n$ processes
besides $p_{k}$, $\textit{value}(O,C^{\prime}\sigma)=s_{\bot}$. Let
$\sigma_{i}$ and $\sigma_{j}$ be two schedules containing all $n$ processes
besides $p_{k}$ such that $\sigma_{i}$ begins with $p_{i}$ and $\sigma_{j}$
begins with $p_{j}$. Then $C^{\prime}\sigma_{i}$ and $C^{\prime}\sigma_{j}$
are indistinguishable to $p_{k}$ and all of the objects have the same values
in these two configurations. Hence, $p_{k}$ decides the same value in its
solo-terminating executions from $C^{\prime}\sigma_{i}$ and
$C^{\prime}\sigma_{j}$. However, $C^{\prime}\sigma_{i}$ is $v$-univalent and
$C^{\prime}\sigma_{j}$ is $\bar{v}$-univalent. This is a contradiction. Hence,
the consensus number of $\mathcal{T}_{n,n^{\prime}}$ is at most $n$. This
completes the proof that the consensus number of $\mathcal{T}_{n,n^{\prime}}$
is $n$. ∎

We first argue that recoverable wait-free binary consensus can be solved among
$n^{\prime}$ processes using a single object $O$ of type
$\mathcal{T}_{n,n^{\prime}}$. The object $O$ begins with value $s$. A process
with input $x\in\\{0,1\\}$ first applies $op_{R}$. If the operation returns a
value $s_{v,i}$, then the process decides $v$. If the operation returns
$\bot$, then the process decides $0$ (we will argue that this never happens).
Otherwise, the operation returns the initial value $s$. In this case, the
process applies $op_{x}$ and then decides the value returned.

Notice that any process with input $x\in\\{0,1\\}$ applies at most one
$op_{x}$ operation, because $op_{0}$ and $op_{1}$ change the value of $O$ from
$s$ to $s_{0,1}$ and $s_{1,1}$, respectively, and once $O$ has a value
different from $s$ it can never have value $s$ again. To change the value of
$O$ from its initial value $s$ to $s_{v,i}$, at least $i$ $op_{0}$ and
$op_{1}$ operations must be applied. Since there are $n^{\prime}$ processes,
the object $O$ can never have value $s_{v,i}$ where $i>n^{\prime}$ during any
execution of our algorithm. Therefore, none of the $op_{R}$ operations can
return $\bot$, and the first $op_{x}$ operation applied to $O$ where
$x\in\\{0,1\\}$ determines the value returned by all subsequent operations.
Hence, the algorithm satisfies agreement. The object $O$ can only have value
$s_{v,i}$, for some $v\in\\{0,1\\}$ and some $i\in\\{1,\ldots,n^{\prime}\\}$,
if the first operation applied to $O$ was $op_{v}$. A process only applies
$op_{v}$ if it has input $v$, so the algorithm satisfies validity. Finally,
starting from its initial state, each process applies at most $2$ operations
to $O$ before deciding, so the algorithm satisfies recoverable wait-freedom.

By considering the set of executions $\mathcal{E}^{\star}_{m}(C)$, where
$m=\lceil\frac{n}{2}\rceil$ and $C$ is an initial configuration that is
bivalent with respect to $\mathcal{E}^{\star}_{m}(C)$, we can perform a
valency argument to prove that the recoverable consensus number of
$\mathcal{T}_{n,n^{\prime}}$ is at most $n^{\prime}$. First, we use Lemma 6
(a) to obtain an execution $\alpha$ that is critical with respect to
$\mathcal{E}^{\star}_{m}(C)$. Lemma 9 can be used along with a standard
argument to show that every process is poised to access the same object $O$ of
type $\mathcal{T}_{n,n^{\prime}}$ in $C\alpha$. We then show that every
process must be poised to apply $op_{0}$ or $op_{1}$ in $C\alpha$. Consider
two permutations $\sigma_{0}$ and $\sigma_{1}$ of
$p_{0},\ldots,p_{n^{\prime}}$, where $\sigma_{0}$ begins with a process on
team $0$ in $C\alpha$ and $\sigma_{1}$ begins with a process on team $1$ in
$C\alpha$. Since each process applies either $op_{0}$ or $op_{1}$ in
$\sigma_{0}$ and $\sigma_{1}$, we argue that the value of $O$ in
$C\alpha\sigma_{0}$ and $C\alpha\sigma_{1}$ must be either $s_{\bot}$ or
$s_{v,i}$ for some $v\in\\{0,1\\}$ and $i>n^{\prime}$. Hence, in any
executions from $C\alpha\sigma_{0}$ or $C\alpha\sigma_{1}$, any process that
applies $op_{R}$ to $O$ will “break” the object by changing its value to
$s_{\bot}$. Using this, we construct two executions $\rho$ and $\tau$ from
$C\alpha\sigma_{0}$ and $C\alpha\sigma_{1}$, respectively, each containing
only steps by $p_{n^{\prime}}$ such that $p_{n^{\prime}}$ decides the same
value in $\rho$ and $\tau$. By showing that $\alpha\sigma_{0}\rho$ and
$\alpha\sigma_{1}\tau$ are both in $\mathcal{E}^{\star}_{m}(C)$, we obtain a
contradiction. We formalize this valency argument in the proof of the
following lemma.

######  Lemma 16.

The recoverable consensus number of type $\mathcal{T}_{n,n^{\prime}}$
$n^{\prime}$.

###### Proof.

We already showed that the recoverable consensus number of
$\mathcal{T}_{n,n^{\prime}}$ is at least $n^{\prime}$. We now show that the
recoverable consensus number of $\mathcal{T}_{n,n^{\prime}}$ is at most
$n^{\prime}$. To obtain a contradiction, suppose that there is a recoverable
wait-free consensus algorithm for $n^{\prime}+1$ processes
$p_{0},\ldots,p_{n^{\prime}}$ using objects of $\mathcal{T}_{n,n^{\prime}}$
and registers. Let $C$ be an initial configuration of this algorithm in which
$p_{0}$ has input $0$ and $p_{1}$ has input $1$. Let
$m=\lceil\frac{n}{2}\rceil$. By Observation 1, $C$ is bivalent with respect to
$\mathcal{E}^{\star}_{m}(C)$. By Lemma 6 (a), there exists a finite execution
$\alpha\in\mathcal{E}^{\star}_{m}(C)$ such that $\alpha$ is critical with
respect to $\mathcal{E}^{\star}_{m}(C)$. Lemma 7 implies that there is a
process on team $0$ in $C\alpha$ and there is a process on team $1$ in
$C\alpha$.

Lemma 9 implies that all of the processes are poised to access the same object
$O$ in $C\alpha$. Since there are $n^{\prime}+1$ processes and
$n^{\prime}+1>1$, a standard argument can be used to show that $O$ is not a
register, that is, $O$ is an object of $\mathcal{T}_{n,n^{\prime}}$. For all
$i\in\\{0,\ldots,n^{\prime}\\}$, define $o_{i}$ as the operation that $p_{i}$
is poised to apply to $O$ in $C\alpha$. First suppose that $o_{i}=op_{R}$ for
some $i$, where $p_{i}$ is on team $v$ in $C\alpha$. Then either
$\textit{value}(O,C\alpha p_{i})=\textit{value}(O,C\alpha)$ or
$\textit{value}(O,C\alpha p_{i})=s_{\bot}$. Let $p_{j}$ be a process on team
$\bar{v}$ in $C\alpha$. In case $\textit{value}(O,C\alpha
p_{i})=\textit{value}(O,C\alpha)$, notice that $C\alpha p_{i}$ and $C\alpha$
are indistinguishable to $p_{j}$ and all of the objects have the same values
in these two configurations, so $p_{j}$ decides the same value in its solo-
terminating executions from $C\alpha p_{i}p_{j}$ and $C\alpha p_{j}$. However,
$\alpha p_{i}p_{j}$ is $v$-univalent with respect to
$\mathcal{E}^{\star}_{m}(C)$ and $\alpha p_{j}$ is $\bar{v}$-univalent with
respect to $\mathcal{E}^{\star}_{m}(C)$, which is a contradiction. Otherwise,
$\textit{value}(O,C\alpha p_{i})=s_{\bot}$. Notice that
$\textit{value}(O,C\alpha p_{j}p_{i})=s_{\bot}$ in this case, no matter what
$o_{j}$ is. Suppose that $i<j$ (the case in which $j<i$ is symmetric), so that
$\textit{exec}(C\alpha,p_{i}c_{j})$ and
$\textit{exec}(C\alpha,p_{j}p_{i}c_{j})$ are in
$\mathcal{E}^{\star}_{m}(C\alpha)$. By Observation 3, $\alpha p_{i}c_{j}$ and
$\alpha p_{j}p_{i}c_{j}$ are in $\mathcal{E}^{\star}_{m}(C)$. Hence, by
Observation 2, $\alpha p_{i}c_{j}$ is $v$-univalent with respect to
$\mathcal{E}^{\star}_{m}(C)$ and $\alpha p_{j}p_{i}c_{j}$ is
$\bar{v}$-univalent with respect to $\mathcal{E}^{\star}_{m}(C)$. But $C\alpha
p_{i}c_{j}$ and $C\alpha p_{j}p_{i}c_{j}$ are indistinguishable to $p_{j}$ and
all of the objects have the same values in these two configurations.
Therefore, $p_{j}$ decides the same values in its solo-terminating executions
from $C\alpha p_{i}c_{j}$ and $C\alpha p_{j}p_{i}c_{j}$, which is a
contradiction. Hence, $o_{0},\ldots,o_{n^{\prime}}$ are all either $op_{0}$ or
$op_{1}$.

Let $\sigma_{0}$ be some permutation of $p_{0},\ldots,p_{n^{\prime}}$
beginning with a process on team $0$ in $C\alpha$, and let $\sigma_{1}$ be a
permutation beginning with a process on team $1$ in $C\alpha$. We proceed by
constructing an execution $\rho$ from $C\alpha\sigma_{0}$ and an execution
$\tau$ from $C\alpha\sigma_{1}$ such that $\rho$ and $\tau$ contain only steps
by $p_{n^{\prime}}$, the executions $\textit{exec}(C\alpha,\sigma_{0})\rho$
and $\textit{exec}(C\alpha,\sigma_{1})\tau$ are both in
$\mathcal{E}^{\star}_{m}(C\alpha)$,
$C\alpha\sigma_{0}\rho\mathrel{\overset{p_{n^{\prime}}}{\scalebox{1.5}[1.0]{$\sim$}}}C\alpha\sigma_{1}\tau$,
and $p_{n^{\prime}}$ has decided the same value in $C\alpha\sigma_{0}\rho$ and
$C\alpha\sigma_{1}\tau$. Observation 3 implies that
$\alpha\sigma_{0}\rho\in\mathcal{E}^{\star}_{m}(C)$ and
$\alpha\sigma_{1}\tau\in\mathcal{E}^{\star}_{m}(C)$. Hence, by Observation 2,
$\alpha\sigma_{0}\rho$ is $0$-univalent with respect to
$\mathcal{E}^{\star}_{m}(C)$ and $\alpha\sigma_{1}\tau$ is $1$-univalent with
respect to $\mathcal{E}^{\star}_{m}(C)$. This is a contradiction.

We will construct $\rho$ and $\tau$ inductively. We define
$\rho_{0},\rho_{1},\ldots,\rho_{\ell}$ and
$\tau_{0},\tau_{1},\ldots,\tau_{\ell}$ such that $p_{n^{\prime}}$ has decided
in $C\alpha\sigma_{0}\rho_{\ell}$ and $C\alpha\sigma_{1}\tau_{\ell}$,
$\ell<n-n^{\prime}-1$, and, for all $i\in\\{0,\ldots,\ell\\}$,

  * •

$C\alpha\sigma_{0}\rho_{i}\mathrel{\overset{p_{n^{\prime}}}{\scalebox{1.5}[1.0]{$\sim$}}}C\alpha\sigma_{0}\tau_{i}$,

  * •

if $i<\ell$, then $p_{n^{\prime}}$ crashes exactly $i+1$ times in $\rho_{i}$
and $\tau_{i}$, and $p_{n^{\prime}}$ crashes either $\ell$ or $\ell+1$ times
in $\rho_{\ell}$ and $\tau_{\ell}$,

  * •

if $i<\ell$, then
$\textit{value}(O,C\alpha\sigma_{0}\rho_{i})=s_{v,n^{\prime}+1+i+j}$ for some
$v\in\\{0,1\\}$ and some $j\geq 0$,

  * •

if $i<\ell$, then
$\textit{value}(O,C\alpha\sigma_{1}\tau_{i})=s_{v^{\prime},n^{\prime}+1+i+j}$
for some $v^{\prime}\in\\{0,1\\}$, and

Define $\rho_{0}=\tau_{0}=c_{n^{\prime}}$. Then
$C\alpha\sigma_{0}\rho_{0}\mathrel{\overset{p_{n^{\prime}}}{\scalebox{1.5}[1.0]{$\sim$}}}C\alpha\sigma_{1}\tau_{0}$.
Recall that $\sigma_{0}$ and $\sigma_{1}$ are both permutations of
$p_{0},\ldots,p_{n^{\prime}}$. Therefore, if $\textit{value}(O,C\alpha)=s$,
then either $\textit{value}(O,C\alpha\sigma_{0})=s_{v,n^{\prime}+1}$ and
$\textit{value}(O,C\alpha\sigma_{1})=s_{v^{\prime},n^{\prime}+1}$ (if
$n^{\prime}+1<n$), or
$\textit{value}(O,C\alpha\sigma_{0})=\textit{value}(O,C\alpha\sigma_{1})=s_{\bot}$
(if $n^{\prime}+1=n$). Similarly, if $\textit{value}(O,C\alpha)=s_{v,j}$, then
either $\textit{value}(O,C\alpha\sigma_{0})=s_{v,j+n^{\prime}+1}$ and
$\textit{value}(O,C\alpha\sigma_{1})=s_{v,j+n^{\prime}+1}$ (if
$j+n^{\prime}+1<n$), or
$\textit{value}(O,C\alpha\sigma_{0})=\textit{value}(O,C\alpha\sigma_{1})=s_{\bot}$
(if $j+n^{\prime}+1\geq n$). Finally, if $\textit{value}(O,C\alpha)=s_{\bot}$,
then
$\textit{value}(O,C\alpha\sigma_{0})=\textit{value}(O,C\alpha\sigma_{1})=s_{\bot}$.
In any of these cases, if
$\textit{value}(O,C\alpha\sigma_{0})=\textit{value}(O,C\alpha\sigma_{1})=s_{\bot}$,
then define $\ell=0$.

Now suppose that we have constructed $\rho_{i}$ and $\tau_{i}$ where $0\leq
i<\ell$. Then
$\textit{value}(O,C\alpha\sigma_{0}\rho_{i})=s_{v,n^{\prime}+1+i+j}$ and
$\textit{value}(O,C\alpha\sigma_{1}\tau_{i})=s_{v^{\prime},n^{\prime}+1+i+j}$
for some $j\geq 0$. Let $\delta$ be the $p_{n^{\prime}}$-only execution from
$C\alpha\sigma_{0}\rho_{i}$ in which $p_{n^{\prime}}$ takes steps until either
it decides a value or it is poised to apply an operation to $O$. Since all of
the objects except possibly $O$ have the same values in
$C\alpha\sigma_{0}\rho_{i}$ and $C\alpha\sigma_{1}\tau_{i}$ and
$C\alpha\sigma_{0}\rho_{i}\mathrel{\overset{p_{n^{\prime}}}{\scalebox{1.5}[1.0]{$\sim$}}}C\alpha\sigma_{1}\tau_{i}$,
there is a $p_{n^{\prime}}$-only execution $\delta^{\prime}$ from
$C\alpha\sigma_{1}\tau_{i}$ such that
$\delta\mathrel{\overset{p_{n^{\prime}}}{\scalebox{1.5}[1.0]{$\sim$}}}\delta^{\prime}$.
If $p_{n^{\prime}}$ has decided in $C\alpha\sigma_{0}\rho_{i}\delta$ and
$C\alpha\sigma_{1}\tau_{i}\delta^{\prime}$, then define
$\rho_{i+1}=\rho_{i}\delta$, $\tau_{i+1}=\tau_{i}\delta^{\prime}$, and
$\ell=i+1$. Notice that $p_{n^{\prime}}$ has crashed exactly $i+1=\ell$ times
in $\rho_{\ell}$ and $\tau_{\ell}$ in this case. Otherwise, define
$\rho_{i+1}=\rho_{i}\delta p_{n^{\prime}}c_{n^{\prime}}$ and
$\tau_{i+1}=\rho_{i}\delta^{\prime}p_{n^{\prime}}c_{n^{\prime}}$. Notice that
$C\alpha\sigma_{0}\rho_{i+1}\mathrel{\overset{p_{n^{\prime}}}{\scalebox{1.5}[1.0]{$\sim$}}}C\alpha\sigma_{1}\tau_{i+1}$.
If $p_{n^{\prime}}$ was poised to apply $op_{R}$ in
$C\alpha\sigma_{0}\rho_{i}\delta$ and
$C\alpha\sigma_{1}\tau_{i}\delta^{\prime}$ or $n^{\prime}+1+i+j=n-1$, then
$\textit{value}(O,C\alpha\sigma_{0}\rho_{i}\delta
p_{n^{\prime}}c_{n^{\prime}})=\textit{value}(O,C\alpha\sigma_{1}\tau_{i}\delta^{\prime}p_{n^{\prime}}c_{n^{\prime}})=s_{\bot}$.
In this case, define $\ell=i+1$. Otherwise, $p_{n^{\prime}}$ is poised to
apply $op_{0}$ or $op_{1}$ in these two configurations,
$n^{\prime}+1+i+j<n-1$,
$\textit{value}(O,C\alpha\sigma_{0}\rho_{i}\delta)=s_{v,n^{\prime}+1+i+j}$,
and
$\textit{value}(O,C\alpha\sigma_{1}\tau_{i}\delta^{\prime})=s_{v^{\prime},n^{\prime}+1+i+j}$.
In this case, when $p_{n^{\prime}}$ applies $op_{0}$ or $op_{1}$ in
$C\alpha\sigma_{0}\rho_{i}\delta$, it changes the value of $O$ to
$s_{v,n^{\prime}+2+i+j}$. Similarly, when $p_{n^{\prime}}$ applies $op_{0}$ or
$op_{1}$ in $C\alpha\sigma_{1}\tau_{i}\delta$, it changes the value of $O$ to
$s_{v^{\prime},n^{\prime}+2+i+j}$. Finally, $p_{n^{\prime}}$ does not crash
during $\delta$ or $\delta^{\prime}$, so $p_{n^{\prime}}$ crashes exactly
$i+2$ times in $\rho_{i+1}=\rho_{i}\delta p_{n^{\prime}}c_{n^{\prime}}$ and
$\tau_{i+1}=\tau_{i}\delta^{\prime}p_{n^{\prime}}c_{n^{\prime}}$. This
completes the construction.

Define $\rho=\sigma_{0}\rho_{\ell}$ and $\tau=\sigma_{1}\tau_{\ell}$. Since
$p_{n^{\prime}}$ crashes at most $\ell+1<n-n^{\prime}$ times in $\rho$ and
$\tau$ and $p_{0}$ takes a step in $\sigma_{0}$ and $\sigma_{1}$, we know that
the number of crash steps by $p_{n^{\prime}}$ in any prefix of $\rho$ or
$\tau$ is at most $n-n^{\prime}\leq n-1$ times the number of steps
collectively taken by $p_{0},\ldots,p_{n^{\prime}-1}$ in that prefix. Since
$n-1\leq\lceil\frac{n}{2}\rceil\cdot
2\leq\lceil\frac{n}{2}\rceil\cdot(n^{\prime}+1)=m\cdot(n^{\prime}+1)$, we know
that $\rho,\tau\in\mathcal{E}^{\star}_{m}(C\alpha)$. This completes the proof.
∎

Lemma 15 and Lemma 16 together say that the consensus number of
$\mathcal{T}_{n,n^{\prime}}$ is $n$ and the recoverable consensus number of
$\mathcal{T}_{n,n^{\prime}}$ is $n^{\prime}$. Hence, the ability of a non-
readable type to solve recoverable wait-free consensus can be much lower than
its ability to solve wait-free consensus.

##  5 Conclusion

In this paper, we proved that the recoverable consensus hierarchy is robust
for deterministic, readable types. To accomplish this, we proved that
Delporte-Gallet, Fatourou, Fauconnier, and Ruppert’s [5] $n$-recording
condition is necessary for solving recoverable wait-free consensus among $n$
processes using deterministic types. These authors originally proved that any
deterministic, readable type with consensus number $n$ has recoverable
consensus number at least $n-2$, though it remained an open question to
determine whether there exists a type with consensus number $n$ and
recoverable consensus number $n-2$. However, for all $n\geq 4$, they defined a
deterministic, readable type $\mathcal{X}_{n}$ that is $n$-discerning,
$(n-2)$-recording, but not $(n-1)$-recording. Our results show that
$\mathcal{X}_{n}$ has recoverable consensus number $n-2$, resolving the open
question above.

We also showed that the gap between the consensus number and recoverable
consensus number of a deterministic, non-readable type can be arbitrarily
large. It is still unknown whether the recoverable consensus hierarchy is
robust for all deterministic types.

## Acknowledgements

I gratefully acknowledge the support of the Natural Sciences and Engineering
Research Council of Canada (NSERC), PDF-578266-2023. I also thank Trevor Brown
for providing feedback on an earlier draft of this paper. Finally, I thank the
anonymous reviewers for their feedback.

## References

  * [1]
  * Attiya et al. [2018] Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler. 2018\.  Nesting-Safe Recoverable Linearizability: Modular Constructions for Non-Volatile Memory. In _Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing_ (Egham, United Kingdom) _(PODC ’18)_. Association for Computing Machinery, New York, NY, USA, 7–16.  https://doi.org/10.1145/3212734.3212753
  * Attiya and Ellen [2014] Hagit Attiya and Faith Ellen. 2014.  _Impossibility Results for Distributed Computing_.  Morgan & Claypool Publishers.  https://doi.org/10.2200/S00551ED1V01Y201311DCT012
  * Berryhill et al. [2016] Ryan Berryhill, Wojciech Golab, and Mahesh Tripunitara. 2016\.  Robust Shared Objects for Non-Volatile Main Memory. In _19th International Conference on Principles of Distributed Systems (OPODIS 2015)_ _(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 46)_ , Emmanuelle Anceaume, Christian Cachin, and Maria Potop-Butucaru (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 20:1–20:17.  https://doi.org/10.4230/LIPIcs.OPODIS.2015.20
  * Delporte-Gallet et al. [2022] Carole Delporte-Gallet, Panagiota Fatourou, Hugues Fauconnier, and Eric Ruppert. 2022.  When is Recoverable Consensus Harder Than Consensus?. In _Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing_ (Salerno, Italy) _(PODC’22)_. Association for Computing Machinery, New York, NY, USA, 198–208.  https://doi.org/10.1145/3519270.3538418
  * Fischer et al. [1985] Michael Fischer, Nancy Lynch, and Mike Paterson. 1985\.  Impossibility of Distributed Consensus with One Faulty Process.  _J. ACM_ 32 (Apr. 1985), 374–382.  https://doi.org/10.1145/3149.214121
  * Friedman et al. [2018] Michal Friedman, Maurice Herlihy, Virendra Marathe, and Erez Petrank. 2018.  A persistent lock-free queue for non-volatile memory. In _Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming_ (Vienna, Austria) _(PPoPP ’18)_. Association for Computing Machinery, New York, NY, USA, 28–40.  https://doi.org/10.1145/3178487.3178490
  * Golab [2020] Wojciech Golab. 2020\.  The Recoverable Consensus Hierarchy. In _Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures_ (Virtual Event, USA) _(SPAA ’20)_. Association for Computing Machinery, New York, NY, USA, 281–291.  https://doi.org/10.1145/3350755.3400212
  * Golab and Ramaraju [2016] Wojciech Golab and Aditya Ramaraju. 2016.  Recoverable Mutual Exclusion: [Extended Abstract]. In _Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing_ (Chicago, Illinois, USA) _(PODC ’16)_. Association for Computing Machinery, New York, NY, USA, 65–74.  https://doi.org/10.1145/2933057.2933087
  * Herlihy [1991] Maurice Herlihy. 1991\.  Wait-Free Synchronization.  13, 1 (Jan. 1991), 124–149.  https://doi.org/10.1145/114005.102808
  * Herlihy and Ruppert [2000] Maurice Herlihy and Eric Ruppert. 2000.  On the existence of booster types. In _Proceedings of the 41st Annual Symposium on Foundations of Computer Science_. 653–663.  https://doi.org/10.1109/SFCS.2000.892333
  * Herlihy and Shavit [1999] Maurice Herlihy and Nir Shavit. 1999.  The Topological Structure of Asynchronous Computability.  _J. ACM_ 46, 6 (Nov. 1999), 858–923.  https://doi.org/10.1145/331524.331529 A preliminary version appeared in PODC ’93.
  * Jayanti [1997] Prasad Jayanti. 1997\.  Robust wait-free hierarchies.  _J. ACM_ 44, 4 (jul 1997), 592–614.  https://doi.org/10.1145/263867.263888
  * Lo and Hadzilacos [2000] Wai-Kau Lo and Vassos Hadzilacos. 2000.  All of Us Are Smarter than Any of Us: Nondeterministic Wait-Free Hierarchies Are Not Robust.  _SIAM J. Comput._ 30, 3 (2000), 689–728.  https://doi.org/10.1137/S0097539798335766 arXiv:https://doi.org/10.1137/S0097539798335766
  * Ruppert [2000] Eric Ruppert. 2000\.  Determining Consensus Numbers.  _SIAM J. Comput._ 30, 4 (2000), 1156–1168.  https://doi.org/10.1137/S0097539797329439 arXiv:https://doi.org/10.1137/S0097539797329439
  * Schenk [1996] Eric Schenk. 1996\.  _Computability and complexity results for agreement problems in shared memory distributed systems_.  Ph. D. Dissertation. University of Toronto.