Invited Paper: Relaxed Data Structures for Practical Parallelism: Survey and Design Recommendations
Open Access
- 5 July 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-5
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.Keywords
Funding Information
- Swedish Research Council (2021-05443)
This publication has 35 references indexed in Scilit:
- Distributed Computation of Persistent Cohomology2026
- Elastic Relaxation of Concurrent Data StructuresIEEE Transactions on Parallel and Distributed Systems, 2025
- How to Relax Instantly: Elastic Relaxation of Concurrent Data Structures2024
- The Contention Avoiding Concurrent Priority Queue2017
- Balanced Allocations: A Simple Proof for the Heavily Loaded CaseLecture Notes in Computer Science, 2014
- Fast and Scalable, Lock-Free k-FIFO QueuesLecture Notes in Computer Science, 2013
- Performance, Scalability, and Semantics of Concurrent FIFO Queues2012
- Balanced Allocations: The Heavily Loaded CaseSIAM Journal on Computing, 2006
- The power of two choices in randomized load balancingIEEE Transactions on Parallel and Distributed Systems, 2001
- Balanced AllocationsSIAM Journal on Computing, 1999