The paper “An EfficientWait-free Resizable Hash Table” by Panagiota Fatourou and Nikolaos D. Kallimanis from ExaNoDe partner FORTH has been accepted by 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2018) taking place from July 16-18 in Vienna. The paper builds on FORTH’s work in ExaNoDe on Lock Oscillation.
This paper presents an efficient wait-free resizable hash table. To achieve high throughput at large core counts, our algorithm is specifically designed to retain the natural parallelism of concurrent hashing, while providing wait-free resizing. An extensive evaluation of our hash table shows that it provides an unprecedented combination of characteristics. When resizing actions are rare, our hash table outperforms all existing lock-free algorithms while providing a stronger progress guarantee.