Fast Concurrent Data-Structures Through Explicit Timestamping
Concurrent data-structures, such as stacks, queues and de-ques, often implicitly enforce a total order over elements with their underlying memory layout. However, linearizability only requires that elements are ordered if the inserting methods ran sequentially. The authors propose a new data-structure design which uses explicit time-stamping to avoid unwanted ordering. Elements can be left unordered by associating them with unordered timestamps if their insert operations ran concurrently. In their approach, more concurrency translates into less ordering, and thus less-contended removal and ultimately higher performance and scalability.