On the Time and Space Complexity of Randomized Test-And-Set

摘要

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 Ο(log~* κ), for contention κ, against the oblivious adversary, improving a previous (non-adaptive) upper bound of Ο(log log n) (Al-istarh and Aspnes, 2011). We also present a modified version of the adaptive Rat-Race TAS algorithm (Alistarh et al., 2010), which improves the space complexity from Ο(n~3) to Ο(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.