Ohad Ben-Baruch

Ben-Gurion University, Israel

Danny Hendler

Ben-Gurion University, Israel

Matan Rusanovsky

Ben-Gurion University and
Israel Atomic Energy Commission, Israel

The emergence of systems with non-volatile main memory (NVM) increases the interest in the design of recoverable concurrent objects that are robust to crash-failures, since their operations are able to recover from such failures by using state retained in NVM. Of particular interest are recoverable algorithms that, in addition to ensuring object consistency, also provide detectability, a correctness condition requiring that the recovery code can infer if the failed operation was linearized or not and, in the former case, obtain its response.

In this work, we investigate the space complexity of detectable algorithms and the external support they require. We make the following three contributions. First, we present the first wait-free bounded-space detectable read/write and CAS object implementations. Second, we prove that the bit complexity of every $N$-process obstruction-free detectable CAS implementation, assuming values from a domain of size at least $N$, is $\Omega(N)$. Finally, we prove that the following holds for obstruction-free detectable implementations of a large class of objects: their recoverable operations must be provided with auxiliary state – state that is not required by the non-recoverable counterpart implementation – whose value must be provided from outside the operation, either by the system or by the caller of the operation. In contrast, this external support is, in general, not required if the recoverable algorithm is not detectable.

§ INTRODUCTION

Byte-addressable non-volatile main memory (NVM)
combines the performance benefits of conventional (volatile) main memory
with the durability of secondary storage.
Systems where non-volatile memory co-exists with volatile main memory already exist and are expected to become more prevalent in the future. This increases the interest in the crash-recovery model, where a failed process may be resurrected by the system following a crash. Traditional log-based recovery techniques can be applied correctly in such systems but fail to take full advantage of the parallelism and efficiency that may be gained by allowing processing cores to concurrently access recovery data directly from NVM, rather than by performing slow block transfers from secondary storage. Consequently, there is increasing interest in the design of recoverable concurrent objects that are robust
to crash-failures, since their operations are able to recover from such failures by using state retained in NVM (see e.g. [3, 9, 11, 10, 12, 19, 20]).

Of particular interest are recoverable algorithms that, in addition to ensuring object consistency, also provide detectability [9]. Detectability requires that the code recovering from a failed operation can infer if it was linearized or not and, in the former case, obtain its response.

Several recent works presented detectable algorithms [3, 4, 9]. In particular, both Ben-David et al. [4] and Attiya et al. [3] presented detectable CAS algorithms and [3] also presented a detectable read/write object. All these algorithms augment the arguments of recoverable operations with unique identifiers, for allowing the recovery code to detect whether or not the failed operation was linearized, consequently incurring unbounded space complexity.[This is also the case with the durable queue algorithm of [9].] In addition, [3] proved that every lock-free detectable test-and-set implementation from (non-recoverable) test-and-set objects must use unbounded space. This raises the question of whether unbounded space complexity is inherent to nonblocking detectable implementations of these objects. We provide a negative answer to this question by presenting the first nonblocking bounded-space detectable CAS and read/write algorithms. Both algorithms are wait-free. Our $N$-process bounded-space CAS algorithm uses $\Theta(N)$ bits in addition to those storing the CAS object's value. In our second contribution, we show that every obstruction-free detectable CAS implementation, assuming values from a domain of size at least $N$, must have $\Omega(2^N)$ different reachable shared-memory configurations, thus establishing that our CAS algorithm's space complexity is asymptotically optimal.

Detectable algorithms often require auxiliary state that helps them infer where in the execution the failure occurred. Informally, auxiliary state is information that is provided to the recoverable operation that is not provided to (nor required by) the “original” (non-recoverable) operation. In some works, it is assumed that this information is provided by the system.

For example, the recoverable mutual exclusion algorithms presented by Golab and Hendler [10] assume a model in which the system provides to each operation an epoch number whose value increases after each (system-wide) failure. Some detectable algorithms presented by Attiya et al. [3] assume that the system provides to the recovery code information identifying the instruction that the failed operation was about to execute via a non-volatile variable.
However, auxiliary state is not necessarily provided by the system.

For example, the read/write algorithm of [3], the CAS algorithm of Ben-David et al. [4] and the queue algorithm of Friedman et al. [9] rely on auxiliary state (e.g. unique identifiers) passed to recoverable operations via their arguments by the operations that invoke them.

We show that, for a large class of objects that includes read/write, CAS and FIFO queue objects, any obstruction-free detectable implementation must receive auxiliary state. As we prove, this auxiliary state must be made available to recoverable operations either via their arguments or via a non-volatile variable accessible by them whose value must be modified outside the operation. In contrast, this external support is, in general, not required if the recoverable algorithm is not detectable.

The rest of the paper is organized as follows. We describe the system model in Section <ref>. We then present our bounded-space detectable read/write and CAS algorithms in Sections <ref> and <ref>, respectively. In Section <ref> we also prove a lower bound on the space complexity of detectable CAS. This is followed by a proof that detectable implementations of a large class of objects require auxiliary state in Section <ref>. The paper is concluded by a short discussion in Section <ref>.

§ SYSTEM MODEL

A set $P$ of $N$ asynchronous crash-prone processes
communicate through shared objects.
The system provides base objects (also called shared variables or registers) that support atomic read, write,
and read-modify-write primitive operations.
Base objects are used to implement higher-level concurrent
objects by defining algorithms, for each process, which use primitive operations to carry
out the operations of the implemented object.

The state of the system consists of non-volatile shared-memory variables and per-process local variables stored in its local volatile cache. Local variables are accessed only by the process to which they belong. For presentation simplicity, we assume that each process $p$ may own non-volatile private variables that reside in the NVM but are accessed only by $p$.
We also assume the abstract private cache model
[4, 18], in which all shared variables are always persistent and there is no shared cache. In this model, primitive operations to shared variables are applied directly to the NVM. At any point during the execution of an operation,
a system-wide crash-failure
(or simply a crash) may occur, which resets the local variables of all processes to their initial values, but preserves the values of all non-volatile variables.

As we explain in Section <ref>, all our results hold also in the more realistic shared-cache model. In this model, in addition to per-process private caches, there is a single (volatile) shared cache. Primitive operations to shared variables are applied to this cache and explicit persistency instructions may be required for guaranteeing that values written to this cache get persisted to the NVM in the correct order [18].

To start executing an operation $Op$, a process $p$ invokes $Op$. We say that Op completes once control returns to the caller of $Op$. Before completing, $Op$ returns a response value, which is stored to a local variable of $p$.
The response value is lost if $p$ crashes before persisting it
(i.e., writing it to a non-volatile variable). We say that a process is idle if it is not in the midst of executing any operation. Each recoverable operation $Op$ of a shared object

is associated with a recovery function, denoted $Op.\texttt{Recover}$, which is responsible to infer whether $Op$ was linearized or not, and to obtain its response in the former case. $Op.\texttt{Recover}$ is performed by $p$ in order to recover from a failure that occurred while $p$ was executing $Op$. We assume that $Op.\texttt{Recover}$ is being called with the same arguments as those with
which $Op$ was invoked when the crash occurred. If $Op.\texttt{Recover}$ infers that $Op$ was not yet linearized, it returns a special  value, otherwise it returns $Op$'s response.

Our lower bounds (Theorems <ref> and <ref>) only require the model assumptions specified above. However, as we prove in Theorem <ref>, detectable algorithms must receive auxiliary state whose value is modified either by the operation's caller or by the system. We therefore make the following additional assumptions that are used by the algorithms we present. Each process $p$ is associated with a private non-volatile structure $Ann_p$ consisting of three fields. $Ann_p.op$ stores the type of recoverable operation currently performed by $p$, as well as the arguments with which it was called. It is accessed only by the caller of the recoverable operation $Op$, which sets its value (thus announcing the operation it is about to perform) immediately before invoking $Op$.

Which function (if any) should be invoked by $p$ in order to recover from a failure is determined according to the value of $Ann_p.op$. Field $Ann_p.resp$ stores the response of the recoverable operation and is initialized to $\init$ immediately before $Op$ is invoked. The 3rd field, $Ann_p.CP$, may be used by recoverable operations and recovery functions for managing checkpoints in their execution flow. Field $Ann_p.CP$ is set to 0 by the caller of the recoverable operation immediately before invoking it. $Ann_p.CP$ can be read and written by recoverable operations and their recovery functions and
is used by $p$ in order to record (in the NVM) the fact that the execution reached a certain point. The recovery function can then use this information in order to correctly recover and to avoid re-execution of critical instructions.

Failed processes recover in an asynchronous manner, independently of each other. Specifically, the recovery of some processes may have already completed while other processes may have not yet completed (or even started) their recovery. $Op.\texttt{Recover}$ may be invoked multiple times
before it completes, because the system may undergo multiple crashes in the course of executing it.

If all the operations of an implementation are recoverable,
then the implementation is called recoverable.

Linearizability [17] requires that each operation applied to a concurrent object takes effect instantaneously at some point between its invocation and response. The correctness condition ensured by our algorithms is durable linearizability (DL) [18]. DL requires that linearizability be maintained in spite of crash-failures. In other words, once the system recovers after a crash-failure, the state of the data structure reflects a history containing all operations that completed before the crash and may also contain some operations that have not completed before the crash. This  captures the idea that an operation can be linearized only once its effect gets persisted to NVM.

The progress conditions we consider are wait-freedom [15] and obstruction-freedom [16]. A recoverable operation or a recovery function is wait-free (resp. obstruction-free) if, starting from any reachable configuration, $p$ completes it in a finite number of its own steps (resp. when running solo), when the system experiences no crashes.
We emphasize that all our results hold also in a model where processes may fail independently, such as that assumed by [3].

§ DETECTABLE READ/WRITE OBJECT

Algorithm <ref> presents the pseudo-code of a detectable read/write object $O$ that uses bounded space from (bounded-space) variables that support read/write primitive operations.

