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

      An Implementation of The Scalable and Correct Time-Stamped Stack

      Preprint
      In review
      research-article
      1 , 1 ,   1 , , 1
      ScienceOpen Preprints
      ScienceOpen
      Bookmark

            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.

            Content

            Author and article information

            Journal
            ScienceOpen Preprints
            ScienceOpen
            30 May 2019
            Affiliations
            [1 ] University of Central Florida
            Author information
            https://orcid.org/0000-0003-3990-9302
            Article
            10.14293/S2199-1006.1.SOR-.PPCLZSY.v1
            99ee827d-e02c-495a-a15b-45bc9bb836ea

            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 .

            History

            Data structures & Algorithms

            Comments

            Comment on this article