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.

Provided by: University of Würzburg Topic: Big Data Date Added: Feb 2014 Format: PDF

Find By Topic