To the best of our knowledge, this is the first detectable read/write algorithm that uses bounded space.
The checkpoint field $Ann_p.CP$ is used by process $p$ in order to allow the recovery function to infer where in the recoverable operation the failure occurred.
Each process $p$ owns two private variables: $RD_p$, storing data used during recovery, and $T_p$, storing an index $\in \{0,1\}$ to one of two size-$n$ toggle-bit arrays, $A[\ ][p][0]$ and $A[\ ][p][1]$, that are used by $p$'s write operations in an alternating manner. $O$'s state consists of a single shared read/write register $R$ storing a triplet of values $\langle v,q,b \rangle$, where $v$ is $O$'s current value, $q$ is the identifier of the process that (last) wrote $v$, and $b$ is the index of the toggle-bit array used by $q$ for that write operation. Initially, $R=\langle v_{init},0,0 \rangle$, where $v_{init}$ is $O$'s initial value, thus “attributing” this value to a write by process $0$ that used toggle-bit array $0$. Register $R$ stores $O(\log n)$ bits in addition to the application value $v$, in contrast with the unbounded state required by the read/write object implementation of Attiya et al. [3]. A 3-dimensional array $A[N][N][2]$ allows each writing process $p$ to coordinate with any other process $q$ using $p$'s two toggle-bit arrays.

The key challenge with which Algorithm <ref> copes is the ABA problem. Attiya et al. [3] avoid it by ensuring that all written values are distinct, at the cost of using a register of unbounded-size. Algorithm <ref> allows the same value to be written multiple times, so a process $p$ may read from $R$ a value $v_q$ (written by process $q$) and then write some value $v_p$ that is later overwritten by another write of $v_q$ by $q$. In this case, if $p$ recovers after a system crash, a mechanism for allowing it to detect whether or not its operation was linearized is required. As we explain below, per-process toggle bits are used to implement this mechanism. Before invoking an operation on the object, its caller initializes the $Ann_p$ structure as described in Section <ref>. Specifically, $Ann_p.CP$ is initialized to $0$ and $Ann_p.resp$ is initialized to $\init$.

The  operation To write, process $p$ reads $R$ (line <ref>), thus learning that $q$ was the last to write to $R$ and which toggle-bit array was used by $q$ for writing. Next, $p$ resets the bit from $q$'s other toggle-bit array corresponding to $p$ (line <ref>), and persists the value read from $R$, as well as the index of the toggle-bit array used by $p$'s current write (stored in $T_p$), into $RD_p$ (lines <ref>-<ref>). Then, $p$ reads $R$ again (line <ref>) and proceeds to write to $R$ (line <ref>) only if it read from $R$ the same value as in line <ref>. In this case, $p$ sets its checkpoint field to $1$ (line <ref>) immediately before the write to $R$ and sets it to $2$ (line <ref>) immediately after it. It then sets all the bits in the toggle-bit array used by its current write operation, switches its toggle-bit array index, persist the response and returns (lines <ref>-<ref>).

If the condition of line <ref> is not satisfied then, as we prove, a write operation $W$ by a process other than $p$ is linearized between $p$'s first and second reads of $R$, hence $p$ can be assumed to have been overwritten by $W$. In this case, $p$ skips lines <ref>-<ref> and proceeds directly to line <ref>.

The  recovery function

Upon recovery from a failed  operation $W$, $p$ first reads $RD_p$ (line <ref>) and then checks if $Ann_p.result$ was set (line <ref>). In this case, $W$ was completed and has been linearized, so the recovery function returns . Next, $p$ checks if $Ann_p.CP$ equals $0$ (line <ref>). In this case, as we prove, $W$ was not linearized before the failure, so the recovery function returns  (line <ref>); the caller of the failed operation can now decide whether or not to reattempt performing $W$. Otherwise, if $Ann_p.CP$ equals $1$ (line <ref>), then the recovery code must determine whether or not $R$ was written in line <ref> (either by $p$ or by another process) since when $W$ read $\langle qval, q,qtoggle \rangle$ from $R$ in line <ref>. This is done in line <ref> as follows. If $R$'s value differs from $\langle qval, q,qtoggle \rangle$, then $R$ was written and so either $W$ performed line <ref> or $W$ can be assumed to have been overwritten by another write, so the recovery code proceeds by performing lines <ref>-<ref> (which are identical to lines <ref>-<ref>). Otherwise, $R$'s value equals $\langle qval, q,qtoggle \rangle$ but it is still possible that $q$ wrote $\langle qval, q,qtoggle \rangle$ to $R$ again after $R$ was read by $W$. This is checked by the 2nd condition of line <ref> which relies

on the following key observation used by our correctness proof: in order for $q$ to write again using the same toggle-bit index, it must first complete a write operation using the other toggle-bit index. However, in that earlier write operation, $q$ sets all its toggle bits of that set to 1 (either in lines <ref>-<ref> of its write operation or in lines <ref>-<ref> of its recovery function). Therefore, upon recovery, if $p$ reads the same value from $R$ as before the crash, it can conclude that a write occurred in between its two reads of $R$ if and only if $q$'s toggle bit that it has set to 0 is now 1. If this is not the case, $p$ concludes that $W$ was not linearized and returns  (line <ref>).

The  operation reads a triplet of values from $R$ and then extracts its first component, writes it to $Ann_p.resp$ and returns it. Its recovery function re-invokes  if $Ann_p.resp=\init$ holds, otherwise it returns it. This simple code is not presented in Algorithm <ref>.

It is easily seen that Algorithm <ref> uses bounded space, assuming that the values written by  operations are of bounded size. It remains to show that the algorithm satisfies durable linearizability, detectability and wait-freedom.

Algorithm <ref> is wait-free and satisfies durable linearizability and detectability.

Consider an execution $\alpha$ of Algorithm <ref>. Assume process $p$ completes  a ($val$) operation $W$ in $\alpha$ (either directly or by completing the recovery function). We prove that one of the following holds: 1) $p$ writes to $R$ exactly once, and this is $W$'s linearization point; 2) $p$ does not write to $R$ and there is a concurrent write operation $W'$ by a different process that writes to $R$, hence we can linearize $W$ immediately before $W'$; or 3) the failure occurred before $W$ wrote to $R$, in which case  returns .

Non-Volatile Shared variables: read/write register $R$ initially $\langle v_{init},0,0 \rangle$, boolean $A[N][N][2]$ initially all $0$

Non-Volatile Private variables: Read/write register $RD_p$ initially $\bot$, $T_p$ initially 0

()  (val)

$\langle qval, q,qtoggle \rangle := R$
$A[p][q][1-qtoggle] := 0$
$mtoggle := T_p$
$RD_p := \langle mtoggle,qval, q,qtoggle \rangle$
$R \neq \langle qval, q,qtoggle \rangle$
goto <ref>

$Ann_p.CP := 1$
$R := \langle val, p, mtoggle \rangle$
$Ann_p.CP := 2$
$i=1$ to $N$
$A[i][p][mtoggle] := 1$

$T_p := 1-mtoggle$
$Ann_p.result := \Ack$

()  ()

$\langle val,p,toggle \rangle := R$

()  (val)

$\langle mtoggle, qval, q,qtoggle \rangle := RD_p$
$Ann_p.result \neq \init$

$Ann_p.CP = 0$

$Ann_p.CP = 1$
$R = \langle qval, q,qtoggle \rangle$ and $A[p][q][1-qtoggle] = 0$

$Ann_p.CP := 2$
$i=1$ to $N$
$A[i][p][mtoggle] := 1$

$T_p := 1-mtoggle$
$Ann_p.result := \Ack$

()  ()

Bounded space detectable read/write object $O$, code for process $p$.

We start by observing that if there is no crash during $W$, then either it writes to $R$ exactly once in line <ref>, or the condition in line <ref> holds, in which case $p$ does not write to $R$ and there was a concurrent write operation $W'$ by a different process that wrote to $R$.

We proceed to prove that the lemma holds also if $W$ and its recovery code experience one or more crashes. If the system crashes before $p$ writes to $\text{CP}_p$ in line <ref>

then $p$ did not write to $R$ while executing $W$, nor did it write to any entry in its toggle-bit arrays $A[i][p][y]$ for $i \neq p$, hence none of its writes is ever read by another process. Thus, $W$ was not linearized yet and the recovery code simply returns  (line <ref>).
Otherwise, consider the case where a crash occurred after $p$ executed line <ref>. Then either $p$  wrote to $R$ in line <ref> (hence $W$ was linearized) or $p$ observed in line <ref> a write by a concurrent write operation $W'$ and so $W$ can be linearized immediately before $W'$. In both cases,  re-executes the for loop of lines <ref>-<ref>, switches its toggle-bit index, and returns.

We are left with the case where a crash occurred after the update of $\text{CP}_p$ in line <ref> but before its update in line <ref>. Upon recovery, in order to satisfy detectability, the algorithm has to determine whether $W$ was linearized or not.

To complete the proof, we establish the following two claims: 1) the condition of line <ref> evaluates to false only if there was a write to $R$ (either by $p$ or by some other process) after $p$ first read it (in line <ref>); 2) if $p$ wrote to $R$ before the crash (in line <ref>), then the condition of line <ref> evaluates to false.

In line <ref>, $p$ reads $R$ and writes its content (together with $p$'s current value of $T_p$) to $RD_p$ in line <ref>. Therefore, $p$ persists the identifer $q$ of the process that last wrote to $R$ and the toggle-bit index used by $q$. Denote by $W_q$ this write of $q$, and let qts denote the toggle-bit index used in $W_q$. Assume that the condition of line <ref> evaluates to false. We prove that some write operation is linearized after $W_q$. Since a write operation can only be linearized when $R$ is written (not necessarily by the linearized operation itself), this would prove claim 1). If $p$ reads from $R$ in line <ref> a value different from the one stored in $RD_p$, then clearly there was a write to $R$ after the read in line <ref> and we are done. Otherwise, $p$ reads the same value from $R$ in line <ref>, and so it holds that $A[p][q][1-qts] = 1$. In line <ref>, $p$ sets $A[p][q][1-qts]$ to 0. Thus, $q$ must have set it to 1 later in the execution. Notice that $q$ sets a bit of the ($1-qts$) toggle-bit array to 1 only during the for loop (in lines <ref>-<ref> or <ref>-<ref>), after completing a write using the toggle-bit index $1-qts$. Denote this write by $\overline{W}_q$. Since $p$ observed the write $W_q$, which is associated with the toggle-bit index $qts$, it must be that write $\overline{W}_q$ was performed after the read of $p$ in line <ref>. This is true since $\overline{W}_q$ must either write to $R$, or observe a write to $R$ by another process, and in both cases, the linearization point of $\overline{W}_q$ must be after $p$ observed $W_q$ in line <ref>.

We now prove claim 2). Assume the system crashed after $p$ wrote to $R$ in line <ref>. Upon recovery, if $p$ reads in line <ref> a value from $R$ other than that stored in $RD_p$, the claim clearly holds. Otherwise, $p$ reads the same value written by $W_q$. Notice that $p$ reads the same value in line <ref>, after setting $A[p][q][1-qts]$ to 0. Moreover, later in the execution $p$ writes to $R$, and thus there must be another write by $q$ to $R$ with the same value as in $W_q$ that was done after $p$ wrote to $R$. In particular, these two writes use the same toggle-bit index qts, thus there must be another write by $q$ using toggle-bit index $1-qts$ in between the two. This write must have been completed, and thus the for loop updating $A[p][q][1-qts]$ to 1 was done after $p$'s read in line <ref>, hence, after $p$ has set $A[p][q][1-qts]$ to 0. Moreover, no process but $p$ can set $A[p][q][1-qts]$ to 0 again. Consequently, the second condition of the if statement in line <ref> does not hold, implying that claim 2) holds.

