lemtheorem lem coroltheorem corol observationtheorem observation

# Tight Lower Bounds for the RMR Complexity of Recoverable Mutual Exclusion

David Yu Cheng Chan<EMAIL_ADDRESS>University of
CalgaryCalgaryAlbertaCanada and  Philipp Woelfel<EMAIL_ADDRESS>University of CalgaryCalgaryAlbertaCanada

(2021)

###### Abstract.

We present a tight RMR complexity lower bound for the recoverable mutual
exclusion (RME) problem, defined by Golab and Ramaraju (Golab and Ramaraju,
2019). In particular, we show that any $n$-process RME algorithm using only
atomic read, write, fetch-and-store, fetch-and-increment, and compare-and-swap
operations, has an RMR complexity of $\Omega(\log n/\log\log n)$ on the CC and
DSM model. This lower bound covers all realistic synchronization primitives
that have been used in RME algorithms and matches the best upper bounds of
algorithms employing swap objects (e.g., (Golab and Hendler, 2017; Jayanti et
al., 2019; Dhoked and Mittal, 2020)).

Algorithms with better RMR complexity than that have only been obtained by
either (i) assuming that all failures are system-wide (Golab and Hendler,
2018), (ii) employing fetch-and-add objects of size $(\log n)^{\omega(1)}$
(Katzan and Morrison, 2020), or (iii) using artificially defined
synchronization primitives that are not available in actual systems (Golab and
Hendler, 2017; Jayanti et al., 2018).

recoverable mutual exclusion, asynchronous system, shared memory, fetch and
increment

††journalyear: 2021††copyright: acmlicensed††conference: Proceedings of the
2021 ACM Symposium on Principles of Distributed Computing; July 26–30, 2021;
Virtual Event, Italy††booktitle: Proceedings of the 2021 ACM Symposium on
Principles of Distributed Computing (PODC ’21), July 26–30, 2021, Virtual
Event, Italy††price: 15.00††doi: 10.1145/3465084.3467938††isbn:
978-1-4503-8548-0/21/07††ccs: Theory of computation Shared memory
algorithms††ccs: Software and its engineering Mutual exclusion††ccs: Computer
systems organization Reliability

##  1\. Introduction

Recent research on the mutual exclusion problem has focused on _recoverable_
algorithms (Ramaraju, 2015; Jayanti and Joshi, 2017; Dhoked and Mittal, 2020;
Jayanti et al., 2018; Golab and Hendler, 2018, 2017; Golab and Ramaraju, 2019;
Jayanti et al., 2019; Chan and Woelfel, 2020; Katzan and Morrison, 2020).
Here, a process may crash at any point during the execution, upon which its
entire local state is being reset, including all its local program variables.
Shared memory, however, is not affected by process crashes. When a process
crashes, it starts a recovery routine that allows it to resume participation
in the mutual exclusion protocol. This variant of mutual exclusion has been
motivated by recent advances in non-volatile memory architectures (Golab and
Ramaraju, 2019).

The standard complexity measure for mutual exclusion algorithms is RMR
complexity. The RMR complexity of conventional, non-recoverable $n$-process
mutual exclusion is well understood: If only read-write registers and compare-
and-swap objects are available, then a worst-case RMR complexity of
$\Theta(\log n)$ is optimal (Yang and Anderson, 1995; Attiya et al., 2008).
Using other standard synchronization primitives, such as fetch-and-store
(swap) or fetch-and-increment, the RMR complexity can be reduced to $O(1)$
(Mellor-Crummey and Scott, 1991; Craig, 1993; Magnusson et al., 1994).

Recoverable mutual exclusion is seemingly harder: Many algorithms use fetch-
and-store objects, and the best ones achieve an RMR complexity of $\Theta(\log
n/\log\log n)$ (Golab and Hendler, 2017; Jayanti et al., 2019). To study what
it takes to achieve better RMR complexity than that, artificially defined
synchronization primitives have been used that do not exist in actual hardware
(Golab and Hendler, 2017; Jayanti et al., 2018). Katzan and Morrison (Katzan
and Morrison, 2020) observed that one can obtain an RMR complexity of
$O(\log_{w}n)$ using $w$-bit fetch-and-add objects. In particular, if
$w=n^{\varepsilon}$ for some $\varepsilon>0$, then constant RMR complexity is
possible. But it is a standard (and reasonable) assumption that $w=O(\log n)$.
Even for poly-logarithmic values of $w$ their algorithm does not beat the best
known upper bounds of $O(\log n/\log\log n)$.

It is therefore not surprising that it has been stated as an open problem (see
e.g., (Katzan and Morrison, 2020; Chan and Woelfel, 2020)), whether there are
algorithms with better RMR complexity. In this paper we provide an answer, for
almost all standard synchronization primitives that have been used to solve
RME, with the exception of fetch-and-add. (For fetch-and-add objects that can
store $w=(\log n)^{\omega(1)}$ bits, the lower bound does not apply due to
(Katzan and Morrison, 2020), but for the more realistic assumption $w=(\log
n)^{O(1)}$ it remains open if there exist algorithms with $o(\log n/\log\log
n)$ RMR complexity.)

###### Theorem 1.

Any deadlock-free $n$-process RME algorithm, where all objects support only
read, write, fetch-and-store, fetch-and-increment, and compare-and-swap
operations, has RMR complexity $\Omega(\log n/\log\log n)$ in the CC and the
DSM model.

This lower bound is tight: It shows that the algorithms by Golab and Hendler
(Golab and Hendler, 2017) (for the CC model) and Jayanti, Jayanti, and Joshi
(Jayanti et al., 2019) (for the CC and DSM model) are optimal. Both algorithms
use registers and fetch-and-store objects, and (Golab and Hendler, 2017) also
uses compare-and-swap. The lower bound demonstrates for the first time, that
RME is strictly harder than non-recoverable mutual exclusion, because, as
mentioned above, the latter has constant RMR complexity if fetch-and-store or
fetch-and-increment objects and registers are available (Mellor-Crummey and
Scott, 1991; Craig, 1993; Magnusson et al., 1994). Chan and Woelfel (Chan and
Woelfel, 2020) gave an RME algorithm with constant _amortized_ RMR complexity
using fetch-and-increment and compare-and-swap objects in addition to
registers. Thus, our result separates worst-case from amortized RMR complexity
for RME. Interestingly, for non-recoverable mutual exclusion, worst-case and
amortized RMR complexity is the same for any subset of primitives (that
includes at least read-write registers) to which our lower bound applies. It
is also worth pointing out that our lower bound applies to all deadlock-free
RME algorithms, and does not rely on the critical-section re-entry property,
which is usually required for RME.

In addition, Golab and Hendler (Golab and Hendler, 2018) showed that with the
stricter system-wide failure model (all processes crash simultaneously), there
exist RME algorithms with $O(1)$ RMR complexity. Thus our lower bound also
demonstrates that RME is strictly harder in the more general failure model
that allows processes to crash independently than in the system-wide failure
model.

Recently, Dhoked and Mittal (Dhoked and Mittal, 2020) gave an algorithm that
adapts to the number of process crashes (in the “recent” past), $F$. In
particular, they achieve an RMR complexity of $O(\min\\{\sqrt{F},\log
n/\log\log n\\})$. In our proof we construct an execution, in which one
process incurs $\Omega(\log n/\log\log n)$ RMRs, even though each process
attempts to enter the critical section at most once and crashes at most once.
This shows that the RMR complexity of mutual exclusion algorithms, such as the
one by Dhoked and Mittal, can only adapt to the _total number_ of
crashes—bounding the number of crashes per process does not not suffice to
improve RMR complexity.

##  2\. Preliminaries

We consider the standard asynchronous shared memory model, where $n$ processes
with unique IDs communicate by executing atomic operations (called steps) on
shared base objects.

A mutual exclusion algorithm is a shared (implemented) object that supports
methods Enter() and Exit(), and calls to these methods must alternate,
starting with Enter(). A process is in the _critical section_ when it has
finished an Enter() call but not yet called Exit(). It is in the _remainder
section_ , if it is not in the critical section and has no pending Enter() or
Exit() call. Such algorithms satisfy at least two conditions: _Mutual
exclusion_ requires that no two processes are in the critical section at the
same time, and _deadlock-freedom_ requires that some process with a pending
Enter() or Exit() call will eventually finish this call, provided that all
processes that are not in the remainder section keep taking steps.

A _recoverable_ mutual exclusion (RME) algorithm provides an additional
method, Recover(). It is assumed that a process may crash at any point.
(Formally, a process performs a crash step, which does not alter any shared
memory objects.) If a process that is not in the remainder section crashes,
all its local variables are reset to their initial values, and the process
immediately begins executing method Recover(). _Deadlock-freedom_ is only
required if the number of crashes is finite. (Otherwise a process might
repeatedly crash in its critical section, preventing other processes from
making progress.) In addition to mutual exclusion and deadlock-freedom, RME
algorithms must satisfy _critical section re-entry_ , which means that if a
process crashes in the critical section, then it will reenter the critical
section before any other process. Our lower bound is independent of that
property (deadlock-freedom and mutual exclusion are sufficient).

There are two common models used for the complexity analysis of mutual
exclusion algorithms. In the cache-coherent (CC) model, processes are equipped
with caches, and whenever a process performs a read operation it obtains a
cache-copy of the corresponding memory location. Any non-read operation of
that memory location invalidates all cache copies. A process’s operation
incurs a _remote memory reference_ (RMR), if it is a read operation and the
process has no valid cache copy, or if it is not a read operation. In the
distributed shared memory (DSM) model, the shared memory is partitioned into
segments, one for each process. An operation on a shared memory location
incurs an RMR if and only if that memory location is not in the calling
process’s memory segment. Almost all work on the efficiency of (recoverable
and non-recoverable) mutual exclusion algorithms has considered RMR complexity
in one of those two models.

A _passage_ of a process begins when it calls Enter() and ends when the
process crashes or when it finishes its following Exit() call. A _super-
passage_ of a process begins when the process calls Enter() and when it
completes its following Exit() call. (Note that in the absence of process
crashes, all passages and super-passages coincide.) The RMR complexity of a
mutual exclusion algorithm is the maximum number of RMRs a process may incur
in any passage.

For our lower bound proof, base objects can store values from arbitrary (even
uncountable) domains. We assume that processes can perform atomically any of
the following operations on a shared object with value $x$:

  * •

read(): returns $x$;

  * •

FAS($x^{\prime}$): writes $x^{\prime}$ and returns $x$;

  * •

CAS($y,x^{\prime}$): writes $x^{\prime}$ and returns true, provided that
$x=y$; otherwise it leaves the value unchanged and returns false.

  * •

FAI(): writes $x+1$ and returns $x$, provided that $x$ is an integer.
Otherwise it does not change the value of the object and returns $x$.

Note that a FAS operation is strictly stronger than a write operation (which
does not return anything), so our lower bound proof does not consider write
operations separately.

##  3\. The RME Lower Bound Proof

We consider an arbitrary algorithm that solves the RME problem with $o(\log
n)$ RMR complexity.

#### Assumptions:

We make the following assumptions w.l.o.g.:

  1. (A1)

In the critical section, each process performs operation(s) that incur at
least one RMR.

  2. (A2)

Since the algorithm incurs $o(\log n)$ RMRs in every passage of every
execution, we assume $n$ is sufficiently large such that every passage of
every execution incurs no more than $\log n$ RMRs.

  3. (A3)

Each process begins at most one super-passage, i.e., it leaves the remainder
section at most once. (Note that this assumption makes our proof stronger,
since a solution for the RME problem that allows multiple super-passages per
process clearly also solves the RME problem in the scenario where each process
can begin at most one super-passage.)

#### Definitions:

We define the following:

  * •

Let $\mathcal{P}=\\{1,\dots,n\\}$ be the set of processes and $\mathcal{R}$ be
the set of objects.

  * •

Given any array $A[0..2^{n}-1]$ and any set $S\subseteq\mathcal{P}$, we use
$A[S]$ to denote $A[\sum_{p\in S}2^{p-1}]$.

  * •

A schedule is a sequence over $\\{p,\hat{p}:p\in\mathcal{P}\\}$, where $p$
denotes a non-crash step by process $p$, and $\hat{p}$ denotes a crash-step by
$p$.

  * •

Let $C_{0}$ denote the initial configuration.

  * •

For each schedule $\sigma$, a configuration $C$, and a register $R$, we define
the following:

    * –

$P(\sigma)$: the set of all processes that have steps in $\sigma$.

    * –

$E(C,\sigma)$: the execution determined by $\sigma$ starting in configuration
$C$. Note: An execution is a sequence of _events_ , where each event
corresponds to a step by some process and contains the following information:
The process that is executing the step, the shared memory operation that
process is executing, the object (register) on which the shared memory
operation is executed, and whether the shared memory operation incurs an RMR.

    * –

$\textit{val}_{R}(C,\sigma)$: the value of $R$ at the end of $E(C,\sigma)$.

    * –

$\textit{state}_{p}(C,\sigma)$: the state of $p$ at the end of $E(C,\sigma)$.

    * –

$\textit{last}_{R}(C,\sigma)$: the process that last performed an operation on
$R$ at the end of $E(C,\sigma)$; or $\bot$ if no process has ever performed an
operation on $R$.

    * –

$F(C,\sigma)$: the set of processes that have finished their super-passage at
the end of $E(C,\sigma)$.

We also define $E(\sigma)=E(C_{0},\sigma)$,
$\textit{val}_{R}(\sigma)=\textit{val}_{R}(C_{0},\sigma)$,
$\textit{state}_{p}(\sigma)=\textit{state}_{p}(C_{0},\sigma)$,
$\textit{last}_{R}(\sigma)=\textit{last}_{R}(C_{0},\sigma)$, and
$F(\sigma)=F(C_{0},\sigma)$.

###  3.1. Overview of the Proof

Our goal is to show that the algorithm has $\Omega(\log n/\log\log n)$ RMR
complexity even when each process begins at most one super-passage and crashes
at most once. Towards that end, we will construct a schedule
$\sigma_{\textit{goal}}$ such that during $E(\sigma_{\textit{goal}})$:

  * •

Each process begins at most one super-passage, and crashes at most once.

  * •

Some process never crashes and never enters the critical section, yet incurs
$\Omega(\log n/\log\log n)$ RMRs.

On a very high level the construction follows the outline of Anderson and
Kim’s lower bound for non-recoverable mutual exclusion algorithms (Anderson
and Kim, 2002). Their proof applies only to read-write registers. In order to
deal with stronger primitives, we have to crash processes at opportune points
in time, so that they “forget” information they may have observed (e.g., as a
result of FAI or FAS operations).

We begin with a simple observation: if multiple processes are ’actively’
attempting to enter the critical section, then they cannot safely enter the
critical section before discovering one another, lest they violate mutual
exclusion. Thus throughout the proof, we will construct several closely
related schedules in which we attempt to maximize both the number of these
_active_ processes and the number of RMRs they incur without discovering one
another.

More formally, let $\sigma_{\textit{round}}[0..\infty][0..2^{n}-1]$ be an
initially empty table of schedules with an unbounded number of rows and
$2^{n}$ columns. Roughly speaking, for every non-negative integer $i$, the
$i$-th row of the table will contain only schedules in which the active
processes have incurred at least $i$ RMRs. For every integer
$s\in\\{0,1,\ldots,2^{n}-1\\}$, we associate the $s$-th column with the unique
set $S\subseteq\mathcal{P}$ of processes such that $s=\sum_{p\in S}2^{p-1}$.
Then the $s$-th column will contain only schedules in which only the processes
in $S$ can begin super-passages.

Filling the first row of the table is simple: in the empty schedule, every
active process has incurred $0$ RMRs, and the set of processes that have begun
super-passages is $\varnothing$, a subset of every possible set of processes.
Thus we set every cell of $\sigma_{\textit{round}}[0][0..2^{n}-1]$ to contain
the empty schedule.

The proof then proceeds in rounds, where in each round $i\geq 1$, we fill in
some cells of the $i$-th row with schedules derived by appending more steps to
the schedules in the $(i-1)$-th row. Since we only want schedules in which the
active processes do not discover one another, many of the cells in each row
will be left with the value $\bot$, indicating that we did not find a schedule
matching the required criteria. Thus as we go down through the rows of the
table, the number of cells in each row that we fill with schedules decreases.

As such, the goal of each round is to limit this decrease, such that
$\Omega(\log n/\log\log n)$ rounds complete before the number of schedules
becomes too few to continue. After which, every schedule in the final round
would have active processes that incur $\Omega(\log n/\log\log n)$ RMRs
without entering the critical section (or crashing).

To facilitate this, we maintain a number of invariants on every row of
schedules that we construct. Roughly speaking, these invariants are:

  1. (1)

There is a _maximal_ schedule which has the maximal number of active
processes, and all other schedules are ’sub’-schedules that correspond to
every possible subset of the active processes in the maximal schedule. This
invariant ensures that if the maximal schedule cannot be extended without
allowing some active processes to discover one another, then a sub-schedule
can be extended and made into the new maximal schedule for the next round.

  2. (2)

