  We study randomized test-and-set (TAS) implementations from registers in the
asynchronous shared memory model with n processes. We introduce the problem of
group election, a natural variant of leader election, and propose a framework
for the implementation of TAS objects from group election objects. We then
present two group election algorithms, each yielding an efficient TAS
implementation. The first implementation has expected max-step complexity
$O(\log^\ast k)$ in the location-oblivious adversary model, and the second has
expected max-step complexity $O(\log\log k)$ against any read/write-oblivious
adversary, where $k\leq n$ is the contention. These algorithms improve the
previous upper bound by Alistarh and Aspnes [2] of $O(\log\log n)$ expected
max-step complexity in the oblivious adversary model. We also propose a
modification to a TAS algorithm by Alistarh, Attiya, Gilbert, Giurgiu, and
Guerraoui [5] for the strong adaptive adversary, which improves its space
complexity from super-linear to linear, while maintaining its $O(\log n)$
expected max-step complexity. We then describe how this algorithm can be
combined with any randomized TAS algorithm that has expected max-step
complexity $T(n)$ in a weaker adversary model, so that the resulting algorithm
has $O(\log n)$ expected max-step complexity against any strong adaptive
adversary and $O(T(n))$ in the weaker adversary model. Finally, we prove that
for any randomized 2-process TAS algorithm, there exists a schedule determined
by an oblivious adversary such that with probability at least $(1/4)^t$ one of
the processes needs at least t steps to finish its TAS operation. This
complements a lower bound by Attiya and Censor-Hillel [7] on a similar problem
for $n\geq 3$ processes.
