  This paper is concerned with voting processes on graphs where each vertex
holds one of two different opinions. In particular, we study the
\emph{Best-of-two} and the \emph{Best-of-three}. Here at each synchronous and
discrete time step, each vertex updates its opinion to match the majority among
the opinions of two random neighbors and itself (the Best-of-two) or the
opinions of three random neighbors (the Best-of-three). Previous studies have
explored these processes on complete graphs and expander graphs, but we
understand significantly less about their properties on graphs with more
complicated structures.
  In this paper, we study the Best-of-two and the Best-of-three on the
stochastic block model $G(2n,p,q)$, which is a random graph consisting of two
distinct Erd\H{o}s-R\'enyi graphs $G(n,p)$ joined by random edges with density
$q\leq p$. We obtain two main results. First, if $p=\omega(\log n/n)$ and
$r=q/p$ is a constant, we show that there is a phase transition in $r$ with
threshold $r^*$ (specifically, $r^*=\sqrt{5}-2$ for the Best-of-two, and
$r^*=1/7$ for the Best-of-three). If $r>r^*$, the process reaches consensus
within $O(\log \log n+\log n/\log (np))$ steps for any initial opinion
configuration with a bias of $\Omega(n)$. By contrast, if $r<r^*$, then there
exists an initial opinion configuration with a bias of $\Omega(n)$ from which
the process requires at least $2^{\Omega(n)}$ steps to reach consensus. Second,
if $p$ is a constant and $r>r^*$, we show that, for any initial opinion
configuration, the process reaches consensus within $O(\log n)$ steps. To the
best of our knowledge, this is the first result concerning multiple-choice
voting for arbitrary initial opinion configurations on non-complete graphs.