The state of every process is the same in every schedule it is part of. This
invariant ensures that the active processes have not discovered one another,
since they have the same state in a schedule where there are no other active
processes.

  3. (3)

For each register, its value in each schedule depends only on whether the
schedule contains the process that last accessed it in the maximal schedule.
This invariant ensures that register values are sufficiently similar across
different schedules that it becomes difficult for the active processes to
later distinguish between different schedules.

  4. (4)

In every schedule, each process crashes at most once, and every process that
is within a super-passage has not yet entered the critical section. The
invariant makes the proof significantly simpler, since it prevents
interactions between the active processes and the inactive processes that have
already entered the critical section but not yet completed their super-
passage.

  5. (5)

In the DSM model, the registers that are owned by active processes have not
been accessed by any other active process. This invariant also simplifies the
proof, since it prevents non-RMR-incurring steps from allowing an active
process to discover another active process, and thus allows the proof to focus
on the RMR-incurring steps.

  6. (6)

In the CC model, for each process $p$, the set of registers that $p$ has valid
cache copies of is identical over all schedules that contain $p$. This
invariant ensures that in the CC model, for each process $p$, the number of
RMRs incurred by $p$ is the same in every schedule it is part of.

  7. (7)

In the $i$-th row, every active process in every schedule has incurred at
least $i$ RMRs.

It is easy to see that these invariants all hold for row $0$. Furthermore, for
every non-negative integer $i$, let $n_{i}$ be the number of active processes
in the maximal schedule of row $i$. Then the first invariant asserts that row
$i$ has $2^{n_{i}}$ schedules. Moreover, to show that $\Omega(\log n/\log\log
n)$ rounds can be completed, it suffices to show that for every integer $i\geq
1$, $n_{i}>n_{i-1}/O(\log^{O(1)}n)$.

Each round of the proof is divided into two phases: a setup phase in which
non-RMR-incurring steps are appended to the schedules until every active
process in every schedule is poised to incur an RMR, and a contention phase,
in which RMR-incurring steps are appended in specific orders that limit the
fraction of active processes discovered.

In the setup phase, multiple non-RMR-incurring step(s) are appended for each
active process until they are poised to incur an RMR. By the above invariants,
the non-RMR-incurring steps appended for each process are the same in every
schedule that contains the process. This is because each process begins with
the same state in every schedule that contains the process, and then:

  * •

In the DSM model, its non-RMR-incurring steps only access its own registers,
which have never been accessed by any other active process, and thus these
steps intuitively provide no new information that would cause the process to
change its next steps.

  * •

In the CC model, its non-RMR-incurring steps would be reads on registers that
it has valid cache copies of in every schedule that contains it. Then, since
the process already has valid cache copies of these registers, they
intuitively provide no new information that would cause the process to change
its next steps.

In the contention phase, our construction method differs depending on the
relative number of registers that the active processes are poised to access
(in the maximal schedule).

In a low contention scenario, the active processes are poised to access a
relatively large number of registers, and so on average, each register has
relatively few processes poised to access it. In this case, we construct a
graph with nodes representing the active processes, and edges that intuitively
indicate processes that could discover one another: either because they are
poised to access the same register, or they are poised to access a register
that is owned or previously accessed by another active process. Since the
contention is relatively low, the resulting graph is relatively sparse, and
thus contains a relatively large independent set. We now discard any schedule
that contains any process outside of this independent set, so that the
remaining schedules only contain active processes that would not discover one
another with their next step. The remaining schedules then have a single step
appended for each active process, and then are used to fill the next row of
$\sigma_{\textit{round}}[0..\infty][0..2^{n}-1]$. It is straightforward to
show that the above invariants still hold for this new row of schedules.
Furthermore, due to the relative largeness of the independent set, it is also
straightforward to show that $n_{i}>n_{i-1}/O(\log^{O(1)}n)$ for every row
$i\geq 1$ constructed in a low contention scenario.

In a high contention scenario, the active processes are poised to access a
relatively small number of registers, and so on average, each register has
relatively many processes poised to access it. In this scenario, it is often
inevitable that some active processes are discovered by the others, and these
active processes must then be inactivated by allowing them to enter the
critical section, then complete their super-passage. To further complicate
matters, each such process could discover $o(\log n)$ other active processes
before completing its super-passage, and these discovered processes must then
be removed (schedules that contain such processes are discarded).
Nevertheless, we can limit the number of discovered processes as follows.

First, we determine the plurality type of operation that the plurality of
active processes are poised to perform. Every active process that is not
poised to perform this plurality type of operation is then removed (schedules
that contain such processes are discarded). Note that since there are only a
constant number of operation types, a constant fraction of the active
processes must remain.

We then divide these remaining active processes into groups of
$O(\log^{O(1)}n)$ processes, such that within each group, all processes are
poised to access the same register (we remove any active processes that cannot
be placed into such groups, the number of which is at most a constant fraction
of the remaining active processes). Then within each group, we select two
active processes (preferentially those applying operations that would change
the value of the register) that we call the alpha processes. Every schedule
that does not contain all of the alpha processes is then discarded.

Intuitively, these alpha processes are the processes that will be discovered:
they will be crashed, and then allowed to run until they complete their super-
passages. Any other active processes that they discover along the way will be
removed (schedules that contain such processes are discarded).

Now recall that each process incurs at most $o(\log n)$ RMRs during its super-
passage, whereas each group contains $O(\log^{O(1)}n)$ processes. Thus we can
ensure that a constant fraction of the groups still contain active processes
that have not been discovered. Then one undiscovered active process in each
such group, called the beta process, is allowed to take an RMR-incurring step
that is intuitively hidden by the steps of the alpha processes in its group as
follows:

  * •

If the plurality type of operation is read, then since reads do not change the
value of a register, the beta process can safely perform its read between the
reads of the alpha processes without affecting the value of the register.

  * •

If the plurality type of operation is fetch-and-store, then since fetch-and-
stores completely overwrite the value of a register, the beta process can
safely perform its fetch-and-store between the fetch-and-stores of the alpha
processes without affecting the final value of the register.

  * •

If the plurality type of operation is fetch-and-increment, we can replace the
fetch-and-increment of the first alpha process with a fetch-and-increment by
the beta process, and the final value of the register will remain the same.

  * •

If the plurality type of operation is compare-and-swap, then there must be an
ordering of the alpha and beta processes such that the beta process fails its
compare-and-swap operation, and so has no effect on the final value of the
register.

Roughly speaking, this allows the beta processes to take their RMR-incurring
steps without changing the value of any register, and although the alpha
processes can immediately discover the beta processes, they will immediately
crash and forget the beta processes, and will never discover the beta
processes again. Thus we can construct schedules that allow the beta processes
to remain active without being discovered; all other remaining active
processes are removed. Since a constant fraction of the groups of
$O(\log^{O(1)}n)$ processes yield an undiscovered beta process for the new
maximal schedule, we can also prove that $n_{i}>n_{i-1}/O(\log^{O(1)}n)$ for
every row $i\geq 1$ constructed in a high contention scenario.

Thus, regardless of whether each round $i\geq 1$ has a low contention phase or
a high contention phase, $n_{i}>n_{i-1}/O(\log^{O(1)}n)$. By the first
invariant, the number of schedules in each row $i$ is $2^{n_{i}}$. So
$\Omega(\log n/\log\log n)$ rounds complete before the number of schedules
becomes too few to continue. After which, the schedules in the final round
would have active processes that incur $\Omega(\log n/\log\log n)$ RMRs
without entering the critical section (or crashing). Consequently, the
algorithm has $\Omega(\log n/\log\log n)$ RMR complexity.

###  3.2. Proof Details

#### Invariants:

To prove the main theorem, we will iteratively construct arrays of schedules.

Let $i$ be a non-negative integer, and $A[0..2^{n}-1]$ be an array such that
each array entry contains either a schedule or $\bot$. Then we say that
$A[0..2^{n}-1]$ is _$i$ -compliant_ if it satisfies the following invariants:

  1. (I1)

For every set $S\subseteq\mathcal{P}$, if $A[S]\neq\bot$, then
$P(A[S])\subseteq S$. (Note that this implies $F(A[S])\subseteq S$.)

  2. (I2)

There is a unique set $S_{\textit{max}}\subseteq\mathcal{P}$ such that for
every set $S\subseteq\mathcal{P}$, $A[S]\neq\bot$ if and only if
$F(A[S_{\textit{max}}])\subseteq S\subseteq S_{\textit{max}}$.

  3. (I3)

For every process $p\in S_{\textit{max}}$ and every set
$S\subseteq\mathcal{P}$ that contains $p$, if $A[S]\neq\bot$, then
$\textit{state}_{p}(A[S])=\textit{state}_{p}(A[S_{\textit{max}}])$.

  4. (I4)

$F(A[S])=F(A[S_{\textit{max}}])$ for every set $S\subseteq\mathcal{P}$ with
$A[S]\neq\bot$. (Note that this invariant immediately follows from Invariants
(I1), (I2), and (I3).)

  5. (I5)

For every register $R\in\mathcal{R}$, there is a value $y_{R}$ such that for
every set $S\subseteq\mathcal{P}$, if $A[S]\neq\bot$, then:

$\textit{val}_{R}{\bigl{(}{A[S]}\bigr{)}}=\begin{cases}\textit{val}_{R}(A[S_{\textit{max}}])&\text{if
$\textit{last}_{R}(A[S_{\textit{max}}])\in S$}\\\
y_{R}&\text{otherwise}\end{cases}$

Note that it is possible that $y_{R}=\textit{val}_{R}(A[S_{\textit{max}}])$.
Furthermore, if $\textit{last}_{R}(A[S_{\textit{max}}])=\bot\not\in S$, then
$\textit{val}_{R}(A[S])=y_{R}$ for every set $S\subseteq\mathcal{P}$ with
$A[S]\neq\bot$.

  6. (I6)

For every set $S\subseteq\mathcal{P}$ with $A[S]\neq\bot$, during $E(A[S])$,
each process crashes at most once, and each process that is not in $F(A[S])$
never crashes.

  7. (I7)

For every set $S\subseteq\mathcal{P}$ with $A[S]\neq\bot$, each process that
is not in $F(A[S])$ does not enter the critical section during $E(A[S])$.

  8. (I8)

In the DSM model, for every process $p\in S_{\textit{max}}\setminus
F(A[S_{\textit{max}}])$, every register $R\in\mathcal{R}$ owned by $p$, and
every set $S\subseteq\mathcal{P}$ with $A[S]\neq\bot$, $R$ can only be
accessed by $p$ during $E(A[S])$. (Or equivalently, In the DSM model, for
every set $S\subseteq\mathcal{P}$ such that $A[S]\neq\bot$, during $E(A[S])$,
each register $R\in\mathcal{R}$ can only be accessed by its owner if the owner
of $R$ is in $S_{\textit{max}}\setminus F(A[S_{\textit{max}}])$.)

  9. (I9)

In the CC model, for every process $p\in S_{\textit{max}}\setminus
F(A[S_{\textit{max}}])$, there is a set $\mathcal{R}_{p}$ of registers such
that for every set $S\subseteq\mathcal{P}$ that contains $p$, if
$A[S]\neq\bot$, then the set of registers that $p$ has valid cache copies of
at the end of $E(A[S])$ is exactly $\mathcal{R}_{p}$. (Or equivalently, for
every set $S\subseteq\mathcal{P}$ such that $A[S]\neq\bot$, and every process
$p\in S\cap(S_{\textit{max}}\setminus F(A[S_{\textit{max}}]))$, the set of
registers that $p$ has valid cache copies of at the end of $E(A[S])$ is
exactly the same as at the end of $E(A[S_{\textit{max}}])$.)

  10. (I10)

For every set $S\subseteq\mathcal{P}$ and every process $p\in S\setminus
F(A[S])$, if $A[S]\neq\bot$, then $p$ incurs at least $i$ RMRs during
$E(A[S])$.

Let $i$ be a non-negative integer, and $A[0..2^{n}-1]$ be an array that is
$i$-compliant. Then we denote by $S_{\textit{max}}(A[0..2^{n}-1])$ the unique
set of Invariant (I2).

Let $\sigma_{\textit{round}}[0..\infty,0..2^{n}-1]$ be a table with all
entries initially containing $\bot$. Our goal is to fill in the table such
that for every non-negative integer $i$, either
$\sigma_{\textit{round}}[i,0..2^{n}-1]$ is $i$-compliant, or $i\in\Omega(\log
n/\log\log n)$.

Let $d$ be a sufficiently large constant and $k=\log^{d}n$.

#### Base Case:

For every set $S\subseteq\mathcal{P}$, let $\sigma_{\textit{round}}[0,S]$ be
set to the empty schedule (so every entry of
$\sigma_{\textit{round}}[0,0..2^{n}-1]$ is the empty schedule). Clearly, the
array $\sigma_{\textit{round}}[0,0..2^{n}-1]$ is $0$-compliant with
$S_{\textit{max}}(\sigma_{\textit{round}}[0,0..2^{n}-1])=\mathcal{P}$ and has
$2^{n}$ non-$\bot$ entries.

We now iterate through $i=1,2,\ldots$ as follows:

####  $i$-th Iteration (Termination Phase):

If $\sigma_{\textit{round}}[i-1,0..2^{n}-1]$ is not $(i-1)$-compliant or has
less than $2^{(k^{3})}$ non-$\bot$ entries, terminate.

####  $i$-th Iteration (Setup Phase):

For every set $S\subseteq\mathcal{P}$, let
$\sigma_{\textit{old}}[S]=\sigma_{\textit{round}}[i-1][S]$. So the array
$\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant.

Thus by Invariant (I2), there is a unique set
$S^{\textit{old}}_{\textit{max}}\subseteq\mathcal{P}$ such that
$\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}]\neq\bot$ and for every
set $S\subseteq\mathcal{P}$, $\sigma_{\textit{old}}[S]\neq\bot$ if and only if
$F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])\subseteq S\subseteq
S^{\textit{old}}_{\textit{max}}$. So by definition,
$S_{\textit{max}}(\sigma_{\textit{old}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$.
Then for every process $p\in S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, let
$S_{p}=\\{p\\}\cup F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$.
Note that $F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])\subseteq
S_{p}\subseteq S^{\textit{old}}_{\textit{max}}$, so
$\sigma_{\textit{old}}[S_{p}]\neq\bot$.

Now for every process $p\in S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, let $\sigma_{p}$
be a schedule consisting only of the maximum non-negative number of non-crash
steps of $p$ such that any RMRs incurred by $p$ in
$E(\sigma_{\textit{old}}[S_{p}]\circ\sigma_{p})$ were also incurred in
$E(\sigma_{\textit{old}}[S_{p}])$. Then let $C_{p}$ be the configuration at
the end of $E(\sigma_{\textit{old}}[S_{p}])$. So by definition, $p$ does not
incur any RMRs in $E(C_{p},\sigma_{p})$. Furthermore, if $\sigma_{p}$ is
finite, then an RMR would be incurred by $p$ at the end of
$E(\sigma_{\textit{old}}[S_{p}]\circ\sigma_{p}\circ p)$.

###### Lemma .

For every process $p\in S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, $\sigma_{p}$ is
finite.

###### Proof.

Let $p$ be any process in $S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$. Suppose, for
contradiction, that $\sigma_{p}$ is infinite.

Recall that $S_{p}=\\{p\\}\cup
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, so
$F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])\subseteq
S_{p}\subseteq S^{\textit{old}}_{\textit{max}}$. Since
$\sigma_{\textit{old}}[0..2^{n}-1]$ is $i-1$-compliant with
$S_{\textit{max}}(\sigma_{\textit{old}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$,
by Invariants (I2) and (I4), $\sigma_{\textit{old}}[S_{p}]\neq\bot$ and
$F(\sigma_{\textit{old}}[S_{p}])=F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$.
So $p\in S_{p}\setminus F(\sigma_{\textit{old}}[S_{p}])$. Thus by Invariant
(I7), $p$ does not enter the critical section during
$E(\sigma_{\textit{old}}[S_{p}])$.

By definition, $C_{p}$ is the configuration at the end of
$E(\sigma_{\textit{old}}[S_{p}])$ and $p$ does not incur any RMRs in
$E(C_{p},\sigma_{p})$. So by Assumption (A1), $p$ does not enter the critical
section during the infinite execution
$E(\sigma_{\textit{old}}[S_{p}]\circ\sigma_{p})$.

Now recall that $S_{p}=\\{p\\}\cup
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, so every process
$q\neq p$ is either in $F(\sigma_{\textit{old}}[S_{p}])$ or not in $S_{p}$. By
Invariant (I1), every process $q\not\in S_{p}$ takes no steps in
$E(\sigma_{\textit{old}}[S_{p}])$. Since $\sigma_{p}$ contains only steps of
$p$ and $p\in S_{p}$, every process $q\not\in S_{p}$ also takes no steps in
$E(\sigma_{\textit{old}}[S_{p}]\circ\sigma_{p})$. So in
$E(\sigma_{\textit{old}}[S_{p}]\circ\sigma_{p})$, $p$ takes infinitely many
steps without entering the critical section while every process $q\neq p$ is
in the remainder section — contradicting that
$E(\sigma_{\textit{old}}[S_{p}]\circ\sigma_{p})$ is an execution of an
algorithm that solves the RME problem. ∎

Since $\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{old}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$,
by Invariant (I2), for every set $S\subseteq\mathcal{P}$,
$\sigma_{\textit{old}}[S]\neq\bot$ if and only if
$F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])\subseteq S\subseteq
S^{\textit{old}}_{\textit{max}}$. So for each set $S\subseteq\mathcal{P}$ such
that $\sigma_{\textit{old}}[S]\neq\bot$, let $p_{1,S}$ be the process with the
smallest ID in $S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, $p_{2,S}$ be the
process with the second smallest ID, and so on. Then let $C_{S}$ be the
configuration at the end of $E(\sigma_{\textit{old}}[S])$, and let
$\sigma_{S}=\sigma_{p_{1,S}}\circ\sigma_{p_{2,S}}\circ\ldots$. Note that by
Section 3.2 and the fact that the system has only $n$ processes, $\sigma_{S}$
is a finite schedule.

