Abstract
Distributed voting is a fundamental topic in distributed computing. In pull voting, in each step every vertex chooses a neighbour uniformly at random, and adopts its opinion. The voting is completed when all vertices hold the same opinion. On many graph classes including regular graphs, pull voting requires Ω(n) expected steps to complete, even if initially there are only two distinct opinions.
In this paper we consider a related process which we call two-sample voting: every vertex chooses two random neighbours in each step. If the opinions of these neighbours coincide, then the vertex revises its opinion according to the chosen sample. Otherwise, it keeps its own opinion. We consider the performance of this process in the case where two different opinions reside on vertices of some (arbitrary) sets A and B, respectively. Here, |A| + |B| = n is the number of vertices of the graph.
We show that there is a constant K such that if the initial imbalance between the two opinions is \(\nu_0 = (|A| -|B|)/n \ge K\sqrt{(1/d) + (d/n)}\), then with high probability two sample voting completes in a random d regular graph in O(logn) steps and the initial majority opinion wins. We also show the same performance for any regular graph, if ν 0 ≥ Kλ 2, where λ 2 is the second largest eigenvalue of the transition matrix. In the graphs we consider, standard pull voting requires Ω(n) steps, and the minority can still win with probability |B|/n.
The full version of this paper is available at arxiv.org/abs/1404.7479. This work was partially supported by EPSRC grant EP/J006300/1, “Random Walks on Computer Networks”, the Austrian Science Fund (FWF) under contract P25214-N23 “Analysis of Epidemic Processes and Algorithms in Large Networks”, and the 2012 SAMSUNG Global Research Outreach (GRO) grant “Fast Low Cost Methods to Learn Structure of Large Networks.”
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdullah, M., Draief, M.: Consensus on the Initial Global Majority by Local Majority Polling for a Class of Sparse Graphs (2013), http://www.arXiv.org
Aldous, D., Fill, J.: Reversible Markov Chains and Random Walks on Graphs, http://stat-www.berkeley.edu/pub/users/aldous/RWG/book.html
Alon, N., Chung, F.R.K.: Explicit construction of linear sized tolerant networks. Discrete Math. 72, 15–19 (1989)
Becchetti, L., Clementi, A., Natale, E., Pasquale, F., Silvestri, R., Trevisan, L.: Simple Dynamics for Majority Consensus (2013), http://www.arXiv.org
Brahma, S., Macharla, S., Pal, S.P., Singh, S.K.: Fair Leader Election by Randomized Voting. In: Ghosh, R.K., Mohanty, H. (eds.) ICDCIT 2004. LNCS, vol. 3347, pp. 22–31. Springer, Heidelberg (2004)
Cooper, C., Elsässer, R., Ono, H., Radzik, T.: Coalescing Random Walks and Voting on Graphs. In: PODC 2012, pp. 47–56 (2012)
Cooper, C., Elsässer, R., Ono, H., Radzik, T.: Coalescing Random Walks and Voting on Connected Graphs. SIAM J. on Discrete Math. 27(4), 1748–1758 (2013)
Cooper, C., Frieze, A., Radzik, B.: Multiple Random Walks in Random Regular Graphs. SIAM J. on Discrete Math. 23(4), 1738–1761 (2009)
Cooper, C., Frieze, A., Reed, B.: Random regular graphs of non-constant degree: connectivity and Hamilton cycles. Combinatorics Prob. & Comp. 11, 249–262 (2002)
Cruise, J., Ganesh, A.: Probabilistic consensus via polling and majority rules. arXiv:1311.4805
Deng, X., Papadimitriou, C.: On the Complexity of Cooperative Solution Concepts. Mathematics of Operations Research 19(2), 257–266 (1994)
Doerr, B., Goldberg, L.A., Minder, L., Sauerwald, T., Scheideler, C.: Stabilizing Consensus with the Power of Two Choices. In: SPAA 2011, pp. 149–158 (2011)
Donnelly, P., Welsh, D.: Finite particle systems and infection models. Math. Proc. Camb. Phil. Soc. 94(1), 167–182 (1983)
Fountoulakis, N., Panagiotou, K.: Rumor Spreading on Random Regular Graphs and Expanders. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010. LNCS, vol. 6302, pp. 560–573. Springer, Heidelberg (2010)
Frieze, A., Łuczak, T.: On the independence and chromatik numbers of random graphs. J. Combinatorial Theory, Ser. B 54, 123–132 (1992)
Friedman, J.: A proof of Alon’s second eigenvalue conjecture. In: STOC 2003, pp. 720–724 (2003)
Gifford, D.: Weighted Voting for Replicated Data. In: SOSP 1979, pp. 150–162 (1979)
Hassin, Y., Peleg, D.: Distributed probabilistic polling and applications to proportionate agreement. Information & Computation 171(2), 248–268 (2001)
Jerrum, M., Sinclair, A.: Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved. In: STOC 1988, pp. 235–244 (1988)
Johnson, B.: Design and Analysis of Fault Tolerant Digital Systems. Addison-Wesley (1989)
Mossel, E., Neeman, J., Tamuz, O.: Majority Dynamics and Aggregation of Information in Social Networks, arXiv:1207.0893 (2012)
Nakata, T., Imahayashi, H., Yamashita, M.: Probabilistic local majority voting for the agreement problem on finite graphs. In: Asano, T., Imai, H., Lee, D.T., Nakano, S.-i., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol. 1627, pp. 330–338. Springer, Heidelberg (1999)
Oliviera, R.I.: On the Coalescence Time of Reversible Random Walks. Trans. Amer. Math. Soc. 364, 2109–2128 (2012)
Wormald, N.C.: Models of random regular graphs. In: Lamb, J.D., Preece, D.A. (eds.) Surveys in Combinatorics, pp. 239–298
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cooper, C., Elsässer, R., Radzik, T. (2014). The Power of Two Choices in Distributed Voting. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43951-7_37
Download citation
DOI: https://doi.org/10.1007/978-3-662-43951-7_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43950-0
Online ISBN: 978-3-662-43951-7
eBook Packages: Computer ScienceComputer Science (R0)