Christoph Senjak, Quantitative Relaxations Of Concurrent Data Structures

Christoph Senjak
Quantitative Relaxations Of Concurrent Data Structures

The importance of concurrent data structures increases---now that multicore architectures are the standard---and distributed computing is widespread. However, keeping those structures consistent can become a bottleneck, so an obvious idea is to relax their strict semantics as far as possible. Informally speaking, it seems plausible that a stack which may permutate elements to some "certain degree" can be implemented more efficiently than a strict stack. It is though not clear what a "certain degree" means here, and this problem is adressed by the paper "Quantitative Relaxations Of Concurrent Data Structures" which gives a general framework for creating relaxations of semantics. I will give a short introduction to the contents of this paper with focus on examples rather than full generality.