###### Lemma .

For every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{old}}[S]\neq\bot$:

  1. (S1)

No RMRs are incurred during $E(C_{S},\sigma_{S})$.

  2. (S2)

For each process $p\in S$,
$\textit{state}_{p}(C_{p},\sigma_{p})=\textit{state}_{p}(C_{S},\sigma_{S})$.

  3. (S3)

For each process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, $p$ incurs an RMR
at the end of $E(C_{S},\sigma_{S}\circ p)$.

  4. (S4)

For each process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, $p$ has not left
the critical section at the end of $E(C_{S},\sigma_{S})$.

  5. (S5)

$F(\sigma_{\textit{old}}[S])=F(\sigma_{\textit{old}}[S]\circ\sigma_{S})$.

  6. (S6)

In the DSM model, each register $R\in\mathcal{R}$ can only be accessed by its
owner during $E(C_{S},\sigma_{S})$.

  7. (S7)

In the DSM model, for each process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$ and each register
$R\in\mathcal{R}$ owned by $p$,
$\textit{val}_{R}(C_{p},\sigma_{p})=\textit{val}_{R}(C_{S},\sigma_{S})$.

  8. (S8)

In the CC model, each register $R\in\mathcal{R}$ can only be read during
$E(C_{S},\sigma_{S})$.

  9. (S9)

In the CC model, during $E(C_{S},\sigma_{S})$, each process $p$ can only read
registers that it already has valid cache copies of.

###### Proof.

Let $S\subseteq\mathcal{P}$ be any set of processes such that
$\sigma_{\textit{old}}[S]\neq\bot$. Since $\sigma_{\textit{old}}[0..2^{n}-1]$
is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{old}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$,
by Invariant (I2), for every set $S^{\prime}\subseteq\mathcal{P}$,
$\sigma_{\textit{old}}[S^{\prime}]\neq\bot$ if and only if
$F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])\subseteq
S^{\prime}\subseteq S^{\textit{old}}_{\textit{max}}$. Thus
$F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])\subseteq S\subseteq
S^{\textit{old}}_{\textit{max}}$. Then since $S\subseteq
S^{\textit{old}}_{\textit{max}}$, by definition we have that for every process
$p\in S\setminus F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$,
$S_{p}=\\{p\\}\cup F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$.

Since $\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant, by Invariant
(I3), for every process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$ and every process
$q\in S_{p}$,
$\textit{state}_{q}(\sigma_{\textit{old}}[S])=\textit{state}_{q}(\sigma_{\textit{old}}[S_{p}])$.
Furthermore, by Invariant (I4),
$F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])=F(\sigma_{\textit{old}}[S])$.
So by Invariant (I7), every process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$ has not entered the
critical section during $E(\sigma_{\textit{old}}[S])$.

The proof now differs depending on the model:

CC Model::

In the CC model, any step that does not incur an RMR must be a read operation
on a register that the invoking process already has a valid cache copy of.
Thus, by definition, for every process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, $p$ only performs
read operations on registers that it already has valid cache copies of during
$E(C_{p},\sigma_{p})$.

Since $\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant, by Invariant
(I9), for every process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, the set of
registers that $p$ has valid cache copies of is in same in $C_{p}$ as in
$C_{S}$. Furthermore, read operations clearly cannot invalidate any valid
cache copies. Thus, by the definition of $\sigma_{S}$, observe that for every
process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, the operations
performed by $p$ during $E(C_{S},\sigma_{S})$ are the same as in during
$E(C_{p},\sigma_{p})$, i.e., $p$ only performs read operations on registers
that it already has valid cache copies of during $E(C_{S},\sigma_{S})$ ((S9)).

This implies the following:

  * •:

Since RMRs are not incurred by any read operation on a register that the
invoking process already has a valid cache copy of, no RMRs are incurred
during $E(C_{S},\sigma_{S})$ ((S1)).

  * •:

Since only read operations are performed during $E(C_{S},\sigma_{S})$, each
register can only be read during $E(C_{S},\sigma_{S})$ ((S8)).

  * •:

By definition, $\sigma_{S}$ contains only steps of processes in $S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$. Thus for every
process $p\in S$, observe that
$\textit{state}_{p}(C_{S},\sigma_{S})=\textit{state}_{p}(C_{p},\sigma_{p})$
((S2)).

Now recall that for every process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, the set of
registers that $p$ has valid cache copies of is in same in $C_{p}$ as in
$C_{S}$. Then, since (i)
$\textit{state}_{p}(C_{S},\sigma_{S})=\textit{state}_{p}(C_{p},\sigma_{p})$,
(ii) the valid cache copies of $p$ are the same in $C_{p}$ as in $C_{S}$,
(iii) new cache copies cannot be created by reading registers that valid cache
copies already exist for, and (iv) $p$ incurs an RMR in
$E(C_{p}\circ\sigma_{p},p)$ by the definition of $\sigma_{p}$, observe that
$p$ also incurs an RMR at the end of $E(C_{S},\sigma_{S}\circ p)$ ((S3)).

  * •:

Since every process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$ has not entered the
critical section during $E(\sigma_{\textit{old}}[S])$ and no RMRs are incurred
during $E(C_{S},\sigma_{S})$, by Assumption (A1), every process $p\in
S\setminus F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$ has not
left the critical section at the end of $E(C_{S},\sigma_{S})$ ((S4)).

Then, since $\sigma_{S}$ contains only non-crash steps, no process completes
during $E(C_{S},\sigma_{S})$. Thus
$F(\sigma_{\textit{old}}[S])=F(\sigma_{\textit{old}}[S]\circ\sigma_{S})$
((S5)).

DSM Model::

In the DSM model, any step that does not incur an RMR must be an operation on
a register owned by the invoking process. Thus, by definition, for every
process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, $p$ only performs
operations on its own registers during $E(C_{p},\sigma_{p})$.

Since $\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{old}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$,
by Invariant (I8), for every process $p\in
S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, every register
$R\in\mathcal{R}$ owned by $p$, and every set $S^{\prime}\subseteq\mathcal{P}$
with $\sigma_{\textit{old}}[S^{\prime}]\neq\bot$, $R$ can only be accessed by
$p$ during $E(\sigma_{\textit{old}}[S^{\prime}])$, so
$\textit{last}_{R}(\sigma_{\textit{old}}[S^{\prime}])$ is either $p$ or
$\bot$. Thus by Invariant (I5), if $\textit{init}_{R}$ is the initial value of
$R$, then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{old}}[S^{\prime}]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])&\text{if
$p\in S^{\prime}$}\\\ \textit{init}_{R}&\text{otherwise}\end{cases}$

So for every process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$ and every register
$R\in\mathcal{R}$ owned by $p$,
$\textit{val}_{R}(\sigma_{\textit{old}}[S])=\textit{val}_{R}(\sigma_{\textit{old}}[S_{p}])$.
Furthermore, operations on registers not owned by $p$ clearly cannot change
the value of registers owned by $p$. Consequently, by the definition of
$\sigma_{S}$, observe that for every process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$, the operations
performed by $p$ during $E(C_{S},\sigma_{S})$ are the same as in during
$E(C_{p},\sigma_{p})$, i.e., $p$ only performs operations on its own registers
during $E(C_{S},\sigma_{S})$.

This implies the following:

  * •:

Since RMRs are not incurred by any operation on a register owned by the
invoking process, no RMRs are incurred during $E(C_{S},\sigma_{S})$ ((S1)).

  * •:

Since each process only accesses its own registers during
$E(C_{S},\sigma_{S})$, for each register $R\in\mathcal{R}$, $R$ can only be
accessed by its owner during $E(C_{S},\sigma_{S})$ ((S6)).

Furthermore, since the operations performed by each process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$ during
$E(C_{S},\sigma_{S})$ are the same as in during $E(C_{p},\sigma_{p})$,
$\textit{val}_{R}(C_{p},\sigma_{p})=\textit{val}_{R}(C_{S},\sigma_{S})$
((S7)).

  * •:

By definition, $\sigma_{S}$ contains only steps of processes in $S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$. Thus for every
process $p\in S$, observe that
$\textit{state}_{p}(C_{S},\sigma_{S})=\textit{state}_{p}(C_{p},\sigma_{p})$
((S2)).

Furthermore, by the definition of $\sigma_{p}$, $p$ incurs an RMR at the end
of $E(C_{p},\sigma_{p}\circ p)$, i.e., $p$ is poised to access a register that
it does not own at the end of $E(C_{p},\sigma_{p})$. Thus, since
$\textit{state}_{p}(C_{S},\sigma_{S})=\textit{state}_{p}(C_{p},\sigma_{p})$,
$p$ is also poised to access a register that it does not own at the end of
$E(C_{S},\sigma_{S})$, and so $p$ also incurs an RMR at the end of
$E(C_{S},\sigma_{S}\circ p)$ ((S3)).

  * •:

Since every process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$ has not entered the
critical section during $E(\sigma_{\textit{old}}[S])$ and no RMRs are incurred
during $E(C_{S},\sigma_{S})$, by Assumption (A1), every process $p\in
S\setminus F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$ has not
left the critical section at the end of $E(C_{S},\sigma_{S})$ ((S4)).

Then, since every process $p\in S\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$ has not left the
critical section at the end of $E(C_{S},\sigma_{S})$, every process $p\in
S\setminus F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$ has not
completed its super-passage at the end of $E(C_{S},\sigma_{S})$. Thus
$F(\sigma_{\textit{old}}[S])=F(\sigma_{\textit{old}}[S]\circ\sigma_{S})$
((S5)).

∎

We now construct a new array $\sigma_{\textit{setupA}}[0..2^{n}-1]$ such that
for every set $S\subseteq\mathcal{P}$, $\sigma_{\textit{setupA}}[S]=\bot$ if
$\sigma_{\textit{old}}[S]=\bot$; otherwise
$\sigma_{\textit{setupA}}[S]=\sigma_{\textit{old}}[S]\circ\sigma_{S}$.

###### Lemma .

Except for Invariant (I7), $\sigma_{\textit{setupA}}[0..2^{n}-1]$ is
$(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{setupA}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$.

###### Proof.

For every set $S\subseteq\mathcal{P}$, if
$\sigma_{\textit{setupA}}[S]\neq\bot$, then by construction,
$\sigma_{\textit{setupA}}[S]=\sigma_{\textit{old}}[S]\circ\sigma_{S}$. Since
$\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant, by Invariant (I1),
$P(\sigma_{\textit{old}}[S])\subseteq S$. By the definition of $\sigma_{S}$,
$\sigma_{S}$ contains only steps of processes in $S$. Thus
$P(\sigma_{\textit{setupA}}[S])\subseteq S$ (Invariant (I1)).

Since $\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{old}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$,
by Invariant (I2), for every set $S\subseteq\mathcal{P}$,
$\sigma_{\textit{old}}[S]\neq\bot$ if and only if
$F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])\subseteq S\subseteq
S^{\textit{old}}_{\textit{max}}$. By construction, for every set
$S\subseteq\mathcal{P}$, $\sigma_{\textit{setupA}}[S]=\bot$ if and only if
$\sigma_{\textit{old}}[S]=\bot$. Furthermore, by Section 3.2 ((S5)),
$F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])=F(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])$.
Thus for every set $S\subseteq\mathcal{P}$,
$\sigma_{\textit{setupA}}[S]\neq\bot$ if and only if
$F(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])\subseteq
S\subseteq S^{\textit{old}}_{\textit{max}}$ (Invariant (I2)).

By Section 3.2 ((S2)), for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{old}}[S]\neq\bot$, and every process $p\in S$,
$\textit{state}_{p}(\sigma_{\textit{setupA}}[S_{p}])=\textit{state}_{p}(C_{p},\sigma_{p})\textit{state}_{p}(C_{S},\sigma_{S})=\textit{state}_{p}(\sigma_{\textit{setupA}}[S])$.
By construction, for every set $S\subseteq\mathcal{P}$,
$\sigma_{\textit{setupA}}[S]=\bot$ if and only if
$\sigma_{\textit{old}}[S]=\bot$. Furthermore, we have already proven that for
every set $S\subseteq\mathcal{P}$, $\sigma_{\textit{setupA}}[S]\neq\bot$ if
and only if
$F(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])\subseteq
S\subseteq S^{\textit{old}}_{\textit{max}}$. Thus observe that for every
process $p\in S^{\textit{old}}_{\textit{max}}$ and every set
$S\subseteq\mathcal{P}$ that contains $p$, if
$\sigma_{\textit{setupA}}[S]\neq\bot$, then
$\textit{state}_{p}(\sigma_{\textit{setupA}}[S])=\textit{state}_{p}(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])$
(Invariant (I3)).

Since we have already proven that Invariants (I1), (I2), and (I3) hold for
$\sigma_{\textit{setupA}}[0..2^{n}-1]$, it immediately follows that Invariant
(I4) also holds.

Since $\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant, Invariant (I6)
holds for $\sigma_{\textit{old}}[0..2^{n}-1]$. For every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{old}}[S]\neq\bot$,
$\sigma_{S}$ contains no crash steps. Thus Invariant (I6) also holds for
$\sigma_{\textit{setupA}}[0..2^{n}-1]$.

Since $\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant, Invariant (I8)
holds for $\sigma_{\textit{old}}[0..2^{n}-1]$. By Section 3.2 ((S6)), for
every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{old}}[S]\neq\bot$, each register $R\in\mathcal{R}$ can only
be accessed by its owner during $E(C_{S},\sigma_{S})$. Thus Invariant (I8)
also holds for $\sigma_{\textit{setupA}}[0..2^{n}-1]$.

Since $\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant, Invariant (I9)
holds for $\sigma_{\textit{old}}[0..2^{n}-1]$. In the CC model, by Section 3.2
((S8)), for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{old}}[S]\neq\bot$, each register $R\in\mathcal{R}$ can only
be read during $E(C_{S},\sigma_{S})$. Thus no valid cache copy can be
invalidated during $E(C_{S},\sigma_{S})$. Furthermore, by Section 3.2 ((S8)),
during $E(C_{S},\sigma_{S})$, each process $p$ can only read registers that it
already has valid cache copies of. Thus no new cache copies can be created
during $E(C_{S},\sigma_{S})$. Consequently, Invariant (I9) also holds for
$\sigma_{\textit{setupA}}[0..2^{n}-1]$.

Since $\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant, Invariant
(I10) holds for $\sigma_{\textit{old}}[0..2^{n}-1]$. Then, since no steps are
removed in the construction of the schedules for
$\sigma_{\textit{setupA}}[0..2^{n}-1]$, clearly Invariant (I10) also holds for
$\sigma_{\textit{setupA}}[0..2^{n}-1]$.

We will now prove that Invariant (I5) holds for
$\sigma_{\textit{setupA}}[0..2^{n}-1]$ as follows. Let $R\in\mathcal{R}$ be
any register. Our goal is to show that there exists a value $y_{R}$ such that
for every set $S\subseteq\mathcal{P}$, if
$\sigma_{\textit{setupA}}[S]\neq\bot$, then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{setupA}}[S]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])&\text{if
$\textit{last}_{R}(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])\in
S$}\\\ y_{R}&\text{otherwise}\end{cases}$

Note that since $\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{old}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$,
by Invariant (I5), there is a value $y_{R}$ such that for every set
$S\subseteq\mathcal{P}$, if $\sigma_{\textit{old}}[S]\neq\bot$, then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{old}}[S]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])&\text{if
$\textit{last}_{R}(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])\in
S$}\\\ y_{R}&\text{otherwise}\end{cases}$

