Sequential Proximity: Towards Provably Scalable Concurrent Search Algorithms
Establishing the scalability of a concurrent algorithm a priori, before implementing and evaluating it on a concrete multi-core platform, seems difficult, if not impossible. In the context of search data structures however, according to all practical work of the past decade, algorithms that scale share a common characteristic: They all resemble standard sequential implementations for their respective data structure type and strive to minimize the number of synchronization operations. In this paper, we present sequential proximity, a theoretical framework to determine whether a concurrent search algorithm is close to its sequential counterpart. With sequential proximity we take the first step towards a theory of scalability for concurrent search algorithms.
SP.pdf
openaccess
558.57 KB
Adobe PDF
333fac4ad7db281ce4c7e598beb5c3b0
SP_TR.pdf
openaccess
490.88 KB
Adobe PDF
f0d729a8cd61ad15afd5e972b94c6f7c