Abstract
This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the Bestoftwo and the Bestofthree. 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 Bestoftwo) or the opinions of three random neighbors (the Bestofthree). 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 Bestoftwo and the Bestofthree on the stochastic block model G(2n,p,q), which is a random graph consisting of two distinct ErdösRényi graphs G(n,p) joined by random edges with density q <= 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 Bestoftwo, and r^*=1/7 for the Bestofthree). 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 multiplechoice voting for arbitrary initial opinion configurations on noncomplete graphs.
BibTeX  Entry
@InProceedings{shimizu_et_al:LIPIcs:2019:11339,
author = {Nobutaka Shimizu and Takeharu Shiraga},
title = {{Phase Transitions of BestofTwo and BestofThree on Stochastic Block Models}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {32:132:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771269},
ISSN = {18688969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11339},
URN = {urn:nbn:de:0030drops113397},
doi = {10.4230/LIPIcs.DISC.2019.32},
annote = {Keywords: Distributed Voting, Consensus Problem, Random Graph}
}
Keywords: 

Distributed Voting, Consensus Problem, Random Graph 
Seminar: 

33rd International Symposium on Distributed Computing (DISC 2019) 
Issue Date: 

2019 
Date of publication: 

11.10.2019 