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.


Editor(s):
El Abbadi, Amr
Garbinato, Benoît
Published in:
Networked Systems, 405-420
Presented at:
Networked Systems: 5th International Conference, Marrakech, Morocco, May 17-19, 2017
Year:
2017
Publisher:
Cham, Springer International Publishing
ISBN:
978-3-319-59646-4
Keywords:
Laboratories:




 Record created 2017-06-29, last modified 2018-06-22

n/a:
SP - Download fulltextPDF
SP_TR - Download fulltextPDF
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)