  We consider leader election in clique networks, where $n$ nodes are connected
by point-to-point communication links. For the synchronous clique under
simultaneous wake-up, i.e., where all nodes start executing the algorithm in
round $1$, we show a tradeoff between the number of messages and the amount of
time. More specifically, we show that any deterministic algorithm with a
message complexity of $n f(n)$ requires $\Omega\left(\frac{\log n}{\log
f(n)+1}\right)$ rounds, for $f(n) = \Omega(\log n)$. Our result holds even if
the node IDs are chosen from a relatively small set of size $\Theta(n\log n)$,
as we are able to avoid using Ramsey's theorem. We also give an upper bound
that improves over the previously-best tradeoff. Our second contribution for
the synchronous clique under simultaneous wake-up is to show that $\Omega(n\log
n)$ is in fact a lower bound on the message complexity that holds for any
deterministic algorithm with a termination time $T(n)$. We complement this
result by giving a simple deterministic algorithm that achieves leader election
in sublinear time while sending only $o(n\log n)$ messages, if the ID space is
of at most linear size. We also show that Las Vegas algorithms (that never
fail) require $\Theta(n)$ messages. For the synchronous clique under
adversarial wake-up, we show that $\Omega(n^{3/2})$ is a tight lower bound for
randomized $2$-round algorithms. Finally, we turn our attention to the
asynchronous clique: Assuming adversarial wake-up, we give a randomized
algorithm that achieves a message complexity of $O(n^{1 + 1/k})$ and an
asynchronous time complexity of $k+8$. For simultaneous wake-up, we translate
the deterministic tradeoff algorithm of Afek and Gafni to the asynchronous
model, thus partially answering an open problem they pose.
