Abstract

Measuring concurrency. Multicore applications require highly concurrent data structures. Yet, the very notion of concurrency is vaguely defined, to say the least. What is meant by a “highly concurrent” data structure implementing a given high-level object type? Generally speaking, one could compare the concurrency of algorithms by running a game where an adversary decides on the schedules of shared memory accesses from different processes. At the end of the game, the more schedules the algorithm would accept without hampering high-level correctness, the more concurrent it would be. The algorithm that accepts all correct schedules would then be considered concurrency-optimal.
The lack of concurrency. To illustrate the difficulty of optimizing concurrency, let us consider a highly concurrency-friendly data structures: the sorted linked list. Since updates on a list-based set affect only a small number of …

Date

2005

Authors

Vincent Gramoli, Petr Kuznetsov, Srivatsan Ravi, Di Shang

Journal

International Symposium on Distributed Computing

Pages

659