Antoniadis, KarolosGuerraoui, RachidStainer, JulienTrigonakis, Vasileios2017-06-292017-06-292017-06-29201710.1007/978-3-319-59647-1_30https://infoscience.epfl.ch/handle/20.500.14299/138694Establishing 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.concurrencytext::conference output::conference proceedings::conference paper