$E(C^{\prime}_{S},\sigma^{\prime}_{S}[j-1])$ and
$E(C^{\prime}_{S},\sigma_{\alpha}[j-1])$. Thus for every register
$R\in\mathcal{R}\setminus R[j]$,
$\textit{val}_{R}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=\textit{val}_{R}(C^{\prime}_{S},\sigma_{\alpha}[j])$.
It now suffices to show that
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=\textit{val}_{R[j]}(C^{\prime}_{S},\sigma_{\alpha}[j])$.

If $\textit{opt}_{H}$ is read, then since reads do not change the value of a
register,
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=\textit{val}_{R[j]}(C^{\prime}_{S},\sigma_{\alpha}[j])$
as wanted.

If $\textit{opt}_{H}$ is FAS, then $\alpha[j]=\alpha_{1}[j]\circ\alpha_{2}[j]$
and $\beta[j]=\alpha_{1}[j]\circ\beta_{1}[j]\circ\alpha_{2}[j]$. Let $v_{2}$
be the value such that $\alpha_{2}[j]$ is poised to perform
$\textsc{FAS}(v_{2})$ at the end of both
$E(C^{\prime}_{S},\sigma^{\prime}_{S}[j-1])$ and
$E(C^{\prime}_{S},\sigma_{\alpha}[j-1])$. Then
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma_{\alpha}[j])=v_{2}$ and
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=v_{2}$. Thus
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=\textit{val}_{R[j]}(C^{\prime}_{S},\sigma_{\alpha}[j])$
as wanted.

If $\textit{opt}_{H}$ is FAI, then $\alpha[j]=\alpha_{1}[j]\circ\alpha_{2}[j]$
and $\beta[j]=\beta_{1}[j]\circ\alpha_{2}[j]$. So
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma_{\alpha}[j])=\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{\alpha}[j-1])+2$
and
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S}[j-1])+2$.
Thus
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=\textit{val}_{R[j]}(C^{\prime}_{S},\sigma_{\alpha}[j])$
as wanted.

Finally, consider the case where $\textit{opt}_{H}$ is CAS. Recall that
$v_{j}=\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S_{H}]\circ\sigma_{\alpha}[j-1])$.
By Section 3.2,
$\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S_{H}])=\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S])$.
Then, since $\sigma_{\alpha}[j-1]$ contains at most one step by each process,
observe that
$\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S_{H}]\circ\sigma_{\alpha}[j-1])=\textit{val}_{R[j]}(\sigma_{\textit{highA}}[S]\circ\sigma_{\alpha}[j-1])$.
By definition, since $\sigma_{\textit{highB}}[S]\neq\bot$,
$\sigma_{\textit{highB}}[S]=\sigma_{\textit{highA}}[S]$. Thus
$v_{j}=\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S]\circ\sigma_{\alpha}[j-1])$.
Then, since 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])$,
$v_{j}=\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}[j-1])$
too.

By definition, either $\alpha_{1}[j]$ is poised to perform a
$\textsc{CAS}(v_{j},v^{\prime})$ operation where $v^{\prime}\neq v_{j}$ at the
end of $E(\sigma_{\textit{highA}}[S_{H}])$, or no process in $G[j]$ is poised
to perform a $\textsc{CAS}(v_{j},v^{\prime})$ operation where $v^{\prime}\neq
v_{j}$ at the end of $E(\sigma_{\textit{highA}}[S_{H}])$. 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
(I3), since $\sigma_{\textit{highB}}[S]=\sigma_{\textit{highA}}[S]\neq\bot$
and $\\{\alpha_{1}[j],\alpha_{2}[j],\beta_{1}[j]\\}\subseteq S$, for each
process $p\in\\{\alpha_{1}[j],\alpha_{2}[j],\beta_{1}[j]\\}$,
$\textit{state}_{p}(\sigma_{\textit{highA}}[S_{H}])=\textit{state}_{p}(\sigma_{\textit{highA}}[S])=\textit{state}_{p}(\sigma_{\textit{highB}}[S])$.

Now recall that 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])$.
So either $\alpha_{1}[j]$ is poised to perform a
$\textsc{CAS}(v_{j},v^{\prime})$ operation where $v^{\prime}\neq v_{j}$ at the
end of both $E(C^{\prime}_{S},\sigma^{\prime}_{S}[j-1])$ and
$E(C^{\prime}_{S},\sigma_{\alpha}[j-1])$, or no process in
$\\{\alpha_{1}[j],\alpha_{2}[j],\beta_{1}[j]\\}$ is poised to perform a
$\textsc{CAS}(v_{j},v^{\prime})$ operation where $v^{\prime}\neq v_{j}$ at the
end of both $E(C^{\prime}_{S},\sigma^{\prime}_{S}[j-1])$ and
$E(C^{\prime}_{S},\sigma_{\alpha}[j-1])$.

In the latter case,
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma_{\alpha}[j])=\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{\alpha}[j-1])=v_{j}$
and
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S}[j-1])=v_{j}$.
Thus
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=\textit{val}_{R[j]}(C^{\prime}_{S},\sigma_{\alpha}[j])$,
as wanted.

In the former case, since $\beta_{1}[j]\in S$, $\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])$. Recall that 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])$.
So $\beta_{1}[j]$ is also poised to perform a
$\textsc{CAS}(v_{\beta},v^{\prime}_{\beta})$ operation on $R[j]$ at the end of
both $E(C^{\prime}_{S},\sigma^{\prime}_{S}[j-1])$ and
$E(C^{\prime}_{S},\sigma_{\alpha}[j-1])$.

By definition, since $\textit{opt}_{H}$ is CAS, if $v_{j}\neq v_{\beta}$, then
$\beta[j]=\beta_{1}[j]\circ\alpha_{1}[j]\circ\alpha_{2}[j]$ otherwise
$\beta[j]=\alpha_{1}[j]\circ\beta_{1}[j]\circ\alpha_{2}[j]$. So if $v_{j}\neq
v_{\beta}$, then in $E(C^{\prime}_{S},\sigma^{\prime}_{S}[j])$, $\beta_{1}[j]$
performs an unsuccessful $\textsc{CAS}(v_{\beta},v^{\prime}_{\beta})$ on
$R[j]$ when $R[j]$ contains $v_{j}\neq v_{\beta}$. Otherwise
$v_{j}=v_{\beta}$, so in $E(C^{\prime}_{S},\sigma^{\prime}_{S}[j])$,
$\beta_{1}[j]$ performs an unsuccessful
$\textsc{CAS}(v_{j},v^{\prime}_{\beta})$ on $R[j]$ immediately after
$\alpha_{1}[j]$ successfully changes the value of $R[j]$ from $v_{j}$ to
$v^{\prime}\neq v_{j}$. Thus regardless of whether $v_{j}=v_{\beta}$, the
$\textsc{CAS}(v_{\beta},v^{\prime}_{\beta})$ operation by $\beta_{1}[j]$ does
not change the value of $R[j]$ during
$E(C^{\prime}_{S},\sigma^{\prime}_{S}[j])$. Consequently,
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S}[j])=\textit{val}_{R[j]}(C^{\prime}_{S},\sigma_{\alpha}[j])$,
as wanted. ∎

###### Lemma .

For every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$:

  1. (H1)

For every process $p\in\mathcal{P}$, if $p$ accesses a register $R$ during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$, then the owner of $R$ is not in
$S_{B}\setminus F(\sigma_{\textit{highB}}[S_{B}])$.

  2. (H2)

For every integer $j\in\\{0,1,\ldots,h-1\\}$,
$\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S])=\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S_{B}])$.

  3. (H3)

In the CC model, for every process $p\in S\setminus
F(\sigma_{\textit{highB}}[S_{B}])$, the set of registers that $p$ has valid
cache copies of at the end of
$E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})$ is exactly the same as
at the end of $E(\sigma_{\textit{highB}}[S_{B}]\circ\sigma^{\prime}_{S_{B}})$.

  4. (H4)

For every integer $j\in\\{0,1,\ldots,h-1\\}$,
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S})=\textit{val}_{R[j]}(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}})$.

  5. (H5)

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

  6. (H6)

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

  7. (H7)

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

  8. (H8)

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

###### 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, the set of registers accessed during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$ is exactly the set of registers in
$R[0..h-1]$. By Section 3.2, for every integer $j\in\\{0,1,\ldots,h-1\\}$:

  * •

$\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S])=\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S_{B}])$
((H2)).

  * •

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

