lock-free

The strict semantics of many concurrent data structures are often useful when designing algorithms. However, such semantics make achieving high degrees of parallelism problematic for data structures such as FIFO queues, where operations contend for a few shared access points (the head and tail in this case). Thus, such data structures suffer large synchronization overheads under high contention, severely limiting scalability.

Relaxed concurrent data structures were introduced as a way to alleviate such synchronization bottlenecks. They achieve this by weakening the ordering semantics of the data structure, essentially trading some order (in a controlled manner) for parallelism. This post introduces the d-CBO queue, which is a state-of-the-art relaxed FIFO queue.

Classical concurrent data structures such as FIFO queues are foundational in many different applications. It is very simple to implement such a queue by wrapping a sequential implementation in a mutex. However, lock-free designs are often preferred, as they can give better scalability and progress guarantees than ones relying on locks. The classic lock-free FIFO queue is the Michael-Scott queue (MS queue), which is a neat lock-free linked list. Lock-free designs are inherently tricky to implement, and linked lists are known to be troublesome in Rust, so this post details my journey of implementing this MS queue in Rust.

In the middle of a flurry of work on relaxed semantics, Henzinger et al. published the paper Quantitative Relaxation of Concurrent Data Structures in 2013. Its primary contribution is ironing out a framework for the theory of relaxed semantics. The idea is to allow incorrect transitions between states in the data structure specification while being able to associate different paths or transitions with different costs. Furthermore, they create a relaxed out-of-order stack. Here we will concisely but informally present the theory, and in the end, quickly outline the stack.