First, suppose that $R$ is not accessed during $E(C_{S},\sigma_{S})$ for every
set $S\subseteq\mathcal{P}$ such that $\sigma_{\textit{old}}[S]\neq\bot$. Then
since $\sigma_{\textit{old}}[S]=\bot$ if and only if
$\sigma_{\textit{setupA}}[S]=\bot$, and $R$ is not accessed during
$E(C_{S^{\textit{old}}_{\textit{max}}},\sigma_{S^{\textit{old}}_{\textit{max}}})$,
$\textit{last}_{R}(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])=\textit{last}_{R}(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])$.
Thus as we wanted, for every set $S\subseteq\mathcal{P}$, if
$\sigma_{\textit{setupA}}[S]\neq\bot$, then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{setupA}}[S]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])&\text{if
$\textit{last}_{R}(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])\in
S$}\\\ y_{R}&\text{otherwise}\end{cases}$

So suppose instead that there exists a set $S^{\prime}\subseteq\mathcal{P}$
such that $\sigma_{\textit{old}}[S^{\prime}]\neq\bot$, and a process $p\in
S^{\prime}\setminus F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$
that accesses $R$ during $E(C_{S^{\prime}},\sigma_{S^{\prime}})$. The proof
now differs depending on the model.

In the DSM model, by Section 3.2 ((S6)), $p$ must be the owner of $R$. Then
since $\sigma_{\textit{old}}[0..2^{n}-1]$ is $(i-1)$-compliant, by Invariant
(I8), either
$\textit{last}_{R}(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])=p$
or
$\textit{val}_{R}(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])=y_{R}$.
Furthermore, by Section 3.2 ((S6) and (S7)), for every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{old}}[S]\neq\bot$, if $p\in
S$, then
$\textit{val}_{R}(C_{S},\sigma_{S})=\textit{val}_{R}(C_{p},\sigma_{p})$;
otherwise $\textit{val}_{R}(C_{S},\sigma_{S})=y_{R}$. Thus as we wanted, for
every set $S\subseteq\mathcal{P}$, if $\sigma_{\textit{setupA}}[S]\neq\bot$,
then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{setupA}}[S]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])&\text{if
$\textit{last}_{R}(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])\in
S$}\\\ y_{R}&\text{otherwise}\end{cases}$

Finally, in the CC model, by Section 3.2 ((S9)), $p$ already has a valid cache
copy of $R$ in $C_{S^{\prime}}$. So since $\sigma_{\textit{old}}[0..2^{n}-1]$
is $(i-1)$-compliant, by Invariant (I9), for every set $S\subseteq\mathcal{P}$
such that $\sigma_{\textit{old}}[S]\neq\bot$ and $p\in S$,
$\textit{val}_{R}(\sigma_{\textit{old}}[S])=\textit{val}_{R}(\sigma_{\textit{old}}[S^{\prime}])$.
Thus either
$\textit{last}_{R}(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])=p$
or
$\textit{val}_{R}(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])=y_{R}$.
Note that if any process other than $p$ also accesses $R$ during
$E(C_{S},\sigma_{S})$, then
$\textit{val}_{R}(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])=y_{R}$.
Furthermore, by Section 3.2 ((S8)), for every set $S\subseteq\mathcal{P}$ such
that $\sigma_{\textit{old}}[S]\neq\bot$,
$\textit{val}_{R}(\sigma_{\textit{old}}[S])=\textit{val}_{R}(\sigma_{\textit{setupA}}[S])$.
Thus observe that as we wanted, for every set $S\subseteq\mathcal{P}$, if
$\sigma_{\textit{setupA}}[S]\neq\bot$, then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{setupA}}[S]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])&\text{if
$\textit{last}_{R}(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])\in
S$}\\\ y_{R}&\text{otherwise}\end{cases}$

Consequently we have proven that Invariant (I5) holds for
$\sigma_{\textit{setupA}}[0..2^{n}-1]$. ∎

We now construct another array $\sigma_{\textit{setupB}}[0..2^{n}-1]$ with the
goal of satisfying Invariant (I7) as follows. If no process is within the
critical section at the end of
$E(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])$, we simply
construct $\sigma_{\textit{setupB}}[0..2^{n}-1]$ such that
$\sigma_{\textit{setupB}}[0..2^{n}-1]=\sigma_{\textit{setupA}}[0..2^{n}-1]$.
Furthermore, we define
$S^{\textit{setup}}_{\textit{max}}=S^{\textit{old}}_{\textit{max}}$.

Otherwise, to avoid violating mutual exclusion, there must be exactly one
process $p\in S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])$ such that at the
end of $E(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])$, $p$ is
within the critical section. Then note that by Section 3.2 and Invariant (I3),
for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{setupA}}[S]\neq\bot$, if $p\in S$ then $p$ is also within the
critical section at the end of $E(\sigma_{\textit{setupA}}[S])$; otherwise no
process is within the critical section at the end of
$E(\sigma_{\textit{setupA}}[S])$. Thus we construct
$\sigma_{\textit{setupB}}[0..2^{n}-1]$ such that for every set
$S\subseteq\mathcal{P}$, if $p\in S$, then $\sigma_{\textit{setupB}}[S]=\bot$;
otherwise $\sigma_{\textit{setupB}}[S]=\sigma_{\textit{setupA}}[S]$.
Furthermore, we define
$S^{\textit{setup}}_{\textit{max}}=S^{\textit{old}}_{\textit{max}}\setminus\\{p\\}$.

###### Lemma .

This new array $\sigma_{\textit{setupB}}[0..2^{n}-1]$ is $(i-1)$-compliant
with
$S_{\textit{max}}(\sigma_{\textit{setupB}}[0..2^{n}-1])=S^{\textit{setup}}_{\textit{max}}$.

###### Proof.

By Section 3.2, except for Invariant (I7),
$\sigma_{\textit{setupA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{setupB}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$.

If no process is within the critical section at the end of
$E(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])$, then
$\sigma_{\textit{setupB}}[0..2^{n}-1]=\sigma_{\textit{setupA}}[0..2^{n}-1]$.
Thus by Section 3.2 and Section 3.2 ((S4)), Invariant (I7) also holds for
$\sigma_{\textit{setupA}}[0..2^{n}-1]$, and so it follows that
$\sigma_{\textit{setupB}}[0..2^{n}-1]=\sigma_{\textit{setupA}}[0..2^{n}-1]$ is
$(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{setupB}}[0..2^{n}-1])=S^{\textit{setup}}_{\textit{max}}=S^{\textit{old}}_{\textit{max}}$.

Otherwise, there is exactly one process $p\in
S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])$ such that $p$ is
within the critical section at the end of
$E(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])$, and for every
set $S\subseteq\mathcal{P}$, if $p\in S$, then
$\sigma_{\textit{setupB}}[S]=\bot$; otherwise
$\sigma_{\textit{setupB}}[S]=\sigma_{\textit{setupA}}[S]$. By Section 3.2,
except for Invariant (I7), $\sigma_{\textit{setupA}}[0..2^{n}-1]$ is
$(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{setupA}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$.
Thus observe that by the construction of
$\sigma_{\textit{setupB}}[0..2^{n}-1]$, Invariants (I1), (I2), (I3), (I4),
(I5), (I6), (I8), (I9), (I10) must all also hold for
$\sigma_{\textit{setupB}}[0..2^{n}-1]$ with
$S_{\textit{max}}(\sigma_{\textit{setupB}}[0..2^{n}-1])=S^{\textit{setup}}_{\textit{max}}=S^{\textit{old}}_{\textit{max}}\setminus\\{p\\}$.

By the construction of $\sigma_{\textit{setupB}}[0..2^{n}-1]$, for every set
$S\subseteq\mathcal{P}$, if $p\in S$, then $\sigma_{\textit{setupB}}[S]=\bot$.
Thus for every set $S\subseteq\mathcal{P}$, if
$\sigma_{\textit{setupB}}[S]\neq\bot$, then $p\not\in S$. Consequently, for
every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{setupB}}[S]\neq\bot$, no process is within the critical
section at the end of
$E(\sigma_{\textit{setupA}}[S])=E(\sigma_{\textit{setupB}}[S])$. Therefore by
Section 3.2 ((S4)), Invariant (I7) holds for
$\sigma_{\textit{setupB}}[0..2^{n}-1]$, and thus
$\sigma_{\textit{setupB}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{setupB}}[0..2^{n}-1])=S^{\textit{setup}}_{\textit{max}}$.
∎

####  $i$-th Iteration (Decision Phase):

Then for each register $R\in\mathcal{R}$, let $B_{R}$ be the set of processes
poised to access $R$ at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$. (So
$B_{R}\cap
F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])=\emptyset$.)
Further, let

$H=\bigcup_{R\in\mathcal{R}\atop|B_{R}|\geq k}B_{R}.$

and

$L=S^{\textit{setup}}_{\textit{max}}\setminus{\bigl{(}{H\cup
F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])}\bigr{)}}.$

####  $i$-th Iteration (Low Contention Phase if $|L|\geq|H|$):

We begin by constructing an undirected graph where the processes in $L$ are
the nodes, and for every pair of nodes $p$ and $q$, we connect an edge between
$p$ and $q$ if and only if at least one of the following is true at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$:

  * •

$p$ and $q$ are poised to access the same register.

  * •

$p$ is poised to access a register owned by $q$, or vice versa.

  * •

$p$ is poised to access a register that $q$ has previously performed an
operation on, or vice versa.

Thus in this graph:

  * •

Since $|B_{R}|<k$ for every register $R\in\mathcal{R}$ that processes in $L$
are poised to access, there are at most $k|L|$ edges representing processes
that are poised to access the same register.

  * •

Since every register $R\in\mathcal{R}$ is owned by at most one process, there
are at most $|L|$ edges representing processes that are poised to access a
register owned by some process in $L$ (one edge for each process, connecting
it to the owner of the register it is poised to access).

  * •

By Assumption (A2), every passage incurs at most $\log n$ RMRs. By Section
3.2, $\sigma_{\textit{setupB}}[0..2^{n}-1]$ is $(i-1)$-compliant. Recall that
$L\cap
F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])=\varnothing$.
So by Invariant (I6), each process in $L$ has never crashed, and so has
started at most one passage. Thus each process in $L$ has performed operations
on at most $\log n$ registers that are not owned by itself. (Note that
registers owned by itself are excluded because their associated edges would
have already been added in the previous step.) Then since $|B_{R}|<k$ for
every register $R\in\mathcal{R}$ that processes in $L$ are poised to access,
there are at most $k|L|\log n$ edges representing processes that are poised to
access a register that some process in $L$ has previously performed an
operation on ($k$ edges from each of the $\log n$ registers previously
accessed by each process in $L$).

Hence, the total number of edges is at most $k|L|+|L|+k|L|\log n<3k|L|\log n$.

Let $I$ be the maximum independent set of the graph.

###### Lemma .

$|I|\geq|L|/(7k\log n)$.

###### Proof.

Since there are at most $3k|L|\log n$ edges, the average degree of the graph
is at most $6k\log n$. The lemma immediately follows by Turan’s Theorem. ∎

Let $S_{I}=F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])\cup
I$. Note that since $I\subseteq L$,
$F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])\subseteq
S_{I}\subseteq S^{\textit{setup}}_{\textit{max}}$. We now construct a new
array $\sigma_{\textit{lowA}}[0..2^{n}-1]$ such that for every set
$S\subseteq\mathcal{P}$, if $S\not\subseteq S_{I}$, then
$\sigma_{\textit{lowA}}[S]=\bot$; otherwise
$\sigma_{\textit{lowA}}[S]=\sigma_{\textit{setupB}}[S]$.

###### Lemma .

This new array $\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowA}}[0..2^{n}-1])=S_{I}$.

###### Proof.

By Section 3.2, $\sigma_{\textit{setupB}}[0..2^{n}-1]$ is $(i-1)$-compliant
with
$S_{\textit{max}}(\sigma_{\textit{setupB}}[0..2^{n}-1])=S^{\textit{setup}}_{\textit{max}}$.
By construction, $\sigma_{\textit{lowA}}[0..2^{n}-1]$ is simply a modification
of $\sigma_{\textit{setupB}}[0..2^{n}-1]$ where every set
$S\subseteq\mathcal{P}$ that contains any process in
$S^{\textit{setup}}_{\textit{max}}\setminus S_{I}$ has had
$\sigma_{\textit{lowA}}[S]$ set to $\bot$, where
$F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])\subseteq
S_{I}\subseteq S^{\textit{setup}}_{\textit{max}}$. It suffices to observe that
every invariant still holds with
$S_{\textit{max}}(\sigma_{\textit{lowA}}[0..2^{n}-1])=S_{I}$, and thus
$\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowA}}[0..2^{n}-1])=S_{I}$. ∎

Now for each set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{lowA}}[S]\neq\bot$, let $C^{\prime}_{S}$ be the configuration
at the end of $E(\sigma_{\textit{lowA}}[S])$, and let $\sigma^{\prime}_{S}$ be
the schedule consisting of exactly one non-crash step by each process in
$S\setminus F(\sigma_{\textit{lowA}}[S_{I}])$ in order from the process with
the smallest ID to the process with the largest ID. Note that
$\sigma^{\prime}_{S}$ is a finite schedule since there are only $n$ processes
in the system. Also note that by Section 3.2,
$\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowA}}[0..2^{n}-1])=S_{I}$, so
$\sigma_{\textit{lowA}}[S]\neq\bot$ if and only if
$F(\sigma_{\textit{lowA}}[S_{I}])\subseteq S\subseteq S_{I}$. Thus
$\sigma^{\prime}_{S}$ contains exactly one non-crash step of each process in
$I\cap S$ and no other steps.

###### Lemma .

For every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{lowA}}[S]\neq\bot$:

  1. (L1)

For each register $R\in\mathcal{R}$, $R$ is accessed by at most one process
$p\in I\cap S$ during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$ and no other
processes.

  2. (L2)

For each process $p\in I$, if $p$ accesses a register $R$ during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$, then the owner of $R$ is not in
$I\setminus\\{p\\}$.

  3. (L3)

For each process $p\in I$, if $p$ accesses a register $R$ during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$, then $R$ has never been accessed by
any process in $I\setminus\\{p\\}$ during $E(\sigma_{\textit{lowA}}[S])$.

  4. (L4)

For each process $p\in I$, during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$, $p$
cannot invalidate any cache copy of any process in $I\setminus\\{p\\}$.

  5. (L5)

For every process $p\in I$, if $p$ accesses a register $R$ during
$E(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})$, then there is a value $y_{R}$
such that for every set $S^{\prime}\subseteq\mathcal{P}$, if
$\sigma_{\textit{lowA}}[S^{\prime}]\neq\bot$, then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{lowA}}[S^{\prime}]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{lowA}}[S_{I}])&\text{if
$p\in S^{\prime}$}\\\ y_{R}&\text{otherwise}\end{cases}$

Note that this implies that for each register $R\in\mathcal{R}$, if $R$ is
accessed during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$ then
$\textit{val}_{R}(\sigma_{\textit{lowA}}[S_{I}])=\textit{val}_{R}(\sigma_{\textit{lowA}}[S])$.

  6. (L6)

For each register $R\in\mathcal{R}$, if $R$ is accessed during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$ then
$\textit{val}_{R}(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})=\textit{val}_{R}(C^{\prime}_{S},\sigma^{\prime}_{S})$.

  7. (L7)

For each process $p\in S$,
$\textit{state}_{p}(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})=\textit{state}_{p}(C^{\prime}_{S},\sigma^{\prime}_{S})$.

  8. (L8)

Each process in $I\cap S$ incurs exactly one RMR during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$.

  9. (L9)

For each process $p\in S\setminus F(\sigma_{\textit{lowA}}[S_{I}])$, $p$ has
not left the critical section during
$E(\sigma_{\textit{lowA}}[S]\circ\sigma^{\prime}_{S})$.

  10. (L10)

$F(\sigma_{\textit{lowA}}[S])=F(\sigma_{\textit{lowA}}[S]\circ\sigma^{\prime}_{S})$.

###### Proof.

Let $S\subseteq\mathcal{P}$ be any set of processes such that
$\sigma_{\textit{lowA}}[S]\neq\bot$. By Section 3.2,
$\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowA}}[0..2^{n}-1])=S_{I}$. So by Invariant
(I2), for every set $S^{\prime}\subseteq\mathcal{P}$,
$\sigma_{\textit{lowA}}[S^{\prime}]\neq\bot$ if and only if
$F(\sigma_{\textit{lowA}}[S_{I}])\subseteq S^{\prime}\subseteq S_{I}$. Thus
$F(\sigma_{\textit{lowA}}[S_{I}])\subseteq S\subseteq S_{I}$.

Furthermore, by Invariants (I3) and (I4), for every process $p\in S$,
$\textit{state}_{p}(\sigma_{\textit{lowA}}[S])=\textit{state}_{p}(\sigma_{\textit{lowA}}[S_{I}])$
and $F(\sigma_{\textit{lowA}}[S])=F(\sigma_{\textit{lowA}}[S_{I}])$. So by
Invariant (I7), every process $p\in S\setminus
F(\sigma_{\textit{lowA}}[S_{I}])$ has not entered the critical section during
$E(\sigma_{\textit{lowA}}[S])$.

