  We investigate the time and space complexity of detecting and preventing ABAs
in shared memory algorithms for systems with n processes and bounded base
objects. To that end, we define ABA-detecting registers, which are similar to
normal read/write registers, except that they allow a process q to detect with
a read operation, whether some process wrote the register since q's last read.
ABA-detecting registers can be implemented trivially from a single unbounded
register, but we show that they have a high complexity if base objects are
bounded: An obstruction-free implementation of an ABA-detecting single bit
register cannot be implemented from fewer than n-1 bounded registers. Moreover,
bounded CAS objects (or more generally, conditional read-modify-write
primitives) offer little help to implement ABA-detecting single bit registers:
We prove a linear time-space tradeoff for such implementations. We show that
the same time-space tradeoff holds for implementations of single bit LL/SC
primitives from bounded writable CAS objects. This proves that the
implementations of LL/SC/VL by Anderson and Moir (1995) as well as Jayanti and
Petrovic (2003) are optimal. We complement our lower bounds with tight upper
bounds: We give an implementation of ABA-detecting registers from n+1 bounded
registers, which has step complexity O(1). We also show that (bounded) LL/SC/VL
can be implemented from a single bounded CAS object and with O(n) step
complexity. Both upper bounds are asymptotically optimal with respect to their
time-space product. These results give formal evidence that the ABA problem is
inherently difficult, that even writable CAS objects do not provide significant
benefits over registers for dealing with the ABA problem itself, and that there
is no hope of finding a more efficient implementation of LL/SC/VL from bounded
CAS objects and registers than the ones mentioned.

Distributed, Parallel, and Cluster Computing