  This paper presents the tracking approach for deriving detectably recoverable
(and thus also durable) implementations of many widely-used concurrent data
structures. Such data structures, satisfying detectable recovery, are appealing
for emerging systems featuring byte-addressable non-volatile main memory
(NVRAM), whose persistence allows to efficiently resurrect failed processes
after crashes. Detectable recovery ensures that after a crash, every executed
operation is able to recover and return a correct response, and that the state
of the data structure is not corrupted. Info-Structure Based (ISB)-tracking
amends descriptor objects used in existing lock-free helping schemes with
additional fields that track an operation's progress towards completion and
persists these fields to memory in order to ensure detectable recovery.
ISB-tracking avoids full-fledged logging and tracks the progress of concurrent
operations in a per-process manner, thus reducing the cost of ensuring
detectable recovery. We have applied ISB-tracking to derive detectably
recoverable implementations of a queue, a linked list, a binary search tree,
and an exchanger. Experimental results show the feasibility of the technique.