Now recall that $\sigma^{\prime}_{S}$ contains exactly one non-crash step of
each process in $I\cap S$ and no other steps. Also recall that by
construction, for every process $p\in S$,
$\textit{state}_{p}(\sigma_{\textit{lowA}}[S])=\textit{state}_{p}(\sigma_{\textit{lowA}}[S_{I}])=\textit{state}_{p}(\sigma_{\textit{setupB}}[S_{I}])=\textit{state}_{p}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$.
Then since $I$ is an independent set of the graph we constructed earlier:

  * •

No pair of processes in $I$ are poised to access the same register at the end
of $E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$. Since
$\textit{state}_{p}(\sigma_{\textit{lowA}}[S])=\textit{state}_{p}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$
for every process $p\in S$, no pair of processes in $I$ are poised to access
the same register at the end of $E(\sigma_{\textit{lowA}}[S])$. Thus every
process in $I\cap S$ accesses a different register during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$ ((L1)).

  * •

No process $p\in I$ is poised to access a register owned by a different
process $q\in I$ at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$. Since
$\textit{state}_{p}(\sigma_{\textit{lowA}}[S])=\textit{state}_{p}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$
for every process $p\in S$, no process $p\in I$ is poised to access a register
owned by a different process $q\in I$ at the end of
$E(\sigma_{\textit{lowA}}[S])$. Thus for each process $p\in I$, if $p$
accesses a register $R$ during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$, then
the owner of $R$ is not in $I\setminus\\{p\\}$. ((L2)).

  * •

No process $p\in I$ is poised to access a register that has previously been
accessed by a different process $q\in I$ at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$. Since
$\textit{state}_{p}(\sigma_{\textit{lowA}}[S])=\textit{state}_{p}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$
for every process $p\in S$, no process $p\in I$ is poised to access a register
that has previously been accessed by a different process $q\in I$ at the end
of $E(\sigma_{\textit{lowA}}[S])$. Thus for each process $p\in I$, if $p$
accesses a register $R$ during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$, then
$R$ has never been accessed by any process in $I\setminus\\{p\\}$ during
$E(\sigma_{\textit{lowA}}[S])$. ((L3)). Therefore, for each process $p\in I$,
if $p$ accesses a register $R$ during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$,
no process in $I\setminus\\{p\\}$ makes a cache copy of $R$ during
$E(\sigma_{\textit{lowA}}[S])$. Consequently, for each process $p\in I$,
during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$, $p$ cannot invalidate any
cache copy of any process in $I\setminus\\{p\\}$ ((L4)).

Furthermore, since
$\textit{state}_{p}(\sigma_{\textit{lowA}}[S_{I}])=\textit{state}_{p}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$
for every process $p\in S$, no process $p\in I$ is poised to access a register
that has previously been accessed by a different process $q\in I$ at the end
of $E(\sigma_{\textit{lowA}}[S_{I}])$. Thus for every process $p\in I$, if $p$
accesses a register $R$ during
$E(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})$, then
$\textit{last}_{R}(\sigma_{\textit{lowA}}[S_{I}])\not\in I\setminus\\{p\\}$,
so either $\textit{last}_{R}(\sigma_{\textit{lowA}}[S_{I}])=p$ or
$\textit{last}_{R}(\sigma_{\textit{lowA}}[S_{I}])\in
F(\sigma_{\textit{lowA}}[S_{I}])\cup(\mathcal{P}\setminus S_{I})$.

By Section 3.2, $\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowA}}[0..2^{n}-1])=S_{I}$. Thus by
Invariant (I5), for every register $R\in\mathcal{R}$, there is a value $y_{R}$
such that for every set $S^{\prime}\subseteq\mathcal{P}$, if
$\sigma_{\textit{lowA}}[S^{\prime}]\neq\bot$, then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{lowA}}[S^{\prime}]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{lowA}}[S_{I}])&\text{if
$\textit{last}_{R}(\sigma_{\textit{lowA}}[S_{I}])\in S^{\prime}$}\\\
y_{R}&\text{otherwise}\end{cases}$

We just showed that for every process $p\in I$, if $p$ accesses a register $R$
during $E(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})$, then either
$\textit{last}_{R}(\sigma_{\textit{lowA}}[S_{I}])=p$ or
$\textit{last}_{R}(\sigma_{\textit{lowA}}[S_{I}])\in
F(\sigma_{\textit{lowA}}[S_{I}])\cup(\mathcal{P}\setminus S_{I})$. Thus for
every process $p\in I$, if $p$ accesses a register $R$ during
$E(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})$, then there is a value $y_{R}$
such that for every set $S^{\prime}\subseteq\mathcal{P}$, if
$\sigma_{\textit{lowA}}[S^{\prime}]\neq\bot$, then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{lowA}}[S^{\prime}]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{lowA}}[S_{I}])&\text{if
$p\in S^{\prime}$}\\\ y_{R}&\text{otherwise}\end{cases}$

Consequently, observe that for each register $R\in\mathcal{R}$, if $R$ is
accessed during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$ then
$\textit{val}_{R}(\sigma_{\textit{lowA}}[S_{I}])=\textit{val}_{R}(\sigma_{\textit{lowA}}[S])$
((L5)).

By Section 3.2, $\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowA}}[0..2^{n}-1])=S_{I}$. So by Invariant
(I3), for each process $p\in S$,
$\textit{state}_{p}(\sigma_{\textit{lowA}}[S])=\textit{state}_{p}(\sigma_{\textit{lowA}}[S_{I}])$.

Then, since we have proven ((L1)) and ((L5)), during both
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$ and
$E(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})$, for each process $p\in I\cap
S$, $p$ performs the same operation on the same register, causing the same
resulting state and response. This implies that:

  * •

For each register $R\in\mathcal{R}$, if $R$ is accessed during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$ then
$\textit{val}_{R}(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})=\textit{val}_{R}(C^{\prime}_{S},\sigma^{\prime}_{S})$
((L6)).

  * •

For each process $p\in S$,
$\textit{state}_{p}(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})=\textit{state}_{p}(C^{\prime}_{S},\sigma^{\prime}_{S})$
((L7)). (Recall that $\sigma^{\prime}_{S}$ consists of exactly one non-crash
step of each process in $I\cap S$ and no other steps, so the states of other
processes do not change.)

Since $\sigma_{\textit{lowA}}[S]\neq\bot$, by construction,
$\sigma_{\textit{old}}[S]\neq\bot$. By Section 3.2 ((S3)), for each process
$p\in S\setminus F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$,
$p$ incurs an RMR at the end of $E(\sigma_{\textit{setupA}}[S]\circ p)$. By
construction and Section 3.2 (Invariant (I4)),
$\sigma_{\textit{lowA}}[S]=\sigma_{\textit{setupB}}[S]=\sigma_{\textit{setupA}}[S]$,
and
$F(\sigma_{\textit{lowA}}[S_{I}])=F(\sigma_{\textit{setupA}}[S_{I}])=F(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])=F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])$.
Thus for each process $p\in S\setminus F(\sigma_{\textit{lowA}}[S_{I}])$, $p$
incurs an RMR at the end of $E(\sigma_{\textit{lowA}}[S]\circ p)$. By
definition, $S_{I}=I\cup F(\sigma_{\textit{lowA}}[S_{I}])$, so since
$S\subseteq S_{I}$, $S\setminus F(\sigma_{\textit{lowA}}[S_{I}])=I\cap S$.
Finally, recall that $\sigma^{\prime}_{S}$ contains exactly one non-crash step
of each process in $I\cap S$ and no other steps. Consequently, since we have
already proven that each process $I\cap S$ accesses a different register
during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$, observe that each process in
$I\cap S$ must incur exactly one RMR during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$ ((L8)).

By Section 3.2, $\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant, so
by Invariant (I7), each process that is not in $F(\sigma_{\textit{lowA}}[S])$
does not enter the critical section during $E(\sigma_{\textit{lowA}}[S])$.
Recall that $\sigma^{\prime}_{S}$ consists of exactly one non-crash step of
each process in $I\cap S=S\setminus F(\sigma_{\textit{lowA}}[S_{I}])$ and no
other steps. Thus, with only one step, although a process could enter the
critical section during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$, it cannot
have taken any steps within the critical section. Thus by Assumption (A1), no
process can leave the critical section during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$. So for each process $p\in S\setminus
F(\sigma_{\textit{lowA}}[S_{I}])$, $p$ has not left the critical section
during $E(\sigma_{\textit{lowA}}[S]\circ\sigma^{\prime}_{S})$ ((L9)).
Therefore, since no process in $S\setminus F(\sigma_{\textit{lowA}}[S_{I}])$
has left the critical section during
$E(\sigma_{\textit{lowA}}[S]\circ\sigma^{\prime}_{S})$, no process in
$S\setminus F(\sigma_{\textit{lowA}}[S_{I}])$ has completed its super-passage
during $E(\sigma_{\textit{lowA}}[S]\circ\sigma^{\prime}_{S})$. Thus
$F(\sigma_{\textit{lowA}}[S])=F(\sigma_{\textit{lowA}}[S]\circ\sigma^{\prime}_{S})$
((L10)). ∎

We now construct a new array $\sigma_{\textit{lowB}}[0..2^{n}-1]$ such that
for every set $S\subseteq\mathcal{P}$, $\sigma_{\textit{lowB}}[S]=\bot$ if
$\sigma_{\textit{lowA}}[S]=\bot$; otherwise
$\sigma_{\textit{lowB}}[S]=\sigma_{\textit{lowA}}[S]\circ\sigma^{\prime}_{S}$.

###### Lemma .

Except for Invariant (I7), $\sigma_{\textit{lowB}}[0..2^{n}-1]$ is
$i$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowB}}[0..2^{n}-1])=S_{I}$.

###### Proof.

For every set $S\subseteq\mathcal{P}$, if $\sigma_{\textit{lowB}}[S]\neq\bot$,
then by construction,
$\sigma_{\textit{lowB}}[S]=\sigma_{\textit{lowA}}[S]\circ\sigma^{\prime}_{S}$.
By Section 3.2, $\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant, so
by Invariant (I1), $P(\sigma_{\textit{lowA}}[S])\subseteq S$. By the
definition of $\sigma^{\prime}_{S}$, $\sigma^{\prime}_{S}$ contains only steps
of processes in $S\cap I$. Thus $P(\sigma_{\textit{lowB}}[S])\subseteq S$
(Invariant (I1)).

By Section 3.2, $\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowA}}[0..2^{n}-1])=S_{I}$. So by Invariant
(I2), for every set $S\subseteq\mathcal{P}$,
$\sigma_{\textit{lowA}}[S]\neq\bot$ if and only if
$F(\sigma_{\textit{lowA}}[S_{I}])\subseteq S\subseteq S_{I}$. By construction,
for every set $S\subseteq\mathcal{P}$, $\sigma_{\textit{lowB}}[S]=\bot$ if and
only if $\sigma_{\textit{lowA}}[S]=\bot$. Furthermore, by Section 3.2 ((L10)),
$F(\sigma_{\textit{lowB}}[S_{I}])=F(\sigma_{\textit{lowA}}[S_{I}])$. Thus for
every set $S\subseteq\mathcal{P}$, $\sigma_{\textit{lowB}}[S]\neq\bot$ if and
only if $F(\sigma_{\textit{lowB}}[S_{I}])\subseteq S\subseteq S_{I}$
(Invariant (I2)).

By Section 3.2 ((L7)), for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{lowA}}[S]\neq\bot$, and every process $p\in S$,
$\textit{state}_{p}(\sigma_{\textit{lowB}}[S_{I}])=\textit{state}_{p}(C^{\prime}_{S_{I}},\sigma_{S_{I}})\textit{state}_{p}(C^{\prime}_{S},\sigma^{\prime}_{S})=\textit{state}_{p}(\sigma_{\textit{lowB}}[S])$.
By construction, for every set $S\subseteq\mathcal{P}$,
$\sigma_{\textit{lowB}}[S]=\bot$ if and only if
$\sigma_{\textit{lowA}}[S]=\bot$. Furthermore, we have already proven that for
every set $S\subseteq\mathcal{P}$, $\sigma_{\textit{lowB}}[S]\neq\bot$ if and
only if $F(\sigma_{\textit{lowB}}[S_{I}])\subseteq S\subseteq S_{I}$. Thus for
every process $p\in S_{I}$ and every set $S\subseteq\mathcal{P}$ that contains
$p$, if $\sigma_{\textit{lowB}}[S]\neq\bot$, then
$\textit{state}_{p}(\sigma_{\textit{lowB}}[S])=\textit{state}_{p}(\sigma_{\textit{lowB}}[S_{I}])$
(Invariant (I3)).

Since we have already proven that Invariants (I1), (I2), and (I3) hold for
$\sigma_{\textit{lowB}}[0..2^{n}-1]$, it immediately follows that Invariant
(I4) also holds.

By Section 3.2 ((L5)), for every process $p\in I$, if $p$ accesses a register
$R$ during $E(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})$, then there is a
value $y_{R}$ such that for every set $S^{\prime}\subseteq\mathcal{P}$, if
$\sigma_{\textit{lowA}}[S^{\prime}]\neq\bot$, then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{lowA}}[S^{\prime}]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{lowA}}[S_{I}])&\text{if
$p\in S^{\prime}$}\\\ y_{R}&\text{otherwise}\end{cases}$

Note that since $p$ accesses $R$ during
$E(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})$, by Section 3.2 ((L1)),
$\textit{last}_{R}(\sigma_{\textit{lowB}}[S_{I}])=p$. By Section 3.2,
$\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant, so if $p\in
S^{\prime}$, then $p$ also accesses $R$ during
$E(C^{\prime}_{S^{\prime}},\sigma^{\prime}_{S^{\prime}})$. Thus by Section 3.2
((L6)), if $p\in S^{\prime}$, then
$\textit{val}_{R}(\sigma_{\textit{lowB}}[S^{\prime}])=\textit{val}_{R}(\sigma_{\textit{lowB}}[S_{I}])$.
Furthermore, by Section 3.2 ((L1)), for every set $S\subseteq\mathcal{P}$ such
that $\sigma_{\textit{lowA}}[S]\neq\bot$, $R$ cannot be accessed by any
process other than $p$ during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$.
Therefore if $p\not\in S^{\prime}$, then $R$ cannot be accessed during
$E(C^{\prime}_{S^{\prime}},\sigma^{\prime}_{S^{\prime}})$, and so
$\textit{val}_{R}(\sigma_{\textit{lowB}}[S^{\prime}])=y_{R}$. Thus we have
that for every register $R\in\mathcal{R}$ such that some process $p$ accesses
$R$ during $E(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})$, for every set
$S^{\prime}\subseteq\mathcal{P}$, if
$\sigma_{\textit{lowB}}[S^{\prime}]\neq\bot$, then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{lowB}}[S^{\prime}]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{lowB}}[S_{I}])&\text{if
$p=\textit{last}_{R}(\sigma_{\textit{lowB}}[S_{I}])\in S^{\prime}$}\\\
y_{R}&\text{otherwise}\end{cases}$

Then, since any register that is not accessed by any process during
$E(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})$ clearly does not change its
state, observe that Invariant (I5) holds for
$\sigma_{\textit{lowB}}[0..2^{n}-1]$.

By Section 3.2, $\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant, so
Invariant (I6) holds for $\sigma_{\textit{lowA}}[0..2^{n}-1]$. For every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{lowA}}[S]\neq\bot$,
$\sigma^{\prime}_{S}$ contains no crash steps. Thus Invariant (I6) also holds
for $\sigma_{\textit{lowB}}[0..2^{n}-1]$.

By Section 3.2, $\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowA}}[0..2^{n}-1])=S_{I}$. So by Invariant
(I8), for every process $p\in S_{I}\setminus
F(\sigma_{\textit{lowA}}[S_{I}])$, every register $R\in\mathcal{R}$ owned by
$p$, and every set $S\subseteq\mathcal{P}$ with
$\sigma_{\textit{lowA}}[S]\neq\bot$, $R$ can only be accessed by $p$ during
$E(\sigma_{\textit{lowA}}[S])$. By Section 3.2 ((L2)), for every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{lowA}}[S]\neq\bot$, for
each process $p\in I$, if $p$ accesses a register $R$ during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$, then the owner of $R$ is not in
$I\setminus\\{p\\}=(S_{I}\setminus
F(\sigma_{\textit{lowA}}[S_{I}]))\setminus\\{p\\}$. In other words, for every
set $S\subseteq\mathcal{P}$ such that $\sigma_{\textit{lowA}}[S]\neq\bot$, for
each process $p\in I$, if $p$ owns a register $R$, then no other process in
$I=S_{I}\setminus F(\sigma_{\textit{lowA}}[S_{I}])$ accesses $R$ during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$. By Section 3.2 ((L10)),
$F(\sigma_{\textit{lowA}}[S_{I}])=F(\sigma_{\textit{lowB}}[S_{I}])$.
Consequently, for every process $p\in S_{I}\setminus
F(\sigma_{\textit{lowB}}[S_{I}])$, every register $R\in\mathcal{R}$ owned by
$p$, and every set $S\subseteq\mathcal{P}$ with
$\sigma_{\textit{lowB}}[S]\neq\bot$, $R$ can only be accessed by $p$ during
$E(\sigma_{\textit{lowB}}[S])$ (Invariant (I8)).

