  The test-and-set object is a fundamental synchronization primitive for shared
memory systems. A test-and-set object stores a bit, initialized to 0, and
supports one operation, test&set(), which sets the bit's value to 1 and returns
its previous value. This paper studies the number of atomic registers required
to implement a test-and-set object in the standard asynchronous shared memory
model with n processes. The best lower bound is log(n)-1 for obstruction-free
(Giakkoupis and Woelfel, 2012) and deadlock-free (Styer and Peterson, 1989)
implementations. Recently a deterministic obstruction-free implementation using
O(sqrt(n)) registers was presented (Giakkoupis, Helmi, Higham, and Woelfel,
2013). This paper closes the gap between these known upper and lower bounds by
presenting a deterministic obstruction-free implementation of a test-and-set
object from Theta(log n) registers of size Theta(log n) bits. We also provide a
technique to transform any deterministic obstruction-free algorithm, in which,
from any configuration, any process can finish if it runs for b steps without
interference, into a randomized wait-free algorithm for the oblivious
adversary, in which the expected step complexity is polynomial in n and b. This
transformation allows us to combine our obstruction-free algorithm with the
randomized test-and-set algorithm by Giakkoupis and Woelfel (2012), to obtain a
randomized wait-free test-and-set algorithm from Theta(log n) registers, with
expected step-complexity Theta(log* n) against the oblivious adversary.
