On Helping and Stacks

Vitalii Aksenov (1, 2) , Petr Kuznetsov (3) , Anatoly Shalyto (1)

1 ITMO University [Russia]
2 GALLIUM - Langages de programmation, types, compilation et preuves
3 Télécom ParisTech

A concurrent algorithm exhibits helping when one process performs work on behalf of other processes. More formally, helping is observed when the order of some operation in a linearization is fixed by a step of another process. In this paper, we show that no wait-free linearizable implementation of a stack using read, write, compare&swap and fetch&add operations can be help-free, correcting a mistake in an earlier proof by Censor-Hillel et al.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]; Algorithme et structure de données [cs.DS]

Vitalii Aksenov, Petr Kuznetsov, Anatoly Shalyto. On Helping and Stacks. The International Conference on Networked Systems, May 2018, Essaouira, Morocco. ⟨hal-01888607⟩