By Section 3.2, $\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowA}}[0..2^{n}-1])=S_{I}$. So by Invariant
(I3), for every process $p\in S_{I}$ and every set $S\subseteq\mathcal{P}$
that contains $p$, if $\sigma_{\textit{lowA}}[S]\neq\bot$, then
$\textit{state}_{p}(\sigma_{\textit{lowA}}[S])=\textit{state}_{p}(\sigma_{\textit{lowA}}[S_{I}])$.
Furthermore, by Invariant (I9), in the CC model, for every process $p\in
S_{I}\setminus F(\sigma_{\textit{lowA}}[S_{I}])$, there is a set
$\mathcal{R}_{p}$ of registers such that for every set $S\subseteq\mathcal{P}$
that contains $p$, if $\sigma_{\textit{lowA}}[S]\neq\bot$, then the set of
registers that $p$ has valid cache copies of at the end of
$E(\sigma_{\textit{lowA}}[S])$ is exactly $\mathcal{R}_{p}$. Recall that for
every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{lowA}}[S]\neq\bot$, $\sigma^{\prime}_{S}$ contains exactly
one non-crash step of each process in $S_{I}$ and no other steps. By Section
3.2 ((L1)), for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{lowA}}[S]\neq\bot$, each register is accessed by at most one
process $p\in I\cap S$ during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$ and no
other processes. Furthermore, by Section 3.2 ((L5)), for every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{lowA}}[S]\neq\bot$, for
every register $R\in\mathcal{R}$, if $R$ is accessed during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$, then
$\textit{val}_{R}(\sigma_{\textit{lowA}}[S_{I}])=\textit{val}_{R}(\sigma_{\textit{lowA}}[S])$.
Thus for every process $p\in S_{I}$ and every set $S\subseteq\mathcal{P}$ such
that $\sigma_{\textit{lowA}}[S]\neq\bot$, during both
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$ and
$E(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})$, $p$ performs the same
operation on the same register which begins with the same value, causing the
same resulting state and response. There are two cases: either this operation
that $p$ performs on $R$ is a read operation, or it is not.

If it is a read operation, then no cache copies are invalidated by the read,
and $p$ creates a new valid cache copy of $R$ during both
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$ and
$E(C^{\prime}_{S_{I}},\sigma^{\prime}_{S_{I}})$, thus observe that for every
set $S^{\prime}\subseteq\mathcal{P}$ that contains $p$, if
$\sigma_{\textit{lowB}}[S^{\prime}]\neq\bot$, then the set of registers that
$p$ has valid cache copies of is exactly $\mathcal{R}_{p}\cup\\{R\\}$. If it
is not a read operation, then cache copies can be invalidated, but by Section
3.2 ((L4)), the invalidated cache copies cannot belong to any process in
$I\setminus\\{p\\}=(S_{I}\setminus
F(\sigma_{\textit{lowA}}[S_{I}]))\setminus\\{p\\}$. Thus the cache copies of
every process in $(S_{I}\setminus
F(\sigma_{\textit{lowA}}[S_{I}]))\setminus\\{p\\}$ are unaffected, whereas
observe that for every set $S^{\prime}\subseteq\mathcal{P}$ that contains $p$,
if $\sigma_{\textit{lowB}}[S^{\prime}]\neq\bot$, then the set of registers
that $p$ has valid cache copies of is exactly
$\mathcal{R}_{p}\setminus\\{R\\}$. By Section 3.2 ((L10)),
$F(\sigma_{\textit{lowA}}[S_{I}])=F(\sigma_{\textit{lowB}}[S_{I}])$.
Consequently, in both cases, for every process $p\in S_{I}\setminus
F(\sigma_{\textit{lowB}}[S_{I}])$, there is a set $\mathcal{R}^{\prime}_{p}$
of registers (namely either $\mathcal{R}_{p}\cup R$ or
$\mathcal{R}_{p}\setminus\\{R\\}$ where $R$ is the one register that $p$ is
poised to access at the end of $E(\sigma_{\textit{lowA}}[S_{I}])$) such that
for every set $S\subseteq\mathcal{P}$ that contains $p$, if
$\sigma_{\textit{lowB}}[S]\neq\bot$, then the set of registers that $p$ has
valid cache copies of is exactly $\mathcal{R}^{\prime}_{p}$ (Invariant (I9)).

By Section 3.2, $\sigma_{\textit{lowA}}[0..2^{n}-1]$ is $(i-1)$-compliant, so
by Invariant (I10), for every set $S\subseteq\mathcal{P}$ and every process
$p\in S\setminus F(\sigma_{\textit{lowA}}[S])$, if
$\sigma_{\textit{lowA}}[S]\neq\bot$, then $p$ incurs at least $i-1$ RMRs
during $E(\sigma_{\textit{lowA}}[S])$. By Section 3.2 ((L8)), for every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{lowA}}[S]\neq\bot$, each
process in $I\cap S$ incurs exactly one RMR during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$. By construction, for every set
$S\subseteq\mathcal{P}$, if $\sigma_{\textit{lowB}}[S]\neq\bot$, then
$\sigma_{\textit{lowB}}[S]=\sigma_{\textit{lowA}}[S]\circ\sigma^{\prime}_{S}$,
i.e., every process in $I\cap S=S\setminus F(\sigma_{\textit{lowA}}[S_{I}])$
incurs exactly one more RMR during $E(\sigma_{\textit{lowB}}[S])$ than during
$E(\sigma_{\textit{lowA}}[S])$. By Section 3.2 ((L10)),
$F(\sigma_{\textit{lowA}}[S_{I}])=F(\sigma_{\textit{lowB}}[S_{I}])$. Since we
have already proven that Invariant (I4) holds for
$\sigma_{\textit{lowB}}[0..2^{n}-1]$,
$F(\sigma_{\textit{lowB}}[S_{I}])=F(\sigma_{\textit{lowB}}[S])$ for every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{lowB}}[S]\neq\bot$. Thus
for every set $S\subseteq\mathcal{P}$ and every process $p\in S\setminus
F(\sigma_{\textit{lowB}}[S])$, if $\sigma_{\textit{lowB}}[S]\neq\bot$, then
$p$ incurs at least $i$ RMRs during $E(\sigma_{\textit{lowA}}[S])$ (Invariant
(I10)). ∎

We now construct another array $\sigma_{\textit{lowB}}[0..2^{n}-1]$ with the
goal of satisfying Invariant (I7) as follows. If no process is within the
critical section at the end of $E(\sigma_{\textit{lowB}}[S_{I}])$, we simply
construct $\sigma_{\textit{lowB}}[0..2^{n}-1]$ such that
$\sigma_{\textit{lowB}}[0..2^{n}-1]=\sigma_{\textit{lowB}}[0..2^{n}-1]$.
Furthermore, we define $S^{\textit{low}}_{\textit{max}}=S_{I}$.

Otherwise, to avoid violating mutual exclusion, there must be exactly one
process $p\in S_{I}\setminus F(\sigma_{\textit{lowB}}[S_{I}])$ such that at
the end of $E(\sigma_{\textit{lowB}}[S_{I}])$, $p$ is within the critical
section. Then note that by Section 3.2 and Invariant (I3), for every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{lowB}}[S]\neq\bot$, if
$p\in S$ then $p$ is also within the critical section at the end of
$E(\sigma_{\textit{lowB}}[S])$; otherwise no process is within the critical
section at the end of $E(\sigma_{\textit{lowB}}[S])$. Thus we construct
$\sigma_{\textit{lowB}}[0..2^{n}-1]$ such that for every set
$S\subseteq\mathcal{P}$, if $p\in S$, then $\sigma_{\textit{lowB}}[S]=\bot$;
otherwise $\sigma_{\textit{lowB}}[S]=\sigma_{\textit{lowB}}[S]$. Furthermore,
we define $S^{\textit{low}}_{\textit{max}}=S_{I}\setminus\\{p\\}$.

###### Lemma .

This new array $\sigma_{\textit{lowB}}[0..2^{n}-1]$ is $i$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowB}}[0..2^{n}-1])=S^{\textit{low}}_{\textit{max}}$.

###### Proof.

By Section 3.2, except for Invariant (I7),
$\sigma_{\textit{lowB}}[0..2^{n}-1]$ is $i$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowB}}[0..2^{n}-1])=S_{I}$.

If no process is within the critical section at the end of
$E(\sigma_{\textit{lowB}}[S_{I}])$, then
$\sigma_{\textit{lowB}}[0..2^{n}-1]=\sigma_{\textit{lowB}}[0..2^{n}-1]$. Thus
by Section 3.2 and Section 3.2 ((L9)), Invariant (I7) also holds for
$\sigma_{\textit{lowB}}[0..2^{n}-1]$, and so it follows that
$\sigma_{\textit{lowB}}[0..2^{n}-1]=\sigma_{\textit{lowB}}[0..2^{n}-1]$ is
$i$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowB}}[0..2^{n}-1])=S^{\textit{low}}_{\textit{max}}=S_{I}$.

Otherwise, there is exactly one process $p\in S_{I}\setminus
F(\sigma_{\textit{lowB}}[S_{I}])$ such that $p$ is within the critical section
at the end of $E(\sigma_{\textit{lowB}}[S_{I}])$, and for every set
$S\subseteq\mathcal{P}$, if $p\in S$, then $\sigma_{\textit{lowB}}[S]=\bot$;
otherwise $\sigma_{\textit{lowB}}[S]=\sigma_{\textit{lowB}}[S]$. By Section
3.2, except for Invariant (I7), $\sigma_{\textit{lowB}}[0..2^{n}-1]$ is
$i$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowB}}[0..2^{n}-1])=S_{I}$. Thus observe
that by the construction of $\sigma_{\textit{lowB}}[0..2^{n}-1]$, Invariants
(I1), (I2), (I3), (I4), (I5), (I6), (I8), (I9), (I10) must all also hold for
$\sigma_{\textit{lowB}}[0..2^{n}-1]$ with
$S_{\textit{max}}(\sigma_{\textit{lowB}}[0..2^{n}-1])=S^{\textit{low}}_{\textit{max}}=S_{I}\setminus\\{p\\}$.

By the construction of $\sigma_{\textit{lowB}}[0..2^{n}-1]$, for every set
$S\subseteq\mathcal{P}$, if $p\in S$, then $\sigma_{\textit{lowB}}[S]=\bot$.
Thus for every set $S\subseteq\mathcal{P}$, if
$\sigma_{\textit{lowB}}[S]\neq\bot$, then $p\not\in S$. Consequently, for
every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{lowB}}[S]\neq\bot$, no process is within the critical section
at the end of $E(\sigma_{\textit{lowB}}[S])=E(\sigma_{\textit{lowB}}[S])$.
Therefore by Section 3.2 ((L9)), Invariant (I7) holds for
$\sigma_{\textit{lowB}}[0..2^{n}-1]$, and thus
$\sigma_{\textit{lowB}}[0..2^{n}-1]$ is $i$-compliant with
$S_{\textit{max}}(\sigma_{\textit{lowB}}[0..2^{n}-1])=S^{\textit{low}}_{\textit{max}}$.
∎

Finally, we terminate this $i$-th iteration by setting
$\sigma_{\textit{round}}[i,0..2^{n}-1]=\sigma_{\textit{lowB}}[0..2^{n}-1]$.

####  $i$-th Iteration (High Contention Phase if $|L|<|H|$):

By Section 3.2, $\sigma_{\textit{setupB}}[0..2^{n}-1]$ is $(i-1)$-compliant
with
$S_{\textit{max}}(\sigma_{\textit{setupB}}[0..2^{n}-1])=S^{\textit{setup}}_{\textit{max}}$.
Recall that $H=\bigcup_{R\in\mathcal{R}\atop|B_{R}|\geq k}B_{R}$, where for
every register $R\in\mathcal{R}$, $B_{R}$ is the set of processes poised to
access $R$ at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$.

We first divide the processes in $H$ into groups of exactly $k$ processes such
that within each group, all processes are poised to access the same register
at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$. We make as
many such groups as possible. Then let $H_{1}$ be the set of processes in the
resulting groups, i.e., $H_{1}$ is a modification of $H$ where all processes
that are not in any group are removed. Note that by this construction, since
$H=\bigcup_{R\in\mathcal{R}\atop|B_{R}|\geq k}B_{R}$, $|H_{1}|>|H|/2$.

Next, let $H_{2}$ be a modification of $H_{1}$ such that for each process
$p\in H_{1}$, $p$ is in $H_{2}$ if and only if both of the following are true:

  * •

No process in $H_{1}$ is poised to access a register owned by $p$ at the end
of $E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$.

  * •

No process in $H_{1}$ is poised to access a register $R$ at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$ such that
$\textit{last}_{R}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])=p$.

Note that since $H_{1}$ is composed of groups of exactly $k$ processes that
are all poised to access the same register at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$, there are at
most $|H_{1}|/k$ registers that are poised to be accessed by processes in
$H_{1}$, and thus there are at most $2|H_{1}|/k$ processes removed in the
construction of $H_{2}$ from $H_{1}$.

Then let $H_{3}$ be a modification of $H_{2}$ such that each remaining group
of $H_{2}$ with at least $k/4$ processes is shrunk to contain only $k/4$
processes, and all other groups are removed. Since at most $2|H_{1}|/k$
processes were removed in the construction of $H_{2}$ from $H_{1}$, and
$k>\log n$, at least half of the processes remain, and so it is easy to see
that at least a quarter of the groups in $H_{2}$ remain with at least $k/4$
processes. So $|H_{3}|\geq|H_{1}|/16>|H|/32$.

Next, recall that all registers support only read, fetch-and-store (FAS),
fetch-and-increment (FAI), and compare-and-swap (CAS) operations. Let
$\textit{opt}_{H}$ denote one of these 4 operation types such that the
plurality of processes in $H$ are poised to perform an operation of type
$\textit{opt}_{H}$ at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$. Then let
$H_{4}$ be a modification of $H_{3}$ such that for each process $p\in H_{3}$,
$p$ is in $H_{4}$ if and only if $p$ is poised to perform an operation of type
$\textit{opt}_{H}$ at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$. Since there
are only 4 operation types, $|H_{4}|\geq|H_{3}|/4$.

Now let $H_{5}$ be a modification of $H_{4}$ such that each group of $H_{4}$
with at least $k/32$ processes is shrunk to contain only $k/32$ processes, and
all other groups are removed. Since each group of $H_{3}$ originally had
exactly $k/4$ processes and $|H_{4}|\geq|H_{3}|/4$ where $k>\log n$, it is
easy to see that at least an eighth of the groups in $H_{4}$ remain with at
least $k/32$ of the processes. So
$|H_{5}|\geq|H_{3}|/64\geq|H_{1}|/1024>|H|/2048$.

Let $h$ be the number of remaining groups in $H_{5}$. Then since $H_{5}$ only
contains groups with exactly $k/32$ processes, $h=32|H_{5}|/k$. We arbitrarily
order these groups, and construct an array $G[0..h-1]$ such that for every
integer $j\in\\{0,1,\ldots,h-1\\}$, $G[j]$ is the $j$-th group in the
ordering. Then for every integer $j\in\\{0,1,\ldots,h-1\\}$, let $R[j]$ be the
register that every process in $G[j]$ is poised to access at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$.

Finally, let
$S_{H}=F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])\cup
H_{5}$. We now construct a new array $\sigma_{\textit{highA}}[0..2^{n}-1]$
such that for every set $S\subseteq\mathcal{P}$, if $S\not\subseteq S_{H}$,
then $\sigma_{\textit{highA}}[S]=\bot$; otherwise
$\sigma_{\textit{highA}}[S]=\sigma_{\textit{setupB}}[S]$.

###### Lemma .

This new array $\sigma_{\textit{highA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{highA}}[0..2^{n}-1])=S_{H}$. Furthermore,
for every integer $j\in\\{0,1,\ldots,h-1\\}$:

  * •

For every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highA}}[S]\neq\bot$, every process in $G[j]\cap S$ is poised
to access $R[j]$ at the end of $E(\sigma_{\textit{highA}}[S])$.

  * •

The owner of $R[j]$ is not in $S_{H}\setminus
F(\sigma_{\textit{highA}}[S_{H}])$.

  * •

For every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highA}}[S]\neq\bot$,
$\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S])=\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S_{H}])$.

###### Proof.

