On the time and space complexity of randomized test-and-set
George Giakkoupis, Philipp Woelfel · 2012
We study the time and space complexity of randomized Test-And-Set (TAS) implementations from atomic read/write registers in asynchronous shared memory models with n processes. We present an adaptive TAS algorithm with an expected (individual) step complexity of O(log* k), for contention k, against the oblivious adversary, improving a previous (non-adaptive) upper bound of O(log log n) (Alistarh and Aspnes, 2011). We also present a modified version of the adaptive RatRace TAS algorithm (Alistarh et al., 2010), which improves the space complexity from O(n3) to O(n), while maintaining logarithmic expected step complexity against the adaptive adversary. We complement this upper bound with an Ω(log n) lower bound on the space complexity of any TAS algorithm that has the nondeterministic solo-termination property (which is a weaker progress condition than wait-freedom). No non-trivial lower bounds on the space requirements of TAS were known prior to this work.