Thus for every process $p\in\mathcal{P}$, if $p$ accesses a register $R$
during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$, then the owner of $R$ is not
in $S_{B}\setminus F(\sigma_{\textit{highB}}[S_{B}])$ ((H1)).

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}$. So by
Invariant (I9), for every process $p\in S\setminus
F(\sigma_{\textit{highB}}[S_{B}])$, the set of registers that $p$ has valid
cache copies of at the end of $E(\sigma_{\textit{highB}}[S])$ is exactly the
same as at the end of $E(\sigma_{\textit{highB}}[S_{B}])$.

Suppose $\textit{opt}_{H}$ is read. Then by Section 3.2 and Invariant (I3),
for every process $p\in S\setminus F(\sigma_{\textit{highB}}[S_{B}])$
$\textit{state}_{p}(\sigma_{\textit{highB}}[S])=\textit{state}_{p}(\sigma_{\textit{highB}}[S_{B}])$.
So at the end of both $E(\sigma_{\textit{highB}}[S])$ and
$E(\sigma_{\textit{highB}}[S_{B}])$, $p\in S\setminus
F(\sigma_{\textit{highB}}[S_{B}])$ is poised to perform a read operation on
the same register $R$. Then, since $\sigma^{\prime}_{S}$ contains exactly one
non-crash step of each process in $S\cap S_{\beta}=S\setminus
F(\sigma_{\textit{highB}}[S_{B}])$, the set of registers that $p$ has valid
cache copies of at the end of
$E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})$ is the union of
$\\{R\\}$ and the set of registers that $p$ has valid cache copies of at the
end of $E(\sigma_{\textit{highB}}[S])$. Furthermore, since
$\sigma^{\prime}_{S_{B}}$ contains exactly one non-crash step of each process
in $S_{B}\cap S_{\beta}=S_{B}\setminus F(\sigma_{\textit{highB}}[S_{B}])$, the
set of registers that $p$ has valid cache copies of at the end of
$E(\sigma_{\textit{highB}}[S_{B}]\circ\sigma^{\prime}_{S_{B}})$ is the union
of $\\{R\\}$ and the set of registers that $p$ has valid cache copies of at
the end of $E(\sigma_{\textit{highB}}[S_{B}])$. Thus the set of registers that
$p$ has valid cache copies of at the end of
$E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})$ is exactly the same as
at the end of $E(\sigma_{\textit{highB}}[S_{B}]\circ\sigma^{\prime}_{S_{B}})$.

Now suppose instead that $\textit{opt}_{H}$ is not read. Then by Section 3.2,
the set of registers accessed during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$
is exactly the set of registers in $R[0..h-1]$ and exactly the set of
registers accessed during $E(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}})$.
Thus, since every non-read operation invalidates all cache copies on a
register, all cache copies of registers in $R[0..h-1]$ are invalidated during
both $E(C^{\prime}_{S},\sigma^{\prime}_{S})$ and
$E(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}})$. So for every process $p\in
S\setminus F(\sigma_{\textit{highB}}[S_{B}])$, the set of registers that $p$
has valid cache copies of at the end of
$E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})$ is exactly the same as
at the end of $E(\sigma_{\textit{highB}}[S_{B}]\circ\sigma^{\prime}_{S_{B}})$.

Consequently, regardless of $\textit{opt}_{H}$, in the CC model, for every
process $p\in S\setminus F(\sigma_{\textit{highB}}[S_{B}])$, the set of
registers that $p$ has valid cache copies of at the end of
$E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})$ is exactly the same as
at the end of $E(\sigma_{\textit{highB}}[S_{B}]\circ\sigma^{\prime}_{S_{B}})$
((H3)).

Now consider $E(C^{\prime}_{S},\sigma_{\alpha})$ and
$E(C^{\prime}_{S_{B}},\sigma_{\alpha})$. By construction, $\sigma_{\alpha}$
contains exactly one non-crash step of every process in $S_{\alpha}$ and no
other steps. 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}$. So by
Invariants (I2) and (I3), since $F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}\subseteq S\subseteq S_{B}$, for every process $p\in S\supset
S_{\alpha}$,
$\textit{state}_{p}(\sigma_{\textit{highB}}[S])=\textit{state}_{p}(\sigma_{\textit{highB}}[S_{B}])$.
By Section 3.2, the set of registers accessed during
$E(C^{\prime}_{S_{B}},\sigma_{\alpha})$ is exactly the set of registers in
$R[0..h-1]$ and exactly the set of registers accessed during
$E(C^{\prime}_{S},\sigma_{\alpha})$. Since we have already proven (H2), for
every integer $j\in\\{0,1,\ldots,h-1\\}$,
$\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S])=\textit{val}_{R[j]}(\sigma_{\textit{highB}}[S_{B}])$.
Therefore during both $E(C^{\prime}_{S},\sigma_{\alpha})$ and
$E(C^{\prime}_{S_{B}},\sigma_{\alpha})$, the same set $S_{\alpha}$ of
processes begin in the same states, and perform the same operations in the
same order on the same registers which also begin with the same values. So for
every integer $j\in\\{0,1,\ldots,h-1\\}$,
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma_{\alpha})=\textit{val}_{R[j]}(C^{\prime}_{S_{B}},\sigma_{\alpha})$.
Thus by Section 3.2, for every integer $j\in\\{0,1,\ldots,h-1\\}$:

$\displaystyle\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S})$
$\displaystyle=\textit{val}_{R[j]}(C^{\prime}_{S},\sigma_{\alpha})$
$\displaystyle=\textit{val}_{R[j]}(C^{\prime}_{S_{B}},\sigma_{\alpha})$
$\displaystyle=\textit{val}_{R[j]}(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}})$

So for every integer $j\in\\{0,1,\ldots,h-1\\}$,
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S})=\textit{val}_{R[j]}(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}})$
((H4)).

Now let $j^{\prime}$ be an integer in $\\{0,1,\ldots,h-1\\}$. Then by Section
3.2:

$\displaystyle\textit{val}_{R[j^{\prime}]}(C^{\prime}_{S},\sigma^{\prime}_{S}[j^{\prime}-1])$
$\displaystyle=\textit{val}_{R[j^{\prime}]}(C^{\prime}_{S},\sigma_{\alpha}[j^{\prime}-1])$
$\displaystyle=\textit{val}_{R[j^{\prime}]}(C^{\prime}_{S_{B}},\sigma_{\alpha}[j^{\prime}-1])$
$\displaystyle=\textit{val}_{R[j^{\prime}]}(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}}[j^{\prime}-1])$

Let $C^{j^{\prime}-1}_{S}$ and $C^{j^{\prime}-1}_{S_{B}}$ be the
configurations at the end of
$E(C^{\prime}_{S},\sigma^{\prime}_{S}[j^{\prime}-1])$ and
$E(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}}[j^{\prime}-1])$ respectively. So
$R[j^{\prime}]$ has the same value in both $C^{j^{\prime}-1}_{S}$ and
$C^{j^{\prime}-1}_{S_{B}}$. In addition, recall that by the definition of
$\sigma^{\prime}_{S}[j^{\prime}-1]$ and
$\sigma^{\prime}_{S_{B}}[j^{\prime}-1]$, processes in $G[j^{\prime}]\cap S$ do
not take any steps during
$E(C^{\prime}_{S},\sigma^{\prime}_{S}[j^{\prime}-1])$ and
$E(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}}[j^{\prime}-1])$. Thus, for every
process $p\in G[j^{\prime}]\cap S\subseteq S$, since
$\textit{state}_{p}(\sigma_{\textit{highB}}[S])=\textit{state}_{p}(\sigma_{\textit{highB}}[S_{B}])$,
the state of $p$ is still the same in both $C^{j^{\prime}-1}_{S}$ and
$C^{j^{\prime}-1}_{S_{B}}$, i.e., $p$ is poised to perform the same operation
on $R[j^{\prime}]$ in both $C^{j^{\prime}-1}_{S}$ and
$C^{j^{\prime}-1}_{S_{B}}$.

Now suppose that $\beta_{1}[j^{\prime}]$ is in $S\subseteq S_{B}$. Then
$\sigma^{\prime}_{S}[j^{\prime}]=\sigma^{\prime}_{S}[j^{\prime}-1]\circ\beta[j^{\prime}]$
and
$\sigma^{\prime}_{S_{B}}[j^{\prime}]=\sigma^{\prime}_{S_{B}}[j^{\prime}-1]\circ\beta[j^{\prime}]$.
Furthermore, in addition to $\alpha_{1}[j^{\prime}]$ and
$\alpha_{2}[j^{\prime}]$, $\beta_{1}[j^{\prime}]$ is also in
$G[j^{\prime}]\cap S$. So $\beta[j^{\prime}]$ contains only processes in
$G[j^{\prime}]\cap S$. Thus during both
$E(C^{j^{\prime}-1}_{S},\beta[j^{\prime}])$ and
$E(C^{j^{\prime}-1}_{S_{B}},\beta[j^{\prime}])$, the same set of processes
(namely those in $\beta[j^{\prime}]$) begin in the same set of states and
perform the same set of operations in the same order on $R[j^{\prime}]$ (which
begins with the same value), and thus must reach the same resulting states.
Finally, since each process in $G[j^{\prime}]\cap S$ takes no more steps in
the remainder of $\sigma^{\prime}_{S}$ and $\sigma^{\prime}_{S_{B}}$,
$\textit{state}_{\beta_{1}[j^{\prime}]}(C^{\prime}_{S},\sigma^{\prime}_{S})=\textit{state}_{\beta_{1}[j^{\prime}]}(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}})$.

