Quasi-majority functional voting on expander graphs

DOI10.4230/LIPICS.ICALP.2020.97MaRDI QIDQ6842474zbMATH OpenFDO

Authors Nobutaka Shimizu, Takeharu Shiraga

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.97

zbMATH Keywords

consensus problemdistributed votingexpander graphMarkov chain

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A biological solution to a fundamental distributed computing problem
• A tight analysis of the parallel undecided-state dynamics with two colors
• Bounds on the Voter Model in Dynamic Networks
• Coalescing random walks and voting on connected graphs
• Consensus of interacting particle systems on Erdős-Rényi graphs
• Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
• Distributed probabilistic polling and applications to proportionate agreement
• Dynamic monopolies of constant size
• Easy impossibility proofs for distributed consensus problems
• Fast consensus for voting on general expander graphs
• Fast plurality consensus in regular expanders
• Global majority consensus by local majority polling on graphs of a given degree sequence
• scientific article; zbMATH DE number 1405692 (Why is no real title available?)
• scientific article; zbMATH DE number 3892344 (Why is no real title available?)
• scientific article; zbMATH DE number 6297761 (Why is no real title available?)
• Ignore or comply? On breaking symmetry in consensus
• Introduction to Random Graphs
• Local majorities, coalitions and monopolies in graphs: A review
• Majority model on random regular graphs
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Nearly-tight analysis for 2-choice and 3-majority consensus dynamics
• On the Laplacian Eigenvalues of G_n,p
• Opinion Forming in Erdös-Rényi Random Graph and Expanders
• Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
• Simple dynamics for plurality consensus
• Size biased couplings and the spectral gap for random regular graphs
• Size bounds for dynamic monopolies
• Stabilizing Consensus with Many Opinions
• The Linear Voting Model
• The Power of Two Choices in Distributed Voting
• The spectral gap of dense random regular graphs

This page was built for publication: Quasi-majority functional voting on expander graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842474)