Probabilistic consensus via polling and majority rules

DOI10.1007/S11134-014-9397-7zbMATH Open1321.60197arXiv1311.4805OpenAlexW1981563978MaRDI QIDQ475128FDOQ475128

Authors: J. Herrera, Sumit K. Garg 

Publication date: 25 November 2014

Published in: Queueing Systems (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1311.4805

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

zbMATH Keywords

Markov chainsdistributed systemsvoter modeldecentralised algorithmsmajority rulesprobabilistic consensus

Mathematics Subject Classification ID

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)

Cites Work

• Quantized consensus
• Title not available (Why is that?)
• Fast Distributed Algorithms for Computing Separable Functions
• Convergence speed in distributed consensus and averaging
• Distributed probabilistic polling and applications to proportionate agreement
• Convergence speed of binary interval consensus
• An Upper Bound on the Convergence Time for Quantized Consensus of Arbitrary Static Graphs
• Finite particle systems and infection models
• Global majority consensus by local majority polling on graphs of a given degree sequence
• Distributed Anonymous Discrete Function Computation
• Coalescing random walks and voting on connected graphs
• Majority dynamics on trees and the dynamic cavity method

Cited In (14)

• 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
• A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem
• Necessary and sufficient consensus conditions for the eventwise aggregation of lower probabili\-ties
• Title not available (Why is that?)
• 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
• Voter and majority dynamics with biased and stubborn agents

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)