  We study the psync complexity of concurrent sets in the non-volatile shared
memory model. Flush instructions are used in non-volatile memory to force
shared state to be written back to non-volatile memory and must typically be
accompanied by the use of expensive fence instructions to enforce ordering
among such flushes. Collectively we refer to a flush and a fence as a psync.
The safety property of strict linearizability forces crashed operations to take
effect before the crash or not take effect at all; the weaker property of
durable linearizability enforces this requirement only for operations that have
completed prior to the crash event. We consider lock-free implementations of
list-based sets and prove two lower bounds. We prove that for any durable
linearizable lock-free set there must exist an execution where some process
must perform at least one redundant psync as part of an update operation. We
introduce an extension to strict linearizability specialized for persistent
sets that we call strict limited effect (SLE) linearizability. SLE
linearizability explicitly ensures that operations do not take effect after a
crash which better reflects the original intentions of strict linearizability.
We show that it is impossible to implement SLE linearizable lock-free sets in
which read-only (or search) operations do not flush or fence. We undertake an
empirical study of persistent sets that examines various algorithmic design
techniques and the impact of flush instructions in practice. We present
concurrent set algorithms that provide matching upper bounds and rigorously
evaluate them against existing persistent sets to expose the impact of
algorithmic design and safety properties on psync complexity in practice as
well as the cost of recovering the data structure following a system crash.
