  We present durable implementations for two well known universal primitives --
CAS (compare-and-swap), and its ABA-free counter-part LLSC (load-linked,
store-conditional). All our implementations are: writable, meaning they support
a Write() operation; have constant time complexity per operation; allow for
dynamic joining, meaning newly created processes (a.k.a. threads) of arbitrary
names can join a protocol and access our implementations; and have adaptive
space complexities, meaning the space use scales in the number of processes $n$
that actually use the objects, as opposed to previous protocols which are
designed for a maximum number of processes $N$. Our durable Writable-CAS
implementation, DuraCAS, requires $O(m + n)$ space to support $m$ objects that
get accessed by $n$ processes, improving on the state-of-the-art $O(m + N^2)$.
By definition, LLSC objects must store "contexts" in addition to object values.
Our Writable-LLSC implementation, DuraLL, requires $O(m + n + C)$ space, where
$C$ is the number of "contexts" stored across all the objects. While LLSC has
an advantage over CAS due to being ABA-free, the object definition seems to
require additional space usage. To address this trade-off, we define an
External Context (EC) variant of LLSC. Our EC Writable-LLSC implementation is
ABA-free and has a space complexity of just $O(m + n)$.
  To our knowledge, we are the first to present durable CAS algorithms that
allow for dynamic joining, and our algorithms are the first to exhibit adaptive
space complexities. To our knowledge, we are the first to implement any type of
durable LLSC objects.
