  We present a fully lock-free variant of the recent Montage system for
persistent data structures. Our variant, nbMontage, adds persistence to almost
any nonblocking concurrent structure without introducing significant overhead
or blocking of any kind. Like its predecessor, nbMontage is buffered durably
linearizable: it guarantees that the state recovered in the wake of a crash
will represent a consistent prefix of pre-crash execution. Unlike its
predecessor, nbMontage ensures wait-free progress of the persistence frontier,
thereby bounding the number of recent updates that may be lost on a crash, and
allowing a thread to force an update of the frontier (i.e., to perform a sync
operation) without the risk of blocking. As an extra benefit, the helping
mechanism employed by our wait-free sync significantly reduces its latency.
  Performance results for nonblocking queues, skip lists, trees, and hash
tables rival custom data structures in the literature -- dramatically faster
than achieved with prior general-purpose systems, and generally within 50% of
equivalent non-persistent structures placed in DRAM.
