On the correctness and efficiency of a novel lock-free hash trie map design

• Tipo: Artigo em Revista Científica Internacional
• Data: 2021

Autores

Miguel Areias (Autor) FCUP; Ricardo Rocha (Autor) FCUP

Revista

Título: Journal of Parallel and Distributed Computing

Vol. 150

Páginas: 184-195

ISSN: 0743-7315

Editora: Elsevier

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 1 Citação

Outras Informações

ID Authenticus: P-00T-ASP

DOI: 10.1016/j.jpdc.2021.01.001

Abstract (EN): Hash tries are a trie-based data structure with nearly ideal characteristics for the implementation of hash maps. In this paper, we present a novel, simple and scalable hash trie map design that fully supports the concurrent search, insert and remove operations on hash maps. To the best of our knowledge, our proposal is the first that puts together the following characteristics: (i) be lock free; (ii) use fixed size data structures; and (iii) maintain the access to all internal data structures as persistent memory references. Our design is modular enough to allow different types of configurations aimed for different performances in memory usage and execution time and can be easily implemented in any type of language, library or within other complex data structures. We discuss in detail the key algorithms required to easily reproduce our implementation by others and we present a proof of correctness showing that our proposal is linearizable and lock-free for the search, insert and remove operations. Experimental results show that our proposal is quite competitive when compared against other state-of-the-art proposals implemented in Java.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 12