The semantics of concurrent data structures is usually given by a sequential specification and a consistency condition. It has been noticed that strong semantics might result in poor performance and scalability which initiated the work on relaxed semantics of concurrent objects, in particular concurrent data structures.

Relaxing the semantics can be done in both dimensions: (1) by relaxing the sequential specification and/or (2) by relaxing the consistency condition. I will present quantitative relaxations that result in (1) as well as local linearizability that provides (2). This is joint work with many coauthors published at POPL'13 and CONCUR'16.