Fast plurality consensus in regular expanders

Abstract

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 Cn\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$.