Distributed probabilistic polling and applications to proportionate agreement

DOI10.1006/INCO.2001.3088zbMath1005.68018OpenAlexW2009169450MaRDI QIDQ1854483

David Peleg, Yehuda Hassin

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

Mathematics Subject Classification ID

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

Related Items (35)

On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols ⋮ Towards Control of Opinion Diversity by Introducing Zealots into a Polarised Social Group ⋮ On convergence and threshold properties of discrete Lotka-Volterra population protocols ⋮ Simple dynamics for plurality consensus ⋮ Voter and majority dynamics with biased and stubborn agents ⋮ Find Your Place: Simple Distributed Algorithms for Community Detection ⋮ Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions ⋮ Reversible random walks on dynamic graphs ⋮ 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? ⋮ Phase transition of the \(k\)-majority dynamics in biased communication models ⋮ Global information from local observations of the noisy voter model on a graph ⋮ Biased opinion dynamics: when the devil is in the details ⋮ Simplified Chernoff bounds with powers-of-two probabilities ⋮ Unnamed Item ⋮ Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model ⋮ Distributed Averaging in Opinion Dynamics ⋮ Brief Announcement: Discrete Incremental Voting ⋮ Step-by-step community detection in volume-regular graphs ⋮ Probabilistic consensus via polling and majority rules ⋮ Global majority consensus by local majority polling on graphs of a given degree sequence ⋮ Phase transition of the 2-choices dynamics on core-periphery networks ⋮ A computational study of \(f\)-reversible processes on graphs ⋮ Reversible iterative graph processes ⋮ Irreversible conversion of graphs ⋮ Near-optimal solutions for the generalized max-controlled set problem ⋮ Computer science and decision theory ⋮ Reaching consensus on a connected graph ⋮ Discordant Voting Processes on Finite Graphs ⋮ Discordant voting protocols for cyclically linked agents ⋮ Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion ⋮ Phase transition of the 3-majority dynamics with uniform communication noise ⋮ Distributed probabilistic polling and applications to proportionate agreement ⋮ Local majorities, coalitions and monopolies in graphs: A review ⋮ On the expected time for Herman's probabilistic self-stabilizing algorithm

Cites Work

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

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