  This paper concerns designing distributed algorithms that are singularly
optimal, i.e., algorithms that are simultaneously time and message optimal, for
the fundamental leader election problem in networks. Our main result is a
randomized distributed leader election algorithm for asynchronous complete
networks that is essentially (up to a polylogarithmic factor) singularly
optimal. Our algorithm uses $O(n)$ messages with high probability and runs in
$O(\log^2 n)$ time (with high probability) to elect a unique leader. The $O(n)$
message complexity should be contrasted with the $\Omega(n \log n)$ lower
bounds for the deterministic message complexity of leader election algorithms
(regardless of time), proven by Korach, Moran, and Zaks (TCS, 1989) for
asynchronous algorithms and by Afek and Gafni (SIAM J. Comput., 1991) for
synchronous networks. Hence, our result also separates the message complexities
of randomized and deterministic leader election. More importantly, our
(randomized) time complexity of $O(\log^2 n)$ for obtaining the optimal $O(n)$
message complexity is significantly smaller than the long-standing
$\tilde{\Theta}(n)$ time complexity obtained by Afek and Gafni and by Singh
(SIAM J. Comput., 1997) for message optimal (deterministic) election in
asynchronous networks.
  In synchronous complete networks, Afek and Gafni showed an essentially
singularly optimal deterministic algorithm with $O(\log n)$ time and $O(n \log
n)$ messages. Ramanathan et al. (Distrib. Comput. 2007) used randomization to
improve the message complexity, and showed a randomized algorithm with $O(n)$
messages and $O(\log n)$ time (with failure probability $O(1 /
\log^{\Omega(1)}n)$). Our second result is a tightly singularly optimal
randomized algorithm, with $O(1)$ time and $O(n)$ messages, for this setting,
whose time bound holds with certainty and message bound holds with high
probability.
