Abstract

We consider an asynchronous voting process on graphs called discordant voting, which can be described as follows. Initially each vertex holds one of two opinions, red or blue. Neighboring vertices with different opinions interact pairwise along an edge. After an interaction both vertices have the same color. The quantity of interest is the time to reach consensus, i.e., the number of steps needed for all vertices have the same color. We show that for a given initial coloring of the vertices, the expected time to reach consensus depends strongly on the underlying graph and the update rule (i.e., push, pull, oblivious).