On the Time and Space Complexity of ABA Prevention and Detection
Zahra Aghazadeh, Philipp Woelfel · 2015
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.