By Section 3.2, $\sigma_{\textit{setupB}}[0..2^{n}-1]$ is $(i-1)$-compliant
with
$S_{\textit{max}}(\sigma_{\textit{setupB}}[0..2^{n}-1])=S^{\textit{setup}}_{\textit{max}}$.
By construction, $\sigma_{\textit{highA}}[0..2^{n}-1]$ is simply a
modification of $\sigma_{\textit{setupB}}[0..2^{n}-1]$ where every set
$S\subseteq\mathcal{P}$ that contains any process in
$S^{\textit{setup}}_{\textit{max}}\setminus S_{H}$ has had
$\sigma_{\textit{highA}}[S]$ set to $\bot$, where
$F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])\subseteq
S_{H}\subseteq S^{\textit{setup}}_{\textit{max}}$. It suffices to observe that
since every invariant still holds with
$S_{\textit{max}}(\sigma_{\textit{highA}}[0..2^{n}-1])=S_{H}$,
$\sigma_{\textit{highA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{highA}}[0..2^{n}-1])=S_{H}$.

Now let $j$ be an integer in $\\{0,1,\ldots,h-1\\}$. By definition, $R[j]$ is
the register that every process in $G[j]$ is poised to access at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$. By Section
3.2, $\sigma_{\textit{setupB}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{setupB}}[0..2^{n}-1])=S^{\textit{setup}}_{\textit{max}}$.
So by Invariant (I3), for every process $p\in
S^{\textit{setup}}_{\textit{max}}$ and every set $S\subseteq\mathcal{P}$ that
contains $p$, if $\sigma_{\textit{setupB}}[S]\neq\bot$, then
$\textit{state}_{p}(\sigma_{\textit{setupB}}[S])=\textit{state}_{p}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$.
Thus for every process $p\in G[j]$ and every set $S\subseteq\mathcal{P}$ that
contains $p$, if $\sigma_{\textit{setupB}}[S]\neq\bot$, then $p$ is also
poised to access $R[j]$ at the end of $E(\sigma_{\textit{setupB}}[S])$.

By the construction of $\sigma_{\textit{highA}}[0..2^{n}-1]$, for every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{highA}}[S]\neq\bot$,
$\sigma_{\textit{highA}}[S]=\sigma_{\textit{setupB}}[S]$. So for every process
$p\in G[j]$ and every set $S\subseteq\mathcal{P}$ that contains $p$, if
$\sigma_{\textit{highA}}[S]\neq\bot$, then $p$ is also poised to access $R[j]$
at the end of $E(\sigma_{\textit{highA}}[S])$. Thus for every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{highA}}[S]\neq\bot$, every
process in $G[j]\cap S$ is poised to access $R[j]$ at the end of
$E(\sigma_{\textit{highA}}[S])$.

Now recall that
$S_{H}=F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])\cup
H_{5}$, where $H_{5}\subseteq H_{2}$. By construction, for each process $p\in
H_{1}$, $p$ is in $H_{2}$ if and only if both of the following are true:

  * •

No process in $H_{1}$ is poised to access a register owned by $p$ at the end
of $E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$.

  * •

No process in $H_{1}$ is poised to access a register $R$ at the end of
$E(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$ such that
$\textit{last}_{R}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])=p$.

We have already shown that $\sigma_{\textit{highA}}[0..2^{n}-1]$ is
$(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{highA}}[0..2^{n}-1])=S_{H}$, and that for
every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highA}}[S]\neq\bot$, every process in $G[j]\cap S$ is poised
to access $R[j]$ at the end of $E(\sigma_{\textit{highA}}[S])$. So by
Invariant (I2), every process in $G[j]\cap S_{H}=G[j]$ is poised to access
$R[j]$ at the end of $E(\sigma_{\textit{highA}}[S_{H}])$. Thus:

  * •

The owner of $R[j]$ is not in $S_{H}\setminus
F(\sigma_{\textit{highA}}[S_{H}])$.

  * •

$\textit{last}_{R[j]}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$
is not in $S_{H}\setminus F(\sigma_{\textit{highA}}[S_{H}])$.

By Section 3.2, $\sigma_{\textit{setupB}}[0..2^{n}-1]$ is $(i-1)$-compliant
with
$S_{\textit{max}}(\sigma_{\textit{setupB}}[0..2^{n}-1])=S^{\textit{setup}}_{\textit{max}}$.
So by Invariant (I5), for every register $R\in\mathcal{R}$, there is a value
$y_{R}$ such that for every set $S\subseteq\mathcal{P}$, if
$\sigma_{\textit{setupB}}[S]\neq\bot$, then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{setupB}}[S]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])&\text{if
$\textit{last}_{R}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])\in
S$}\\\ y_{R}&\text{otherwise}\end{cases}$

We have just shown that
$\textit{last}_{R[j]}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$
is not in $S_{H}\setminus F(\sigma_{\textit{highA}}[S_{H}])$. So either
$\textit{last}_{R[j]}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])\in
F(\sigma_{\textit{highA}}[S_{H}])$ or
$\textit{last}_{R}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])\not\in
S_{H}$.

By the construction of $\sigma_{\textit{highA}}[0..2^{n}-1]$, for every set
$S\subseteq\mathcal{P}$, if $\sigma_{\textit{highA}}[S]\neq\bot$, then
$\sigma_{\textit{highA}}[S]=\sigma_{\textit{setupB}}[S]$. Thus if
$\textit{last}_{R[j]}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$
is in $F(\sigma_{\textit{highA}}[S_{H}])$, then for every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{highA}}[S]\neq\bot$,
$\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S])=\textit{val}_{R[j]}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$.

Otherwise
$\textit{last}_{R}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$
is not in $S_{H}$. Since we have already proven that
$\sigma_{\textit{highA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{highA}}[0..2^{n}-1])=S_{H}$, by Invariant
(I2), for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highA}}[S]\neq\bot$, $S\subseteq S_{H}$, and so
$\textit{last}_{R}(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])$
is not in $S$. Thus for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highA}}[S]\neq\bot$,
$\textit{val}_{R}(\sigma_{\textit{highA}}[S])=y_{R}$.

So in both cases, for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highA}}[S]\neq\bot$,
$\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S])=\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S_{H}])$.
∎

We now iterate over $j\in\\{0,1,\ldots,h-1\\}$ to construct two arrays
$\alpha_{1}[0..h-1]$ and $\alpha_{2}[0..h-1]$ of processes and an array
$\alpha[0..h-1]$ of schedules as follows. If $\textit{opt}_{H}$ is not CAS,
then let $\alpha_{1}[j]$ and $\alpha_{2}[j]$ be two arbitrary but distinct
processes in $G[j]$, and let $\alpha[j]=\alpha_{1}[j]\circ\alpha_{2}[j]$.
Otherwise, consider the register $R[j]$ that every process in $G[j]$ is poised
to access at the end of $E(\sigma_{\textit{highA}}[S_{H}])$. Let
$v_{j}=\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S_{H}]\circ\alpha[0]\circ\alpha[1]\circ\ldots\circ\alpha[j-1])$.
Then let $\alpha_{1}[j]$ be any process in $G[j]$ such that $\alpha_{1}[j]$ is
about to perform a $\textsc{CAS}(v_{j},v^{\prime})$ operation where
$v^{\prime}\neq v_{j}$; if no such process exists, then let $\alpha_{1}[j]$ be
any process in $G[j]$. Next, let $\alpha_{2}[j]$ be any process in
$G[j]\setminus\\{\alpha_{1}[j]\\}$. Finally, let
$\alpha[j]=\alpha_{1}[j]\circ\alpha_{2}[j]$.

For every integer $j\in\\{0,1,\ldots,h-1\\}$, let $\sigma^{j}_{\alpha}$ be the
concatenation of all schedules in $\alpha[0..j]$, i.e.,
$\sigma^{j}_{\alpha}=\alpha[0]\circ\alpha[1]\circ\ldots\circ\alpha[j]$. Then
let $\sigma_{\alpha}=\sigma^{h-1}_{\alpha}$. Furthermore, let $S_{\alpha}$ be
the set of all processes with steps in $\sigma_{\alpha}$. Note that since
$\alpha[j]=\alpha_{1}[j]\circ\alpha_{2}[j]$ for $0\leq j\leq h-1$,

$S_{\alpha}=\bigcup^{h-1}_{j=0}\\{\alpha_{1}[j],\alpha_{2}[j]\\}$

In addition, note that $S_{\alpha}\subseteq H_{5}$ and
$|S_{\alpha}|=2h=64|H_{5}|/k$.

Next, let $S_{F}=S_{\alpha}\cup F(\sigma_{\textit{highA}}[S_{H}])$. Since
$S_{\alpha}\subseteq H_{5}$ and $S_{H}=F(\sigma_{\textit{highA}}[S_{H}])\cup
H_{5}$, $F(\sigma_{\textit{highA}}[S_{H}])\subseteq S_{F}\subseteq S_{H}$. By
Section 3.2, $\sigma_{\textit{highA}}[0..2^{n}-1]$ is $(i-1)$-compliant, so:

  * •

By Invariant (I2), $\sigma_{\textit{highA}}[S_{F}]\neq\bot$.

  * •

By Invariant (I1), $P(\sigma_{\textit{highA}}[S_{F}])\subseteq S_{F}$.

  * •

By Invariant (I4)
$F(\sigma_{\textit{highA}}[S_{F}])=F(\sigma_{\textit{highA}}[S_{H}])$.

Thus observe that to avoid violating deadlock freedom, there must exist a
schedule $\sigma_{F}$ such that:

  * •

$\sigma_{F}$ begins with exactly one crash step of every process in
$S_{\alpha}$, and contains no other crash steps.

  * •

$\sigma_{F}$ contains only steps of processes in $S_{\alpha}=S_{F}\setminus
F(\sigma_{\textit{highA}}[S_{F}])$, i.e., $P(\sigma_{F})=S_{\alpha}$.

  * •

During $E(\sigma_{\textit{highA}}[S_{F}]\circ\sigma_{\alpha}\circ\sigma_{F})$,
every process in $S_{F}$ begins and then completes a super-passage, i.e.,
$F(\sigma_{\textit{highA}}[S_{F}]\circ\sigma_{\alpha}\circ\sigma_{F})=S_{F}$.

Let $C_{F}$ be the configuration at the end of
$E(\sigma_{\textit{highA}}[S_{F}]\circ\sigma_{\alpha})$. Then let
$\mathcal{R}_{F}$ be the set of every register that is accessed during
$E(C_{F},\sigma_{F})$ (after the crash steps of every process in $S_{\alpha}$
at the beginning of $\sigma_{F}$). Next, let $\mathcal{D}\subseteq\mathcal{P}$
be the set of every process $p\in H_{5}\setminus S_{\alpha}$ such that there
exists a register $R\in\mathcal{R}_{F}$ such that either $p$ owns $R$, or
$\textit{last}_{R}(\sigma_{\textit{highA}}[S_{H}])=p$.

###### Lemma .

$|\mathcal{D}|\leq 2|S_{\alpha}|\log n=\frac{128}{k}|H_{5}|\log n$.

###### Proof.

First, consider each register $R\in\mathcal{R}_{F}$ such that $R$ is owned by
a process in $S_{\alpha}$. Since $\mathcal{D}\subseteq H_{5}\setminus
S_{\alpha}$, the owner of $R$ is not in $\mathcal{D}$. Furthermore, by Section
3.2, $\sigma_{\textit{highA}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{highA}}[0..2^{n}-1])=S_{H}$, so by Invariant
(I8), since the owner of $R$ is in $S_{\alpha}\subseteq H_{5}\subseteq
S_{H}\setminus F(\sigma_{\textit{highA}}[S_{H}])$, $R$ cannot be accessed by
any process in $H_{5}\setminus S_{\alpha}$ during
$E(\sigma_{\textit{highA}}[S_{H}])$. So
$\textit{last}_{R}(\sigma_{\textit{highA}}[S_{H}])\not\in\mathcal{D}$. Thus
intuitively, each register $R\in\mathcal{R}_{F}$ that is owned by a process in
$S_{\alpha}$ does not contribute any processes to $\mathcal{D}$.

So it suffices to consider the registers in $\mathcal{R}_{F}$ that are not
owned by any process in $S_{\alpha}$. By Assumption (A2), each process
accesses at most $\log n$ registers that it does not own during a passage.
Thus there are at most $|S_{\alpha}|\log n$ registers in $\mathcal{R}_{F}$
that are not owned by any process in $S_{\alpha}$. Consequently,
$|\mathcal{D}|\leq 2|S_{\alpha}|\log n=\frac{160}{k}|H_{5}|\log n$. ∎

Now let $H_{6}$ be a modification of $H_{5}$ where every process $p\in H_{5}$
is in $H_{6}$ if and only if $p\not\in\mathcal{D}$. Note that since
$\mathcal{D}\subseteq H_{5}\setminus S_{\alpha}$ and $S_{\alpha}\subseteq
H_{5}$, $S_{\alpha}\subseteq H_{6}$. By Section 3.2,
$|\mathcal{D}|\leq\frac{128}{k}|H_{5}|\log n$, so
$|H_{6}|\geq|H_{5}|-\frac{128}{k}|H_{5}|\log n$. For sufficiently large $k$
($k\geq 256\log n$), $\frac{128}{k}|H_{5}|\log n\leq 0.5|H_{5}|$. Thus, at
least half of the processes in $H_{5}$ remain in $H_{6}$, and so it is easy to
see that at least a quarter of the groups in $H_{6}$ remain with at least
$k/128$ processes (out of the $k/32$ originally in $H_{5}$). Furthermore,
since $S_{\alpha}\subseteq H_{6}$, for $0\leq j\leq h-1$, since $S_{\alpha}$
contains $\alpha_{1}[j]$ and $\alpha_{2}[j]$,
$\\{\alpha_{1}[j],\alpha_{2}[j]\\}\subseteq G[j]\cap H_{6}$. So let
$G^{\prime}[0..h-1]$ be a new array such that for all
$j\in\\{0,1,\ldots,h-1\\}$, $G^{\prime}[j]=G[j]\cap H_{6}$, and so
$\\{\alpha_{1}[j],\alpha_{2}[j]\\}\subseteq G^{\prime}[j]$.

Now for every integer $j\in\\{0,1,\ldots,h-1\\}$, let $\beta_{1}[j]$ be
$\varnothing$ if $|G^{\prime}[j]|<k/160$; otherwise, let $\beta_{1}[j]$ be an
arbitrary process in
$G^{\prime}[j]\setminus\\{\alpha_{1}[j],\alpha_{2}[j]\\}$. Then let:

$S_{\beta}=\bigcup^{h-1}_{j=0}\\{\alpha_{1}[j],\alpha_{2}[j],\beta_{1}[j]\\}$

So:

$S_{\beta}=S_{\alpha}\cup\bigcup^{h-1}_{j=0}\\{\beta_{1}[j]\\}$

Note that by construction, $S_{\alpha}\subseteq S_{\beta}\subseteq
H_{6}\subseteq H_{5}$.

###### Lemma .

$|S_{\beta}\setminus S_{\alpha}|>\frac{|H|}{204.8k}$.

###### Proof.

Since at least a quarter of the $h$ groups in $H_{6}$ have at least $k/128$
processes, $\beta_{1}[j]\neq\varnothing$ for at least a quarter of the
integers $j\in\\{0,1,\ldots,h-1\\}$. Thus $|S_{\beta}\setminus S_{\alpha}|\geq
0.25h=8|H_{5}|/k$.

Now recall that $|H_{5}|\geq|H_{3}|/64\geq|H_{1}|/1024>|H|/2048$. So
$|S_{\beta}\setminus S_{\alpha}|\geq 10|H_{5}|/k>\frac{|H|}{204.8k}$. ∎

Next, let $S_{B}=S_{\beta}\cup F(\sigma_{\textit{highA}}[S_{H}])$. We now
construct a new array $\sigma_{\textit{highB}}[0..2^{n}-1]$ such that for
every set $S\subseteq\mathcal{P}$, if $S\not\subseteq S_{B}$, then
$\sigma_{\textit{highB}}[S]=\bot$; otherwise
$\sigma_{\textit{highB}}[S]=\sigma_{\textit{highA}}[S]$. Note that since
$S_{\beta}\subseteq H_{6}\subseteq H_{5}$ and
$S_{H}=F(\sigma_{\textit{highA}}[S_{H}])\cup H_{5}$,
$F(\sigma_{\textit{highA}}[S_{H}])\subseteq S_{B}\subseteq S_{H}$.

###### Lemma .

This new array $\sigma_{\textit{highB}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{highB}}[0..2^{n}-1])=S_{B}$. Furthermore,
for every integer $j\in\\{0,1,\ldots,h-1\\}$:

  * •

For every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highB}}[S]\neq\bot$, every process in $G[j]\cap S$ is poised
to access $R[j]$ at the end of $E(\sigma_{\textit{highB}}[S])$.

  * •

The owner of $R[j]$ is not in $S_{B}\setminus
F(\sigma_{\textit{highB}}[S_{B}])$.

  * •

For every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highB}}[S]\neq\bot$,
$\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S])=\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S_{B}])$.

