Blog
About

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

      An Implementation of The Scalable and Correct Time-Stamped Stack

      Preprint

      1 , 1 ,   , 1 , 1

      ScienceOpen Preprints

      ScienceOpen

      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

          Many concurrent data structures impose real time ordering over their elements. This is needed only if the insertions modifying the data structure ran sequentially. A new approach using time stamps was proposed to avoid unneeded ordering. Our implementation is based on that time-stamped (TS) stack. Concurrent insertions can be left unordered and then ordered as necessary at removal. Because of this weak ordering, using linearizability to establish correctness is not possible. The original paper presents a new approach to proving correctness for the TS stack. This proof technique is a new, generic proof for correctness on concurrent data structures. In this paper, we highlight our general approach to re-implementing the Time-Stamped stack, discuss our modifications made to to the stack, give an overview of our implementation of a stack using software transactional memory, and analyze comparative performance graphs based on our experimental data.

          Related collections

          Most cited references 2

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

          A scalable lock-free stack algorithm

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

            The ABA Problem in Multicore Data Structures with Collaborating Operations

             Damian Dechev (2011)
              Bookmark

              Author and article information

              Journal
              ScienceOpen Preprints
              ScienceOpen
              30 May 2019
              Affiliations
              [1 ] University of Central Florida
              Article
              10.14293/S2199-1006.1.SOR-.PPCLZSY.v1

              This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at www.scienceopen.com .

              Data structures & Algorithms

              Comments

              Comment on this article