To conclude the proof of durable linearizability and detectability, we claim that every completed  operation returns the value of the latest  operation linearized before it, or $v_{init}$ if there are no such  operations. We linearize a  operation $Op$ when it writes to $Ann_p.resp$ and its linearization point is then set to its previous read of $R$. It follows that the response of a completed  is the value of $R$'s first component when last read by the operation. A  operation $W$ can be linearized either when it writes to $R$ (line <ref>) or when it does not write to $R$ but is linearized before a concurrent  operation $W'$ that does write to $R$. The claim now follows from the atomicity of $R$.

It is easily seen that the algorithm is wait-free, since neither ,  or their recovery functions contain any loops, so each of these operations/functions terminates in a constant number of steps if it experiences no crashes.

§ A DETECTABLE CAS ALGORITHM AND LOWER BOUND

We now present a wait-free detectable implementation of an $N$-process durable linearizable CAS object from (bounded-space) variables that support read/CAS primitive operations. As far as we know, this is the first bounded-space detectable CAS implementation. Our algorithm uses $\Theta(N)$ bits in addition to those storing the CAS object's value. We then prove that any such implementation requires $\Omega(N)$ bits, thus establishing that our algorithm is asymptotically space optimal.

§.§ A Bounded-Space Recoverable CAS Algorithm

Our implementation of a detectable CAS object $O$ is presented by Algorithm <ref>. $O$'s state is represented by a shared variable $C$ (supporting primitive read/CAS operations) that stores both $O$'s value (initially $v_{init}$) and an $N$-bit vector $vec$ (all of whose components are initially $0$). Each process $p$ owns a private variable $RD_p$, storing $p$'s recovery data.

The  operation
To perform a  operation, $p$ first reads $C$. If $O$'s current value differs from argument old, the CAS should fail, so $p$ persists a false response to $Ann_p.result$ and then returns false (lines <ref>-<ref>).
Otherwise, $p$ flips the bit $vec[p]$ (line <ref>), persists the flipped value, and increments its checkpoint variable (lines <ref>-<ref>).
Then, $p$ attempts to atomically both change $C$'s value and flip $vec[p]$ using an atomic  (line <ref>). Finally, it persists the  response and returns it (lines <ref>-<ref>).

The  recovery function
Upon recovery from a crash inside , $p$ first checks if it crashed after persisting the response, in which case it returns it (lines <ref>-<ref>). Otherwise, if $Ann_p.CP$ is 0, implying $p$ surely crashed before attempting the , then it returns fail (lines <ref>-<ref>). Finally, $p$ must determine if it performed a successful  before crashing. Observe that $p$ is the only process to ever change $vec[p]$, hence a successful  operation flips $vec[p]$ and it will remain flipped until $p$'s next successful , whereas a failed  attempt does not change $vec[p]$. Leveraging this observation, $p$ reads the vector stored in $C$ and returns true if $vec[p]$ has been changed (lines <ref>-<ref>, <ref>-<ref>). If the bit was not changed (implying that either the  failed or the crash occurred before $p$ performed it), $p$ returns fail (line <ref>).

A  operation simply reads $C$, extracts $O$'s value, writes it to $Ann_p.resp$ and returns it. Its recovery function re-invokes  if $Ann_p.resp=\init$ holds, otherwise it returns it. This simple code is not shown.

Algorithm <ref> is wait-free and satisfies durable linearizability and detectability.

Consider an execution $\alpha$ of Algorithm <ref>. Assume process $p$ completes a ($old, val$) operation $Op$ in $\alpha$ (either directly or by completing the recovery function). We prove that one of the following holds:
1) $p$ successfully writes to $C$ exactly once and the return value of $Op$ is true, in which case this is $Op$'s linearization point;
2) $p$ does not write to $C$ and $C$ contains a value different then $old$ at some point during $Op$, hence we can linearize $Op$ at this point and it returns false;
or 3) a failure occurs before $Op$ wrote to $C$, in which case  returns .

We start by observing that if $Op$ does not experience a crash, then either $p$ reads a value different from $old$ in $C$, thus it returns false (lines <ref>-<ref>), or $p$ performs a single  in line <ref> and returns its response. The  is successful only if the value stored in $C$ is $old$, in which case $p$ returns true. On the other hand, the  fails only if another process performed a successful  to $C$ after $p$ first read it in line <ref>, hence the value of $C$ after it must be other than $old$, and this is also the linearization point of $Op$, which indeed returns false.

Note that $p$ is the only process to ever update $vec[p]$ and the only place in which this update occurs is the  of line <ref>. Moreover, this is the only place in the code where a  is performed. Thus, since lines <ref>-<ref> have to be executed before line <ref> (even in case of a crash), each successful  to $C$ by $p$ will flip the bit $vec[p]$ stored in $C$, and it will remain flipped until $p$'s next successful .

We proceed to prove that the lemma holds also if $Op$ experiences one or more crashes.
If a crash occurs before $Op$ writes to $Ann_p.CP$ in line <ref>,
then $p$ did not write to $C$ while executing $Op$. Thus, $Op$ was not linearized yet and  simply re-invokes $Op$ (line <ref>).
Otherwise, consider the case where a crash occurs after $p$ performs line <ref>. If $p$ performed a successful  at line <ref> before the crash, then the operation was already linearized. As per our previous observation, $C.vec[p] = RD_p$ will hold as long as $p$ does not perform another (successful) . Hence, the condition in line <ref> is evaluated as false, and $p$ persists $\True$ as its response and then returns (lines <ref>-<ref>).

It remains to consider the case where the crash occurred when $p$ did not perform a successful  at line <ref>, either because the  failed or because $p$ crashed before performing line <ref>. In this case, we can consider $Op$ as not having been linearized yet, since it did not change the value of any variable that operations by other processes may read.

In both cases, $vec[p] \neq RD_p$ holds, since $vec[p]$ stores the old, un-flipped, value, whereas $RD_p$ stores the new, flipped, value. Moreover, no process but $p$ can change $vec[p]$. Thus, the condition of line <ref> is evaluated as true and the recovery function returns  in line <ref>.

Non-Volatile Shared variables: $C$, supporting primitive read/CAS operations, initially $\langle v_{init}, \langle 0,\ldots,0 \rangle \rangle$

Non-Volatile Private variables: read/write register $RD_p$ containing boolean field, initially $\bot$

()  (old, new)

$\langle val, vec \rangle := C$
(*[f]CAS failed; return) $val \neq old$
$Ann_p.result := \False$

$newvec := flipBit(vec,p)$ *flip vec[p]
$RD_p := newvec[p]$ *persist new bit
$Ann_p.CP := 1$  *set check-point
$res := C.\CAS (\langle val, vec \rangle, \langle new, newvec \rangle)$
$Ann_p.result := res$  *persist response

()  (old, new)

$Ann_p.result \neq \init$

$Ann_p.CP = 0$

$\langle val, vec \rangle := C$
$vec[p] \neq RD_p$
*CAS failed or not performed

$Ann_p.result := \True$ *CAS was successful

Bounded-space detectable CAS object $O$, code for process $p$.

§.§ A Space Lower Bound on Detectable CAS

Algorithm <ref> uses $\Theta(N)$ shared memory bits, in addition to those required for storing the CAS object's value.
Let $\mathcal{V}$ denote the set of states that may be assumed by a CAS object $O$. Assuming that $\vert {\mathcal{V}} \vert \geq N$, we prove that any recoverable and detectable obstruction-free implementation $A$ of $O$ must have at least $2^{N-1}$ reachable configurations with distinct shared-memory states. This implies that $A$ uses at least $N-1$ shared-memory bits. If $\vert {\mathcal{V}} \vert = O(N)$, then only $O(\log N)$ bits are required for storing the CAS object's value, implying that  $\Omega(N)$ additional shared-memory bits are required for supporting detectability. Before proceeding with the proof, we need the following two definitions.  We say that configurations $C,D$ are memory-equivalent if the values of each shared memory variable is the same in both configurations. We say that a step $s$ by some process $p$ is a modifying step [14] w.r.t. to an operation $Op$ by another process $q$ in some configuration $C$, if the solo execution of $Op$ by $q$ after $C$ and after $C \circ s$ return different responses. Figure <ref> illustrates the structure of the inductive construction of the proof that follows.

[scale=0.9, transform shape]
[circle, minimum height=1.1cm] (c) at (-1.5,0) $C$;
[circle, minimum height=1.1cm] (ct) at (1,0) $C'$;

[circle, minimum height=1.1cm] (cs) at (4,-1) $C_{s}$;
[circle, minimum height=1.1cm] (cns) at (4,1) $C_{ns}$;
[circle, scale=0,label=right:$S_1$] (tns) at (6,1.7) ;
[circle, scale=0] (bns) at (6,0.3) ;
(6,1) ellipse (0.15cm and 0.7cm);
[circle, scale=0.2, draw, fill] (mns) at (6,1) ;

[circle, scale=0,label=right:$S_2$] (ts) at (6,-0.3) ;
[circle, scale=0] (bs) at (6,-1.7) ;
(6,-1) ellipse (0.15cm and 0.7cm);
[circle, scale=0.2, draw, fill] (ms) at (6,-1) ;

[circle, scale=0] (rns) at (14,1) ;
[circle, scale=0] (rs) at (14,-1) ;

[circle] (dns) at (6.5,1) $D_{ns}$;
[circle] (ds) at (6.5,-1) $D_s$;

