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 (). 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 , with only constant space overhead. Our algorithm ensures that two operations delay each other only if they are within distance O(k) 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.