Thus we have shown that for every integer $j\in\\{0,1,\ldots,h-1\\}$,
$\textit{state}_{\beta_{1}[j]}(C^{\prime}_{S},\sigma^{\prime}_{S})=\textit{state}_{\beta_{1}[j]}(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}})$.
Now note that for each process $p\in S\setminus S_{\alpha}$, since $S\subseteq
S_{B}$, there exists an integer $j\in\\{0,1,\ldots,h-1\\}$ such that
$p=\beta_{1}[j]$. So for each process $p\in S\setminus S_{\alpha}$,
$\textit{state}_{p}(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}})=\textit{state}_{p}(C^{\prime}_{S},\sigma^{\prime}_{S})$
((H5)).

Since $\sigma_{\textit{highB}}[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{highB}}[S]=\sigma_{\textit{setupB}}[S]=\sigma_{\textit{setupA}}[S]$,
and
$F(\sigma_{\textit{highB}}[S_{B}])=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{highB}}[S_{B}])$, $p$
incurs an RMR at the end of $E(\sigma_{\textit{highB}}[S]\circ p)$. By
definition, $S_{B}=S_{\beta}\cup F(\sigma_{\textit{highB}}[S_{B}])$, so since
$S\subseteq S_{B}$, $S\setminus
F(\sigma_{\textit{highB}}[S_{B}])=S_{\beta}\cap S$. By construction,
$\sigma^{\prime}_{S}$ contains exactly one non-crash step of each process in
$S_{\beta}\cap S$ and no other steps. So in the DSM model, every process in
$S_{\beta}\cap S$ is poised to access a register it does not own in
$C^{\prime}_{S}$, and so every process in $S_{\beta}\cap S$ incurs exactly one
RMR during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$. In the CC model, every
process in $S_{\beta}\cap S$ is poised to perform a non-read operation or read
a register that it does not have a valid cache copy of in $C^{\prime}_{S}$,
and so every process in $S_{\beta}\cap S$ incurs exactly one RMR during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$. Thus in both the DSM and CC models,
each process in $S_{\beta}\cap S$ incurs exactly one RMR during
$E(C^{\prime}_{S},\sigma^{\prime}_{S})$ ((H6)).

By Section 3.2, $\sigma_{\textit{highB}}[0..2^{n}-1]$ is $(i-1)$-compliant, so
by Invariant (I7), each process that is not in $F(\sigma_{\textit{highB}}[S])$
does not enter the critical section during $E(\sigma_{\textit{highB}}[S])$.
Recall that $\sigma^{\prime}_{S}$ consists of exactly one non-crash step of
each process in $S_{\beta}\cap S=S\setminus F(\sigma_{\textit{highB}}[S_{B}])$
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{highB}}[S_{B}])$, $p$ has not left the critical section
during $E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})$ ((H7)).
Therefore, since no process in $S\setminus F(\sigma_{\textit{highB}}[S_{B}])$
has left the critical section during
$E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})$, no process in
$S\setminus F(\sigma_{\textit{highB}}[S_{B}])$ has completed its super-passage
during $E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})$. Thus
$F(\sigma_{\textit{highB}}[S])=F(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})$
((H8)). ∎

Now recall that $S_{F}=S_{\alpha}\cup F(\sigma_{\textit{highA}}[S_{H}])$ and
that by Section 3.2 and Invariant (I4),
$F(\sigma_{\textit{highA}}[S_{H}])=F(\sigma_{\textit{highA}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])$.
Thus $S_{F}=S_{\alpha}\cup F(\sigma_{\textit{highB}}[S_{B}])$, and so
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S_{F}\subseteq
S_{B}$. Furthermore, recall that by definition, since
$S_{F}=\sigma_{\alpha}\cup F(\sigma_{\textit{highB}}[S_{B}])$,
$\sigma_{\alpha}=\sigma^{\prime}_{S_{F}}$. Thus
$E(C^{\prime}_{S_{F}},\sigma^{\prime}_{S_{F}})=E(C^{\prime}_{S_{F}},\sigma_{\alpha})$.

###### Lemma .

For every register $R\in\mathcal{R}_{F}$, 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})=\textit{val}_{R}(C^{\prime}_{S_{F}},\sigma_{\alpha})$.

###### Proof.

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 and Invariant (I2), since
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S_{F}\subseteq
S_{B}$ and $F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq
S\subseteq S_{B}$, both $\sigma_{\textit{highB}}[S_{F}]\neq\bot$ and
$\sigma_{\textit{highB}}[S]\neq\bot$. So by Section 3.2, for every register
$R\in\mathcal{R}_{F}$,
$\textit{val}_{R}(\sigma_{\textit{highB}}[S_{F}])=\textit{val}_{R}(\sigma_{\textit{highB}}[S_{B}])=\textit{val}_{R}(\sigma_{\textit{highB}}[S])$.

Now consider $E(C^{\prime}_{S},\sigma^{\prime}_{S})$ and
$E(C^{\prime}_{S_{F}},\sigma^{\prime}_{S_{F}})$. By Section 3.2, only
registers in $R[0..h-1]$ are accessed during both executions. So for every
register $R\in\mathcal{R}_{F}$, if $R$ is not one of $R[0..h-1]$, then
$\textit{val}_{R}(C^{\prime}_{S},\sigma^{\prime}_{S})=\textit{val}_{R}(C^{\prime}_{S_{F}},\sigma^{\prime}_{S_{F}})$.

Next, by Section 3.2 ((H4)), for every integer $j\in\\{0,1,\ldots,h-1\\}$,
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S})=\textit{val}_{R[j]}(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}})=\textit{val}_{R[j]}(C^{\prime}_{S_{F}},\sigma^{\prime}_{S_{F}})$.
Therefore, for every register $R\in\mathcal{R}_{F}$, regardless of whether $R$
is one of $R[0..h-1]$,
$\textit{val}_{R}(C^{\prime}_{S},\sigma^{\prime}_{S})=\textit{val}_{R}(C^{\prime}_{S_{F}},\sigma^{\prime}_{S_{F}})=\textit{val}_{R}(C^{\prime}_{S_{F}},\sigma_{\alpha})$.
∎

Next, recall that there exists 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}])$.

  * •

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}$.

By Section 3.2 and Invariant (I4),
$F(\sigma_{\textit{highA}}[S_{F}])=F(\sigma_{\textit{highA}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])$.
By construction,
$\sigma_{\textit{highB}}[S_{F}]=\sigma_{\textit{highA}}[S_{F}]$. Thus:

  * •

$\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{highB}}[S_{B}])$.

  * •

During $E(\sigma_{\textit{highB}}[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{highB}}[S_{F}]\circ\sigma_{\alpha}\circ\sigma_{F})=S_{F}$.

Further recall that by definition, $C_{F}$ is the configuration at the end of
$E(\sigma_{\textit{highA}}[S_{F}]\circ\sigma_{\alpha})$, and $\mathcal{R}_{F}$
is 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}$).

Now 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\prime}_{S}$ be the configuration at the end of
$E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})$. Then
$E(\sigma_{\textit{highA}}[S_{F}]\circ\sigma_{\alpha})=E(\sigma_{\textit{highB}}[S_{F}]\circ\sigma^{\prime}_{S_{F}})$,
so $C_{F}=C^{\prime\prime}_{S_{F}}$.

###### Lemma .

For every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$,
during both $E(C^{\prime\prime}_{S},\sigma_{F})$ and
$E(C^{\prime\prime}_{S_{F}},\sigma_{F})=E(C_{F},\sigma_{F})$, the same set of
processes (namely $S_{\alpha}$) crash, then perform the same operations in the
same order on the same set of registers (namely $\mathcal{R}_{F}$) and so must
reach the same resulting states.

###### Proof.

