36
views
0
recommends
+1 Recommend
0 collections
    2
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Tracking in Order to Recover: Recoverable Lock-Free Data Structures

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We present the \emph{tracking approach} for deriving \emph{recoverable} implementations of several widely-used concurrent data structures. Recoverability is appealing for emerging systems featuring byte-addressable \emph{non-volatile main memory} (\emph{NVRAM}), whose durability allows to efficiently resurrect a failed process after it crashes. The tracking approach ensures that after a crash occurs, every executed operation is able to recover and return a correct response, in addition to guaranteeing that the state of the data structure is not corrupted. The approach is applicable to lock-free concurrent data structures that use helping and rely on information structures to track the progress of operations. Such a tracking mechanism is already present in a wide range of well-known concurrent data structures, in particular, linked lists, trees and elimination stacks, making it relatively easy to derive their recoverable versions using the tracking approach. The tracking approach illustrates that full-fledged logging is not needed and ensures that the progress of concurrent operations is tracked in a \emph{per-process} manner, thus reducing the cost of ensuring recoverability.

          Related collections

          Most cited references 24

          • Record: found
          • Abstract: not found
          • Conference Proceedings: not found

          Simple, fast, and practical non-blocking and blocking concurrent queue algorithms

            Bookmark
            • Record: found
            • Abstract: not found
            • Book Chapter: not found

            A Pragmatic Implementation of Non-blocking Linked-lists

              Bookmark
              • Record: found
              • Abstract: not found
              • Conference Proceedings: not found

              Non-blocking binary search trees

                Bookmark

                Author and article information

                Journal
                31 May 2019
                Article
                1905.13600

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                cs.DC

                Networking & Internet architecture

                Comments

                Comment on this article