TY - GEN
T1 - On helping and stacks
AU - Aksenov, Vitaly
AU - Kuznetsov, Petr
AU - Shalyto, Anatoly
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/85059952036
U2 - 10.1007/978-3-030-05529-5_8
DO - 10.1007/978-3-030-05529-5_8
M3 - Conference contribution
AN - SCOPUS:85059952036
SN - 9783030055288
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 107
EP - 121
BT - Networked Systems - 6th International Conference, NETYS 2018, Revised Selected Papers
A2 - Podelski, Andreas
A2 - Taïani, François
PB - Springer Verlag
T2 - 6th International Conference on Networked Systems, NETYS 2018
Y2 - 9 May 2018 through 11 May 2018
ER -