By Section 3.2, for every register $R\in\mathcal{R}_{F}$ and every set
$S\subseteq\mathcal{P}$ such that $F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}\subseteq S\subseteq S_{B}$, $R$ has the same value in
$C_{F}=C^{\prime\prime}_{S_{F}}$ as in $C^{\prime\prime}_{S}$. Furthermore, by
the definition of $\sigma_{F}$, $\sigma_{F}$ begins with a crash step of every
process in $P(\sigma_{F})=S_{\alpha}$. The lemma immediately follows. ∎

We now construct a new array $\sigma_{\textit{highC}}[0..2^{n}-1]$ such that
for every set $S\subseteq\mathcal{P}$, if
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$,
then
$\sigma_{\textit{highC}}[S]=\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F}$;
otherwise $\sigma_{\textit{highC}}[S]=\bot$.

###### Lemma .

This new array $\sigma_{\textit{highC}}[0..2^{n}-1]$ is $i$-compliant with
$S_{\textit{max}}(\sigma_{\textit{highC}}[0..2^{n}-1])=S_{B}$. Furthermore,
$F(\sigma_{\textit{highC}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}$.

###### Proof.

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

Now for every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$,
consider
$F(\sigma_{\textit{highC}}[S])=F(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F})$.
By Section 3.2 ((H8)),
$F(\sigma_{\textit{highB}}[S])=F(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})=F(C^{\prime\prime}_{S},\sigma^{\prime}_{S})$.
By definition, every process in $S_{\alpha}$ completes its super-passage
during $E(C_{F},\sigma_{F})$. So by Section 3.2, every process in $S_{\alpha}$
also completes its super-passage during $E(C^{\prime\prime}_{S},\sigma_{F})$.
Thus $F(\sigma_{\textit{highC}}[S])=F(\sigma_{\textit{highB}}[S])\cup
S_{\alpha}$. Therefore,
$F(\sigma_{\textit{highC}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}$.

Furthermore, by Section 3.2 and Invariants (I2) and (I4), for every set
$S\subseteq\mathcal{P}$ such that $F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}\subseteq S\subseteq S_{B}$,
$F(\sigma_{\textit{highB}}[S])=F(\sigma_{\textit{highB}}[S_{B}])$, and so
$F(\sigma_{\textit{highC}}[S])=F(\sigma_{\textit{highB}}[S])\cup
S_{\alpha}=F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}=F(\sigma_{\textit{highC}}[S_{B}])$.

By construction, for every set $S\subseteq\mathcal{P}$, if
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$,
then
$\sigma_{\textit{highC}}[S]=\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F}$;
otherwise $\sigma_{\textit{highC}}[S]=\bot$. 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}$. So by Invariant
(I2), for every set $S\subseteq\mathcal{P}$,
$\sigma_{\textit{highB}}[S]\neq\bot$ if and only if
$F(\sigma_{\textit{highB}}[S_{B}])\subseteq S\subseteq S_{B}$. Thus for every
set $S\subseteq\mathcal{P}$, if $F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}\subseteq S\subseteq S_{B}$, then
$\sigma_{\textit{highB}}[S]\neq\bot$ and
$\sigma_{\textit{highC}}[S]=\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F}\neq\bot$.
Then, since we have already proven that
$F(\sigma_{\textit{highC}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}$, for every set $S\subseteq\mathcal{P}$,
$\sigma_{\textit{highC}}[S]\neq\bot$ if and only if
$F(\sigma_{\textit{highC}}[S_{B}])\subseteq S\subseteq S_{B}$ (Invariant
(I2)).

Furthermore, we have already shown that for every set $S\subseteq\mathcal{P}$
such that $F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq
S\subseteq S_{B}$,
$F(\sigma_{\textit{highC}}[S])=F(\sigma_{\textit{highC}}[S_{B}])$. Thus, since
we just proved that Invariant (I2) holds for
$\sigma_{\textit{highC}}[0..2^{n}-1]$ with
$S_{\textit{max}}(\sigma_{\textit{highC}}[0..2^{n}-1])=S_{B}$ and
$F(\sigma_{\textit{highC}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}$, it follows that for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highC}}[S]\neq\bot$,
$F(\sigma_{\textit{highC}}[S])=F(\sigma_{\textit{highC}}[S_{B}])$ (Invariant
(I4)).

By Section 3.2 ((H5)), for every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}=F(\sigma_{\textit{highC}}[S_{B}])\subseteq S\subseteq S_{B}$, for
every process $p\in S\setminus S_{\alpha}$,
$\textit{state}_{p}(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}})=\textit{state}_{p}(C^{\prime}_{S},\sigma^{\prime}_{S})$.
Since $\sigma_{F}$ only contains steps of processes in $S_{\alpha}$, for every
set $S\subseteq\mathcal{P}$ such that $F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}=F(\sigma_{\textit{highC}}[S_{B}])\subseteq S\subseteq S_{B}$, for
every process $p\in S\setminus S_{\alpha}$,
$\textit{state}_{p}(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}}\circ\sigma_{F})=\textit{state}_{p}(C^{\prime}_{S},\sigma^{\prime}_{S}\circ\sigma_{F})$.
Thus for every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highC}}[S_{B}])\subseteq S\subseteq S_{B}$, for every
process $p\in S\setminus S_{\alpha}$,
$\textit{state}_{p}(\sigma_{\textit{highC}}[S_{B}])=\textit{state}_{p}(\sigma_{\textit{highC}}[S])$.
Furthermore, we have already proven that
$F(\sigma_{\textit{highC}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}$, and that Invariants (I2) and (I4) hold for
$\sigma_{\textit{highC}}[0..2^{n}-1]$ with
$S_{\textit{max}}(\sigma_{\textit{highC}}[0..2^{n}-1])=S_{B}$, for every set
$S\subseteq\mathcal{P}$ such that $F(\sigma_{\textit{highC}}[S_{B}])\subseteq
S\subseteq S_{B}$, $S_{\alpha}$ is in both $F(\sigma_{\textit{highC}}[S])$ and
$F(\sigma_{\textit{highC}}[S_{B}])$, so for every process $p\in S_{\alpha}$,
$\textit{state}_{p}(\sigma_{\textit{highC}}[S_{B}])=\textit{state}_{p}(\sigma_{\textit{highC}}[S])$.
Consequently, for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highC}}[S]\neq\bot$, for every process $p\in S$, regardless
of whether $p$ is in $S_{\alpha}$,
$\textit{state}_{p}(\sigma_{\textit{highC}}[S_{B}])=\textit{state}_{p}(\sigma_{\textit{highC}}[S])$
(Invariant (I3)).

Next, by Section 3.2, for every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highC}}[S_{B}])\subseteq S\subseteq S_{B}$, and every
register $R\in\mathcal{R}_{F}$,
$\textit{val}_{R}(\sigma_{\textit{highC}}[S])=\textit{val}_{R}(\sigma_{\textit{highC}}[S_{F}])$.
Furthermore, only registers in $\mathcal{R}_{F}$ are accessed during
$E(C^{\prime\prime}_{S},\sigma_{F})$. So for every integer
$j\in\\{0,1,\ldots,h-1\\}$, if $R[j]\not\in\mathcal{R}_{F}$, then by Section
3.2 ((H4)),
$\textit{val}_{R[j]}(C^{\prime}_{S},\sigma^{\prime}_{S}\circ\sigma_{F})=\textit{val}_{R[j]}(C^{\prime}_{S_{B}},\sigma^{\prime}_{S_{B}}\circ\sigma_{F})$,
i.e.,
$\textit{val}_{R[j]}(\sigma_{\textit{highC}}[S])=\textit{val}_{R[j]}(\sigma_{\textit{highC}}[S_{B}])$.
Thus we have shown that for every register $R\in\mathcal{R}$ such that either
$R\in\mathcal{R}_{F}$ or $R$ is one of $R[0..h-1]$, and every set
$S\subseteq\mathcal{P}$ such that $F(\sigma_{\textit{highC}}[S_{B}])\subseteq
S\subseteq S_{B}$,
$\textit{val}_{R}(\sigma_{\textit{highC}}[S])=\textit{val}_{R}(\sigma_{\textit{highC}}[S_{B}])$.
Then since we have already proven that Invariant (I2) holds for
$\sigma_{\textit{highC}}[0..2^{n}-1]$ with
$S_{\textit{max}}(\sigma_{\textit{highC}}[0..2^{n}-1])=S_{B}$, for every
register $R\in\mathcal{R}$ such that either $R\in\mathcal{R}_{F}$ or $R$ is
one of $R[0..h-1]$, and every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highC}}[S]\neq\bot$,
$\textit{val}_{R}(\sigma_{\textit{highC}}[S])=\textit{val}_{R}(\sigma_{\textit{highC}}[S_{B}])$.
So for every register $R\in\mathcal{R}$ such that either $R\in\mathcal{R}_{F}$
or $R$ is one of $R[0..h-1]$, regardless of
$\textit{last}_{R}(\sigma_{\textit{highC}}[S_{B}])$, if
$y_{R}=\textit{val}_{R}(\sigma_{\textit{highC}}[S_{B}])$, then we have that
for every set $S\subseteq\mathcal{P}$, if
$\sigma_{\textit{highC}}[S]\neq\bot$, then:

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