[->, anchor=north] (c.east) – node[below] $\alpha$ node[above, scale=0.8] $\casfunc_{p_N}(0,1)$ (ct.west);

[->] (ct) edge[sloped, above, scale=0.8] node[align=center] true
$\casfunc_q(0,1)$ (cns);
[->] (ct) edge[sloped, below, scale=0.8] node[align=center] $s \circ \casfunc_q(0,1)$
false (cs);
[->, anchor=south, sloped, scale=0.7] (cns) – node (tns.west);
[->, anchor=south, sloped, scale=0.7] (cns) – node (bns.west);
[->, sloped, dashed, above, scale=0.8] (cns) – node[] $\beta _{ns}$  (mns);
[->, anchor=south, sloped, scale=0.7] (cs) – node (ts.west);
[->, anchor=south, sloped, scale=0.7] (cs) – node (bs.west);
[->, sloped, dashed, above, scale=0.8] (cs) – node[] $\beta _{s}$  (ms);

[->] (ds) edge[sloped] node[below, align=center] $\gamma$ node[above, scale=0.8, align=center] $\qquad \qquad \qquad $ false / fail
$CRASH \circ \casrecover_{p_N}(0,1)$ (rs.west);

[->] (dns) edge[sloped] node[below, align=center] $\gamma$ node[above, scale=0.8, align=center] $\qquad \qquad \qquad$ false / fail
$CRASH \circ \casrecover_{p_N}(0,1)$ (rns.west);

The induction step of Theorem <ref>. Response of completed operations are in blue font.

Let $A$ be an $N$-process obstruction-free implementation of a CAS object $O$ (using any primitive operations) satisfying durable linearizability and detectability, assuming values from a domain $\mathcal{V}$ of size at least $N$. Then $A$ has at least $2^{N-1}$ different reachable configurations, no two of which are memory-equivalent.

We prove the claim by induction on $N$. The claim holds trivially for $N=1$. Assume the claim holds for $N$ and let $A$ be an ($N$+1)-process  obstruction-free recoverable implementation of a CAS object $O$ satisfying durable linearizability and detectability, assuming values from a domain $\mathcal{V}$ of size at least $N+1$. Denote the processes using $A$ by $p_1, p_2, \ldots, p_N, q$. Assume also WLOG that $\{0, 1, \ldots, N\} \subseteq {\mathcal{V}}$ and that $O$'s value in the initial configuration $C$ is $0$. Starting from $C$, we let $p_N$ perform a $\casfunc_{p_N}(0,1)$ operation until it is about to perform the first modifying step $s$ with respect to a $\casfunc_q(0,1)$ operation by process $q$. We denote by $\alpha$ the prefix of $p_N$'s execution up to (but not including) step $s$. That is, a solo execution of $\casfunc_q(0,1)$ by $q$ after $C \circ \alpha$ returns true, while its solo execution after $C \circ \alpha \circ s$ returns false. Such a modifying step exists because $A$ is obstruction-free, a solo execution of $\casfunc_q(0,1)$ starting from $C$ returns true, but a solo execution of $\casfunc_q(0,1)$ after $\casfunc_{p_N}(0,1)$ completes returns false.
We define the following two configurations:

$$ C_{ns} = C \circ \alpha \circ \casfunc_q(0,1) \qquad C_s = C \circ \alpha \circ s \circ \casfunc_q(0,1) $$

that are reached after $\casfunc_q(0,1)$ returns. The executions leading to $C_{ns}$ and $C_s$ exist, since $A$ is obstruction-free. From linearizability, $O$'s value is $1$ in both $C_s$ and $C_{ns}$, that is, a ( ) (resp. a $(1, 0)$) operation on $O$, performed to completion immediately after either $C_s$ or $C_{ns}$, must return $1$ (resp. return true and change the object's value to $0$). Moreover, $\casfunc_q(0,1)$ returns true in the execution leading to $C_{ns}$  and false in the execution leading to $C_{s}$.
Notice that all processes but $p_N$ are idle in $C_{ns}$. Moreover, if we fix $C_{ns}$ as an initial configuration, halt $p_N$ starting from this point on and restrict processes $p_1, \ldots, p_{N-1}, q$ to perform CAS operations with arguments from the domain ${\mathcal{V}} \setminus \{0\}$, then we obtain an $N$-process algorithm $A'$ for which we can apply the induction hypothesis. Thus, there is a set $S_1$ of at least $2^{N-1}$ configurations reachable from $C_{ns}$ in $p_N$-free executions, no two of which are memory-equivalent. The same argument can be applied to configuration $C_s$, resulting in a second set $S_2$ of $2^{N-1}$ configurations reachable from $C_s$, no two of which are memory-equivalent.

To complete the proof, we show that no configuration reachable from $S_1$ can be memory-equivalent with any configuration reachable from $S_2$. Intuitively, this is because the modifying step $s$ must write to shared memory and does not modify any of $p_N$'s local variables. Thus, if we can extend both $C_s$ and $C_{ns}$ and reach two memory-equivalent configurations, then $p_N$ will behave the same after a crash in both of them, which leads to a contradiction. The formal proof follows.

Assume towards a contradiction that there exist executions $\beta_{ns}$ and $\beta_s$ starting from $C_{ns}$ and $C_s$, respectively, leading to memory-equivalent configurations $D_{ns} \in S_1$ and $D_s \in S_2$. Note that both $\beta_{ns}$ and $\beta_s$ are $p_N$-free. We extend $D_{ns}$ by a system crash, followed by a recovery of $p_N$, followed by an execution in which $p_N$ performs its recovery function $\emph{\text{\casrecover}}_{p_N}(0,1)$ to completion. Denote this extension by $\gamma$. Since $\emph{\text{\casfunc}}_{p_N}(0,1)$ can be linearized only after $\emph{\text{\casfunc}}_q(0,1)$ (as the latter returns true in the execution leading to $C_{ns}$) and as $O$'s state is positive all throughout $\beta_{ns}$, $\emph{\text{\casrecover}}_{p_N}(0,1)$ must return either false or fail in $\gamma$.

Since all of $p_N$'s local variables are reset after the crash,

and since $D_{ns}$ and $D_s$ are memory-equivalent, if the system crashes after $D_s$, and then $p_N$ recovers by performing $\emph{\text{\casrecover}}_{p_N}(0,1)$ to completion, it will return false or fail as well. However, as $\emph{\text{\casfunc}}_q(0,1)$ returned false in the execution leading to $C_s$, from linearizability, $\emph{\text{\casrecover}}_{p_N}(0,1)$ must return true. This is a contradiction.

§ DETECTABLE ALGORITHMS REQUIRE AUXILIARY STATE

The detectable algorithms we presented in Sections
<ref>-<ref> use auxiliary state, provided via the non-volatile $Ann_p.CP$ field used for managing checkpoints.

As we've mentioned in Section <ref>, detectable algorithms often require auxiliary state that helps them infer where in the execution the failure occurred [3, 9]. We now formalize this notion.

Let $Op$ be a recoverable operation. We say that auxiliary state is provided to $Op$ via NVM, if in-between every two successive invocations of $Op$, a write is made to a non-volatile variable that can be accessed by $Op$. We say that auxiliary state is provided to $Op$ via operation arguments, if the arguments to $Op$ contain data not specified by the object's abstract operation.

For example, in our model, the system provides auxiliary state via $Ann_p.CP$, since it sets its value to $0$ before any invocation of a recoverable operation by $p$. The queue algorithm of [9] provides auxiliary state via unique operation identifiers passed as arguments.

In the following, we prove that the usage of auxiliary state is inevitable for obtaining detectable implementations for a large class of objects that includes read/write, CAS, resettable test-and-set and FIFO queue objects.

Some works considered a weaker notion of detectability than ours, where upon a recovery a process can infer the response of its last completed operation. For example, <cit.> presented universal constructions that can be made detectable under this weaker definition. The proofs we present below do not hold for this definition. In contrast, in this work we consider a variant of detectability which requires a process to infer to response of its last invoked operation, hence the recovery function needs to distinguish between different invocations of the same operation, as we later formalize.
Our proof holds for any implementation satisfying the following weak progress condition (which extends <cit.>).

A recoverable implementation $A$ satisfies weak obstruction-freedom if for every process $p$, starting from any configuration (reached by an execution of $A$) in which all processes other than $p$ are idle, if $p$ runs by itself while performing an operation or a recovery function and incurs no crashes, then it completes it.

It is easily seen that weak obstruction-freedom is satisfied by any recoverable algorithm that satisfies obstruction-freedom or deadlock-freedom. Our proof holds for the class of doubly-perturbing objects, a notion we define next.

Given an object $O$ and a sequential history $H$, we say that an operation $\Op$ is perturbing after H, if there exists an operation $\Op'$ by a different process such that $\Op'$ returns different responses in $H \circ \Op \circ \Op'$ and in $H \circ \Op'$. We also say that Op is perturbing with respect to $\Op'$ after H. We say that $O$ is doubly-perturbing if there exists an operation $\Op_p$ by some process $p$ and a sequential history $H_1$ of $O$ such that the following conditions hold:

* $\Op_p$ is perturbing with respect to some $\Op'$ after $H_1$.

* $H_1 \circ \Op_p \circ \Op'$ has a $p$-free extension, resulting in a sequential history $H_2$, such that $\Op_p$ is perturbing after $H_2$.

We say that $\Op_p$ witnesses that $O$ is doubly-perturbing.

It is easily shown that many widely-used objects

are doubly-perturbing. We now prove that a read/write object is doubly perturbing. In the appendix, we provide proofs that establish that the counter, CAS, fetch-and-add and FIFO queue objects are doubly-perturbing as well.

A read/write object is doubly-perturbing.

Consider a read/write object $O$ over a domain of values including at least two distinct values $v_0$, $v_1$, initialized to $v_0$. We claim that $write_p(v_1)$ witnesses that $O$ is doubly-perturbing. For any process $q \neq p$, $write_p(v_1)$ is perturbing w.r.t. $read_q$ after the empty sequential history. This satisfies the first condition of Definition <ref>. Moreover, $write_p(v_1) \circ read_q$ can be extended by a $write_q(v_0)$ operation, resulting in a sequential history $H_2=write_p(v_1) \circ read_q \circ write_q(v_0)$, such that (a second instance of) $write_p(v_1)$ is perturbing w.r.t. (a second instance of) $read_q$ operation after $H_2$. This satisfies the second condition of Definition <ref>. Thus, $O$ is doubly-perturbing.

