Evolving trends in hardware, especially the shift from single-core to multicore and many-core processors, have pushed current programming to the center of the discussion in many designs and implementations. Many reports published in recent years address the parallelization of single-threaded programs for multicore and many-core architectures.

This paper tackles the problem from an entirely different angle. To reduce contention and thus improve scalable performance in multithreaded programming, the authors propose quantitative relaxation of concurrent data structures. They present examples of k-stack and k-stuttering counters that illustrate the implementation of relaxed data structures, accompanied by illuminating discussions.

The significance of this paper is that it provides a framework for quantitative relaxation of concurrent data structures, and thus opens a new path for exploring concurrency in single-threaded designs.