Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics

DOI10.1145/3212734.3212738zbMath1428.68068arXiv1705.05583OpenAlexW2811510304MaRDI QIDQ5197695

Mohsen Ghaffari, Johannes Lengler

Publication date: 19 September 2019

Published in: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

probabilistic dynamicsconsensus2-choice dynamics3-majority dynamics

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (11)

Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions ⋮ 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 ⋮ Suppression of resilient targets via coordinated swarms ⋮ Unnamed Item ⋮ Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model ⋮ Brief Announcement: Discrete Incremental Voting ⋮ The Maximum Label Propagation Algorithm on Sparse Random Graphs ⋮ Phase transition of the 2-choices dynamics on core-periphery networks ⋮ Phase transition of the 3-majority dynamics with uniform communication noise

This page was built for publication: Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics