Document Open Access Logo

Quasi-Majority Functional Voting on Expander Graphs

Authors Nobutaka Shimizu, Takeharu Shiraga

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.97.pdf
  • Filesize: 0.64 MB
  • 19 pages

Document Identifiers

Author Details

Nobutaka Shimizu
  • The University of Tokyo, Japan
Takeharu Shiraga
  • Chuo University, Tokyo, Japan

Funding

  • Shimizu, Nobutaka: JSPS KAKENHI Grant Number 19J12876, Japan
  • Shiraga, Takeharu: JSPS KAKENHI Grant Number 19K20214, Japan

Cite As Get BibTex

Nobutaka Shimizu and Takeharu Shiraga. Quasi-Majority Functional Voting on Expander Graphs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 97:1-97:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.97

Abstract

Consider a distributed graph where each vertex holds one of two distinct opinions. In this paper, we are interested in synchronous voting processes where each vertex updates its opinion according to a predefined common local updating rule. For example, each vertex adopts the majority opinion among 1) itself and two randomly picked neighbors in best-of-two or 2) three randomly picked neighbors in best-of-three. Previous works intensively studied specific rules including best-of-two and best-of-three individually.
In this paper, we generalize and extend previous works of best-of-two and best-of-three on expander graphs by proposing a new model, quasi-majority functional voting. This new model contains best-of-two and best-of-three as special cases. We show that, on expander graphs with sufficiently large initial bias, any quasi-majority functional voting reaches consensus within O(log n) steps with high probability. Moreover, we show that, for any initial opinion configuration, any quasi-majority functional voting on expander graphs with higher expansion (e.g., Erdős-Rényi graph G(n,p) with p = Ω(1/√n)) reaches consensus within O(log n) with high probability. Furthermore, we show that the consensus time is O(log n/log k) of best-of-(2k+1) for k = o(n/log n).

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed voting
  • consensus problem
  • expander graph
  • Markov chain

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. M. A. Abdullah and M. Draief. Global majority consensus by local majority polling on graphs of a given degree sequence. Discrete Applied Mathematics, 1(10):1-10, 2015. Google Scholar
  2. Y. Afek, N. Alon, O. Barad, E. Hornstein, N. Barkai, and Z. Bar-Joseph. A biological solution to a fundamental distributed computing problem. Science, 331(6014):183-185, 2011. Google Scholar
  3. D. Aldous and J. Fill. Reversible Markov chains and random walks on graphs. URL: http://statwww.berkeley.edu/pub/users/aldous/RWG/book.html.
  4. L. Becchetti, A. Clementi, E. Natale, F. Pasquale, R. Silvestri, and L. Trevisan. Simple dynamics for plurality consensus. Distributed Computing, 30(4):293-306, 2017. Google Scholar
  5. L. Becchetti, A. Clementi, E. Natale, F. Pasquale, and L. Trevisan. Stabilizing consensus with many opinions. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 620-635, 2016. Google Scholar
  6. I. Benjamini, S.-O. Chan, R. O'Donnell, O. Tamuzc, and L.-Y. Tand. Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs. Stochastic Processes and their Applications, 126(9):2719-2733, 2016. Google Scholar
  7. P. Berenbrink, A. Clementi, R. Elsässer, P. Kling, F. Mallmann-Trenn, and E. Natale. Ignore or comply? On breaking symmetry in consensus. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 335-344, 2017. Google Scholar
  8. P. Berenbrink, G. Giakkoupis, Anne-Marie Kermarrec, and F. Mallmann-Trenn. Bounds on the voter model in dynamic networks. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), 2016. Google Scholar
  9. E. Berger. Dynamic monopolies of constant size. Journal of Combinatorial Theory Series B, 83(2):191-200, 2001. Google Scholar
  10. R. Pastor-Satorras C. Castellano, M. A. Muñoz. The non-linear q-voter model. Physical Review E, 80, 2009. Google Scholar
  11. A. Clementi, M. Ghaffari, L. Gualà, E. Natale, F. Pasquale, and G. Scornavacca. A tight analysis of the parallel undecided-state dynamics with two colors. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), 117(28):1-15, 2018. Google Scholar
  12. A. Coja-Oghlan. On the laplacian eigenvalues of G_n,p. Combinatorics, Probability and Computing, 16(6):923-946, 2007. Google Scholar
  13. Nicholas Cook, Larry Goldstein, and Tobias Johnson. Size biased couplings and the spectral gap for random regular graphs. The Annals of Probability, 46(1):72-125, 2018. Google Scholar
  14. C. Cooper, R. Elsässer, H. Ono, and T. Radzik. Coalescing random walks and voting on connected graphs. SIAM Journal on Discrete Mathematics, 27(4):1748-1758, 2013. Google Scholar
  15. C. Cooper, R. Elsässer, and T. Radzik. The power of two choices in distributed voting. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), 2:435-446, 2014. Google Scholar
  16. C. Cooper, R. Elsässer, T. Radzik, N. Rivera, and T. Shiraga. Fast consensus for voting on general expander graphs. In Proceedings of the 29th International Symposium on Distributed Computing (DISC), pages 248-262, 2015. Google Scholar
  17. C. Cooper, T. Radzik, N. Rivera, and T. Shiraga. Fast plurality consensus in regular expanders. In Proceedings of the 31st International Symposium on Distributed Computing (DISC), 91(13):1-16, 2017. Google Scholar
  18. C. Cooper and N. Rivera. The linear voting model. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), 55(144):1-12, 2016. Google Scholar
  19. E. Cruciani, E. Natale, A. Nusser, and G. Scornavacca. Phase transition of the 2-choices dynamics on core-periphery networks. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 777-785, 2018. Google Scholar
  20. E. Cruciani, E. Natale, and G. Scornavacca. Distributed community detection via metastability of the 2-choices dynamics. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pages 6046-6053, 2019. Google Scholar
  21. B. Doerr, L. A. Goldberg, L. Minder, T. Sauerwald, and C. Scheideler. Stabilizing consensus with the power of two choices. In Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 149-158, 2011. Google Scholar
  22. M. Fischer, N. Lynch, and M. Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1(1):26-39, 1986. Google Scholar
  23. A. Frieze and M. Karońsky. Introduction to random graphs. Campridge University Press, 2016. Google Scholar
  24. B. Gärtner and A. N. Zehmakan. Majority model on random regular graphs. In Proceedings of the 13th Latin American Symposium on Theoretical Informatics (LATIN), pages 572-583, 2018. Google Scholar
  25. M. Ghaffari and J. Lengler. Nearly-tight analysis for 2-choice and 3-majority consensus dynamics. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 305-313, 2018. Google Scholar
  26. S. Gilbert and D. Kowalski. Distributed agreement with optimal communication complexity. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 965-977, 2010. Google Scholar
  27. Y. Hassin and D. Peleg. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation, 171(2):248-268, 2001. Google Scholar
  28. N. Kang and R. Rivera. Best-of-three voting on dense graphs. In Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 115-121, 2019. Google Scholar
  29. D. A. Levin and Y. Peres. Markov chain and mixing times: second edition. The American Mathematical Society, 2017. Google Scholar
  30. T. M. Liggett. Interacting particle systems. Springer-Verlag, 1985. Google Scholar
  31. R. Montenegro and P. Tetali. Mathematical aspects of mixing times in Markov chains. NOW Publishers, 2006. Google Scholar
  32. E. Mossel, J. Neeman, and O. Tamuz. Majority dynamics and aggregation of information in social networks. Autonomous Agents and Multiagent Systems, 28(3):408-429, 2014. Google Scholar
  33. T. Nakata, H. Imahayashi, and M. Yamashita. Probabilistic local majority voting for the agreement problem on finite graph. In Proceedings of the 5th Annual International Computing and Combinatorics Conference (COCOON), pages 330-338, 1999. Google Scholar
  34. D. Peleg. Size bounds for dynamic monopolies. Discrete Applied Mathematics, 86(2-3):263-273, 1998. Google Scholar
  35. D. Peleg. Local majorities, coalitions and monopolies in graphs: a review. Theoretical Computer Science, 282(2):231-257, 2002. Google Scholar
  36. G. Schoenebeck and F. Yu. Consensus of interacting particle systems on Erdős-Rényi graphs. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1945-1964, 2018. Google Scholar
  37. N. Shimizu and T. Shiraga. Phase transitions of best-of-two and best-of-three on stochastic block models. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC), pages 32:1-32:17, 2019. Google Scholar
  38. N. Shimizu and T. Shiraga. Quasi-majority functional voting on expander graphs. arXiv, 2020. URL: http://arxiv.org/abs/2002.07411.
  39. K. Tikhomirov and P. Youssef. The spectral gap of dense random regular graphs. The Annals of Probability, 47(1):362-419, 2019. Google Scholar
  40. A. N. Zehmakan. Opinion forming in Erdős-Rényi random graph and expanders. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC), pages 4:1-4:13, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact