Probabilistic consensus via polling and majority rules
From MaRDI portal
Markov chainsdistributed systemsvoter modeldecentralised algorithmsmajority rulesprobabilistic consensus
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Stochastic network models in operations research (90B15) Distributed systems (68M14)
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
- Publication:4938673
- 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
- scientific article; zbMATH DE number 3934150 (Why is no real title available?)
- 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
- Majority dynamics on trees and the dynamic cavity method
- Quantized consensus
Cited in
(14)- Voter and majority dynamics with biased and stubborn agents
- Majority dynamics and the median process: connections, convergence and some new conjectures
- Diffusion of binary opinions in a growing population with heterogeneous behaviour and external influence
- Approximate majority analyses using tri-molecular chemical reaction networks
- Reach almost sure consensus with only group information
- Necessary and sufficient consensus conditions for the eventwise aggregation of lower probabili\-ties
- A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem
- scientific article; zbMATH DE number 1405692 (Why is no real title available?)
- Simple dynamics for plurality consensus
- Global majority consensus by local majority polling on graphs of a given degree sequence
- A Local Algorithm for Ad Hoc Majority Voting via Charge Fusion
- On convergence and threshold properties of discrete Lotka-Volterra population protocols
- On convergence and threshold properties of discrete Lotka-Volterra population protocols
- Distributed probabilistic polling and applications to proportionate agreement
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)