The notion of doubly-perturbing objects bears similarity to the notion of perturbable objects defined by Jayanti et al. [21]. Although most common perturbable objects (including read/write, counter, compare-and-swap, swap and fetch-and-add objects) are also doubly-perturbing, the two classes of objects are incomparable.

We now prove that there are perturbable objects that are not doubly-perturbing (e.g., a max register [2]). In the appendix we prove that a bounded counter is doubly-perturbing but not perturbable.

A max register object is not doubly-perturbing.

Consider a max register object $O$, which supports a $writeMax(v)$ operation and a $read()$ operation that returns the largest value written to the register preceding it. Clearly, a $read$ operation cannot witness that $O$ is doubly-perturbing, as it cannot be observed by other operations. As for a $writeMax(v)$ operation by some process $p$, once the operation is lineraized any read must return a value $v$ or higher. Thus, invoking $writeMax(v)$ for a second time cannot modify $O$'s value, and thus cannot change the response of any other operation.

Lemma <ref> proves that max register is not doubly-perturbing. However, it is known to be perturbable [21]. Thus, Theorem <ref> below does not apply for a max register object. This raises the question of whether there is an obstruction-free implementation of a max-register satisfying durable linearizability and detectability that does not use auxiliary state. We now show that this is indeed the case.

Algorithm <ref> presents the pseudo-code of a detectable max register implementation that uses no auxiliary state.
The max register is composed of an integers array $MR$, such that process $p$ is associated with entry $MR[p]$. To perform $(val)$, $p$ simply checks if the value in $MR[p]$ is smaller than $val$, and if so updates it. To perform , $p$ uses a local array. For simplicity of presentation, we use an array-assignment/comparison notation as a shorthand for copying/comparing the array entry by entry. Process $p$ repeatedly copies the contents of $MR$ until the first successful double collect. Upon success, $p$ managed to obtain a valid snapshot of $MD$, so the largest value in $MD$ was the value of the max register at some point in the execution interval of .
The recovery function of each of these operations simply re-invokes the operation, and thus the code is not shown.

Non-Volatile Shared variables: integer array $MR[N]$ initially all 0

()  (val)

$MR[p] < val$
$MR[p] := val$

()  ()

$a[N]$, initially all 0
$a \neq MR$
$a := MR$

$res :=$ highest value in $a$
$Ann_p.result := res$

recoverable Max-Register object $O$, code for process $p$.

Next, we present our impossibility result.
The following two definitions are required for the proof.  We say that configurations $C,D$ are indistinguishable to process $p$, denoted by $C \stackrel{p}{\sim} D$,  if the values of all shared-memory variables, as well as those of $p$'s local variables, are the same in both configurations. We say that $C \stackrel{Q}{\sim} D$ for a set of processes $Q$ if $C \stackrel{p}{\sim} D$ for any $p \in Q$.
Figure <ref> depicts the structure of the execution constructed by our proof.
We note that Theorem <ref> holds regardless of the primitive operations used by the implementation.

[scale=0.9, transform shape]
[circle, minimum height=1.1cm, dotted] (ca) at (0,0) $C_{\alpha}$;
[circle, scale=0, draw] (c0) at (-1,0) ;
[circle, minimum height=1.1cm, dotted] (cb) at (2,0) $C_{\beta}$;
[circle, minimum height=1.1cm, dotted] (cg) at (4,0) $C_{\gamma}$;
[circle, minimum height=1.1cm, dotted] (d1) at (8.5,0) $D_1$;
[circle, minimum height=1.1cm, dotted] (d2) at (11.5,0) $D_2$;

