  We consider distributed plurality consensus in a complete graph of size $n$
with $k$ initial opinions. We design an efficient and simple protocol in the
asynchronous communication model that ensures that all nodes eventually agree
on the initially most frequent opinion. In this model, each node is equipped
with a random Poisson clock with parameter $\lambda=1$. Whenever a node's clock
ticks, it samples some neighbors, uniformly at random and with replacement, and
adjusts its opinion according to the sample.
  A prominent example is the so-called two-choices algorithm in the synchronous
model, where in each round, every node chooses two neighbors uniformly at
random, and if the two sampled opinions coincide, then that opinion is adopted.
This protocol is very efficient and well-studied when $k=2$. If
$k=O(n^\varepsilon)$ for some small $\varepsilon$, we show that it converges to
the initial plurality opinion within $O(k \cdot \log{n})$ rounds, w.h.p., as
long as the initial difference between the largest and second largest opinion
is $\Omega(\sqrt{n \log n})$. On the other side, we show that there are cases
in which $\Omega(k)$ rounds are needed, w.h.p.
  One can beat this lower bound in the synchronous model by combining the
two-choices protocol with randomized broadcasting. Our main contribution is a
non-trivial adaptation of this approach to the asynchronous model. If the
support of the most frequent opinion is at least $(1+\varepsilon)$ times that
of the second-most frequent one and $k=O(\exp(\log{n}/\log \log{n}))$, then our
protocol achieves the best possible run time of $O(\log n)$, w.h.p. We relax
full synchronicity by allowing $o(n)$ nodes to be poorly synchronized, and the
well synchronized nodes are only required to be within a certain time
difference from one another. We enforce this synchronicity by introducing a
novel gadget into the protocol.