Now consider the registers that are not in $\mathcal{R}_{F}$ and not one of
$R[0..h-1]$, i.e., the registers that are not accessed during
$E(C^{\prime}_{S},\sigma^{\prime}_{S}\circ\sigma_{F})$ for every set
$S\subseteq\mathcal{P}$ such that $F(\sigma_{\textit{highC}}[S_{B}])\subseteq
S\subseteq S_{B}$. 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}$. So by Invariant
(I5), for each such register $R$, there exists a value $y_{R}$ such that for
every set $S\subseteq\mathcal{P}$, if $\sigma_{\textit{highB}}[S]\neq\bot$,
then:

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

Then, since each such register $R$ is not accessed during
$E(C^{\prime}_{S},\sigma^{\prime}_{S}\circ\sigma_{F})$ for every set
$S\subseteq\mathcal{P}$ such that $F(\sigma_{\textit{highC}}[S_{B}])\subseteq
S\subseteq S_{B}$, and we have already proven that Invariant (I2) holds for
$\sigma_{\textit{highC}}[0..2^{n}-1]$ with
$S_{\textit{max}}(\sigma_{\textit{highC}}[0..2^{n}-1])=S_{B}$:

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

Consequently, for every register $R\in\mathcal{R}$, regardless of whether
$R\in\mathcal{R}_{F}$ and whether $R$ is one of $R[0..h-1]$, there is a value
$y_{R}$ such that for every set $S\subseteq\mathcal{P}$, if
$\sigma_{\textit{highC}}[S]\neq\bot$, then:

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

So Invariant (I5) holds for $\sigma_{\textit{highC}}[0..2^{n}-1]$.

By Section 3.2, $\sigma_{\textit{highB}}[0..2^{n}-1]$ is $(i-1)$-compliant. So
by Invariant (I6), for every set $S\subseteq\mathcal{P}$ with
$\sigma_{\textit{highB}}[S]\neq\bot$, during $E(\sigma_{\textit{highB}}[S])$,
each process crashes at most once, and each process that is not in
$F(\sigma_{\textit{highB}}[S])$ never crashes.

By construction, for every set $S\subseteq\mathcal{P}$ with
$\sigma_{\textit{highC}}[S]\neq\bot$, $\sigma^{\prime}_{S}$ does not contain
any crash steps. Furthermore, $\sigma_{F}$ contains exactly one crash step for
each process in $S_{\alpha}$ and no other crash steps.

We have already proven that
$F(\sigma_{\textit{highC}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}$ and that Invariant (I4) holds for
$\sigma_{\textit{highC}}[0..2^{n}-1]$. By Section 3.2, Invariant (I4) also
holds for $\sigma_{\textit{highB}}[0..2^{n}-1]$. So for every set
$S\subseteq\mathcal{P}$ with $\sigma_{\textit{highC}}[S]\neq\bot$,
$F(\sigma_{\textit{highC}}[S])=F(\sigma_{\textit{highB}}[S])\cup S_{\alpha}$.

So for every process $p\not\in F(\sigma_{\textit{highC}}[S_{B}])$, $p$ never
crashes during $E(\sigma_{\textit{highC}}[S])$. Furthermore, since
$S_{\alpha}\not\in F(\sigma_{\textit{highB}}[S])$, processes in $S_{\alpha}$
never crash during $E(\sigma_{\textit{highB}}[S])$, and thus crash at most
once during
$E(\sigma_{\textit{highC}}[S])=E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F})$.
Finally, processes in $F(\sigma_{\textit{highB}}[S])$ do not have any (crash)
steps in either $\sigma^{\prime}_{S}$ or $\sigma_{F}$, so they also still
crash at most once during
$E(\sigma_{\textit{highC}}[S])=E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F})$.
Consequently, for every set $S\subseteq\mathcal{P}$ with
$\sigma_{\textit{highC}}[S]\neq\bot$, during $E(\sigma_{\textit{highC}}[S])$,
each process crashes at most once, and each process that is not in
$F(\sigma_{\textit{highC}}[S])$ never crashes (Invariant (I6)).

Now suppose, for contradiction, that for some set $S\subseteq\mathcal{P}$ with
$\sigma_{\textit{highC}}[S]\neq\bot$, some process $p$ that is not in
$F(\sigma_{\textit{highC}}[S])$ enters the critical section during
$E(\sigma_{\textit{highC}}[S])=E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F})$.
Since we have already proven that Invariant (I1) holds for
$\sigma_{\textit{highC}}[0..2^{n}-1]$, $p\in S$. Furthermore, we have also
already shown that
$F(\sigma_{\textit{highC}}[S])=F(\sigma_{\textit{highB}}[S])\cup S_{\alpha}$,
so $p\not\in F(\sigma_{\textit{highB}}[S])\cup S_{\alpha}$.

By Section 3.2, $\sigma_{\textit{highB}}[0..2^{n}-1]$ is $(i-1)$-compliant. So
by Invariant (I7), since $p\not\in F(\sigma_{\textit{highB}}[S])$, $p$ does
not enter the critical section during $E(\sigma_{\textit{highB}}[S])$.
Furthermore, by the definition of $\sigma_{F}$, since $p\not\in S_{\alpha}$,
$\sigma_{F}$ contains no steps of $p$. Thus $p$ must be one of the processes
that take a step during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$, and must
enter the critical section with this one step. By Assumption (A1), a process
that enters the critical section cannot leave the critical section before
incurring an RMR within the critical section. Thus, since $\sigma_{F}$
contains no steps of $p\not\in S_{\alpha}$, $p$ remains in the critical
section throughout $E(C^{\prime\prime}_{S},\sigma_{F})$.

Now consider the processes in $S_{\alpha}$. Since
$\sigma_{\textit{highB}}[0..2^{n}-1]$ is $(i-1)$-compliant, and
$S_{\alpha}\cap F(\sigma_{\textit{highB}}[S])=\varnothing$, the processes in
$S_{\alpha}$ do not enter the critical section during
$E(\sigma_{\textit{highB}}[S])$. Since $p$ is in the critical section in
$C^{\prime\prime}_{S}$, and $\sigma^{\prime}_{S}$ contains at most one step of
each process, to avoid violating mutual exclusion, each process in
$S_{\alpha}$ cannot enter the critical section with its at most one step taken
during $E(C^{\prime}_{S},\sigma^{\prime}_{S})$ by Assumption (A1). Thus during
$E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})$, the processes in
$S_{\alpha}$ do not enter the critical section. Furthermore, since $p$ remains
in the critical section throughout $E(C^{\prime\prime}_{S},\sigma_{F})$, to
avoid violating mutual exclusion, the processes in $S_{\alpha}$ also do not
enter the critical section during
$E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F})$.

However, we have already shown that
$F(\sigma_{\textit{highC}}[S])=F(\sigma_{\textit{highB}}[S])\cup S_{\alpha}$.
Thus we have that during
$E(\sigma_{\textit{highC}}[S])=E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F})$,
every process in $S_{\alpha}$ completes its super-passage without entering the
critical section — a contradiction. Consequently, for every set
$S\subseteq\mathcal{P}$ with $\sigma_{\textit{highC}}[S]\neq\bot$, each
process that is not in $F(\sigma_{\textit{highC}}[S])$ does not enter the
critical section during $E(\sigma_{\textit{highC}}[S])$ (Invariant (I7)).

Next, by Section 3.2, for every register $R\in\mathcal{R}$ such that either
$R$ is one of $R[0..h-1]$ or $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, the
definition of $\mathcal{R}_{F}$, and Section 3.2, for every set
$S\subseteq\mathcal{P}$ such that $\sigma_{\textit{highC}}[S]\neq\bot$, each
register $R\in\mathcal{R}$ is only accessed during
$E(\sigma_{\textit{highC}}[S])=E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F})$
if either $R$ is one of $R[0..h-1]$ or $R\in\mathcal{R}_{F}$. Therefore, for
every register $R\in\mathcal{R}$, if $R$ is accessed during
$E(C^{\prime}_{S},\sigma^{\prime}_{S}\circ\sigma_{F})$, then the owner of $R$
is not in $S_{B}\setminus F(\sigma_{\textit{highB}}[S_{B}])$. Consequently,
for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highC}}[S]\neq\bot$, during
$E(C^{\prime}_{S},\sigma^{\prime}_{S}\circ\sigma_{F})$, each register
$R\in\mathcal{R}$ cannot be accessed if the owner of $R$ is in $S_{B}\setminus
F(\sigma_{\textit{highB}}[S_{B}])$.

