Highly concurrent multi-word synchronization

The design of concurrent data structures is greatly facilitated by the availability of synchronization operations that atomically modify $k$ arbitrary items, such as $k$-read–modify–write ($k\text{<mi mathsize="small" is="true">RMW</mi>}$). Aiming to increase concurrency in order to exploit the parallelism offered by today’s multi-core and multi-processing architectures, we propose a highly concurrent software implementation of $k\text{<mi mathsize="small" is="true">RMW</mi>}$, with only constant space overhead. Our algorithm ensures that two operations delay each other only if they are within distance $O\left(k\right)$ in the conflict graph, induced by the operations’ data items.The algorithm uses double compare-and-swap (dcas). When dcas is not supported by the architecture, the algorithm of Attiya and Dagan (2001) [3] can be used to replace dcas with (unary) cas, with only a slight increase in the interference among operations.