[circle, minimum height=1.1cm, dotted] (cbt) at (2,2) $C_{\beta}^{'}$;
[circle, minimum height=1.1cm, dotted] (cgt) at (4,2) $C_{\gamma}^{'}$;
[circle, minimum height=1.1cm, dotted] (cgtd) at (6,2) $C_{\gamma}^{'} \delta$;

[circle, minimum height=1.1cm, dotted] (e1) at (8.5,2) $E_1$;
[circle, minimum height=1.1cm, dotted] (e2) at (11.5,2) $E_2$;

[circle, scale=0] (cgtr) at (5.5,2.9) ;
[circle, scale=0] (cgtdr) at (7.5,2.9) ;
[circle, scale=0, draw] (e1r) at (10,2.9) ;
[circle, scale=0, draw] (d1r) at (10,0.9) ;
[circle, scale=0, draw] (e2r) at (13,2.9) ;
[circle, scale=0, draw] (d2r) at (13,0.9) ;

[->, anchor=north] (c0.east) – node $\alpha$ (ca.west);

[->] (ca) – node[above, scale=0.8] $\Op_p$ node[below] $\beta$ (cb);
[->] (cb) – node[sloped, above, scale=0.7] $p.RES$  (cbt);

[->] (cb) – node[above, scale=0.8] $\Op_r\circ ...$ node[below] $\gamma$ (cg);
[->] (cbt) – node[above, scale=0.8] $\Op_r\circ ...$ node[below] $\gamma$ (cgt);
[->] (cgt) – node[below] $\delta$ (cgtd);
[->] (cg) – node[sloped, above, scale=0.7] $p.RES\circ \Op_p.INV \circ CRASH$  (e1);

(cg)  edge[->, anchor=south, scale=0.8] node $CRASH$ (d1);
(d1)  edge[->, anchor=south, scale=0.8] node $p.REC \circ \zeta$ (d2);
(e1)  edge[->, anchor=south, scale=0.8] node $p.REC \circ \zeta$ (e2);

[->, anchor=south, sloped, dashed, scale=0.7] (cgt) – node $\Op_q:u$(cgtr.west);
[->, anchor=south, sloped, dashed, scale=0.7] (cgtd) – node $\Op_q:v$(cgtdr.west);
[->, anchor=south, sloped, dashed, scale=0.7] (e1) – node $\Op_q:u$(e1r.west);
[->, anchor=south, sloped, dashed, scale=0.7] (d1) – node $\Op_q:u$(d1r.west);
[->, anchor=south, sloped, dashed, scale=0.7] (e2) – node $\Op_q:v$(e2r.west);
[->, anchor=south, sloped, dashed, scale=0.7] (d2) – node $\Op_q:v$(d2r.west);

The execution of $A$ constructed in the proof of Theorem <ref>.

Let $A$ be a weak obstruction-free recoverable implementation of a doubly-perturbing object $O$ satisfying durable linearizability and detectability and let $Op$ be a recoverable operation of $Op$. Then either auxiliary state is provided to $Op$ via NVM, or it is provided to $Op$ via operation arguments.

Assume towards a contradiction that auxiliary state is not provided to $Op$ neither via NVM nor via the arguments to $Op$, so the arguments to operations in $A$ are identical to those applied to the implemented object. For example, if $O$ is a read/write object, our assumption means that read operations receive no arguments and a write operation invoked for writing value $v$ receives a single argument whose value is $v$. We construct an execution of $A$ that will establish that $A$ violates durable linearizability, thus reaching a contradiction.

We first provide an intuition for the construction. Let $\Op_p$ be an operation by some process $p$ witnessing that $O$ is doubly-perturbing. That is, there exists an history in which $\Op_p$ is executed twice by process $p$, and each time it perturbs some other operation. A key point in the construction is that an invocation as well as a response step of $p$ does not effect any other process, as those steps are local and does not write to shared memory. Moreover, under our assumption, if a crash occurs immediately before $p$ returns from the first occurrence of $\Op_p$, or if we let $p$ complete $\Op_p$, invoke its next $\Op_p$, and only then a crash occurs, upon recovery $p$ can not distinguish between the two resulting configurations. This is due to the fact that no non-volatile variable is written between the two steps of $p$, and the arguments passed to both operations are identical. Hence, upon recovery all shared-memory variables, as well as $p$'s local variables that have been initialized by the crash, are the same. Therefore, the recovery function of $\Op_p$ in both cases is identical. However, the first $\Op_p$ was already linearized, and thus the recovery function in the first case must return its response, while the second $\Op_p$ was yet to take any steps, and the recovery function in the second case should return fail. A formal proof follows.

Since $O$ is doubly-perturbing, there exists an operation $\Op_p$ by some process $p$, witnessing that $O$ is doubly-perturbing. Thus, from the first condition of Definition <ref>,
there is a sequential history $H_1$ such that $\Op_p$ is perturbing w.r.t. to some operation $\Op_r$ after $H_1$, for $r \neq p$. Since $A$ satisfies weak obstruction-freedom, there exists an execution $\alpha$ in which processes perform their operations according to $H_1$ in a sequential manner, starting from an initial configuration, leading to a configuration $C_\alpha$. Starting from $C_\alpha$, let $p$ apply its $\Op_p$ operation and halt just before returning; denote the resulting configuration by $C_\beta$. Starting from $C_\beta$, let $p$ complete its $\Op_p$ operation on $O$ by returning from it and denote the resulting configuration by $C'_\beta$. As $A$ satisfies weak obstruction-freedom, the executions leading to $C_\beta$ and $C'_\beta$ exist, since in both $p$ runs solo starting from a quiescent configuration. Since returning a response does not change any shared variable and no auxiliary state is provided via NVM, we get: $\text{(1) }\forall q \neq p: C_\beta \stackrel{q}{\sim} C'_\beta.$

Notice that $C'_\beta$ is a quiescent configuration.
Since $\Op_p$ witnesses that $O$ is  doubly-perturbing, from the second condition of Definition <ref>, the history $H_1 \circ \Op_p \circ \Op_r$ has a $p$-free extension resulting in a sequential history $H_2$ (extending $H_1$) such that $\Op_p$ is perturbing after $H_2$. Assume it is perturbing w.r.t. an operation $\Op_q$ (for some $q \neq p$). Since $A$ is weak obstruction-free, there exists an execution $\gamma$ starting from $C'_\beta$ in which first $r$ performs to completion $\Op_r$, followed by a $p$-free sequential execution corresponding to the extension of $H_1 \circ \Op_p \circ \Op_r$, resulting in configuration $C'_\gamma$. Moreover, let $\delta$ denote the solo execution of $\Op_p$ after $C'_\gamma$, then $\Op_q$ returns different responses when executed after $C'_\gamma$ and after $C'_\gamma \delta$.
Since $\gamma$ is a $p$-free execution, and from Equation (1),
we get that $\gamma$ is also an execution starting from $C_\beta$ such that: $\text{(2) }\forall q \neq p: C_\gamma \stackrel{q}{\sim} C'_\gamma.$

$\Op_r$ was performed to completion in $\gamma$. Since $\Op_r$ returns the same response in the executions leading to $C'_\gamma$ and to $C_\gamma$ and as $\Op_p$ perturbed its response, it follows that the linearization point of $\Op_p$ precedes that of $\Op_r$ in both executions.

Next, consider the following two configurations: $D_1 = C_\gamma \circ CRASH $ and $E_1 = C_\gamma \circ (\Op_p.RES) \circ  (\Op_p.INV) \circ CRASH $. Thus, in the execution leading to $D_1$, the system crashes just before $p$ returns from its first $\Op_p$ operation, whereas, in the execution leading to $E_1$, $p$ completes that operation (thus $p$ returns its response), invokes a second $\Op_p$ operation and then the system crashes immediately after $p$'s invocation. Note that both these executions exist, since all processes but $p$ are idle in $C_\gamma$ and $A$ satisfies weak obstruction-freedom. Since neither responses nor invocations change any shared variables and since no auxiliary state is provided, neither via NVM nor via operation arguments, and as a crash reset all local variables of $p$ we get: $\text{(3) }D_1 \stackrel{P}{\sim} E_1$.

Next, starting from $E_1$, we extend the execution by recovering $p$, letting it perform a solo execution of its recovery function to completion, denoted by $\zeta$. We let $E_2 = E_1 \circ (p.REC) \circ \zeta$ denote the resulting configuration. $\zeta$ exists, since all processes but $p$ are idle in $E_1$ and $A$ satisfies weak obstruction-freedom. From Equation (3), $p$ performs the same execution $\zeta$ after $E_1 \circ (p.REC)$ and after $D_1 \circ (p.REC)$, hence $D_2 = D_1 \circ (p.REC) \circ \zeta$ exists and we have: $\text{(4) }D_2 \stackrel{P}{\sim} E_2$.

Finally, starting from configuration $E_2$, extend the execution by letting process $q \neq p$ perform $\Op_q$ to completion. $\Op_q$ completes, since $E_2$ is quiescent and $A$ satisfies weak obstruction-freedom. Assume that $\Op_q$ returns value $v$. From Equation (4), $\Op_q$ returns $v$ also if it is performed starting from configuration $D_2$.
Notice that $p$ cannot return  in its recovery function in $\zeta$. This is due to the fact that in the execution leading to $D_1$ $p$ executed a single $\Op_p$ operation which perturbs the response of $\Op_r$. Hence, $\Op_p$ must be linearized before $\Op_r$, and the recovery function returns its response. In particular, the recovery function of $p$ executed in $E_2$ returns a response different then , and thus the second $\Op_p$ must have a linearization point in the execution leading to $E_2$.
Moreover, since $\Op_p$ is perturbing w.r.t. $\Op_q$ after $H_2$, executing $\Op_q$ starting from $E_1$ returns a response $u \neq v$.
That is, the execution of $\Op_p$ in $\zeta_p$ perturbs the response of $\Op_q$. From Equation (3), we get that executing $\Op_q$ starting from $D_1$ returns $u$ as well.
It follows that $p$'s recovery function, executed in $\zeta$ after $D_1$, perturbs the response of $\Op_q$ performed after $D_2$. However, $p$ executed a single $\Op_p$ operation in the execution leading to $D_2$, which was linearized before $\Op_r$, while a second linearization point of $\Op_p$ must exist in the execution of $\Op_p$'s recovery function ($\zeta$), since it perturbs the response of $\Op_q$. Thus, $\Op_p$ has two linearization points in the same execution. This is a contradiction to our assumption that $A$ satisfies durable linearizability.

§ DISCUSSION

Several works propose different correctness conditions for the crash-recovery model [1, 5, 13]. Izraelevitz et al. [18] presented durable linearizability (DL) that assumes a system-wide crash model. Roughly speaking, it requires that after the system recovers from a crash, the state of each object reflects a consistent sub-history that contains all the operations that completed before the crash. Detectability [9] requires, in addition, that a process recovering from a crash that occurred while it was performing an operation $Op$ can infer if $Op$ took effect (was linearized) and, in such case, obtain its response. This allows for a “client” operation that called $Op$ to continue its execution after the crash, since $Op$'s response is made available to it. If $Op$ was not linearized, the client operation can choose whether or not to re-invoke it.

Attiya et al. [3] formalized a strict variant of this notion as nesting-safe recoverable linearizability (NRL). NRL requires that $Op.\texttt{Recover}$ complete the crashed operation and persist its response before returning, thus allowing the client operation access to this response. NRL is stricter than detectability [9], since the latter provides the client code with the flexibility of choosing whether or not to re-invoke a crashed operation that was not linearized (upon receiving a  response), whereas NRL will re-attempt such an operation again and again until it completes (if it ever does).

We note that NRL implies DL and detectability, as each crashed operation must complete, persist the response, and is linearized before $Op.\texttt{Recover}$ completes. As for the other direction, given an implementation that satisfies both DL and detectability, one can easily transform it into an implementation satisfying NRL by having the recovery function $Op.\texttt{Recover}$ invoke $Op$ again instead of returning a  response. Therefore, all algorithms presented in this paper can be easily be transformed to satisfy NRL.

The private cache model [9, 18] is an abstract model, where primitive operations are applied directly to NVM and processes do not share a cache. In the more realistic shared cache model [18], the main memory is non-volatile, while primitive operations are applied to a volatile shared cache. In this model, explicit persistency instructions are used in order to ensure that writes get persisted to the NVM and do so in the right order. Upon a crash, the shared cache content, as well as any the values of local variables, are lost.

It is easily seen that our impossibility and lower-bound results hold also in the shared cache model. As for our algorithms, for presentation simplicity, we specified and analyzed them assuming the private cache model. A simple syntactic transformation was proposed by [18], where persistency instructions are added to the code, thus transforming it to an implementation for the shared cache model. By applying this transformation to our algorithms, they maintain their correctness (as well as their space complexity) in the shared cache model as well.

An alternative approach for achieving recoverability is the design of persistent universal constructions. For example, [7] designed a persistent log-based universal construction that requires only one round trip to NVRAM per operation, which is optimal. However, logging imposes significant overheads in time and space, which are even more pronounced for concurrent
data structures, where there is an extra cost of synchronizing
accesses to the log.
[5] presented a recoverable variant of Herlihy's wait-free universal construction.
These constructions do not provide detectability as defined by [9]. However, upon recovery processes are able to determine which operations were linearized before the crash and obtain their response.
Such implementations does not require auxiliary state, as upon recovery process can not infer whether its last invoked operation was linearized. For example, assume process $p$ performs the same operation $Op$ twice, and a crash occurs during its second instance of $Op$. Upon recovery, $p$ is able to conclude that its last linearized operation was $Op$, and obtain its response. However, $p$ can not tell what instance of $Op$ was linearized. Unlike it, detectability requires $p$ to infer if the second instance of $Op$, during which the crash occurred, was linearized.

Ben-David et al. [4] showed that any implementation using only read, write and  primitives can be made
detectable by partitioning the code into capsules,
each containing a single  followed by several reads,
and replacing each  with its recoverable version.

Some recent works study the recoverable mutual exclusion (RME) problem, defined by Golab and Ramaraju [11, 10, 12, 19, 20].
Much work was also done on implementing persistent transactional memory frameworks (see [8, 22, 24, 26]).
Several previous works investigated recoverable implementations for specific data-structures. Friedman et al. [9] presented concurrent lock-free queue algorithms exhibiting different
tradeoffs between consistency and efficiency.
Coburn et al. [6] presented NV-heaps. Several works proposed persistent algorithms for index trees
[27, 23, 25, 27].

In this work, we presented the first bounded-space detectable CAS and read/write algorithms. Detectable algorithms have the advantage of supporting composability.  On the downside, as we established, this comes with a price tag in terms of space complexity and the need to provide recoverable operations and recovery functions with auxiliary data.

*Open Problems
Theorem <ref> establishes a space lower bound of $\Omega(N)$ shared bits on any obstruction-free detectable implementation of a  object, thus establishing that Algorithm <ref> is asymptotically space optimal. However, Algorithm <ref> uses a single $\Omega(N)$-bits shared variable. Finding such an algorithm which uses registers of size $O(\log N)$ bits, or alternatively proving that such an algorithm is impossible, is an interesting research direction.

No (non-trivial) space lower bound for a detectable read/write object is known and finding the tight bound is another open question. Finally, exploring the tradeoff between space and time complexity for detectable implementations, as well as the tradeoff between the complexities of a recoverable operation and its recovery function, is another interesting avenue for future work.

[1]
Aguilera, M. K., and Frølund, S.
Strict linearizability and the power of aborting.
In Tech. Rep. HPL-2003-241 (2003), HP Labs.

[2]
Aspnes, J., Attiya, H., and Censor-Hillel, K.
Polylogarithmic concurrent data structures from monotone circuits.
J. ACM 59, 1 (2012), 2:1–2:24.

[3]
Attiya, H., Ben-Baruch, O., and Hendler, D.
Nesting-safe recoverable linearizability: Modular constructions for
non-volatile memory.
In Proceedings of the 2018 ACM Symposium on Principles of
Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27,
2018 (2018), C. Newport and I. Keidar, Eds., ACM, pp. 7–16.

[4]
Ben-David, N., Blelloch, G. E., Friedman, M., and Wei, Y.
Delay-free concurrency on faulty persistent memory.
In The 31st ACM on Symposium on Parallelism in Algorithms and
Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019 (2019),
C. Scheideler and P. Berenbrink, Eds., ACM, pp. 253–264.

[5]
Berryhill, R., Golab, W. M., and Tripunitara, M.
Robust shared objects for non-volatile main memory.
In 19th International Conference on Principles of Distributed
Systems, OPODIS 2015, December 14-17, 2015, Rennes, France (2015),
E. Anceaume, C. Cachin, and M. G. Potop-Butucaru, Eds., vol. 46 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
pp. 20:1–20:17.

[6]
Coburn, J., Caulfield, A. M., Akel, A., Grupp, L. M., Gupta, R. K., Jhala,
R., and Swanson, S.
Nv-heaps: making persistent objects fast and safe with
next-generation, non-volatile memories.
In Proceedings of the 16th International Conference on
Architectural Support for Programming Languages and Operating Systems,
ASPLOS 2011, Newport Beach, CA, USA, March 5-11, 2011 (2011), R. Gupta
and T. C. Mowry, Eds., ACM, pp. 105–118.

[7]
Cohen, N., Guerraoui, R., and Zablotchi, I.
The inherent cost of remembering consistently.
In Proceedings of the 30th on Symposium on Parallelism in
Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18,
2018 (2018), C. Scheideler and J. T. Fineman, Eds., ACM, pp. 259–269.

[8]
Correia, A., Felber, P., and Ramalhete, P.
Romulus: Efficient algorithms for persistent transactional memory.
In Proceedings of the 30th on Symposium on Parallelism in
Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18,
2018 (2018), C. Scheideler and J. T. Fineman, Eds., ACM, pp. 271–282.

[9]
Friedman, M., Herlihy, M., Marathe, V. J., and Petrank, E.
A persistent lock-free queue for non-volatile memory.
In Proceedings of the 23rd ACM SIGPLAN Symposium on
Principles and Practice of Parallel Programming, PPoPP 2018, Vienna, Austria,
February 24-28, 2018 (2018), A. Krall and T. R. Gross, Eds., ACM,
pp. 28–40.

[10]
Golab, W., and Hendler, D.
Recoverable mutual exclusion under system-wide failures.
In Proceedings of the 2018 ACM Symposium on Principles of
Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27,
2018 (2018), C. Newport and I. Keidar, Eds., ACM, pp. 17–26.

[11]
Golab, W. M., and Hendler, D.
Recoverable mutual exclusion in sub-logarithmic time.
In Proceedings of the ACM Symposium on Principles of
Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017
(2017), E. M. Schiller and A. A. Schwarzmann, Eds., ACM, pp. 211–220.

[12]
Golab, W. M., and Ramaraju, A.
Recoverable mutual exclusion: [extended abstract].
In Proceedings of the 2016 ACM Symposium on Principles of
Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016
(2016), G. Giakkoupis, Ed., ACM, pp. 65–74.

[13]
Guerraoui, R., and Levy, R. R.
Robust emulations of shared memory in a crash-recovery model.
In 24th International Conference on Distributed Computing
Systems (ICDCS 2004), 24-26 March 2004, Hachioji, Tokyo, Japan (2004),
IEEE Computer Society, pp. 400–407.

[14]
Hendler, D., and Shavit, N.
Solo-valency and the cost of coordination.
Distributed Computing 21, 1 (2008), 43–54.

[15]
Herlihy, M.
Wait-free synchronization.
ACM Trans. Program. Lang. Syst. 13, 1 (1991), 124–149.

[16]
Herlihy, M., Luchangco, V., and Moir, M.
Obstruction-free synchronization: Double-ended queues as an example.
In 23rd International Conference on Distributed Computing
Systems (ICDCS 2003), 19-22 May 2003, Providence, RI, USA (2003),
IEEE Computer Society, pp. 522–529.

[17]
Herlihy, M., and Wing, J. M.
Linearizability: A correctness condition for concurrent objects.
ACM Trans. Program. Lang. Syst. 12, 3 (1990), 463–492.

[18]
Izraelevitz, J., Mendes, H., and Scott, M. L.
Linearizability of persistent memory objects under a
full-system-crash failure model.
In Distributed Computing - 30th International Symposium, DISC
2016, Paris, France, September 27-29, 2016. Proceedings (2016),
C. Gavoille and D. Ilcinkas, Eds., vol. 9888 of Lecture Notes in
Computer Science, Springer, pp. 313–327.

[19]
Jayanti, P., Jayanti, S. V., and Joshi, A.
Optimal recoverable mutual exclusion using only FASAS.
In Networked Systems - 6th International Conference, NETYS
2018, Essaouira, Morocco, May 9-11, 2018, Revised Selected Papers (2018),
A. Podelski and F. Taïani, Eds., vol. 11028 of Lecture Notes in
Computer Science, Springer, pp. 191–206.

[20]
Jayanti, P., and Joshi, A.
Recoverable FCFS mutual exclusion with wait-free recovery.
In 31st International Symposium on Distributed Computing, DISC
2017, October 16-20, 2017, Vienna, Austria (2017), A. W. Richa, Ed.,
vol. 91 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, pp. 30:1–30:15.

[21]
Jayanti, P., Tan, K., and Toueg, S.
Time and space lower bounds for nonblocking implementations.
SIAM J. Comput. 30, 2 (2000), 438–456.

[22]
Kolli, A., Pelley, S., Saidi, A. G., Chen, P. M., and Wenisch, T. F.
High-performance transactions for persistent memories.
In Proceedings of the Twenty-First International Conference on
Architectural Support for Programming Languages and Operating Systems,
ASPLOS '16, Atlanta, GA, USA, April 2-6, 2016 (2016), T. Conte and
Y. Zhou, Eds., ACM, pp. 399–411.

[23]
Lee, S. K., Lim, K. H., Song, H., Nam, B., and Noh, S. H.
WORT: write optimal radix tree for persistent memory storage
In 15th USENIX Conference on File and Storage Technologies,
FAST 2017, Santa Clara, CA, USA, February 27 - March 2, 2017 (2017),
G. Kuenning and C. A. Waldspurger, Eds., USENIX Association, pp. 257–270.

[24]
Liu, M., Zhang, M., Chen, K., Qian, X., Wu, Y., Zheng, W., and Ren, J.
Dudetm: Building durable transactions with decoupling for persistent
In Proceedings of the Twenty-Second International Conference on
Architectural Support for Programming Languages and Operating Systems,
ASPLOS 2017, Xi'an, China, April 8-12, 2017 (2017), Y. Chen, O. Temam,
and J. Carter, Eds., ACM, pp. 329–343.

[25]
Oukid, I., Lasperas, J., Nica, A., Willhalm, T., and Lehner, W.
Fptree: A hybrid SCM-DRAM persistent and concurrent b-tree for
storage class memory.
In Proceedings of the 2016 International Conference on
Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26
- July 01, 2016 (2016), F. Özcan, G. Koutrika, and S. Madden, Eds.,
ACM, pp. 371–386.

[26]
Volos, H., Tack, A. J., and Swift, M. M.
Mnemosyne: lightweight persistent memory.
In Proceedings of the 16th International Conference on
Architectural Support for Programming Languages and Operating Systems,
ASPLOS 2011, Newport Beach, CA, USA, March 5-11, 2011 (2011), R. Gupta
and T. C. Mowry, Eds., ACM, pp. 91–104.

[27]
Yang, J., Wei, Q., Chen, C., Wang, C., Yong, K. L., and He, B.
Nv-tree: Reducing consistency cost for nvm-based single level
In Proceedings of the 13th USENIX Conference on File and
Storage Technologies, FAST 2015, Santa Clara, CA, USA, February 16-19,
2015 (2015), J. Schindler and E. Zadok, Eds., USENIX Association,
pp. 167–181.

[1]
Aguilera, M. K., and Frølund, S.
Strict linearizability and the power of aborting.
In Tech. Rep. HPL-2003-241 (2003), HP Labs.

[2]
Aspnes, J., Attiya, H., and Censor-Hillel, K.
Polylogarithmic concurrent data structures from monotone circuits.
J. ACM 59, 1 (2012), 2:1–2:24.

[3]
Attiya, H., Ben-Baruch, O., and Hendler, D.
Nesting-safe recoverable linearizability: Modular constructions for
non-volatile memory.
In Proceedings of the 2018 ACM Symposium on Principles of
Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27,
2018 (2018), C. Newport and I. Keidar, Eds., ACM, pp. 7–16.

[4]
Ben-David, N., Blelloch, G. E., Friedman, M., and Wei, Y.
Delay-free concurrency on faulty persistent memory.
In The 31st ACM on Symposium on Parallelism in Algorithms and
Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019 (2019),
C. Scheideler and P. Berenbrink, Eds., ACM, pp. 253–264.

[5]
Berryhill, R., Golab, W. M., and Tripunitara, M.
Robust shared objects for non-volatile main memory.
In 19th International Conference on Principles of Distributed
Systems, OPODIS 2015, December 14-17, 2015, Rennes, France (2015),
E. Anceaume, C. Cachin, and M. G. Potop-Butucaru, Eds., vol. 46 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
pp. 20:1–20:17.

[6]
Coburn, J., Caulfield, A. M., Akel, A., Grupp, L. M., Gupta, R. K., Jhala,
R., and Swanson, S.
Nv-heaps: making persistent objects fast and safe with
next-generation, non-volatile memories.
In Proceedings of the 16th International Conference on
Architectural Support for Programming Languages and Operating Systems,
ASPLOS 2011, Newport Beach, CA, USA, March 5-11, 2011 (2011), R. Gupta
and T. C. Mowry, Eds., ACM, pp. 105–118.

[7]
Cohen, N., Guerraoui, R., and Zablotchi, I.
The inherent cost of remembering consistently.
In Proceedings of the 30th on Symposium on Parallelism in
Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18,
2018 (2018), C. Scheideler and J. T. Fineman, Eds., ACM, pp. 259–269.

[8]
Correia, A., Felber, P., and Ramalhete, P.
Romulus: Efficient algorithms for persistent transactional memory.
In Proceedings of the 30th on Symposium on Parallelism in
Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18,
2018 (2018), C. Scheideler and J. T. Fineman, Eds., ACM, pp. 271–282.

[9]
Friedman, M., Herlihy, M., Marathe, V. J., and Petrank, E.
A persistent lock-free queue for non-volatile memory.
In Proceedings of the 23rd ACM SIGPLAN Symposium on
Principles and Practice of Parallel Programming, PPoPP 2018, Vienna, Austria,
February 24-28, 2018 (2018), A. Krall and T. R. Gross, Eds., ACM,
pp. 28–40.

[10]
Golab, W., and Hendler, D.
Recoverable mutual exclusion under system-wide failures.
In Proceedings of the 2018 ACM Symposium on Principles of
Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27,
2018 (2018), C. Newport and I. Keidar, Eds., ACM, pp. 17–26.

[11]
Golab, W. M., and Hendler, D.
Recoverable mutual exclusion in sub-logarithmic time.
In Proceedings of the ACM Symposium on Principles of
Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017
(2017), E. M. Schiller and A. A. Schwarzmann, Eds., ACM, pp. 211–220.

[12]
Golab, W. M., and Ramaraju, A.
Recoverable mutual exclusion: [extended abstract].
In Proceedings of the 2016 ACM Symposium on Principles of
Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016
(2016), G. Giakkoupis, Ed., ACM, pp. 65–74.

[13]
Guerraoui, R., and Levy, R. R.
Robust emulations of shared memory in a crash-recovery model.
In 24th International Conference on Distributed Computing
Systems (ICDCS 2004), 24-26 March 2004, Hachioji, Tokyo, Japan (2004),
IEEE Computer Society, pp. 400–407.

[14]
Hendler, D., and Shavit, N.
Solo-valency and the cost of coordination.
Distributed Computing 21, 1 (2008), 43–54.

[15]
Herlihy, M.
Wait-free synchronization.
ACM Trans. Program. Lang. Syst. 13, 1 (1991), 124–149.

[16]
Herlihy, M., Luchangco, V., and Moir, M.
Obstruction-free synchronization: Double-ended queues as an example.
In 23rd International Conference on Distributed Computing
Systems (ICDCS 2003), 19-22 May 2003, Providence, RI, USA (2003),
IEEE Computer Society, pp. 522–529.

[17]
Herlihy, M., and Wing, J. M.
Linearizability: A correctness condition for concurrent objects.
ACM Trans. Program. Lang. Syst. 12, 3 (1990), 463–492.

[18]
Izraelevitz, J., Mendes, H., and Scott, M. L.
Linearizability of persistent memory objects under a
full-system-crash failure model.
In Distributed Computing - 30th International Symposium, DISC
2016, Paris, France, September 27-29, 2016. Proceedings (2016),
C. Gavoille and D. Ilcinkas, Eds., vol. 9888 of Lecture Notes in
Computer Science, Springer, pp. 313–327.

[19]
Jayanti, P., Jayanti, S. V., and Joshi, A.
Optimal recoverable mutual exclusion using only FASAS.
In Networked Systems - 6th International Conference, NETYS
2018, Essaouira, Morocco, May 9-11, 2018, Revised Selected Papers (2018),
A. Podelski and F. Taïani, Eds., vol. 11028 of Lecture Notes in
Computer Science, Springer, pp. 191–206.

[20]
Jayanti, P., and Joshi, A.
Recoverable FCFS mutual exclusion with wait-free recovery.
In 31st International Symposium on Distributed Computing, DISC
2017, October 16-20, 2017, Vienna, Austria (2017), A. W. Richa, Ed.,
vol. 91 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, pp. 30:1–30:15.

[21]
Jayanti, P., Tan, K., and Toueg, S.
Time and space lower bounds for nonblocking implementations.
SIAM J. Comput. 30, 2 (2000), 438–456.

[22]
Kolli, A., Pelley, S., Saidi, A. G., Chen, P. M., and Wenisch, T. F.
High-performance transactions for persistent memories.
In Proceedings of the Twenty-First International Conference on
Architectural Support for Programming Languages and Operating Systems,
ASPLOS '16, Atlanta, GA, USA, April 2-6, 2016 (2016), T. Conte and
Y. Zhou, Eds., ACM, pp. 399–411.

[23]
Lee, S. K., Lim, K. H., Song, H., Nam, B., and Noh, S. H.
WORT: write optimal radix tree for persistent memory storage
In 15th USENIX Conference on File and Storage Technologies,
FAST 2017, Santa Clara, CA, USA, February 27 - March 2, 2017 (2017),
G. Kuenning and C. A. Waldspurger, Eds., USENIX Association, pp. 257–270.

[24]
Liu, M., Zhang, M., Chen, K., Qian, X., Wu, Y., Zheng, W., and Ren, J.
Dudetm: Building durable transactions with decoupling for persistent
In Proceedings of the Twenty-Second International Conference on
Architectural Support for Programming Languages and Operating Systems,
ASPLOS 2017, Xi'an, China, April 8-12, 2017 (2017), Y. Chen, O. Temam,
and J. Carter, Eds., ACM, pp. 329–343.

[25]
Oukid, I., Lasperas, J., Nica, A., Willhalm, T., and Lehner, W.
Fptree: A hybrid SCM-DRAM persistent and concurrent b-tree for
storage class memory.
In Proceedings of the 2016 International Conference on
Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26
- July 01, 2016 (2016), F. Özcan, G. Koutrika, and S. Madden, Eds.,
ACM, pp. 371–386.

[26]
Volos, H., Tack, A. J., and Swift, M. M.
Mnemosyne: lightweight persistent memory.
In Proceedings of the 16th International Conference on
Architectural Support for Programming Languages and Operating Systems,
ASPLOS 2011, Newport Beach, CA, USA, March 5-11, 2011 (2011), R. Gupta
and T. C. Mowry, Eds., ACM, pp. 91–104.

[27]
Yang, J., Wei, Q., Chen, C., Wang, C., Yong, K. L., and He, B.
Nv-tree: Reducing consistency cost for nvm-based single level
In Proceedings of the 13th USENIX Conference on File and
Storage Technologies, FAST 2015, Santa Clara, CA, USA, February 16-19,
2015 (2015), J. Schindler and E. Zadok, Eds., USENIX Association,
pp. 167–181.

§ DOUBLY-PERTURBING OBJECTS

A counter object is doubly-perturbing.

Consider a counter object $O$ over a domain of values including at least three distinct values $v_0$, $v_0+1$, $v_0+2$, initialized to $v_0$. We claim that $Increment_p$ witnesses that $O$ is doubly-perturbing. For any process $q \neq p$, $Increment_p$ is perturbing w.r.t. $read_q$ after the empty sequential history. This satisfies the first condition of Definition <ref>. Moreover, $Increment_p \circ read_q$ can be extended by a an empty $p-free$ extension, resulting in a sequential history $H_2=Increment_p \circ read_q$, such that (a second instance of) $Increment_p$ is perturbing w.r.t. (a second instance of) $read_q$ operation after $H_2$. This satisfies the second condition of Definition <ref>. Thus, $O$ is doubly-perturbing.

Lemma <ref> proves that a bounded counter, supporting only $\{0,1,2\}$ values, is doubly-perturbing. However, such a bounded counter is not perturbable, since clearly an operation $Op$ can change its response at most twice.

A compare-and-swap object is doubly-perturbing.

Consider a compare-and-swap object $O$ over a domain of values including at least two distinct values $v_0$, $v_1$, initialized to $v_0$. We claim that $CAS_p(v_0,v_1)$ witnesses that $O$ is doubly-perturbing. For any process $q \neq p$, $CAS_p(v_0,v_1)$ is perturbing w.r.t. $CAS_q(v_0,v_1)$ after the empty sequential history. This satisfies the first condition of Definition <ref>. Moreover, $CAS_p(v_0,v_1) \circ CAS_q(v_0,v_1)$ can be extended by a $CAS_q(v_1,v_0)$ operation, resulting in a sequential history $H_2=CAS_p(v_0,v_1) \circ CAS_q(v_0,v_1) \circ CAS_q(v_1,v_0)$, such that (a second instance of) $CAS_p(v_0,v_1)$ is perturbing w.r.t. (a second instance of) $CAS_q(v_0,v_1)$ operation after $H_2$. This satisfies the second condition of Definition <ref>. Thus, $O$ is doubly-perturbing.

A fetch-and-add object is doubly-perturbing.

Since fetch-and-add object support an addition of the value $1$, the proof from Lemma
<ref> will hold here too. More formally, consider a fetch-and-add object $O$ over a domain of values including at least three distinct values $v_0$, $v_0+1$, $v_0+2$, initialized to $v_0$. We claim that $FAA_p(1)$ witnesses that $O$ is doubly-perturbing. For any process $q \neq p$, $FAA_p(1)$ is perturbing w.r.t. $read_q$ after the empty sequential history. This satisfies the first condition of Definition <ref>. Moreover, $FAA_p(1) \circ read_q$ can be extended with the empty $p-free$ extension, resulting in a sequential history $H_2=FAA_p(1) \circ read_q$, such that (a second instance of) $FAA_p(1)$ is perturbing w.r.t. (a second instance of) $read_q$ operation after $H_2$. This satisfies the second condition of Definition <ref>. Thus, $O$ is doubly-perturbing.

A FIFO queue object is doubly-perturbing.

Consider a FIFO queue object $O$ over a domain of values including at least two distinct values $v_0$, $v_1$, initialized to an empty queue. We claim that $Deq_p$ witnesses that $O$ is doubly-perturbing. After the empty sequential history, we perform the following sequence of operations $Enq_p(v_0) \circ Enq_p(v_1)$, and denote the resulting history as $H_1$.
For any process $q \neq p$, $Deq_p$ is perturbing w.r.t. $Deq_q$ after $H_1$. This satisfies the first condition of Definition <ref>. Moreover, $Deq_p \circ Deq_q$ can be extended by the sequence of operations:  $Enq_q(v_0) \circ Enq_q(v_1)$ as before, resulting in a sequential history $H_2=Enq_p(v_0) \circ Enq_p(v_1) \circ Deq_p \circ Deq_q \circ Enq_q(v_0) \circ Enq_q(v_1)$, such that (a second instance of) $Deq_p$ is perturbing w.r.t. (a second instance of) $Deq_q$ operation after $H_2$. This satisfies the second condition of Definition <ref>. Thus, $O$ is doubly-perturbing.

§ SYSTEM SUPPORT

In the following we

Non-Volatile Shared variables: read/write announcements array $annc[N]$, holding tuples of $\langle Op_name; params; result \rangle$, initially all tuples are set to $\bot $

Non-Volatile Private variables:

()  (Op, params)
$annc[p] := \langle Op; params; \bot \rangle$
$annc[p].result := $ (params)

()  ()

$\langle op; params; res \rangle := annc[p]$
$res \neq \bot$

$annc[p].result := $ (params)

Announce code for a compiler, and Announce Recovery code for process $p$.

On each call of some object operation $Op$ with the operation parameters $params$, the compiler/library should translate the call to $(Op, params)$. In case that process $p$ crashes, the system makes $p$ invoke the pre-compiled function $()$ that resides in the Non-Volatile memory, immediately upon recovery.