Probabilistic consensus via polling and majority rules
From MaRDI portal
(Redirected from Publication:475128)
decentralised algorithmsdistributed systemsmajority rulesMarkov chainsprobabilistic consensusvoter model
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Distributed systems (68M14) Stochastic network models in operations research (90B15)
Abstract: In this paper, we consider lightweight decentralised algorithms for achieving consensus in distributed systems. Each member of a distributed group has a private value from a fixed set consisting of, say, two elements, and the goal is for all members to reach consensus on the majority value. We explore variants of the voter model applied to this problem. In the voter model, each node polls a randomly chosen group member and adopts its value. The process is repeated until consensus is reached. We generalize this so that each member polls a (deterministic or random) number of other group members and changes opinion only if a suitably defined super-majority has a different opinion. We show that this modification greatly speeds up the convergence of the algorithm, as well as substantially reducing the probability of it reaching consensus on the incorrect value.
Recommendations
- Distributed probabilistic polling and applications to proportionate agreement
- Probability laws of consensus in a broadcast-based consensus-forming algorithm
- Consensus Algorithms and the Decomposition-Separation Theorem
- Distributed consensus, revisited
- scientific article; zbMATH DE number 1405692
- Deterministic population protocols for exact majority and plurality
- Efficient algorithms for the consensus decision problem
- Deriving consensus in multiagent systems
- A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem
- Reaching consensus via polynomial stochastic operators: A general study
Cites work
- An Upper Bound on the Convergence Time for Quantized Consensus of Arbitrary Static Graphs
- Coalescing random walks and voting on connected graphs
- Convergence speed in distributed consensus and averaging
- Convergence speed of binary interval consensus
- Distributed Anonymous Discrete Function Computation
- Distributed probabilistic polling and applications to proportionate agreement
- Fast Distributed Algorithms for Computing Separable Functions
- Finite particle systems and infection models
- Global majority consensus by local majority polling on graphs of a given degree sequence
- scientific article; zbMATH DE number 3934150 (Why is no real title available?)
- Majority dynamics on trees and the dynamic cavity method
- Quantized consensus
Cited in
(16)- Distributed probabilistic polling and applications to proportionate agreement
- Majority dynamics and the median process: connections, convergence and some new conjectures
- On convergence and threshold properties of discrete Lotka-Volterra population protocols
- Reach almost sure consensus with only group information
- Simple dynamics for plurality consensus
- Voter and majority dynamics with biased and stubborn agents
- On convergence and threshold properties of discrete Lotka-Volterra population protocols
- A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem
- 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?)
- A Local Algorithm for Ad Hoc Majority Voting via Charge Fusion
- Diffusion of binary opinions in a growing population with heterogeneous behaviour and external influence
- Approximate majority analyses using tri-molecular chemical reaction networks
- Phase transitions in biased opinion dynamics with 2-choices rule
- An analysis of avalanche consensus
- Necessary and sufficient consensus conditions for the eventwise aggregation of lower probabili\-ties
This page was built for publication: Probabilistic consensus via polling and majority rules
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475128)
