Abstract
Relaxed data structures offer a systematic approach for improving scalability in highly concurrent systems by weakening restrictive data ordering constraints that limit parallelism. By relaxing semantics such as exact FIFO ordering in queues, threads can access the data structure through multiple disjoint access points, reducing contention and significantly improving throughput. Prior work has extensively studied relaxed data structures, primarily focusing on concurrent FIFO, LIFO, and priority queues, demonstrating that substantial scalability gains can be achieved while preserving useful ordering guarantees. In particular, relaxed priority queues have emerged as effective scheduling primitives, enabling state-of-the-art performance in applications such as parallel Single-Source Shortest Paths. This paper surveys the design space of relaxed data structures, identifying key relaxation models and implementation techniques, systematically comparing the strengths and weaknesses of existing algorithms. The survey highlights fundamental trade-offs between ordering guarantees and performance, aiming to provide guidance for both designers and users of relaxed concurrent data structures.
Funding Information
  • Swedish Research Council (2021-05443)

This publication has 35 references indexed in Scilit: