  We consider an asynchronous voting process on graphs which we call discordant
voting, and which can be described as follows. Initially each vertex holds one
of two opinions, red or blue say. Neighbouring vertices with different opinions
interact pairwise. After an interaction both vertices have the same colour. The
quantity of interest is T, the time to reach consensus , i.e. the number of
interactions needed for all vertices have the same colour.
  An edge whose endpoint colours differ (i.e. one vertex is coloured red and
the other one blue) is said to be discordant. A vertex is discordant if its is
incident with a discordant edge. In discordant voting, all interactions are
based on discordant edges. Because the voting process is asynchronous there are
several ways to update the colours of the interacting vertices. Push: Pick a
random discordant vertex and push its colour to a random discordant neighbour.
Pull: Pick a random discordant vertex and pull the colour of a random
discordant neighbour. Oblivious: Pick a random endpoint of a random discordant
edge and push the colour to the other end point.
  We show that E(T), the expected time to reach consensus, depends strongly on
the underlying graph and the update rule. For connected graphs on n vertices,
and an initial half red, half blue colouring the following hold. For oblivious
voting, E(T) =n^2/4 independent of the underlying graph. For the complete graph
K_n, the push protocol has E(T)= Theta(n log(n)), whereas the pull protocol has
E(T)= Theta(2^n). For the cycle C_n all three protocols have E(T) = Theta(n^2).
For the star graph however, the pull protocol has E(T)=O(n^2), whereas the push
protocol is slower with E(T) = Theta(n^2 log(n)).
  The wide variation in E(T) for the pull protocol is to be contrasted with the
well known model of synchronous pull voting, for which E(T) = O(n) on many
classes of expanders.
