An Implementation of The Scalable and Correct Time-Stamped Stack

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.