In addition, for every register $R\in\mathcal{R}_{F}$,

  * •

The owner of $R$ is not in $S_{B}\setminus F(\sigma_{\textit{highB}}[S_{B}])$.

  * •

For every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highB}}[S]\neq\bot$,
$\textit{val}_{R}(\sigma_{\textit{highB}}[S])=\textit{val}_{R}(\sigma_{\textit{highB}}[S_{B}])$.

###### Proof.

By Section 3.2, $\sigma_{\textit{highA}}[0..2^{n}-1]$ is $(i-1)$-compliant
with $S_{\textit{max}}(\sigma_{\textit{highA}}[0..2^{n}-1])=S_{H}$. By
construction, $\sigma_{\textit{highB}}[0..2^{n}-1]$ is simply a modification
of $\sigma_{\textit{highA}}[0..2^{n}-1]$ where every set
$S\subseteq\mathcal{P}$ that contains any process in $S_{H}\setminus S_{B}$
has had $\sigma_{\textit{highB}}[S]$ set to $\bot$, where
$F(\sigma_{\textit{highA}}[S_{H}])\subseteq S_{B}\subseteq S_{H}$. It suffices
to observe that since every invariant still holds with
$S_{\textit{max}}(\sigma_{\textit{highB}}[0..2^{n}-1])=S_{B}$,
$\sigma_{\textit{highB}}[0..2^{n}-1]$ is $(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{highB}}[0..2^{n}-1])=S_{B}$.

Furthermore, by Section 3.2, for every integer $j\in\\{0,1,\ldots,h-1\\}$:

  * •

For every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highA}}[S]\neq\bot$, every process in $G[j]\cap S$ is poised
to access $R[j]$ at the end of $E(\sigma_{\textit{highA}}[S])$.

  * •

The owner of $R[j]$ is not in $S_{H}\setminus
F(\sigma_{\textit{highA}}[S_{H}])$.

  * •

For every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highA}}[S]\neq\bot$,
$\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S])=\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S_{H}])$.

By the construction of $\sigma_{\textit{highB}}[0..2^{n}-1]$, for every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{highB}}[S]\neq\bot$,
$\sigma_{\textit{highB}}[S]=\sigma_{\textit{highA}}[S]$. Thus for every
integer $j\in\\{0,1,\ldots,h-1\\}$ and every set $S\subseteq\mathcal{P}$ such
that $\sigma_{\textit{highB}}[S]\neq\bot$, every process in $G[j]\cap S$ is
poised to access $R[j]$ at the end of $E(\sigma_{\textit{highB}}[S])$.

By Section 3.2, $\sigma_{\textit{highA}}[0..2^{n}-1]$ is $(i-1)$-compliant. So
by Invariant (I4),
$F(\sigma_{\textit{highA}}[S_{H}])=F(\sigma_{\textit{highA}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])$.
Then, since $S_{B}\subseteq S_{H}$, for every integer
$j\in\\{0,1,\ldots,h-1\\}$, the owner of $R[j]$ is not in $S_{B}\setminus
F(\sigma_{\textit{highB}}[S_{B}])$.

Next, for every integer $j\in\\{0,1,\ldots,h-1\\}$ and every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{highB}}[S]\neq\bot$,

$\displaystyle\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S])$
$\displaystyle=\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S])$
$\displaystyle=\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S_{H}])$
$\displaystyle=\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S_{B}])$
$\displaystyle=\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S_{B}])$

Thus we have proven that for every integer $j\in\\{0,1,\ldots,h-1\\}$:

  * •

For every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highB}}[S]\neq\bot$, every process in $G[j]\cap S$ is poised
to access $R[j]$ at the end of $E(\sigma_{\textit{highB}}[S])$.

  * •

The owner of $R[j]$ is not in $S_{B}\setminus
F(\sigma_{\textit{highB}}[S_{B}])$.

  * •

For every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highB}}[S]\neq\bot$,
$\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S])=\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S_{B}])$.

By definition, $\mathcal{D}\subseteq\mathcal{P}$ is the set of every process
$p\in H_{5}\setminus S_{\alpha}$ such that there exists a register
$R\in\mathcal{R}_{F}$ such that either $p$ owns $R$, or
$\textit{last}_{R}(\sigma_{\textit{highA}}[S_{H}])=p$. By construction,
$H_{6}\cap\mathcal{D}=\varnothing$, $S_{\beta}\subseteq H_{6}$, and
$S_{B}=S_{\beta}\cup F(\sigma_{\textit{highA}}[S_{H}])$. Furthermore, recall
that $F(\sigma_{\textit{highA}}[S_{H}])=F(\sigma_{\textit{highB}}[S_{B}])$.
Thus for every register $R\in\mathcal{R}_{F}$, the owner of $R$ is not in
$S_{B}\setminus F(\sigma_{\textit{highB}}[S_{B}])$.

By Section 3.2, $\sigma_{\textit{highA}}[0..2^{n}-1]$ is $(i-1)$-compliant
with $S_{\textit{max}}(\sigma_{\textit{highA}}[0..2^{n}-1])=S_{H}$. So by
Invariant (I5), for every register $R\in\mathcal{R}_{F}$, there is a value
$y_{R}$ such that for every set $S\subseteq\mathcal{P}$, if
$\sigma_{\textit{highA}}[S]\neq\bot$, then:

$\textit{val}_{R}{\bigl{(}{\sigma_{\textit{highA}}[S]}\bigr{)}}=\begin{cases}\textit{val}_{R}(\sigma_{\textit{highA}}[S_{H}])&\text{if
$\textit{last}_{R}(\sigma_{\textit{highA}}[S_{H}])\in S$}\\\
y_{R}&\text{otherwise}\end{cases}$

Since $\textit{last}_{R}(\sigma_{\textit{highA}}[S_{H}])\in\mathcal{D}$ and
$\mathcal{D}\cap S_{\beta}=\varnothing$, for every set $S\subseteq\mathcal{P}$
such that
$F(\sigma_{\textit{highA}}[S_{H}])=F(\sigma_{\textit{highB}}[S_{B}])\subseteq
S\subseteq S_{B}\subseteq S_{H}$,
$\textit{val}_{R}(\sigma_{\textit{highB}}[S])=y_{R}$. Furthermore, since we
have already proven that $\sigma_{\textit{highB}}[0..2^{n}-1]$ is
$(i-1)$-compliant with
$S_{\textit{max}}(\sigma_{\textit{highB}}[0..2^{n}-1])=S_{B}$, by Invariant
(I2), for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highB}}[S]\neq\bot$,
$F(\sigma_{\textit{highB}}[S_{B}])\subseteq S\subseteq S_{B}$. Thus for every
register $R\in\mathcal{R}_{F}$, and every set $S\subseteq\mathcal{P}$ such
that $\sigma_{\textit{highB}}[S]\neq\bot$,
$\textit{val}_{R}(\sigma_{\textit{highB}}[S])=\textit{val}_{R}(\sigma_{\textit{highB}}[S_{B}])$.
∎

We now iterate over $j\in\\{0,1,\ldots,h-1\\}$ to construct an array
$\beta[0..h-1]$ of schedules as follows. Recall that by definition,

  * •

$\beta_{1}[j]$ is $\varnothing$ if $|G^{\prime}[j]|<k/160$; otherwise,
$\beta_{1}[j]$ is an arbitrary process in
$G^{\prime}[j]\setminus\\{\alpha_{1}[j],\alpha_{2}[j]\\}$.

  * •

$v_{j}=\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S_{H}]\circ\sigma^{j-1}_{\alpha})$.

If $\textit{opt}_{H}$ is CAS and $\beta_{1}[j]\neq\varnothing$, then let
$v_{\beta}$ and $v^{\prime}_{\beta}$ be such that $\beta_{1}[j]$ is poised to
perform a $\textsc{CAS}(v_{\beta},v^{\prime}_{\beta})$ operation on $R[j]$ at
the end of $E(\sigma_{\textit{highB}}[S_{B}])$. Note that by Section 3.2 and
Invariant (I3), $\beta_{1}[j]$ would also be poised to perform a
$\textsc{CAS}(v_{\beta},v^{\prime}_{\beta})$ operation on $R[j]$ at the end of
$E(\sigma_{\textit{highB}}[S])$ for every set $S\subseteq\mathcal{P}$ such
that $\sigma_{\textit{highB}}[S]\neq\bot$ and $\beta_{1}[j]\in S$. We then
define:

$\beta[j]=\begin{cases}\alpha_{1}[j]\circ\alpha_{2}[j]=\alpha[j]&\text{if
$|G^{\prime}[j]<k/160$}\\\ \beta_{1}[j]\circ\alpha_{2}[j]&\text{if
$\textit{opt}_{H}$ is FAI}\\\
\beta_{1}[j]\circ\alpha_{1}[j]\circ\alpha_{2}[j]&\text{if $\textit{opt}_{H}$
is CAS and $v_{\beta}\neq v_{j}$}\\\
\alpha_{1}[j]\circ\beta_{1}[j]\circ\alpha_{2}[j]&\text{otherwise}\end{cases}$

By Section 3.2, $\sigma_{\textit{highB}}[0..2^{n}-1]$ is $(i-1)$-compliant
with $S_{\textit{max}}(\sigma_{\textit{highB}}[0..2^{n}-1])=S_{B}$.
Furthermore, $S_{\alpha}\subseteq S_{\beta}\subseteq S_{B}$, so
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S_{B}$. Thus by
Invariant (I2), for every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$,
$\sigma_{\textit{highB}}[S]\neq\bot$.

So for every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$,
let $C^{\prime}_{S}$ be the configuration at the end of
$E(\sigma_{\textit{highB}}[S])$, and let $\sigma^{\prime}_{S}$ be a
modification of $\sigma_{\alpha}$ such that for every integer
$j\in\\{0,1,\ldots,h-1\\}$, if $\beta_{1}[j]\neq\varnothing$ and
$\beta_{1}[j]\in S$, then $\alpha[j]$ is replaced by $\beta[j]$ in
$\sigma^{\prime}_{S}$. Note that by this construction, $\sigma^{\prime}_{S}$
contains exactly one non-crash step of each process in $S_{\beta}\cap S$ and
no other steps.

###### Lemma .

For every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$,
the set of registers accessed during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$
is exactly the set of registers accessed during
$E(C^{\prime}_{S},\sigma_{\alpha})$ and exactly the set of registers in
$R[0..h-1]$.

###### Proof.

First, recall that for every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$,
$\sigma_{\textit{highB}}[S]\neq\bot$. So let $S\subseteq\mathcal{P}$ be a set
of processes such that $F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}\subseteq S\subseteq S_{B}$.

By Section 3.2, for every integer $j\in\\{0,1,\ldots,h-1\\}$, every process in
$G[j]\cap S$ is poised to access $R[j]$ at the end of
$E(\sigma_{\textit{highB}}[S])$. By construction, both $\sigma^{\prime}_{S}$
and $\sigma_{\alpha}$ contain at most one non-crash step of each process in
$S_{\beta}\cap S$ and no other steps. Since $S_{\beta}\subseteq H_{5}$, where
$G[0..h-1]$ are the groups of processes that constitute $H_{5}$, every process
with a step in $\sigma^{\prime}_{S}$ or $\sigma_{\alpha}$ is poised to access
a register in $R[0..h-1]$ at the end of $E(\sigma_{\textit{highB}}[S])$.
Therefore every register accessed during either
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$ or $E(C^{\prime}_{S},\sigma_{\alpha})$
is in $R[0..h-1]$.

Next, by construction, for every integer $j\in\\{0,1,\ldots,h-1\\}$, both
$\sigma^{\prime}_{S}$ and $\sigma_{\alpha}$ contain a non-crash step of
$\alpha_{2}[j]$. By Section 3.2, for every integer $j\in\\{0,1,\ldots,h-1\\}$,
$\alpha_{2}[j]$ is poised to access $R[j]$ at the end of
$E(\sigma_{\textit{highB}}[S])$. So every register in $R[0..h-1]$ is accessed
during both $E(C^{\prime}_{S},\sigma^{\prime}_{S})$ and
$E(C^{\prime}_{S},\sigma_{\alpha})$.

Thus we have shown that the set of registers accessed during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$ is exactly the set of registers
accessed during $E(C^{\prime}_{S},\sigma_{\alpha})$ and exactly the set of
registers in $R[0..h-1]$. ∎

Now for every integer $j\in\\{0,1,\ldots,h-1\\}$, let $\sigma^{\prime}_{S}[j]$
and $\sigma_{\alpha}[j]$ be the suffixes of $\sigma^{\prime}_{S}$ and
$\sigma_{\alpha}$ that contain only the steps of processes in $G[0..j]$. (So
for every integer $j\in\\{0,1,\ldots,h-1\\}$,
$\sigma_{\alpha}[j]=\sigma^{j}_{\alpha}$.) We also define
$\sigma^{\prime}_{S}[-1]=\sigma_{\alpha}[-1]=\varnothing$.

###### Lemma .

For every register $R\in\mathcal{R}$ every integer $j\in\\{0,1,\ldots,h-1\\}$,
and every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$,
$\textit{val}_{R}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=\textit{val}_{R}(C^{\prime}_{S},\sigma_{\alpha}[j])$.

###### Proof.

First, recall that for every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$,
$\sigma_{\textit{highB}}[S]\neq\bot$. So let $S\subseteq\mathcal{P}$ be a set
of processes such that $F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}\subseteq S\subseteq S_{B}$.

By definition, $\sigma^{\prime}_{S}[-1]=\sigma_{\alpha}[-1]=\varnothing$. Thus
for every register $R\in\mathcal{R}$,
$\textit{val}_{R}(C^{\prime}_{S},\sigma^{\prime}_{S}[-1])=\textit{val}_{R}(C^{\prime}_{S},\sigma_{\alpha}[-1])$.
So it suffices to show that for every register $R\in\mathcal{R}$ and every
integer $j\in\\{0,1,\ldots,h-1\\}$, if
$\textit{val}_{R}(C^{\prime}_{S},\sigma^{\prime}_{S}[j-1])=\textit{val}_{R}(C^{\prime}_{S},\sigma_{\alpha}[j-1])$,
then
$\textit{val}_{R}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=\textit{val}_{R}(C^{\prime}_{S},\sigma_{\alpha}[j])$.

Thus let $j$ be an integer in $\\{0,1,\ldots,h-1\\}$, and suppose that for
every register $R\in\mathcal{R}$,
$\textit{val}_{R}(C^{\prime}_{S},\sigma^{\prime}_{S}[j-1])=\textit{val}_{R}(C^{\prime}_{S},\sigma_{\alpha}[j-1])$.
By the construction of $\sigma^{\prime}_{S}$, $\alpha[j]$ is replaced by
$\beta[j]$ if and only if $\beta_{1}[j]\neq\varnothing$ and $\beta_{1}[j]\in
S$. Thus if either $\beta_{1}[j]=\varnothing$ or $\beta_{1}[j]\not\in S$, then
for every register $R\in\mathcal{R}$,
$\textit{val}_{R}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=\textit{val}_{R}(C^{\prime}_{S},\sigma_{\alpha}[j])$
as wanted.

Otherwise, $\beta_{1}[j]\neq\varnothing$ and $\beta_{1}[j]\in S$. Then by the
definition of $\beta[j]$:

$\beta[j]=\begin{cases}\beta_{1}[j]\circ\alpha_{2}[j]&\text{if
$\textit{opt}_{H}$ is FAI}\\\
\beta_{1}[j]\circ\alpha_{1}[j]\circ\alpha_{2}[j]&\text{if $\textit{opt}_{H}$
is CAS and $v_{\beta}\neq v_{j}$}\\\
\alpha_{1}[j]\circ\beta_{1}[j]\circ\alpha_{2}[j]&\text{otherwise}\end{cases}$

Since $\alpha_{1}[j]$ and $\alpha_{2}[j]$ are in $S_{\alpha}\subseteq S$, all
of $\alpha_{1}[j]$, $\alpha_{2}[j]$, and $\beta_{1}[j]$ are in $G[j]\cap S$.
So by Section 3.2, all of $\alpha_{1}[j]$, $\alpha_{2}[j]$, and $\beta_{1}[j]$
are poised to access $R[j]$ at the end of $E(\sigma_{\textit{highB}}[S])$. By
construction, both $\sigma^{\prime}_{S}$ and $\sigma_{\alpha}$ contain at most
one non-crash step of each process and no other steps. Thus for each process
$p\in\\{\alpha_{1}[j],\alpha_{2}[j],\beta_{1}[j]\\}$,
$\textit{state}_{p}(C^{\prime}_{S},\sigma^{\prime}_{S}[j-1])=\textit{state}_{p}(\sigma_{\textit{highB}}[S])=\textit{state}_{p}(C^{\prime}_{S},\sigma_{\alpha}[j-1])$.

Therefore all of $\alpha_{1}[j]$, $\alpha_{2}[j]$, and $\beta_{1}[j]$ are
poised to access $R[j]$ at the end of both