By Section 3.2, Invariant (I8) holds for $\sigma_{\textit{highB}}[0..2^{n}-1]$
and $S_{\textit{max}}(\sigma_{\textit{highB}}[0..2^{n}-1])=S_{B}$. So in the
DSM model, for every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highB}}[S]\neq\bot$, during $E(\sigma_{\textit{highB}}[S])$,
each register $R\in\mathcal{R}$ can only be accessed by its owner if the owner
of $R$ is in $S_{B}\setminus F(\sigma_{\textit{highB}}[S_{B}])$. Thus for
every set $S\subseteq\mathcal{P}$ such that
$\sigma_{\textit{highC}}[S]\neq\bot$, during
$E(\sigma_{\textit{highC}}[S])=E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F})$,
each register $R\in\mathcal{R}$ can only be accessed by its owner if the owner
of $R$ is in $S_{B}\setminus F(\sigma_{\textit{highB}}[S_{B}])$. Then, since
$F(\sigma_{\textit{highC}}[S_{B}])\supseteq
F(\sigma_{\textit{highB}}[S_{B}])$, $S_{B}\setminus
F(\sigma_{\textit{highC}}[S_{B}])\subseteq S_{B}\setminus
F(\sigma_{\textit{highB}}[S_{B}])$. Consequently, in the DSM model, for every
set $S\subseteq\mathcal{P}$ such that $\sigma_{\textit{highC}}[S]\neq\bot$,
during
$E(\sigma_{\textit{highC}}[S])=E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F})$,
each register $R\in\mathcal{R}$ can only be accessed by its owner if the owner
of $R$ is in $S_{B}\setminus F(\sigma_{\textit{highC}}[S_{B}])$ (Invariant
(I8)).

By Section 3.2 ((H3)), in the CC model,for every set $S\subseteq\mathcal{P}$
such that $F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq
S\subseteq S_{B}$, and every process $p\in S\setminus
F(\sigma_{\textit{highB}}[S_{B}])$, the set of registers that $p$ has valid
cache copies of at the end of
$E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S})$ is exactly the same as
at the end of $E(\sigma_{\textit{highB}}[S_{B}]\circ\sigma^{\prime}_{S_{B}})$.
By Section 3.2, for every register $R\in\mathcal{R}$, if a non-read operation
is performed on $R$ during $E(C^{\prime\prime}_{S},\sigma_{F})$, it is also
performed on $R$ during $E(C^{\prime\prime}_{S_{B}},\sigma_{F})$. By
definition, $\sigma_{F}$ contains only steps of processes in $S_{\alpha}$. So
for every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$,
and every process $p\in S\setminus(F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha})$, the set of registers that $p$ has valid cache copies of at the
end of
$E(\sigma_{\textit{highC}}[S])=E(\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F})$
is exactly the same as at the end of
$E(\sigma_{\textit{highC}}[S_{B}])=E(\sigma_{\textit{highB}}[S_{B}]\circ\sigma^{\prime}_{S_{B}}\circ\sigma_{F})$.

Now recall that we have already proven that
$F(\sigma_{\textit{highC}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}$, and that Invariant (I2) holds for
$\sigma_{\textit{highC}}[0..2^{n}-1]$ with
$S_{\textit{max}}(\sigma_{\textit{highC}}[0..2^{n}-1])=S_{B}$. Thus for every
set $S\subseteq\mathcal{P}$ such that $\sigma_{\textit{highC}}[S]\neq\bot$,
and every process $p\in S\cap(S_{B}\setminus
F(\sigma_{\textit{highC}}[S_{B}]))$, the set of registers that $p$ has valid
cache copies of at the end of $E(\sigma_{\textit{highC}}[S])$ is exactly the
same as at the end of $E(\sigma_{\textit{highC}}[S_{B}])$ (Invariant (I9)).

Finally, by Section 3.2, $\sigma_{\textit{highB}}[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{highB}}[S])$, if $\sigma_{\textit{highB}}[S]\neq\bot$, then
$p$ incurs at least $i-1$ RMRs during $E(\sigma_{\textit{highB}}[S])$. By
Section 3.2 ((H6)), for every set $S\subseteq\mathcal{P}$ such that
$F(\sigma_{\textit{highB}}[S_{B}])\cup S_{\alpha}\subseteq S\subseteq S_{B}$,
each process in $S_{\beta}\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{highC}}[S]\neq\bot$, then
$\sigma_{\textit{highC}}[S]=\sigma_{\textit{highB}}[S]\circ\sigma^{\prime}_{S}\circ\sigma_{F}$,
i.e., every process in $S_{\beta}\cap S=S\setminus
F(\sigma_{\textit{highB}}[S_{B}])$ incurs at least one more RMR during
$E(\sigma_{\textit{highC}}[S])$ than during $E(\sigma_{\textit{highB}}[S])$.
Thus for every set $S\subseteq\mathcal{P}$ and every process $p\in S\setminus
F(\sigma_{\textit{highB}}[S_{B}])$ if $\sigma_{\textit{highC}}[S]\neq\bot$,
then $p$ incurs at least $i$ RMRs during $E(\sigma_{\textit{highC}}[S])$.

Now recall that we have already proven that
$F(\sigma_{\textit{highC}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}$, and that Invariant (I4) holds for
$\sigma_{\textit{highC}}[0..2^{n}-1]$. So for every set
$S\subseteq\mathcal{P}$, if $\sigma_{\textit{highC}}[S]\neq\bot$, then
$F(\sigma_{\textit{highC}}[S])=F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}$. Thus $(S\setminus
F(\sigma_{\textit{highB}}[S_{B}]))\supseteq(S\setminus
F(\sigma_{\textit{highC}}[S]))$. Therefore for every set
$S\subseteq\mathcal{P}$ and every process $p\in S\setminus
F(\sigma_{\textit{highC}}[S])$ if $\sigma_{\textit{highC}}[S]\neq\bot$, then
$p$ incurs at least $i$ RMRs during $E(\sigma_{\textit{highC}}[S])$ ((I10)). ∎

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

#### Analysis:

For every non-negative integer $i$, if $\sigma_{\textit{round}}[i,0..2^{n}-1]$
is $i$-compliant, then let
$S^{i}_{\textit{max}}=S_{\textit{max}}(\sigma_{\textit{round}}[i,0..2^{n}-1])$,
and let $n_{i}=|S^{i}_{\textit{max}}\setminus
F(\sigma_{\textit{round}}[i,S^{i}_{\textit{max}}])|$.

###### Lemma .

For every non-negative integer $i$, if $\sigma_{\textit{round}}[i,0..2^{n}-1]$
has non-$\bot$ entries, then $\sigma_{\textit{round}}[i,0..2^{n}-1]$ is
$i$-compliant.

###### Proof.

If $i=0$, then 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.

So suppose $i>0$. Thus if $\sigma_{\textit{round}}[i,0..2^{n}-1]$ has
non-$\bot$ entries, then either
$\sigma_{\textit{round}}[i,0..2^{n}-1]=\sigma_{\textit{lowB}}[0..2^{n}-1]$ or
$\sigma_{\textit{round}}[i,0..2^{n}-1]=\sigma_{\textit{highC}}[0..2^{n}-1]$.
The lemma immediately follows from Section 3.2 and Section 3.2. ∎

###### Lemma .

For every positive integer $i$, if $\sigma_{\textit{round}}[i,0..2^{n}-1]$ is
$i$-compliant, then $n_{i}\geq n_{i-1}/(640\log^{d+1}n)-2$

###### Proof.

Since $\sigma_{\textit{round}}[i,0..2^{n}-1]$ is $i$-compliant, either
$\sigma_{\textit{round}}[i,0..2^{n}-1]=\sigma_{\textit{lowB}}[0..2^{n}-1]$ or
$\sigma_{\textit{round}}[i,0..2^{n}-1]=\sigma_{\textit{highC}}[0..2^{n}-1]$.

Case 1.:

$\sigma_{\textit{round}}[i,0..2^{n}-1]=\sigma_{\textit{lowB}}[0..2^{n}-1]$.

Then by Section 3.2,
$S_{\textit{max}}(\sigma_{\textit{lowB}}[0..2^{n}-1])=S^{\textit{low}}_{\textit{max}}$.
Thus $n_{i}=|S^{\textit{low}}_{\textit{max}}\setminus
F(\sigma_{\textit{lowB}}[S^{\textit{low}}_{\textit{max}}])|$.

