Abstract

It is common practice to use the epithet “highly concurrent” referring to data structures that are supposed to perform well in concurrent environments. But how do we measure the concurrency of a data structure in the first place? In this paper, we propose a way to do this, which allowed us to formalize the notion of a concurrency-optimal implementation.
The concurrency of a program is defined here as the program’s ability to accept concurrent schedules, i.e., interleavings of steps of its sequential implementation. To make the definition sound, we introduce a novel correctness criterion, LS-linearizability, that, in addition to classical linearizability, requires the interleavings of memory accesses to be locally indistinguishable from sequential executions. An implementation is then concurrency-optimal if it accepts all LS-linearizable schedules. We explore the concurrency properties of search data …

Date

2016

Authors

Vincent Gramoli, Petr Kuznetsov, Srivatsan Ravi

Conference

Structural Information and Communication Complexity: 23rd International Colloquium, SIROCCO 2016, Helsinki, Finland, July 19-21, 2016, Revised Selected Papers 23

Pages

143-158

Publisher

Springer International Publishing