2026-08-11T08:34:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11339 2024-03-06T10:47:59Z ddc:004 open_access

Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models Shimizu, Nobutaka Shiraga, Takeharu Distributed Voting Consensus Problem Random Graph This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the Best-of-two and the 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ős-Ré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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nobutaka Shimizu and Takeharu Shiraga 2019 Is Part Of LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2019.32 urn:nbn:de:0030-drops-113397 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.32 eng https://creativecommons.org/licenses/by/3.0/legalcode