Now recall that in the construction of $\sigma_{\textit{lowB}}[0..2^{n}-1]$,
we checked whether there exists a 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}])$. If such a process $p$
exists, then we set $\sigma_{\textit{lowB}}[0..2^{n}-1]$ to be a simple
modification of $\sigma_{\textit{lowB}}[0..2^{n}-1]$ where every set
$S\subseteq\mathcal{P}$ that contains $p$ has had $\sigma_{\textit{lowB}}[S]$
set to $\bot$; otherwise we set
$\sigma_{\textit{lowB}}[0..2^{n}-1]=\sigma_{\textit{lowB}}[0..2^{n}-1]$. By
Section 3.2, $S_{\textit{max}}(\sigma_{\textit{lowB}}[0..2^{n}-1])=S_{I}$. So
by the construction of $\sigma_{\textit{lowB}}[0..2^{n}-1]$,
$|S^{\textit{low}}_{\textit{max}}\setminus
F(\sigma_{\textit{lowB}}[S^{\textit{low}}_{\textit{max}}])|\geq|S_{I}\setminus
F(\sigma_{\textit{lowB}}[S_{I}])|-1$. Thus $n_{i}\geq|S_{I}\setminus
F(\sigma_{\textit{lowB}}[S_{I}])|-1$.

Then recall that by the construction of $\sigma_{\textit{lowB}}[0..2^{n}-1]$,
for every set $S\subseteq\mathcal{P}$, $\sigma_{\textit{lowB}}[S]=\bot$ if and
only if $\sigma_{\textit{lowA}}[S]=\bot$. By Section 3.2 and Section 3.2,
Invariant (I2) holds for both $\sigma_{\textit{lowB}}[0..2^{n}-1]$ and
$\sigma_{\textit{lowA}}[0..2^{n}-1]$, with
$S_{\textit{max}}(\sigma_{\textit{lowB}}[0..2^{n}-1])=S_{\textit{max}}(\sigma_{\textit{lowA}}[0..2^{n}-1])=S_{I}$.
So $|S_{I}\setminus F(\sigma_{\textit{lowB}}[S_{I}])|=|S_{I}\setminus
F(\sigma_{\textit{lowA}}[S_{I}])|$. Thus $n_{i}\geq|S_{I}\setminus
F(\sigma_{\textit{lowA}}[S_{I}])|-1$.

Next, recall that by the construction of $\sigma_{\textit{lowA}}[0..2^{n}-1]$,
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]$. By definition,
$S_{I}=F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])\cup I$.

Furthermore, 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}-])=S^{\textit{setup}}_{\textit{max}}$.
So by Invariant (I4),
$F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])=F(\sigma_{\textit{lowA}}[S_{I}])$.
By construction, $I\cap
F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])=\varnothing$.
Thus $n_{i}\geq|S_{I}\setminus F(\sigma_{\textit{lowA}}[S_{I}])|-1=|I|-1$.

By Section 3.2, $|I|\geq|L|/(7k\log n)$. By construction, $|L|\geq
0.5|S^{\textit{setup}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])|$. Thus
$n_{i}\geq|L|/(7k\log n)-1\geq|S^{\textit{setup}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])|/(14k\log
n)-1$.

Case 2.:

$\sigma_{\textit{round}}[i,0..2^{n}-1]=\sigma_{\textit{highC}}[0..2^{n}-1]$.

Then by Section 3.2,
$S_{\textit{max}}(\sigma_{\textit{highC}}[0..2^{n}-1])=S_{B}$. Thus
$n_{i}=|S_{B}\setminus F(\sigma_{\textit{highC}}[S_{B}])|$.

Recall that by definition, $S_{B}=S_{\beta}\cup
F(\sigma_{\textit{highA}}[S_{H}])$. Furthermore, by Section 3.2,
$F(\sigma_{\textit{highC}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha}$.

Also recall that by the construction of $\sigma_{\textit{highB}}[0..2^{n}-1]$,
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]$. Thus by Section 3.2
and Invariant (I4),
$F(\sigma_{\textit{highA}}[S_{H}])=F(\sigma_{\textit{highA}}[S_{B}])=F(\sigma_{\textit{highB}}[S_{B}])$.

Finally, recall that by construction, $S_{\alpha}\cap
F(\sigma_{\textit{highA}}[S_{H}])=\varnothing$ and $S_{\beta}\cap
F(\sigma_{\textit{highA}}[S_{H}])=\varnothing$. Therefore:

$\displaystyle S_{B}\setminus F(\sigma_{\textit{highC}}[S_{B}])$
$\displaystyle=S_{B}\setminus(F(\sigma_{\textit{highB}}[S_{B}])\cup
S_{\alpha})$
$\displaystyle=S_{B}\setminus(F(\sigma_{\textit{highA}}[S_{H}])\cup
S_{\alpha})$ $\displaystyle=(S_{\beta}\cup
F(\sigma_{\textit{highA}}[S_{H}]))\setminus(F(\sigma_{\textit{highA}}[S_{H}])\cup
S_{\alpha})$ $\displaystyle=S_{\beta}\setminus S_{\alpha}$

By Section 3.2, $|S_{\beta}\setminus S_{\alpha}|>\frac{|H|}{204.8k}$. Thus
$n_{i}=|S_{B}\setminus F(\sigma_{\textit{highC}}[S_{B}])|>\frac{|H|}{204.8k}$.

By construction, $|H|\geq 0.5|S^{\textit{setup}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])|$. Thus
$n_{i}>\frac{|H|}{204.8k}\geq|S^{\textit{setup}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])|/(409.6k)$.

So in both cases, $n_{i}\geq|S^{\textit{setup}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])|/(409.6k\log
n)-1$.

Now recall that in the construction of $\sigma_{\textit{setupB}}[0..2^{n}-1]$,
we checked whether there exists a 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}}])$. If such a
process $p$ exists, then we set $\sigma_{\textit{setupB}}[0..2^{n}-1]$ to be a
simple modification of $\sigma_{\textit{setupA}}[0..2^{n}-1]$ where every set
$S\subseteq\mathcal{P}$ that contains $p$ has had
$\sigma_{\textit{setupB}}[S]$ set to $\bot$; otherwise we set
$\sigma_{\textit{setupB}}[0..2^{n}-1]=\sigma_{\textit{setupA}}[0..2^{n}-1]$.
By Section 3.2,
$S_{\textit{max}}(\sigma_{\textit{setupA}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$.
So by the construction of $\sigma_{\textit{setupB}}[0..2^{n}-1]$,
$|S^{\textit{setup}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])|\geq|S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])|-1$. Thus
$n_{i}\geq|S^{\textit{setup}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupB}}[S^{\textit{setup}}_{\textit{max}}])|/(409.6k\log
n)-1\geq|S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])|/(409.6k\log
n)-2$

Recall that by the construction of $\sigma_{\textit{setupA}}[0..2^{n}-1]$, for
every set $S\subseteq\mathcal{P}$, $\sigma_{\textit{setupA}}[S]=\bot$ if and
only if $\sigma_{\textit{old}}[S]=\bot$. By Section 3.2, Invariant (I2) holds
for $\sigma_{\textit{setupA}}[0..2^{n}-1]$ and
$S_{\textit{max}}(\sigma_{\textit{setupA}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$.
Also recall that by definition, $\sigma_{\textit{old}}[0..2^{n}-1]$ is
$(i-1)$-compliant and
$S_{\textit{max}}(\sigma_{\textit{old}}[0..2^{n}-1])=S^{\textit{old}}_{\textit{max}}$.
So $|S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])|=|S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])|$. Thus
$n_{i}\geq|S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{setupA}}[S^{\textit{old}}_{\textit{max}}])|/(409.6k\log
n)-2\geq|S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])|/(409.6k\log n)-2$

Finally, recall that $\sigma_{\textit{old}}[0..2^{n}-1]$ is simply
$\sigma_{\textit{round}}[i-1,0..2^{n}-1]$. So
$|S^{\textit{old}}_{\textit{max}}\setminus
F(\sigma_{\textit{old}}[S^{\textit{old}}_{\textit{max}}])|=n_{i-1}$.
Consequently, $n_{i}\geq n_{i-1}/(409.6k\log n)-2$. Then, since $k=\log^{d}n$,
$n_{i}\geq n_{i-1}/(409.6\log^{d+1}n)-2$. ∎

