  Pull voting is a classic method to reach consensus among $n$ vertices with
differing opinions in a distributed network: each vertex at each step takes on
the opinion of a random neighbour. This method, however, suffers from two
drawbacks. Even if there are only two opposing opinions, the time taken for a
single opinion to emerge can be slow and the final opinion is not necessarily
the initially held majority.
  We refer to a protocol where 2 neighbours are contacted at each step as a
2-sample voting protocol. In the two-sample protocol a vertex updates its
opinion only if both sampled opinions are the same. Not much was known about
the performance of two-sample voting on general expanders in the case of three
or more opinions. In this paper we show that the following performance can be
achieved on a $d$-regular expander using two-sample voting. We suppose there
are $k \ge 3$ opinions, and that the initial size of the largest and second
largest opinions is $A_1, A_2$ respectively.
  We prove that, if $A_1 - A_2 \ge C n \max\{\sqrt{(\log n)/A_1}, \lambda\}$,
where $\lambda$ is the absolute second eigenvalue of matrix $P=Adj(G)/d$ and
$C$ is a suitable constant, then the largest opinion wins in $O((n \log
n)/A_1)$ steps with high probability.
  For almost all $d$-regular graphs, we have $\lambda=c/\sqrt{d}$ for some
constant $c>0$. This means that as $d$ increases we can separate an opinion
whose majority is $o(n)$, whereas $\Theta(n)$ majority is required for $d$
constant.
  This work generalizes the results of Becchetti et. al (SPAA 2014) for the
complete graph $K_n$.
