Document Open Access Logo

Discordant Voting Processes on Finite Graphs

Authors Colin Cooper, Martin Dyer, Alan Frieze, Nicolás Rivera

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.145.pdf
  • Filesize: 0.55 MB
  • 13 pages

Document Identifiers

Author Details

Colin Cooper
Martin Dyer
Alan Frieze
Nicolás Rivera

Cite As Get BibTex

Colin Cooper, Martin Dyer, Alan Frieze, and Nicolás Rivera. Discordant Voting Processes on Finite Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 145:1-145:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.145

Abstract

We consider an asynchronous voting process on graphs which we call discordant voting, and which can be described as follows. Initially each vertex holds one of two opinions, red or blue say. Neighbouring vertices with different opinions interact pairwise. After an interaction both vertices have the same colour. The quantity of interest is T, the time to reach consensus, i.e. the number of interactions needed for all vertices have the same colour.

An edge whose endpoint colours differ (i.e. one vertex is coloured red and the other one blue) is said to be discordant. A vertex is discordant if its is incident with a discordant edge. In discordant voting, all interactions are based on discordant edges. Because the voting process is asynchronous there are several ways to update the colours of the interacting vertices. 

- Push: Pick a random discordant vertex and push its colour to a random discordant neighbour. 

- Pull: Pick a random discordant vertex and pull the colour of a random discordant neighbour. 

- Oblivious: Pick a random endpoint of a random discordant edge and push the colour to the other end point.

We show that ET, the expected time to reach consensus, depends strongly on the underlying graph and the update rule. For connected graphs on n vertices, and an initial half red, half blue colouring the following hold. For oblivious voting, ET = (n^2)/4 independent of the underlying graph. For the complete graph Kn, the push protocol has ET = Theta(n*log(n)), whereas the pull protocol has ET = Theta(2^n). For the cycle C_n all three protocols have ET = Theta(n^2). For the star graph however, the pull protocol has ET = O(n^2), whereas the push protocol is slower with ET = Theta(n^2*log(n)).

The wide variation in ET for the pull protocol is to be contrasted with the well known model of synchronous pull voting, for which ET = O(n) on many classes of expanders.

Subject Classification

Keywords
  • Distributed consensus
  • Voter model
  • Interacting particles
  • Randomized algorithm

Metrics

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

References

  1. D. Aldous and J. Fill. Reversible markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014, available at URL: http://www.stat.berkeley.edu/~aldous/RWG/book.html.
  2. J. Aspnes and E. Ruppert. An introduction to population protocols. In Middleware for Network Eccentric and Mobile Applications, pages 97-120. Springer, 2009. Google Scholar
  3. R. Basu and A. Sly. Evolving voter model on dense random graphs. arXiv preprint. arXiv:1501.03134, 2015. Google Scholar
  4. S. Brahma, S. Macharla, S. Pal, and S. Singh. Fair leader election by randomized voting. In Distributed Computing and Internet Technology, pages 22-31. Springer, 2004. Google Scholar
  5. C. Cooper, M. Dyer, A. Frieze, and N. Rivera. Discordant voting processes on finite graphs (full version). arXiv preprint. arxiv.org/abs/1604.06884, 2015. Google Scholar
  6. C. Cooper, R. Elsasser, 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
  7. C. Cooper, A. Frieze, and T. Radzik. Multiple random walks in random regular graphs. SIAM Journal on Discrete Mathematics, 23(4):1738-1761, 2009. Google Scholar
  8. R. Durrett, J. Gleeson, A. Lloyd, P. Mucha, F. Shi, D. Sivakoff, J. Socolar, and C. Varghese. Graph fission in an evolving voter model. Proceedings of the National Academy of Sciences, 109(10):3682-3687, 2012. Google Scholar
  9. W. Feller. An introduction to probability theory and its applications, volume 2. John Wiley &Sons, 2008. Google Scholar
  10. D. Gifford. Weighted voting for replicated data. In Proceedings of the seventh ACM symposium on Operating systems principles, pages 150-162. ACM, 1979. Google Scholar
  11. T. Gross and H. Sayama. Adaptive networks. Springer, 2009. Google Scholar
  12. Y. Hassin and D. Peleg. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation, 171(2):248-268, 2001. Google Scholar
  13. P. Holme and M. Newman. Nonequilibrium phase transition in the coevolution of networks and opinions. Physical Review E, 74(5):056108, 2006. Google Scholar
  14. B. Johnson. Design &analysis of fault tolerant digital systems. Addison-Wesley Longman Publishing Co., Inc., 1988. Google Scholar
  15. D. Levin, Y. Peres, and E. Wilmer. Markov chains and mixing times. AMS Bookstore, 2009. Google Scholar
  16. E. Mossel and S. Roch. Slow emergence of cooperation for win-stay lose-shift on trees. Machine Learning, 67(1-2):7-22, 2007. Google Scholar
  17. T. Nakata, H. Imahayashi, and M. Yamashita. Probabilistic local majority voting for the agreement problem on finite graphs. In Computing and Combinatorics, pages 330-338. Springer, 1999. Google Scholar
  18. H. Sayama, I. Pestov, J. Schmidt, B. Bush, C. Wong, J. Yamanoi, and T. Gross. Modeling complex systems with adaptive networks. Computers &Mathematics with Applications, 65(10):1645-1664, 2013. Google Scholar
  19. B. Sury. Sum of the reciprocals of the binomial coefficients. European Journal of Combinatorics, 14(4):351-353, 1993. Google Scholar
  20. D. Williams. Probability with martingales. Cambridge University Press, 1991. Google Scholar
  21. Deng X and C. Papadimitriou. On the complexity of cooperative solution concepts. Mathematics of Operations Research, 19(2):257-266, 1994. 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