Since $S_{\textit{max}}(\sigma_{\textit{round}}[0,0..2^{n}-1])=\mathcal{P}$
and $\sigma_{\textit{round}}[0,\mathcal{P}]$ is the empty schedule,
$F(\sigma_{\textit{round}}[0,\mathcal{P}])=\varnothing$ and $n_{0}=n$. By
Section 3.2, for every positive integer $i$, if
$\sigma_{\textit{round}}[i,0..2^{n}-1]$ is $i$-compliant, then $n_{i}\geq
n_{i-1}/O(\log^{d+1}n)$.

Consequently, if $\mathcal{I}$ is the largest positive integer such that
$\sigma_{\textit{round}}[\mathcal{I},0..2^{n}-1]$ is $\mathcal{I}$-compliant,
then $\mathcal{I}$ is $\Omega(\log n/\log\log n)$. So
$\sigma_{\textit{round}}[\mathcal{I},S^{\mathcal{I}}_{\textit{max}}]$ contains
a schedule such that:

  * •

Since we reach the $\mathcal{I}$-th iteration,
$\sigma_{\textit{round}}[\mathcal{I}-1,0..2^{n}-1]$ has at least $2^{(k^{3})}$
non-$\bot$ entries, i.e., $n_{\mathcal{I}-1}\geq k^{3}=\log^{3d}n$. So
$n_{\mathcal{I}}\geq\log^{3d}n/(640\log^{d+1}n)-2$, which for a sufficiently
large constant $d$, $n_{\mathcal{I}}\geq\log^{d}n$. Thus
$|S^{\mathcal{I}}_{\textit{max}}\setminus
F(\sigma_{\textit{round}}[\mathcal{I},S^{\mathcal{I}}_{\textit{max}}])|\geq\log^{d}n$

  * •

For every process $p\in S^{\mathcal{I}}_{\textit{max}}\setminus
F(\sigma_{\textit{round}}[\mathcal{I},S^{\mathcal{I}}_{\textit{max}}])$, $p$
incurs at least $\mathcal{I}$ RMRs during
$E(\sigma_{\textit{round}}[\mathcal{I},S^{\mathcal{I}}_{\textit{max}}])$
(Invariant (I10)).

  * •

For every process $p\in S^{\mathcal{I}}_{\textit{max}}\setminus
F(\sigma_{\textit{round}}[\mathcal{I},S^{\mathcal{I}}_{\textit{max}}])$, $p$
never crashes during
$E(\sigma_{\textit{round}}[\mathcal{I},S^{\mathcal{I}}_{\textit{max}}])$
(Invariant (I6)).

  * •

For every process $p\in S^{\mathcal{I}}_{\textit{max}}\setminus
F(\sigma_{\textit{round}}[\mathcal{I},S^{\mathcal{I}}_{\textit{max}}])$, $p$
never enters the critical section during
$E(\sigma_{\textit{round}}[\mathcal{I},S^{\mathcal{I}}_{\textit{max}}])$
(Invariant (I7)).

Thus we have proven Theorem 1.

##  4\. Conclusion

We proved a tight RMR lower bound for RME, which applies to almost all
standard shared memory primitives that have been used to solve the problem.
The lower bound separates the RMR complexity of mutual exclusion in the
traditional, non-recoverable model from the recoverable model, for systems
that provide fetch-and-store and fetch-and-increment objects in addition to
registers and compare-and-swap objects. It applies to objects of arbitrary
(even unbounded) size.

RME can be solved in constant RMRs with fetch-and-add primitives of size
$n^{\Omega(1)}$ bits (Dhoked and Mittal, 2020), so obviously our lower bound
cannot be extended to cover such primitives. But it remains an open problem,
whether fetch-and-add operations can help, under the standard assumption that
objects can store only $O(\log n)$-bits. We believe that this is not the case.
In fact, we conjecture that in general objects that can only store $O(\log n)$
bits of information are not sufficient to break through the $\Omega(\log
n/\log\log n)$ RMR complexity barrier.

###### Acknowledgements.

Support is gratefully acknowledged from the Natural Science and Engineering
Research Council of Canada (NSERC) under Discovery Grant RGPIN/2019-04852, and
the Canada Research Chairs program.

## References

  * (1)
  * Anderson and Kim (2002) James H. Anderson and Yong-Jik Kim. 2002.  An Improved Lower Bound for the Time Complexity of Mutual Exclusion.  _Distr. Comp._ 15 (2002), 221–253.
  * Attiya et al. (2008) Hagit Attiya, Danny Hendler, and Philipp Woelfel. 2008\.  Tight RMR Lower Bounds for Mutual Exclusion and Other Problems. In _Proc. of 40th ACM STOC_. 217–226.
  * Chan and Woelfel (2020) David Yu Cheng Chan and Philipp Woelfel. 2020.  Recoverable Mutual Exclusion with Constant Amortized RMR Complexity from Standard Primitives. In _Proc. of the 2020 ACM PODC_. ACM, 181–190.  https://doi.org/10.1145/3382734.3405736
  * Craig (1993) Travis Craig. 1993\.  Building FIFO and Priority-Queuing Spin Locks from Atomic Swap.  Technical Report TR-93-02-02, Department of Computer Science, University of Washington.
  * Dhoked and Mittal (2020) Sahil Dhoked and Neeraj Mittal. 2020.  An Adaptive Approach to Recoverable Mutual Exclusion. In _Proc. of the 2020 ACM PODC_. ACM, 1–10.  https://doi.org/10.1145/3382734.3405739
  * Golab and Hendler (2017) Wojciech Golab and Danny Hendler. 2017.  Recoverable Mutual Exclusion in Sub-logarithmic Time. In _Proc. of the 2017 ACM PODC_. ACM, 211–220.  https://doi.org/10.1145/3087801.3087819
  * Golab and Hendler (2018) Wojciech Golab and Danny Hendler. 2018.  Recoverable Mutual Exclusion Under System-Wide Failures. In _Proc. of the 2018 ACM PODC_. ACM, 17–26.  https://doi.org/10.1145/3212734.3212755
  * Golab and Ramaraju (2019) Wojciech Golab and Aditya Ramaraju. 2019.  Recoverable mutual exclusion.  _Distr. Comp._ 32, 6 (2019), 535–564.  https://doi.org/10.1007/s00446-019-00364-0
  * Jayanti et al. (2018) Prasad Jayanti, Siddhartha Jayanti, and Anup Joshi. 2018\.  Optimal Recoverable Mutual Exclusion Using only FASAS. In _Proc. of 6th NETYS_ _(LNCS, Vol. 11028)_. Springer, 191–206.  https://doi.org/10.1007/978-3-030-05529-5_13
  * Jayanti et al. (2019) Prasad Jayanti, Siddhartha V. Jayanti, and Anup Joshi. 2019\.  A Recoverable Mutex Algorithm with Sub-logarithmic RMR on Both CC and DSM. In _Proc. of the 2019 ACM PODC_. ACM, 177–186.  https://doi.org/10.1145/3293611.3331634
  * Jayanti and Joshi (2017) Prasad Jayanti and Anup Joshi. 2017.  Recoverable FCFS Mutual Exclusion with Wait-Free Recovery. In _Proc. of 31st DISC_ _(LIPIcs, Vol. 91)_. 30:1–30:15.  https://doi.org/10.4230/LIPIcs.DISC.2017.30
  * Katzan and Morrison (2020) Daniel Katzan and Adam Morrison. 2020.  Recoverable, Abortable, and Adaptive Mutual Exclusion with Sublogarithmic RMR Complexity. In _Proc. of 24th OPODIS_ _(LIPIcs, Vol. 184)_. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 15:1–15:16.  https://doi.org/10.4230/LIPIcs.OPODIS.2020.15
  * Magnusson et al. (1994) Peter Magnusson, Anders Landin, and Erik Hagersten. 1994\.  Queue Locks on Cache Coherent Multiprocessors. In _Proc. of 8th International Symposium on Parallel Processing_ , Howard Jay Siegel (Ed.). IEEE Computer Society, 165–171.  https://doi.org/10.1109/IPPS.1994.288305
  * Mellor-Crummey and Scott (1991) John M. Mellor-Crummey and Michael L. Scott. 1991.  Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.  _ACM Trans. Comput. Syst._ 9, 1 (1991), 21–65.
  * Ramaraju (2015) Aditya Ramaraju. 2015\.  _RGLock: Recoverable mutual exclusion for non-volatile main memorysystems_.  Master’s thesis. University of Waterloo.  https://uwspace.uwaterloo.ca/handle/10012/9473
  * Yang and Anderson (1995) Jae-Heon Yang and James H. Anderson. 1995.  A Fast, Scalable Mutual Exclusion Algorithm.  _Distr. Comp._ 9, 1 (1995), 51–60.