  The emergence of systems with non-volatile main memory (NVM) increases the
interest in the design of \emph{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
\emph{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
\emph{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.
