Lock-free data structures : new method to solve the ABA problem and comparisons in the rust language

Abstract

The ABA problem is a race condition typical of atomic instructions failing to detect changes in lock-free concurrent algorithms. In this work, we present a novel solution to the ABA problem. We also discuss some existing solutions and derivatives, for comparison purposes. To exemplify these solutions, we discuss designs of lock-free data structures vulnerable to the ABA problem, preventing it with the application of the solutions. Finally, we present evaluations on the solutions, including time and memory performance metrics collected by experiments, as well as a comparison of properties.

O problema ABA é uma condição de corrida típica de instruções atômicas que falham em detectar mudanças em algoritmos concorrentes lock-free. Neste trabalho, apresentamos uma nova solução para o problema ABA. Também discutimos algumas soluções existentes e derivadas, para o propósito de comparação. Para exemplificar essas solu- ções, discutimos o design de estruturas de dados lock-free vulneráveis ao problema ABA, prevenindo-o com a aplicação das soluções. Finalmente, apresentamos avaliações nas soluções, incluindo métricas de performance de tempo e de memória coletadas por experimentos, assim como uma comparação de propriedades.