Distributed probabilistic polling and applications to proportionate agreement

DOI10.1006/INCO.2001.3088zbMATH Open1005.68018OpenAlexW2009169450MaRDI QIDQ1854483FDOQ1854483

Authors: Yehuda Hassin, David Peleg 

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2001.3088

Recommendations

• Probabilistic consensus via polling and majority rules
• A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem
• Publication:4938673
• Fast and simple distributed consensus
• Space-optimal proportion consensus with population protocols

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• On periodical behaviour in societies with symmetric influences
• A survey of gossiping and broadcasting in communication networks
• Reaching a Consensus
• Title not available (Why is that?)
• Ergodic theorems for weakly interacting infinite systems and the voter model
• Title not available (Why is that?)
• Title not available (Why is that?)
• A guided tour of Chernoff bounds
• The Byzantine Generals Problem
• Decreasing energy functions as a tool for studying threshold networks
• Title not available (Why is that?)
• Periodic behaviour of generalized threshold functions
• Title not available (Why is that?)
• Local stabilizer
• Distributed probabilistic polling and applications to proportionate agreement
• Finite particle systems and infection models
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (44)

• A control-theoretic perspective on the design of distributed agreement protocols
• Global information from local observations of the noisy voter model on a graph
• Towards control of opinion diversity by introducing zealots into a polarised social group
• On the expected time for Herman's probabilistic self-stabilizing algorithm
• Step-by-step community detection in volume-regular graphs
• Irreversible conversion of graphs
• A computational study of \(f\)-reversible processes on graphs
• Local majorities, coalitions and monopolies in graphs: A review
• Asynchronous opinion dynamics in social networks
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Near-optimal solutions for the generalized max-controlled set problem
• A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem
• Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
• On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
• Asymptotic behaviour of the noisy voter model density process
• Reaching consensus on a connected graph
• Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions
• Title not available (Why is that?)
• Reversible random walks on dynamic graphs
• Discordant Voting Processes on Finite Graphs
• Simple dynamics for plurality consensus
• Reversible iterative graph processes
• Probabilistic consensus via polling and majority rules
• Global majority consensus by local majority polling on graphs of a given degree sequence
• Simplified Chernoff bounds with powers-of-two probabilities
• Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model
• Brief Announcement: Discrete Incremental Voting
• Distributed Averaging in Opinion Dynamics
• Find Your Place: Simple Distributed Algorithms for Community Detection
• Quasi-majority functional voting on expander graphs
• Biased opinion dynamics: when the devil is in the details
• Phase transition of the 3-majority opinion dynamics with noisy interactions
• Phase transition of the \(k\)-majority dynamics in biased communication models
• On convergence and threshold properties of discrete Lotka-Volterra population protocols
• On convergence and threshold properties of discrete Lotka-Volterra population protocols
• Computer science and decision theory
• Discordant voting protocols for cyclically linked agents
• Distributed probabilistic polling and applications to proportionate agreement
• A tight analysis of the parallel undecided-state dynamics with two colors
• Voting protocols on the star graph
• Phase transition of the 2-choices dynamics on core-periphery networks
• Phase transition of the 3-majority dynamics with uniform communication noise
• THE PROPORTIONAL LOTTERY PROTOCOL IS STRONGLY β-PARTICIPATORY AND VNM-STRATEGY-PROOF
• Voter and majority dynamics with biased and stubborn agents

This page was built for publication: Distributed probabilistic polling and applications to proportionate agreement

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